第一章線性規(guī)劃

1.1線性規(guī)劃的模型與圖解法

1.2單純形法

1.3對偶問題與靈敏度分析

1.4線性整數(shù)規(guī)劃

1.5運輸問題第一章線性規(guī)劃

1.1線性規(guī)劃的模型與圖解法1.1線性規(guī)劃的模型與圖解法一、線性規(guī)劃問題及其數(shù)學模型

在生產(chǎn)管理和經(jīng)營活動中經(jīng)常需要解決：如何合理地利用有限的資源，以得到最大的效益。1.1線性規(guī)劃的模型與圖解法在生產(chǎn)管理和經(jīng)營活動

例1.1某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關數(shù)據(jù)列表如下：

試擬訂使總收入最大的生產(chǎn)計劃方案。例1.1某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三1）決策變量：需決策的量，即待求的未知數(shù)；2）目標函數(shù)：需優(yōu)化的量，即欲達的目標，用決策變量的表達式表示；3）約束條件：為實現(xiàn)優(yōu)化目標需受到的限制，用決策變量的等式或不等式表示。線性規(guī)劃模型的三要素1）決策變量：需決策的量，即待求的未知數(shù)；2）目標函數(shù)：需優(yōu)

例1.1某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關數(shù)據(jù)列表如下：

試擬訂使總收入最大的生產(chǎn)計劃方案。例1.1某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三在本例中約束條件：分別來自資源煤、電、油限量的約束，和產(chǎn)量非負的約束，表示為決策變量：甲、乙產(chǎn)品的計劃產(chǎn)量，記為；目標函數(shù)：總收入記為,則,為體現(xiàn)對其追求極大化，在的前面冠以極大號Max；在本例中約束條件：分別來自資源煤、電、油限量的約束，和產(chǎn)量非解：設安排甲、乙產(chǎn)量分別為,總收入為，則模型為：解：設安排甲、乙產(chǎn)量分別為,總收入為，則模型為：線性規(guī)劃模型的一個基本特點：

目標和約束均為變量的線性表達式。如果模型中出現(xiàn)如的非線性表達式，則不屬于線性規(guī)劃。線性規(guī)劃模型的一個基本特點：

目標和約束均為變量的線例1.2某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應量見下表：水泥(公斤/m2)4000(千工日)147000(千塊)150000(噸)20000(噸)110000(千元)資源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105磚混住宅人工(工日/m2)磚(塊/m2)鋼材(公斤/m2)造價(元/m2)

資源住宅體系要求在充分利用各種資源條件下使建造住宅的總面積為最大，求建造方案。例1.2某市今年要興建大量住宅,已知有三種住宅體系可以大量

解:設今年計劃修建磚混、壁板、大模住宅各為,為總面積,則本問題的數(shù)學模型為:

前蘇聯(lián)的尼古拉也夫斯克城住宅興建計劃采用了上述模型，共用了12個變量，10個約束條件。解:設今年計劃修建磚混、壁板、大模住宅各為練習：某畜牧廠每日要為牲畜購買飼料以使其獲取A、B、C、D四種養(yǎng)分。市場上可選擇的飼料有M、N兩種。有關數(shù)據(jù)如下：

0.40.62.01.7

00.10.20.1

0.100.10.2410售價（元/公斤）牲畜每日每頭需要量NM

每公斤含營養(yǎng)成分

ABCD試決定買M與N二種飼料各多少公斤而使支出的總費用為最少？練習：某畜牧廠每日要為牲畜購買飼料以使其獲取A、B、C、D四解：設購買M、N飼料各為，則解：設購買M、N飼料各為，則線性規(guī)劃模型的一般形式：以MAX型、約束為例決策變量：目標函數(shù)：約束條件：線性規(guī)劃模型的一般形式：以MAX型、約束為例決策變量：模型一般式的矩陣形式則模型可表示為記模型一般式的矩陣形式則模型可表示為記回顧例1.1的模型其中表示決策變量的向量；表示產(chǎn)品的價格向量；表示資源限制向量；表示產(chǎn)品對資源的單耗系數(shù)矩陣。回顧例1.1的模型一般地

中稱為決策變量向量，

稱為價格系數(shù)向量,

稱為技術系數(shù)矩陣,

稱為資源限制向量。問題：為什么稱為技術系數(shù)矩陣？一般地

中稱為決策變量向量，稱為價格系數(shù)向量,圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質。二、線性規(guī)劃問題的圖解法圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解1.做約束的圖形

先做非負約束的圖形；再做資源約束的圖形。以例1.1為例，其約束為圖解法步驟1.做約束的圖形以例1.1為例，其約束為圖解法步驟問題：不等式的幾何意義是什么？怎樣做圖？問題：不等式的幾何意義是什么？怎樣做圖？1.做約束的圖形

先做非負約束的圖形；再做資源約束的圖形。以例1.1為例，其約束為圖解法步驟各約束的公共部分即模型的約束，稱可行域。1.做約束的圖形以例1.1為例，其約束為圖解法步驟各約束的公

對于目標函數(shù)任給二不同的值，便可做出相應的二直線，用虛線表示。2.做目標的圖形以例1.1為例，其目標為，分別令，做出相應的二直線，便可看出增大的方向。對于目標函數(shù)2.做目標的圖形以例1.1為例，其目標3.求出最優(yōu)解將目標直線向使目標優(yōu)化的方向移，直至可行域的邊界為止，這時其與可行域的“切”點即最優(yōu)解。

如在例1.1中，是可行域的一個角點，經(jīng)求解交出的二約束直線聯(lián)立的方程，可解得3.求出最優(yōu)解如在例1.1中，由圖解法的結果得到例1.1的最優(yōu)解，將其代入目標函數(shù)求得相應的最優(yōu)目標值。說明當甲產(chǎn)量安排20個單位，乙產(chǎn)量安排24個單位時，可獲得最大的收入428。由圖解法的結果得到例1.1的最優(yōu)解練習：用圖解法求解

下面的線性規(guī)劃。練習：用圖解法求解

下面的線性規(guī)劃。-最優(yōu)解在什么位置獲得？-線性規(guī)劃的可行域是一個什么形狀？問題：在上兩例中

——多邊形，而且是“凸”形的多邊形。——在邊界，而且是在某個頂點獲得。-最優(yōu)解在什么位置獲得？-線性規(guī)劃的可行域是一個什么（1）線性規(guī)劃的約束集（即可行域）是一個凸多面體。凸多面體是凸集的一種。所謂凸集是指：集中任兩點的連線仍屬此集。試判斷下面的圖形是否凸集：凸集中的“極點”，又稱頂點或角點，是指它屬于凸集，但不能表示成集中某二點連線的內(nèi)點。如多邊形的頂點。由圖解法得到線性規(guī)劃解的一些特性（1）線性規(guī)劃的約束集（即可行域）是一個凸多面體。凸多面體因為，由圖解法可知，只有當目標直線平移到邊界時，才能使目標z達到最大限度的優(yōu)化。問題：本性質有何重要意義？（2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的頂點獲得?！沟迷诳尚杏蛑袑?yōu)的工作由“無限”上升為“有限”，從而為線性規(guī)劃的算法設計提供了重要基礎。因為，由圖解法可知，只有當目標直線平移到邊界時，才能使目標（3）線性規(guī)劃解的幾種情形1）唯一最優(yōu)解2）多重最優(yōu)解3）無可行解4）無有限最優(yōu)解（無界解）（3）線性規(guī)劃解的幾種情形1）唯一最優(yōu)解2）多重最優(yōu)解3）無

內(nèi)容回顧與思考1.線性規(guī)劃解決的是一類什么問題？2.線性規(guī)劃模型構成的三要素？3.線性規(guī)劃模型的一般式？4.圖解法的一般步驟？5.圖解法得到線性規(guī)劃哪些性質？內(nèi)容回顧與思考

單純形法是求解線性規(guī)劃的主要算法，1947年由美國斯坦福大學教授丹捷格（G.B.Danzig）提出。盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡單實用的特色始終保持著絕對的“市場”占有率。1.2單純形法單純形法是求解線性規(guī)劃的主要算法，1947年由美

早在二戰(zhàn)期間，在美國空軍服役的科學家丹捷格就提出了“單純形方法”。這個方法當時曾經(jīng)保密，直到戰(zhàn)后的1947年，當?shù)そ莞耠x開軍隊，轉任斯坦福大學教授之后，才公開發(fā)表。

丹捷格不僅提出了單純形法，而且在線性規(guī)劃相關研究領域做出了一系列杰出的貢獻。他被人們譽為“線性規(guī)劃之父”，以他的名字命名的“丹捷格獎”成為運籌學界的最高獎項之一。（1914-2005）早在二戰(zhàn)期間，在美國空軍服役的科學家丹捷格就提出了“單一、單純形法的預備知識1.線性規(guī)劃的標準型來自實際問題的線性規(guī)劃模型形式各異，在用單純形法求解之前，先要將模型化為統(tǒng)一的形式——標準型：標準型的特征：Max型、等式約束、非負約束一、單純形法的預備知識1.線性規(guī)劃的標準型標準型的特征：M非標準形式如何化為標準？（1）Min型化為Max型因為，求一個函數(shù)的極小點，等價于求該函數(shù)的負函數(shù)的極大點。注意：Min化為Max后，最優(yōu)解不變，最優(yōu)值差負號。加負號如非標準形式如何化為標準？注意：Min化為Max后，最優(yōu)解不（2）不等式約束化為等式約束分析：以例1.1中煤的約束為例

x3稱為松弛變量。問題：它的實際意義是什么？——煤資源的“剩余”。之所以“不等”是因為左右兩邊有一個差額，可稱為“松弛量”，若在左邊加上這個松弛量，則化為等式。而這個松弛量也是變量，記為x3

，則有（2）不等式約束化為等式約束x3稱為松弛變量。問題：它的實練習：請將例1.1的約束化為標準型解：增加松弛變量則約束化為可見：松弛變量的系數(shù)恰構成單位陣問題：松弛變量在目標中的系數(shù)為何？問題：標準型與原來模型解的關系？練習：請將例1.1的約束解：增加松弛變量則約束化為可見：松弛一般地，記松弛變量的向量為Xs，則(3)當模型中有某變量xk沒有非負要求，稱為自由變量,則可令

化為標準型。一般地，記松弛變量的向量為Xs，則(3)當模型中有某例如可化為X2為自由變量例如可化為X2為自由變量2.基本概念（1）可行解與最優(yōu)解直觀上，可行解是可行域中的點，是一個可行的方案；最優(yōu)解是可行域的邊界角點，是一個最優(yōu)的方案。2.基本概念直觀上，可行解是可行域中的點，是一個可行的方案（2）基矩陣與基變量基矩陣(簡稱基)：系數(shù)陣A中的m階可逆子陣，記為B；其余部分稱為非基矩陣，記為N。基向量：基B中的列；其余稱非基向量。基變量：與基向量Pj對應的決策變量xj，記其組成的向量為XB；與非基向量對應的變量稱非基變量，記其組成的向量為XN。如指出A中的基。記A中的列為Pj，則每個Pj對應于一個xj，即。（2）基矩陣與基變量基矩陣(簡稱基)：系數(shù)陣A中的m階可逆子第一章線性規(guī)劃課件——6個。一般地，m×n

階矩陣A中基的個數(shù)最多有多少個？問題：本例的中一共有幾個基？——6個。一般地，m×n階矩陣A中基的個數(shù)最多有多少個？（3）基本解與基本可行解（3）基本解與基本可行解可見：一個基本解是由一個基決定的。注意：基本解僅是資源約束的解，并未要求其非負，因此其未必可行。稱非負的基本解為基本可行解（簡稱基可行解）?？梢姡阂粋€基本解是由一個基決定的。稱非負的基本解為基本可行解例1.4

在例1.3的模型中，求相應于基B1和B2的基本解，它們是否基本可行解？例1.4在例1.3的模型中，求相應于基B1和B2的基本解第一章線性規(guī)劃課件上二組概念間的聯(lián)系：系數(shù)陣A中可找出若干個基B每個基B都對應于一個基本解非負的基本解就是基本可行解上二組概念間的聯(lián)系：系數(shù)陣A中可找出若干個基B幾種解之間的關系：可行解基本解非可行解基本可行解問題：基本可行解是可行域中的哪些點？幾種解之間的關系：可行解基本解非可行解基本可行解問題：基本可3.基本定理（1）線性規(guī)劃的可行域是一個凸多面體。（2）線性規(guī)劃可行域的頂點與基本可行解一

一對應。（3）線性規(guī)劃的最優(yōu)解（若存在的話）必能

在可行域的頂點獲得。3.基本定理（1）線性規(guī)劃的可行域是一個凸多面體。（2）線

二、單純形法的步驟確定初始基本可行解檢驗其是否最優(yōu)？尋找更好的基本可行解否是stop單純形法是一種迭代的算法，它的思想是在可行域的頂點——基本可行解中尋優(yōu)。由于頂點是有限個（為什么？）,因此，算法經(jīng)有限步可終止。方法前提：模型化為標準型二、單純形法的步驟確定初始基本可行解檢驗其是否最優(yōu)？尋找1.確定初始基可行解由于基可行解是由一個可行基決定的，因此，確定初始基可行解X0相當于確定一個初始可行基B0。方法：若A中含I，則B0=I；若A中不含I，則要用人工變量法構造一

個I。問題：若B0=I，則X0=？1.確定初始基可行解由于基可行解是由一個可行基決定的，因此，2.最優(yōu)性檢驗分析：用什么檢驗？——目標。記為σ，當σ≤0時，當前解為最優(yōu)。σ稱檢驗數(shù)向量。而目標所以2.最優(yōu)性檢驗分析：用什么檢驗？——目標。記為σ，當σ方法：（1）計算每個xj的檢驗數(shù)（2）若所有σj

≤0，則當前解為最優(yōu)；否則，非最優(yōu)，轉3。問題：非最優(yōu)的特征為何？方法：（1）計算每個xj的檢驗數(shù)（2）若所有σj≤0，則3.尋找更好的基可行解由于基可行解與基對應，即尋找一個新的基可行解，相當于從上一個基B0變換為下一個新的基B1，因此，本步驟也稱為基變換。3.尋找更好的基可行解由于基可行解與基對應，即尋找一個新的基第一章線性規(guī)劃課件換基后，轉2。即再檢驗，直至滿足最優(yōu)性條件。換基后，轉2。即再檢驗，直至滿足最優(yōu)性條件。以例1.1為例，可按上述單純形法的步驟求出其最優(yōu)解，其大致的過程如下。（1）先將模型化為標準型A中含I（P3，P4，P5），可以用單純形法求解。以例1.1為例，可按上述單純形法的步驟求出其最優(yōu)解，其大致的(2)確定初始基可行解、檢驗(2)確定初始基可行解、檢驗計算檢驗數(shù)確定進基向量為P2計算檢驗數(shù)確定進基向量為P2再計算檢驗比確定出基向量為P5。再計算檢驗比確定出基向量為P5。（3）換基、計算下一個基可行解、再檢驗，直

至最優(yōu)計算檢驗數(shù)，確定進基向量為P1再計算檢驗比，確定出基向量為P4（3）換基、計算下一個基可行解、再檢驗，直計算檢驗數(shù)，確定進第一章線性規(guī)劃課件練習：對于下面的線性規(guī)劃（1）先用圖解法求解；（2）將模型化為標準型；（3）再用單純形法步驟求出其最優(yōu)解，并指出求解過程中每一個基可行解相當于可行域的哪一個角點。練習：對于下面的線性規(guī)劃（1）先用圖解法求解；解：（1）圖解法求解0解：（1）圖解法求解0（2）將模型化為標準型A中含I（P3，P4），可以用單純形法求解。（2）將模型化為標準型A中含I（P3，P4），可以用單純形法（3）用單純形法求解計算檢驗數(shù)，確定進基向量為P1再計算檢驗比，確定出基向量為P4.確定初始基可行解、檢驗（3）用單純形法求解計算檢驗數(shù)，確定進基向量為P1再計算檢驗第一章線性規(guī)劃課件0求解過程中每一個基可行解相當于可行域的哪一個角點？0求解過程中每一個基可行解相當于可行域的哪一個角點？問題：當模型規(guī)模較大時，計算量很大。事實上，單純形法的實現(xiàn)是在單純形表上完成的。總結上述過程：問題：當模型規(guī)模較大時，計算量很大。事實上，單純形法的實現(xiàn)是三、單純形表

單純形表是基于單純形法的步驟設計的計算表格，是單純形法的具體實現(xiàn)。回顧單純形法步驟三、單純形表單純形表是基于單純形法的步驟設而相鄰兩個之間只有一列不同，可分析其逆陣間關系：即每個可由上一個經(jīng)以為主元的初等行變換得到，基于此設計了單純形表。而相鄰兩個之間只有一列不同，可分析其逆陣間關系：即每個單純形表的主要結構：表頭的完整結構：θ第一張表的B-1是什么？第一組基變量是什么？單純形表的主要結構：表頭的完整結構：θ第一張表的B-1是什么用單純形表計算的主要過程：（1）建立初表：（4）計算下一張表（用

初等行變換）：（2）計算檢驗數(shù)判斷最優(yōu)：（3）計算檢驗比換基：用單純形表計算的主要過程：（1）建立初表：（4）計算下一張表例1.5用單純形法解例1.1例1.5用單純形法解例1.1標準模型的A中是否含I？——松弛變量系數(shù)恰好構成I。標準模型的A中是否含I？——松弛變量系數(shù)恰好構成I。[][]中表示進基列與出基行的交叉元，下一張表將實行以它為主元的初等行變換（也稱高斯消去）。方法是：先將主元消成1，再用此1將其所在列的其余元消成0。[][]中表示進基列與出基行的交叉元，下一[][][][]（請解釋其實際意義）[]甲乙產(chǎn)品產(chǎn)量的最優(yōu)計劃、相應的最大收入和資源剩余（請解釋其實際意義）[]甲乙產(chǎn)品產(chǎn)量的最優(yōu)計劃、相基變量的檢驗數(shù)和系數(shù)列有何特征？檢驗數(shù)均為0，系數(shù)列均為單位向量列[][]本題全部單純形表基變量的檢驗數(shù)和系數(shù)列有何特征？檢驗數(shù)均為0，系數(shù)列均為單位練習：用單純形法求解下面的線性規(guī)劃練習：用單純形法求解下面的線性規(guī)劃0前面曾用圖解法和單純形法步驟求解過：0前面曾用圖解法和單純形法步驟求解過：第一章線性規(guī)劃課件[]注：1.表上每一列的含義：2.每張表上B-1的位置在哪？——對應于初表中I的位置。如果整個，則為無界解[]注：1.表上每一列的含義：2.每張表上B-1的位每張表的每一列都等于本表的B-1乘以初表的相應列[][]每張表的每一列都等于本表的B-1乘以初表的相應列[[]例1.6：填出下面表中的空白L[]例1.6：填出下面表中的空白L[]L基變量的系數(shù)列[]L基變量的系數(shù)列練習：用單純形法求解下面的線性規(guī)劃直觀上有什么特點？——目標與某約束斜率相同練習：用單純形法求解下面的線性規(guī)劃直觀上有什么特點？——目標第一章線性規(guī)劃課件[]問題：本題的單純形終表檢驗數(shù)有何特點？——

非基變量x2的檢驗數(shù)等于零。多重最優(yōu)[]問題：本題的單純形終表檢驗數(shù)有何特點？四、大M法設模型已經(jīng)化為標準型但A中不含I。添加人工變量，將模型（1）化為（2）四、大M法添加人工變量，將模用單純形法求解（2）的結果：-最優(yōu)解基變量中不含，則（2）的最

優(yōu)解的前n個分量即（1）的最優(yōu)解；-最優(yōu)解基變量中含有，則（1）無解。M稱為罰因子，其作用是迫使出基。用單純形法求解（2）的結果：M稱為罰因子，其作用是迫使例1.7：用單純形法求解下面的線性規(guī)劃模型已經(jīng)是標準型，但A中不含I。例1.7：用單純形法求解下面的線性規(guī)劃模型已經(jīng)是標準型，但A解：增加人工變量將模型化為解：增加人工變量將模型化為[][]人工變量出基后，不會再進基，故其出基后的系數(shù)列不必再參加迭代運算。[][]人工變量出基后，不會再進基，故[]人工變量都已出基[]人工變量都已出基注：（1）解的幾種情況在單純形表上的體現(xiàn)-唯一最優(yōu)：終表非基檢驗數(shù)均小于零；-多重最優(yōu)：終表非基檢驗數(shù)有等于零；-無界解：有正檢驗數(shù)相應系數(shù)列均非正；-無解：最優(yōu)基中含有人工變量。（2）Min型單純形表與Max型的區(qū)別僅在于：

檢驗數(shù)反號，即-令負檢驗數(shù)中最小的對應的變量進基；-當檢驗數(shù)均大于等于零時為最優(yōu)。

問題：Min型模型的大M法人工變量模型是什么？注：（2）Min型單純形表與Max型的區(qū)別僅在于：問題：Mi

內(nèi)容回顧與思考1.基本可行解的概念和幾何意義？2.單純形法的原理步驟？3.單純形表的原理和結構？4.大M法的原理和步驟？5.Min型單純形表計算方法？內(nèi)容回顧與思考1.3對偶問題與靈敏度分析一、對偶問題及其模型

對偶理論是線性規(guī)劃的重要基礎理論，它揭示了：每一個線性規(guī)劃都存在與它對偶的一個線性規(guī)劃，二者之間有密切的聯(lián)系，以至于把二者放在一起研究往往比單獨研究一個問題更有意義。

1.3對偶問題與靈敏度分析一、對偶問題及其模型例1.8回顧例1.1的生產(chǎn)問題，記為（P）甲乙煤電油（P）這時有另一家廠商提出要購買其煤、電、油全部資源，并希望花費盡量少。試建立購買者的線性規(guī)劃模型。例1.8回顧例1.1的生產(chǎn)問題，記為（P）甲乙煤電9y1+4y2+3y3≥74y1+5y2+10y3≥12解：設其購買三種資源的價格分別為y1,y2,y3，總花費為w，則MinW=360y1+200y2+300y3煤電油甲乙s.t.y1,y2,y3≥0（D）分析模型的三要素：購買者的決策變量、目標函數(shù)、約束條件9y1+4y2+3y3≥74y1+5y2+10y3≥12解：甲乙煤電油（P）煤電油甲乙（D）9y1+4y2+3y3≥74y1+5y2+10y3≥12Minw=360y1+200y2+300y3s.t.y1,y2,y3≥0≤bACmaxnm（P）≥minCTATbTnm（D）（D）稱為（P）的對偶問題，（P）稱為（D）的原始問題甲乙煤電油（P）煤電油甲乙（D）對偶模型的一般式（對偶定義）（P）（D）原始問題對偶問題這是最常見的對稱式對偶模型。例1.8已經(jīng)顯示了二者間具有十分對稱的對應關系。對偶模型的一般式（對偶定義）（P）（D）原始問題對偶問題這是二、對偶性質1.對稱性：對偶的對偶就是原始問題。maxw’=-Ybs.t.-YA≤-C Y≥0minz’=-CXs.t.-AX≥-b X≥0對偶定義minw=Ybs.t.YA≥CY≥0maxz=CXs.t.AX

≤

b X≥0對偶定義即（P）和（D）互為對偶，是對稱的。二、對偶性質maxw’=-Ybminz’=-CX對偶定義如果模型中含有等式約束或自由變量，則可轉化為不等式約束和非負變量的形式分析。maxz=CXs.t.AX=b X≥0minw=Ybs.t.YA≥C

如果模型中含有等式約束或自由變量，則可轉化為不等式約束和非負練習：寫出下面線性規(guī)劃的對偶模型練習：寫出下面線性規(guī)劃的對偶模型解：既然模型是Min型，可按（D）整理，令解：既然模型是Min型，可按（D）整理，令然后按（P）寫出其對偶：設對偶變量為然后按（P）寫出其對偶：設對偶變量為證：由（P），（D）的約束可得2.弱對偶性設

分別為（P），（D）的任一可行解，則。（P）（D）圖示：問題：若(P),(D)有一為無界解，則另一為何？證：由（P），（D）的約束可得2.弱對偶性設3.解的最優(yōu)性設，分別為（P）與（D）的可行解，且,則，

。

證：對任可行解，由弱對偶性，故，同理，。圖示：3.解的最優(yōu)性設，分別為（P）與（D）的可行解，設線性規(guī)劃問題1為例1.9,Y*是其對偶問題的最優(yōu)解；又設線性規(guī)劃問題2為其中k是已知常向量。求證：設線性規(guī)劃問題1為例1.9,Y*是其對偶問題的最優(yōu)解；又設證：問題1與問題2的對偶問題分別是（Ⅰ）（Ⅱ）（Ⅰ）與（Ⅱ）的約束相同，故（Ⅰ）的最優(yōu)解Y*是（Ⅱ）的可行解。由弱對偶性，而由解的最優(yōu)性，，故證：問題1與問題2的對偶問題分別是（Ⅰ）（Ⅱ）（Ⅰ）與（Ⅱ）4.對偶定理若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且最優(yōu)值相同。證：對（P）增加松弛變量Xs，化為4.對偶定理若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且最優(yōu)值設其最優(yōu)基為B，則終表為其檢驗數(shù)為則滿足即是（D）的可行解，且，由解的最優(yōu)性，。取，設其最優(yōu)基為B，則終表為其檢驗數(shù)為則滿足即是由對偶定理的證明過程可知，原始問題（P）的單純形終表可同時得到（P）和（D）的最優(yōu)解由對偶定理的證明過程可知，原始問題（P）的單純形終表可同時得例如，在1.2的練習中已知的終表如下，指出其對偶問題的最優(yōu)解和最優(yōu)值。例如，在1.2的練習中已知的終表如下，指出其對偶問題的最5.互補松弛定理設

分別為（P）與（D）的可行解，則

是最優(yōu)解的充要條件是。證：5.互補松弛定理設分別為（P）與（D）的y1…

yi…

ym

ym+1…ym+j…ym+nx1…xj…xnxn+1…xn+i…xn+m

對偶問題的變量對偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0，yixn+i=0（i=1,2,…,m;j=1,2,…,n），在一對變量中，一個大于0，另一個一定等于0。y1…yi…ymym+1…ym+j…例1.10已知線性規(guī)劃問題其對偶問題的最優(yōu)解為，利用對偶性質求原始問題的最優(yōu)解。例1.10已知線性規(guī)劃問題其對偶問題的最優(yōu)解為解：先寫出其對偶將代入約束，第二至四約束為嚴格不等式，由互補松弛性，又，故解得解：先寫出其對偶將三、對偶的經(jīng)濟意義1.對偶最優(yōu)解的經(jīng)濟解釋：資源的影子價格（ShadowPrice）

——對偶問題的最優(yōu)解：買主最低出價；

——原問題資源的影子價格：當該資源

增加1單位時引起的總收入的增量：賣主的內(nèi)控價格。注意：影子價格是在最優(yōu)解前提下，并且其他資源不變。三、對偶的經(jīng)濟意義1.對偶最優(yōu)解的經(jīng)濟解釋：資源的影子價格（例1.11

例1.1（煤電油例）的單純形終表如下：（1）請指出資源煤電油的影子價格，并解釋其經(jīng)濟意義。（2）由影子價格的定義推導電的影子價格。例1.11例1.1（煤電油例）的單純形終表如下：（1）請解：（1）煤、電、油的影子價格分別是0，1.36，0.52；其經(jīng)濟意義是當煤、電、油分別增加1單位時可使總收入分別增加0、1.36、0.52。解：增量恰好為1.36。（2）由影子價格的定義，在最優(yōu)解前提下，電再增加1單位引起總收入由變化為：增量恰好為1.36。（2）由影子價格的定義，在最優(yōu)解前提下，2.對偶約束的經(jīng)濟解釋——產(chǎn)品的機會成本機會成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的收益y1y2ym增加單位資源可以增加的收益減少一件產(chǎn)品可以節(jié)省的資源2.對偶約束的經(jīng)濟解釋——產(chǎn)品的機會成本機會成本y1增加3.對偶松弛變量的經(jīng)濟解釋——產(chǎn)品的差額成本機會成本差額成本利潤差額成本=機會成本－利潤3.對偶松弛變量的經(jīng)濟解釋——產(chǎn)品的差額成本機會成本差額成

在利潤最大化的生產(chǎn)計劃中（1）影子價格大于0的資源沒有剩余；（2）有剩余的資源影子價格等于0；（3）安排生產(chǎn)的產(chǎn)品機會成本等于利潤；（4）機會成本大于利潤的產(chǎn)品不安排生產(chǎn)。4.互補松弛關系的經(jīng)濟解釋在利潤最大化的生產(chǎn)計劃中4.互補松弛關系的經(jīng)濟解釋練習：填空1.根據(jù)線性規(guī)劃的互補松弛定理，影子價格大于零的資源一定

剩余；安排生產(chǎn)的產(chǎn)品機會成本一定

利潤。（）A．沒有，小于B．沒有，大于C．沒有，等于D．有，等于C2.若線性規(guī)劃的原始問題增加一個變量，則其對偶問題就增加一個

；因而對偶的最優(yōu)目標值將可能變

。（）A．約束，好B．約束，壞C．變量，好D．變量，壞B練習：填空CB四、對偶單純形法回顧單純形法是在保持可行性下改善最優(yōu)性。能否嘗試對稱的思路，在保持下改善可行性？四、對偶單純形法回顧單純形法是在保持可行性下改主要步驟（1）確定初始基，使；（2）檢驗，若，是最優(yōu)，否則轉（3）；（3）基變換：先確定出基，再確定進基?；儞Q后再轉（2）。效果：出基改善，進基保持。若，則無可行解主要步驟（1）確定初始基，使；基變例1.12：求解下面的線性規(guī)劃特點：化為標準型后A中不含I，但能否不用大M法？如果檢驗數(shù)均非正則可。例1.12：求解下面的線性規(guī)劃特點：化為標準型后A中不含I，引入松弛變量，化為標準型[]引入松弛變量，化為標準型[][][][][]將線性規(guī)劃與經(jīng)濟問題相關聯(lián)的研究貢獻，使得

T.G.Koopman（庫普曼）和

L.V.Kamtorovich（康脫羅維奇）二人共同分享了1975年的第7屆諾貝爾經(jīng)濟學獎。將線性規(guī)劃與經(jīng)濟問題相關聯(lián)的研究貢獻，使得主要討論C、b和變量結構變化時對解的影響。討論模型的系數(shù)或變量發(fā)生小的變化時對解的影響（如它們在何范圍內(nèi)變化時可使原最優(yōu)解或最優(yōu)基不變？）五、靈敏度分析對解怎樣影響？可行性：最優(yōu)性：主要討論C、b和變量結構變化時對解的影響。討論模型的系數(shù)或變1.b變化時的分析設第r種資源變?yōu)椋驗樗挥绊懣尚行?，故只要變化后的使得，則原最優(yōu)基不變。只要由解出的范圍即可。1.b變化時的分析設第r種資源變?yōu)槔?.13

例1.1（煤電油例）的單純形終表如下：問題：油的資源限量在何范圍變化時，可使原最優(yōu)基不變？例1.13例1.1（煤電油例）的單純形終表如下：問題：油解：由解得：，即油的限量在增加100至減少72范圍內(nèi)變化時，原最優(yōu)基保持不變。最優(yōu)基不變是什么意思？——投產(chǎn)結構不變。解：由解得：，即油的限量在增加10價格變?yōu)闀r，因為它只影響最優(yōu)性，即對檢驗數(shù)產(chǎn)生影響，故只要其使變化后的即可。2.C變化時的分析當是非基變量的價格系數(shù)時，只影響自己的檢驗數(shù)，由一個不等式解得的范圍。當是基變量的價格系數(shù)時，要影響所有的檢驗數(shù)，由一組不等式解得的范圍。價格變?yōu)闀r，因為它只影響最優(yōu)性，即[]例1.14在下面的線性規(guī)劃問題中，分析價格系數(shù)c2在何范圍內(nèi)變化時可使原最優(yōu)解不變。解：c2是非基價格系數(shù)，由解得，即c2價格上漲不超過4都不會投產(chǎn)。[]例1.14在下面的線性規(guī)劃問題中，分析價格系數(shù)3.增加新變量時的分析

主要討論增加新變量xn+1是否有利。經(jīng)濟意義是第n+1種新產(chǎn)品是否應當投產(chǎn)，數(shù)學意義是xn+1是否應進基。方法：計算的檢驗數(shù)，

若，則增加，即投產(chǎn)有利；

若，則不增加，即投產(chǎn)無利。市場價影子價經(jīng)濟意義：3.增加新變量時的分析方法：計算的檢驗數(shù)[]例1.15在例1.14中，若再考慮一個新變量x5，其價格系數(shù)為3，對兩種資源的單耗系數(shù)分別為2和1，請分析它是否應進基。x5應進基。[]例1.15在例1.14中，若再考慮一個新變量x（1）電的影子價格是多少？使最優(yōu)基仍適用的電的變化范圍為何？（2）若有人愿以每度1元的價格向該廠供應25度電，是否值得接受？（3）甲產(chǎn)品的價格在何范圍內(nèi)變化時，現(xiàn)最優(yōu)解不變？例1.16

例1.1（煤電油例）的單純形終表如下：（1）電的影子價格是多少？使最優(yōu)基仍適用的電的變化范圍為何？（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，售價為6.5，問該產(chǎn)品是否應投產(chǎn)？解：（1）電的影子價格是1.36。由解得，即是原最優(yōu)基B仍適用的電的變化范圍。（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，售價為（2）若有人愿以每度1元的價格向該廠供應25度

電，是否值得接受？解：（2）值得。

因25在B的適用范圍內(nèi)（即影子價格適用），且。（2）若有人愿以每度1元的價格向該廠供應25度（3）甲產(chǎn)品的價格在何范圍內(nèi)變化時，現(xiàn)最優(yōu)解不變？解：甲產(chǎn)品的價格c1是基變量的價格系數(shù)。由得，故使不變的的變化范圍為：。由得，（3）甲產(chǎn)品的價格在何范圍內(nèi)變化時，現(xiàn)最優(yōu)解不變？解：甲產(chǎn)品（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，售價為6.5，問該產(chǎn)品是否可投產(chǎn)？因為故丙產(chǎn)品可以投產(chǎn)。解：（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，售價為綜合案例：派公司的產(chǎn)品規(guī)劃派公司是一個生產(chǎn)高爾夫器材的小型公司，近期推出了高、中價位的高爾夫袋新產(chǎn)品（標準袋和高檔袋），經(jīng)銷商對此產(chǎn)品十分感興趣，并訂購了派公司下3個月的全部產(chǎn)品。該高爾夫袋的生產(chǎn)過程主要包括4道工序：切割并印染原材料、縫合、成型（插入支撐架和球棒分離裝置等）、檢驗和包裝。有關數(shù)據(jù)如表1。派公司需決定標準袋和高檔袋各生產(chǎn)多少可使公司的總利潤最大。綜合案例：派公司的產(chǎn)品規(guī)劃派公司是一個生產(chǎn)高爾夫器材（1）寫出此問題的線性規(guī)劃模型，約束及決策變量依表1中次序；工序時間單耗產(chǎn)品表1切割印染縫合成型檢驗包裝

產(chǎn)品單位利潤（美元）標準袋高檔袋7/1011/25/612/31/101/41093個月內(nèi)最大生產(chǎn)能力（小時）630600708135（小時）（1）寫出此問題的線性規(guī)劃模型，約束及決策變量依表1中次序；（2）引入松弛變量（依約束次序）后用單純形法計算得某單純形表如表2，請?zhí)钔瓯碇锌瞻祝⑴袛嗥涫欠窠K表，如果是，請寫出最優(yōu)生產(chǎn)計劃、最大利潤和資源剩余；表2（2）引入松弛變量（依約束次序）后用單純形法計算得某單純形表（3）寫出此問題的對偶問題的模型，及對偶的最優(yōu)解與最優(yōu)值；（4）寫出成型時間的影子價格，求使該影子價格不變的成型時間的變化范圍；（5）若標準袋的利潤可能發(fā)生變化，則其在何范圍內(nèi)變化時，可使原最優(yōu)計劃不改變？解：（1）設標準袋和高檔袋的產(chǎn)量分別為，總利潤為z,則模型為（3）寫出此問題的對偶問題的模型，及對偶的最優(yōu)解與最優(yōu)值；解第一章線性規(guī)劃課件

是終表，最優(yōu)生產(chǎn)計劃是生產(chǎn)標準袋540個，高檔袋252個，最大利潤7668美元，縫合時間余120，檢驗包裝余18。（2）是終表，最優(yōu)生產(chǎn)計劃是生產(chǎn)標準袋540個，高檔袋25（3）設對偶變量為

，對偶目標為w，則對偶模型為（3）設對偶變量為，對偶目標為w，則對偶（4）成型時間的影子價格為6.9375；由

解得

，從而

，即使該影子價格保持不變的成型時間變化范圍。（5）由

和

解得

，從而

，即使原最優(yōu)計劃不改變的標準袋利潤的變化范圍。（4）成型時間的影子價格為6.9375；由解得教材第二章習題和參考書中有很多線性規(guī)劃的習題，請盡量練習。教材第二章習題和參考書中有很多線性規(guī)劃的習題，請盡量練習。線性規(guī)劃計算軟件：CPLEX、LINGO、EXCELEXCEL使用簡介（以例1.1為例）（1）在EXCEL表格輸入模型基本數(shù)據(jù)。123456線性規(guī)劃計算軟件：CPLEX、LINGO、EXCELEXCE（2）在工具欄規(guī)劃求解的“規(guī)劃求解參數(shù)”對話框輸入模型完整信息：-“目標單元格”寫入“$B$6”,選擇“最大值”，可變單元格寫入“$B$1:$B$2”；-在“約束”的添加欄的“添加約束”對話框依次輸入約束信息，如約束，在“單元格引用”中添入“$B$1”，選“=>”，在“約束值”框中添入“0”。（2）在工具欄規(guī)劃求解的“規(guī)劃求解參數(shù)”對話框輸入模型完整信（3）回到“規(guī)劃求解參數(shù)”對話框，選擇“求解”和輸出選項。運算結果（包括靈敏度分析）報告（3）回到“規(guī)劃求解參數(shù)”對話框，選擇“求解”和輸出選項。運第一章線性規(guī)劃課件

內(nèi)容回顧與思考1.對偶問題的定義是什么？2.對偶有哪些性質？3.對偶有哪些經(jīng)濟意義？4.對偶單純形法的思想和主要步驟？5.靈敏度分析的方法？內(nèi)容回顧與思考線性規(guī)劃1-3節(jié)綜合練習一、知識點

線性規(guī)劃1-3節(jié)綜合練習一、知識點二、綜合練習

1．建模問題：某工廠在今后4個月內(nèi)需租用倉庫堆放物資。已知各月份所需倉庫面積如表1；倉庫租用費用隨合同期定，期限越長折扣越大，具體數(shù)據(jù)如表2。租用倉庫的合同每月初都可辦理，每份合同將具體規(guī)定租用面積數(shù)和期限。因此該廠可根據(jù)需要在任何一個月初辦理租用合同，每次可簽一份或多份合同。工廠需決定如何租用可使總的所付租用費用最小。請建立此問題的線性規(guī)劃模型（不解）。二、綜合練習1．建模表1表2分析：建模需要確定三要素變量：如何租用（每月租的面積和時間，怎么表示）目標：費用最小約束：不低于所需面積表1表2分析：建模需要確定三要素解答：

設第i個月租用j個月期的面積為解答：2．圖解法

問題：以下線性規(guī)劃問題的圖解如下圖。在下面各問題中，選擇一個或多個正確的答案填入相應的括號中。2．圖解法的圖解如下圖。在下面各問題中，選擇一個或多個正確的（1）這個線性規(guī)劃的可行域為（

）；ABDDEFBDEOFHIFEIGOEGCAEOBFODIGEHG（2）這個線性規(guī)劃的最優(yōu)解位于（

），如果變量

，則最優(yōu)解位于（

）；ABCDEFGHIO4321BAEx1-2-11234FDHIGCOx2（1）這個線性規(guī)劃的可行域為（ ）；4BAEx1-2分析：

由圖解法可確定約束的圖形(DIG)，目標的圖形向下移；

如果

，則可行域EFIG。4321BAEx1-2-11234FDHIGCOx2解答：（1）DIG；

（2）D、E分析：4BAEx1-2-113．解的概念問題：考慮線性規(guī)劃問題

（P）證明：（1）若均為（P）的可行解，則也是（P）的可行解；（2）若B是A中一個可行基，且 ，則B為最優(yōu)基。3．解的概念問題：考慮線性規(guī)劃問題證明：分析：

（1）考察可行解的概念，證明結果說明可行域

是凸集；

（2）考察最優(yōu)性檢驗的理解，即檢驗數(shù)的證明。證明：（1）是（P）的可行解。分析：

（1）考察可行解的概念，證明結果說明可行域

是凸集；(2)（P）的可行解可表示為目標可表示為∴任意（P）的可行解代入目標，都不大于B相應的基可行解的目標值，即B為最優(yōu)基。(2)（P）的可行解可表示為目標可表示為∴任意（P）的可行解4．單純形法（表）

問題：推導單純形表任一次迭代前后檢驗數(shù)之間的關系，并由此說明變量出基后，在緊鄰的下一階段不會再進基。分析：考察對單純形法步驟和單純形表的熟

練掌握，并用一般式表示。4．單純形法（表） 問題：推導單純形表任一次迭代前后證明：單純形表任一迭代前后的關系：證明：單純形表任一迭代前后的關系：由檢驗數(shù)定義計算得迭代后的檢驗數(shù)代前的檢驗數(shù)的關系為與迭特別，對于迭代前出基的變量，即j=l，故下一階段它不會再進基。有（為什么？）（說明檢驗數(shù)之間也具有同系數(shù)行之間的高斯消去關系）由檢驗數(shù)定義計算得迭代后的檢驗數(shù)代前的檢驗數(shù)的關系為與迭5．對偶理論問題：設，分別為下列兩個問題的最優(yōu)值，是問題(Ⅰ)的對偶問題的最優(yōu)解。

試證明：

分析：（I）和（II）的目標相同，因此其對偶的約束相同，于是也是問題（II）的對偶問題的可行解。5．對偶理論問題：設，分別為下列兩個問題的最優(yōu)值，是問題(Ⅰ證明：（Ⅰ）和（Ⅱ）的對偶分別為和是的最優(yōu)解，則也是的可行解。因此有最優(yōu)解，記為則有，而，得證。證明：（Ⅰ）和（Ⅱ）的對偶分別為6．靈敏度分析問題：已知線性規(guī)劃問題當

時，用單純形法求得最終表如表3。6．靈敏度分析問題：已知線性規(guī)劃問題當時，用表3要求：（1）確定

的值；（2）當

時，t2在什么范圍內(nèi)變化上述最優(yōu)基不變；（3）當

時，t1在什么范圍內(nèi)變化上述最優(yōu)解不變，圖示并說明其幾何意義。表3要求：（1）確定分析：（1）考察對單純形表結構的掌握：單純形表的每一列等于本表的

乘以初表的相應列、檢驗數(shù)公式（2）b變化時的分析（3）c變化時的分析解：（1）由，解得。分析：解：（1）由，解得。同理，解得

由，解得同理，解得由（2）由

，

解得

。（3）由，解得。

第一章線性規(guī)劃課件

幾何意義：當

的變化幅度

時，最優(yōu)目標直線在如圖箭頭所示范圍擺動，這時最優(yōu)解都不變（圖1）。圖1幾何意義：當?shù)淖兓葧r，最優(yōu)目標直線在7．綜合應用

問題:某公司生產(chǎn)家用的清潔產(chǎn)品，為了在高度的市場競爭中增加市場份額，公司決定進行一次大規(guī)模的廣告行動。表4給出了公司準備做廣告的三種產(chǎn)品名稱、估計每做一單位廣告（一個廣告標準批量）使每種產(chǎn)品的市場份額增加量、公司擬定的廣告后每種產(chǎn)品市場份額增加量的最低目標和兩種可選的廣告方式的單價。7．綜合應用單位增量產(chǎn)品廣告種類電視印刷媒體廣告后市場份額最低增量去污劑液體洗滌劑洗衣粉0%1%3%3%2%18%-1%4%4%100200廣告單位成本（萬元）表4其中洗衣粉的市場份額出現(xiàn)負值是由于液體洗滌劑的份額增加會造成洗衣粉份額的減少。單位增量產(chǎn)品廣告種類電視印刷媒體廣告后市場份

現(xiàn)公司需擬定使廣告總費用最少的廣告計劃，即決定電視和印刷媒體的廣告數(shù)量（分別記為x1和x2）。

（1）請寫出此問題的線性規(guī)劃模型（約束依表4中產(chǎn)品的次序），并將模型化為標準型。

（2）用（Min型）單純形法求解此問題，得單純形終表如表5。現(xiàn)公司需擬定使廣告總費用最少的廣告計劃，即決定電視和表5

請?zhí)钔瓯碇锌瞻?；由表指出最?yōu)廣告計劃并求出相應的最低廣告費用，此最優(yōu)計劃使每種產(chǎn)品的市場份額最低增量目標達成情況如何？表5請?zhí)钔瓯碇锌瞻祝挥杀碇赋鲎顑?yōu)廣告計劃并求出相應的（3）寫出此問題的對偶問題模型，由表5求出對偶最優(yōu)解Y*，并解釋Y*的實際意義。分析：（1）建立模型，標準型（min型）（2）填表，將解代入約束可得份額增量目標情況（3）對偶模型，對偶解的意義（min型的對偶解

一般含義是什么）（3）寫出此問題的對偶問題模型，由表5求出對偶最優(yōu)解Y*，并解：（1）解：（1）（2）

即做電視廣告4，印刷媒體3，最低廣告費1000，前兩種產(chǎn)品正好達到目標，第三種超額4%；010001-14/32/3-1（3）填表：（2）00-14/3（3）填表：,實際意義是有另一個承包商來承攬三種產(chǎn)品增加份額的業(yè)務，承攬的目標是總收益最大化，約束是以不超過公司自己做廣告的成本，

即承攬的最優(yōu)單位收益。,實際意義是有另一個8．應用案例除塵器生產(chǎn)計劃

某機器公司可以生產(chǎn)三種不同型號小型的除塵器，一種是政府用，另一種是工業(yè)用，還有一種是民用除塵器。但最后一種已經(jīng)不生產(chǎn)了。政府用除塵器的單價是1500元，工業(yè)用除塵器的單價是1400元。

為了完成各月訂貨，生產(chǎn)車間必須制定出一個生產(chǎn)計劃以使費用最低。因為政府用和工業(yè)用除塵器都分別有兩種型號：一種是使用優(yōu)質的高8．應用案例除塵器生產(chǎn)計劃碳鋼和一些鋁；另一種是使用低碳鋼和大量鋁，而金屬價格差別很大，所以制定最優(yōu)生產(chǎn)計劃并非易事?？蛻舨⒉辉谝夤緸樗麄兩a(chǎn)的除塵器是屬于兩種型號中的哪一種，公司決定使用線性規(guī)劃制定最優(yōu)計劃，問題的關鍵是滿足客戶的總訂貨要求，不超過公司的熟練工人與非熟練技術工人以及生產(chǎn)能力的限制，以使生產(chǎn)費用最小。

鋁的費用：107元/10kg；高碳鋼：38元/10kg，低碳鋼：29元/10kg，表6給出生產(chǎn)三種除塵器所需的原材料及勞動力工時等。碳鋼和一些鋁；另一種是使用低碳鋼和大量鋁，而金屬價格差別很大表6生產(chǎn)所需資源數(shù)據(jù)

公司下月的訂貨為：工業(yè)用除塵器300只，政府用除塵器500只，其金屬費用為305820元。表6生產(chǎn)所需資源數(shù)據(jù)公司下月的訂貨為：工業(yè)用除塵器3

由于開工不足，公司決定再次生產(chǎn)民用輕型除塵器，售價為800元/只，數(shù)用量不超過100只。技術工人可以加班，費用15元/小時。

線性規(guī)劃模型如表7，模型的變量有9個，前三個為三種金屬的購買量，后五個是五種不同除塵器的生產(chǎn)數(shù)量；最后一個是熟練工加班小時數(shù)。約束也有9個，前三個表明購買的三種金屬的數(shù)量至少應滿足生產(chǎn)需求；后兩個表明生產(chǎn)政府用和工業(yè)用除塵器的數(shù)量要滿足訂貨；再后三個是熟練工、技術工和生產(chǎn)線生產(chǎn)能力的限制，最后一個表明最多可以生產(chǎn)100個民用輕型除塵器。由于開工不足，公司決定再次生產(chǎn)民用輕型除塵器，售價為80表7

線性規(guī)劃模型表7線性規(guī)劃模型問題1：下面各量哪些在目標函數(shù)中考慮了，哪些沒有考慮？a)金屬的費用

有______沒有______；

b)正常勞動成本

有______沒有______；c)加班勞動成本

有______沒有______；d)管理費用

有______沒有______。問題2：為什么在目標函數(shù)中沒有考慮工業(yè)用和政府用除塵器的收益，但卻考慮了民用除塵器的收益？使用Lindo軟件對模型計算的結果如下：案例分析√√√√（固定）問題1：下面各量哪些在目標函數(shù)中考慮了，哪些沒有考慮？使用LOBJECTIVEFUNCTIONVALUE1)263280.000VARIABLE VALUE REDUCEDCOSTX1 240.000000 .000000X2 6600.000000 .000000X3 2200.000000 .000000X8 100.000000 .000000X9 200.000000 .000000X5 .000000 574.400000X6 100.000000 .000000X7 200.000000 .000000X4 500.000000 .000000ROW SLACKORSURPLUS DUALPRICES2 .000000 107.0000003 .000000 38.0000004 .000000 29.0000005 .000000 –776.2003006 .000000 –852.2003007 .000000 15.0000008 1400.000000 .0000009 .000000 36.40004010 .000000 296.799700RANGESINWHICHTHEBASISSUNCHANGEDLindo計算結果鋁高碳低碳輕型加班政二工一工二政一鋁高碳低碳政訂工訂技術熟練生產(chǎn)輕型OBJECTIVEFUNCTIONVALUELindo計

OBJCOEFFICIENTRANGESVARIABLE CURRENT COEFALLOWABLEINCREASEALLOWABLEDECREASEX1107.00000045.50005054.962920X238.000000 3.372724 3.033336X3 29.000000 3.309094 3.854542X8–800.000000 296.799700 INFINITYX915.000000 36.400040 15.000000X5.000000 INFINITY 574.400000X6.000000 42.399960 36.400040X7.000000 36.400040 42.399970X4 .000000 574.400000 INFINITYRIGHTHANDSIDERANGESROWCURRENTRHS ALLOWABLE INCREASEALLOWABLEDECREASE2.000000 240.000000 INFINITY3.000000 6600.000000 INFINITY4 .000000 2200.000000 INFINITY5 500.000000 25.000000 12.5000006 300.000000 28.571430 12.50000076400.000000 200.000000 INFINITY8 9600.000000 INFINITY