第十章線性規(guī)劃建模

1、第十章 線性規(guī)劃建模§10.1 線性規(guī)劃引例（生產(chǎn)規(guī)劃問題）：某廠利用a、b、c三種原料生產(chǎn)A、B、C三種產(chǎn)品，已知生產(chǎn)每種產(chǎn)品在消耗原料方面的各項(xiàng)技術(shù)條件和單位產(chǎn)品的利潤(rùn)，以及可利用的各種原料的量（具體數(shù)據(jù)如下表），試制訂適當(dāng)?shù)纳a(chǎn)規(guī)劃使得該廠的總的利潤(rùn)最大。        產(chǎn)品原料生產(chǎn)每單位產(chǎn)品所消耗的原料現(xiàn)有原料的量ABCa34260b21240c13280單位產(chǎn)品利潤(rùn)243   l      

2、60;         以、分別表示生產(chǎn)A、B、C三種產(chǎn)品的量，稱之為決策變量。l                目標(biāo)函數(shù)：利潤(rùn)最大化、成本最小化，表現(xiàn)為決策變量的一個(gè)函數(shù)；l              

3、60; 約束條件：資源、工期等，表現(xiàn)為決策變量的一些等式或不等式。 1            線性規(guī)劃問題：在滿足由一些線性等式或不等式組成的約束條件下，求決策變量的一組具體取值，使得一個(gè)線性目標(biāo)函數(shù)實(shí)現(xiàn)最優(yōu)（大或?。┗?#160;   l               

4、0;決策變量、；l                、（， ）均為常數(shù)；l                整數(shù)規(guī)劃：決策變量限取整數(shù)值的最優(yōu)化問題；l          &

5、#160;     非線性規(guī)劃：目標(biāo)函數(shù)或存在約束條件函數(shù)是決策變量的非線性函數(shù)的最優(yōu)化問題 2            線性規(guī)劃方法建模：決策變量的提取，目標(biāo)函數(shù)的合理構(gòu)造，約束條件的理清。 例（紙張的切割問題）：設(shè)有60個(gè)單位長(zhǎng)的標(biāo)準(zhǔn)玻璃紙，現(xiàn)需將其裁剪為三種小規(guī)格（28，20，15）的紙張，市場(chǎng)對(duì)三種小規(guī)格玻璃紙的需求量（30，60，80）卷，問題：用盡可能少的標(biāo)準(zhǔn)玻璃紙，通過適當(dāng)?shù)牟眉舴绞揭詽M足市場(chǎng)的

6、需求。 1            線性規(guī)劃的標(biāo)準(zhǔn)型：稱如下形式的線性規(guī)劃問題為具有標(biāo)準(zhǔn)型的線性規(guī)劃l                稱矩陣為以上具有標(biāo)準(zhǔn)型的線性規(guī)劃問題的單純形表，其中，l          &

7、#160;     若記，則以上具有標(biāo)準(zhǔn)型的線性規(guī)劃問題可記為   2            所有線性規(guī)劃問題可以標(biāo)準(zhǔn)型化：（1）                      

8、60;     （2）                            且；（3）               &

9、#160;            且；（4）                            等價(jià)于以取代，則，等價(jià)于以取代，則；（5）     

10、;                       ，即無(wú)取值限制,這等價(jià)于以取代，且附加條件；稱（2）、（3）中的分別為剩余、松弛變量. 5 線性規(guī)劃的典型形l                

11、所有線性規(guī)劃問題均可以典型形化：（1）                            ；（2）                  &

12、#160;         且 6           線性規(guī)劃的幾何特征設(shè) 滿足線性規(guī)劃問題全部約束條件，則稱之為此線性規(guī)劃問題的一個(gè)可行解；稱由所有可行解組成的集合為該線性規(guī)劃問題的可行域，用表示；使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解稱為此線性規(guī)劃問題的一個(gè)最優(yōu)解；稱最優(yōu)解的目標(biāo)函數(shù)值為該線性規(guī)劃問題的最優(yōu)值。（1）     

13、60;              可行域?yàn)橥辜簬讉€(gè)典型的凸集（區(qū)域） 幾個(gè)典型的非凸集（區(qū)域）  （2）                    若線性規(guī)劃有最優(yōu)解，則必在可行域邊界達(dá)到；若可行域?yàn)橛薪玳]集，則最優(yōu)解必在的某一頂點(diǎn)

14、達(dá)到。 例 . 求解 l                圖解法:    上圖中紅色區(qū)域?yàn)樵摼€性規(guī)劃的可行域，一條（藍(lán)色）有向線段表示目標(biāo)函數(shù)的梯度向量，幾條藍(lán)色平行線表示目標(biāo)函數(shù)的一簇等值線，考慮問題是求目標(biāo)函數(shù)的最大值，從直觀上不難發(fā)現(xiàn)可行域右方的頂點(diǎn)為該問題的解。  （3）     &

15、#160;              線性規(guī)劃解的存在性（考慮典型形）i .  最優(yōu)解存在且唯一的情形:左圖對(duì)應(yīng)可行域?yàn)橐挥薪玳]集的情形，左圖為一無(wú)界集 ii.  最優(yōu)解存在但不唯一；左圖對(duì)應(yīng)可行域?yàn)橐挥薪玳]集的情形，左圖為一無(wú)界集 iii.  ，可行解存在但目標(biāo)函數(shù)值在內(nèi)無(wú)下界；這一情形只發(fā)生在可行域?yàn)橐粺o(wú)界區(qū)域的時(shí)候 iv.  ，可行

16、解不存在。§10.2 線性規(guī)劃的求解單純形法 l                  本節(jié)討論具有標(biāo)準(zhǔn)型形式的線性規(guī)劃: 這里，目標(biāo)函數(shù)表達(dá)式中較一些流行運(yùn)籌學(xué)教材多了常數(shù)項(xiàng) ,記 ，表示 維列向量，而以  表示 維向量空間，余者：， ，  ；l    

17、;              具有標(biāo)準(zhǔn)型形式的線性規(guī)劃模型可簡(jiǎn)記為：，顯然它與分塊矩陣  一一對(duì)應(yīng)，稱  為線性規(guī)劃 的單純形表。  1線性規(guī)劃的等價(jià)：稱二線性規(guī)劃  與  等價(jià)，若它們具有相同的可行域，且對(duì)任一可行解均有相同的目標(biāo)函數(shù)值，即滿足： , 其中 、 分別為線性規(guī)劃 與 

18、60;的可行域； 對(duì)任意  均有  。2定理3.2 設(shè)  為 階可逆方陣， 為 維列向量，則線性規(guī)劃與線性規(guī)劃  等價(jià)。證明：  記  、 分別為線性規(guī)劃  與 的可行域，對(duì)任意 ，即  且 ，因?yàn)?#160; 為 階可逆方陣，所以等價(jià)于  且 ，即 且 ，進(jìn)而 ；反之

19、亦然，故。     對(duì)任意 , 因?yàn)? 所以, 即線性規(guī)劃  與 在可行解  有相同的目標(biāo)函數(shù)值。    綜合 、, 定理得證。 l                  該定理表明求解具有標(biāo)準(zhǔn)型形式的線性規(guī)劃,&

20、#160;可以對(duì)它的單純形表  作如下的初等行變換:  對(duì)它的前  行 作任意的初等行變換,而對(duì)最后一行  可以加上前  行行向量組的任意線性組合.即在單純形表  左乘一可逆方陣 。我們也將滿足這樣特點(diǎn)的初等變換稱為線性規(guī)劃的等價(jià)變換. 3幾個(gè)簡(jiǎn)單的具有標(biāo)準(zhǔn)型形式的線性規(guī)劃例：例1  例2 例3  例4 例5  例6 l   &

21、#160;              例1 對(duì)應(yīng),令 ，容易看出 為滿足等式約束的一解，目標(biāo)函數(shù)值 . 然而由于  不滿足決策變量的非負(fù)約束，故不是可行解；l                  類似，可以看出&

22、#160; 為例24的一組可行解，相應(yīng)的目標(biāo)函數(shù)值皆為 ；l                  而就例5，可以看出  為它的一組滿足等式約束的解，但因   不滿足決策變量的非負(fù)約束，故不是可行解。l            

23、0;     例6，其形式較前5例要繁，很難直接發(fā)現(xiàn)它的某些特殊解；l                  例14，它們的單純形表中有共同的一塊，表中3列從左到右對(duì)應(yīng)變量 ，例5中，則含塊，表中3列從左到右對(duì)應(yīng)變量 ； 4          

24、    像例15，我們稱在塊  中含塊 的單純形表為最簡(jiǎn)單純形表，其中  的列向量組構(gòu)成  列向量組的一個(gè)極大線性無(wú)關(guān)組，且其列向量中只有一個(gè)分量為  而余者皆為 ，的分量全為 。l                  顯然，一個(gè)線性規(guī)劃的單純形表可以通過線性規(guī)劃的等價(jià)變

25、換化為最簡(jiǎn)型的，而且通常不唯一。 5              不妨仍然以表示某線性規(guī)劃的單純形表經(jīng)過等價(jià)變換化為的最簡(jiǎn)單純形表，即 中含塊，則稱為該線性規(guī)劃的基單純形表，而稱  的列向量組在  中對(duì)應(yīng)的決策變量為該基單純形表對(duì)應(yīng)的基變量，其余為非基變量.令所有非基變量取 值，等式約束方程組所對(duì)應(yīng)的解為該線性規(guī)劃的一個(gè)基解。l     &

26、#160;            就例5, 為對(duì)應(yīng)基變量  的基單純形表，相應(yīng)的一組基解為 ；l                  例3, 其目標(biāo)函數(shù)為 , 一方面前面已論述了它對(duì)應(yīng)一基本可行解 , 相應(yīng)的目標(biāo)

27、函數(shù)值為  而另一方面, 考慮非負(fù)約束 , 可知, 對(duì)任一可行解  都有 , 考慮到目標(biāo)函數(shù)求極小, 為最優(yōu)解, 最優(yōu)值為  ；l                  例4,對(duì)  的任意取值，+皆為該線性規(guī)劃的可行解，而目標(biāo)函數(shù)值顯然 ，該線性規(guī)劃目標(biāo)

28、函數(shù)無(wú)下界，進(jìn)而無(wú)最優(yōu)解。6              定理4.7 設(shè)線性規(guī)劃的某基單純形表,  為相應(yīng)的基解, 有:. 若 , 則基解  為一可行解；. 若  且 , 則基解  為一最優(yōu)解,  為最優(yōu)值；. 若  ,且  中有某

29、一分量  而 (即  的第  個(gè)列向量非正），則該線性規(guī)劃目標(biāo)函數(shù)無(wú)下界，進(jìn)而無(wú)最優(yōu)解。 7. 單純形法:. 給出線性規(guī)劃的一張可行的初始基單純形表, 不妨 , 這里除要求其為一基單純形表外, 還要求滿足 ；. 檢驗(yàn)向量 , 若 , 則寫出該單純形表對(duì)應(yīng)的基本解 , 為最優(yōu)解, 而 為最優(yōu)值, 停; 否則, 轉(zhuǎn) ；.&

30、#160;檢驗(yàn)向量 , 若存在 ,  且 (即對(duì)任意 都有), 則該線性規(guī)劃目標(biāo)函數(shù)無(wú)下界，進(jìn)而無(wú)最優(yōu)解, 停;  否則, 轉(zhuǎn) ；. 取 、, 滿足 , 記 , , 以  為樞軸元素, 構(gòu)造等價(jià)變換矩陣 , 其中 ,   令 ,  轉(zhuǎn) 。 l

31、0;                 從步 . 可看出以上單純形法作為求解線性規(guī)劃的算法是不完整的, 就可行的初始基單純形表的獲得還需專門的討論. 例. 求解線性規(guī)劃問題 8            兩階段法：本節(jié)討論具有標(biāo)準(zhǔn)型形式的線性規(guī)劃（LP）且

32、設(shè)，引入人工變量構(gòu)造線性規(guī)劃（LPM）用單純形法求解（LPM），若得某基可行解（單純形表）滿足均為非基變量，此時(shí)，則為（LP）的一基可行解；在對(duì)應(yīng)的（LPM）的基單純形表的基礎(chǔ)上刪除第列，以取代余表的第行，以線性規(guī)劃的等價(jià)變換構(gòu)造（LP）的對(duì)應(yīng)的基可行單純形表；用單純形法求解（LP）。 9            定理：具有標(biāo)準(zhǔn)型形式的線性規(guī)劃（LP）且設(shè)，引入人工變量構(gòu)造線性規(guī)劃（LPM）則（LPM）的最優(yōu)目標(biāo)函數(shù)值為“”（LP）的可行域非空。§10.3&

33、#160;對(duì)偶問題引例（生產(chǎn)規(guī)劃問題）：某廠利用a、b、c三種原料生產(chǎn)A、B、C三種產(chǎn)品，已知生產(chǎn)每種產(chǎn)品在消耗原料方面的各項(xiàng)技術(shù)條件和單位產(chǎn)品的產(chǎn)值，以及可利用的各種原料的量（具體數(shù)據(jù)如下表），試制訂適當(dāng)?shù)纳a(chǎn)規(guī)劃使得該廠的總的產(chǎn)值最大。        產(chǎn)品原料生產(chǎn)每單位產(chǎn)品所消耗的原料現(xiàn)有原料的量ABCa34260b21240c13280單位產(chǎn)品利潤(rùn)243  l    另一相關(guān)的問題：若打算直接將a、b、c三種原料轉(zhuǎn)讓，如何給出它們的合理定價(jià)？ l    （對(duì)偶）決策變量：分別表示a、b、c三種原料的定價(jià)；l    以價(jià)格直接轉(zhuǎn)讓a、b、c三種原料，其收益應(yīng)不少于將之加工為A、B、C三種產(chǎn)品后獲得的效益：l    l    原料總價(jià)值：；極小化？  1稱線性規(guī)劃問題（LPD）：      為線