管理運籌學(xué)-第一章線性規(guī)劃及單純形法

1、第一章 線性規(guī)劃及單純形法Linear Programming and Simplex Method,北京物資學(xué)院運籌學(xué)教學(xué)課件,北京物資學(xué)院信息學(xué)院 李珍萍2017年2月,第一節(jié) 線性規(guī)劃問題的數(shù)學(xué)模型第二節(jié) 兩變量線性規(guī)劃問題的圖解法第三節(jié) 線性規(guī)劃問題的基本定理第四節(jié) 單純形法第五節(jié) 單純形法的進(jìn)一步討論第六節(jié) 線性規(guī)劃應(yīng)用案例分析,本章內(nèi)容,第一節(jié) 線性規(guī)劃問題的數(shù)學(xué)模型,線性規(guī)劃是運籌學(xué)中研究

2、較早、發(fā)展較快、應(yīng)用較廣、比較成熟的一個分支，它是一種合理利用和調(diào)配有限資源的數(shù)學(xué)方法。,線性規(guī)劃研究的問題：,極大化問題：面對一定的資源，要求充分利用，以獲得最大的經(jīng)濟(jì)效益。,極小化問題：給定一項任務(wù)，要求統(tǒng)籌安排，盡量做到用最少的人力、物力資源去完成這一任務(wù)。,,一、引例： 生產(chǎn)安排問題 原料配比問題 運輸問題二、線性規(guī)劃問題的結(jié)構(gòu)特征三、線性規(guī)劃問題的數(shù)學(xué)模型 線性規(guī)劃問題的一般形式

3、 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 一般形式向標(biāo)準(zhǔn)形式的轉(zhuǎn)化,,本節(jié)內(nèi)容安排,,一、引例,例1 [生產(chǎn)安排問題],某企業(yè)使用A、B、C三臺機(jī)器生產(chǎn)甲、乙兩種產(chǎn)品。已知未來兩周內(nèi)A、B、C三臺機(jī)器的使用時間分別不得超過80，60，45小時，生產(chǎn)每單位產(chǎn)品所需要各臺機(jī)器的加工時間及每單位產(chǎn)品的利潤如下表所示，問企業(yè)如何安排未來兩周的生產(chǎn)，才能使總利潤達(dá)到最大？,可控因素：生產(chǎn)兩種產(chǎn)品的數(shù)量，設(shè)分別為x1 , x2，目標(biāo)是生產(chǎn)利潤最大

4、，設(shè)生產(chǎn)利潤為z.,利潤函數(shù)為：,限制條件：三臺設(shè)備的使用時間不超過可利用機(jī)時設(shè)備A: 2x1+4x2≤80設(shè)備B: 3x1+2x2≤60設(shè)備C: 3x1 ≤45,蘊(yùn)涵約束：產(chǎn)量為非負(fù) x1?0, x2 ?0,目標(biāo)函數(shù)約束條件,設(shè)生產(chǎn)甲乙兩種產(chǎn)品的數(shù)量分別為x1,x2單位，總利潤為z.,例2 [ 原料配比問題] 某企業(yè)使用三種原料B1,B2,B3配制某種食品，要求食品中蛋白質(zhì)、脂肪、糖

5、、維生素的含量分別不低于15、20、25、30單位。以上三種原料的單價以及每單位原料所含各種成分的數(shù)量如下表所示，問應(yīng)如何配置食品，才能使成本最低？,設(shè)x1,x2,x3分別表示原料B1,B2,B3的用量，z表示食品成本。該問題的數(shù)學(xué)模型為：,,例3 [運輸問題],設(shè)要從甲地調(diào)出物資2000噸，從乙地調(diào)出物資600噸，從丙地調(diào)出物資500噸，分別供應(yīng)給A地1700噸、B地1100噸、C地200噸、D地100噸。已知每噸運費如下表所示。,

6、假定運費與運量成正比例，問怎樣才能找到一個總運費最省的調(diào)撥計劃？,丙,17,26,38,43,15,37,51,51,乙,15,7,25,21,甲,D,C,B,A,銷地產(chǎn)地,,,,,,,,,,,,單位：元 / 噸,,用 （i=1,2,3; j=1,2,3,4）分別表示從甲乙丙三個產(chǎn)地運往A,B,C,D四個銷地的物資數(shù)量。,則該問題的數(shù)學(xué)模型為,簡化表達(dá)式,,二、線性規(guī)劃問題的結(jié)構(gòu)特征：,（1）都有一組決策變量。（2）都有一組線

7、性的約束條件，它們是線性等式或不等式。（3）都有一個確定的目標(biāo)，這個目標(biāo)可以表示成決策變量的線性函數(shù)，根據(jù)問題不同，有的要求實現(xiàn)極大化，有的要求實現(xiàn)極小化。,線性規(guī)劃問題的本質(zhì)：研究在一組線性約束下，一個線性函數(shù)的極值問題。所以稱為線性規(guī)劃 linear programming (LP),,1. 線性規(guī)劃問題的一般形式,一般形式的簡化表達(dá),三、線性規(guī)劃問題的數(shù)學(xué)模型：,規(guī)范形式,極大化問題,極小化問題,2. 線性規(guī)劃的標(biāo)準(zhǔn)形式,標(biāo)

8、準(zhǔn)形式的簡化表達(dá),標(biāo)準(zhǔn)形式的矩陣表達(dá),標(biāo)準(zhǔn)形式的向量表達(dá),標(biāo)準(zhǔn)形式的特點：,(1).目標(biāo)函數(shù)極大化,(2).約束條件全部是等式,(3).所有的變量都是非負(fù)的,(4).約束條件右端常數(shù)為非負(fù)的,3.一般形式向標(biāo)準(zhǔn)形式的轉(zhuǎn)化：,(1) 目標(biāo)函數(shù)極大化,(2) 不等式約束化等式約束,對于 形的不等式，可以在不等式的左邊加上（減去）一個非負(fù)的變量使不等式化成等式。這樣的變量稱為松弛（剩余）變量。,例如：,,,(3) 自由變量化

9、非負(fù)變量的差,自由變量可以用兩個非負(fù)變量的差代替，例如對于一個符號無限制的變量 ，可以引進(jìn)兩個非負(fù)變量 并設(shè),(4) 約束條件右端的負(fù)常數(shù)化為正常數(shù),對于右端常數(shù)為負(fù)數(shù)的約束，可以兩端同時乘以-1。,取值小于等于0的變量，可以用一個非負(fù)變量的相反數(shù)表示。,例 將下列LP問題化成標(biāo)準(zhǔn)形式,,s.t.,,課堂練習(xí)：將下列LP問題化成標(biāo)準(zhǔn)形式,,作業(yè)： P46頁

10、 習(xí)題 1-4題,,,第二節(jié) 兩變量線性規(guī)劃問題的圖解法,一、幾個概念二、兩變量線性規(guī)劃問題的圖解法三、兩變量線性規(guī)劃問題解的性質(zhì),可行解：任何一組滿足所有約束條件的決策變量值 稱為LP問題的一個可行解。,最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大（?。┲档目尚薪?。最優(yōu)值：最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值。,,可行域：所有可行解的集合稱為可行域。,,一、幾個概念：,二、兩變量LP問題的圖

11、解法,圖解法是根據(jù)平面直角坐標(biāo)系和二元一次方程（不等式）的特點設(shè)計的。,1. 圖解法的一般步驟：,（1） 建立直角坐標(biāo)系，以 為橫軸， 為縱軸。,（2） 將約束條件在直角坐標(biāo)系中表示，并找出可行域。,（3）作出目標(biāo)函數(shù)的等值線簇，找出目標(biāo)函數(shù)值的增加（或減小）方向，用箭頭表示。,（4）確定出問題的最優(yōu)解。若為極大（?。┗瘑栴}，目標(biāo)函數(shù)沿增加（減?。┓较蚱揭疲c可行域的最后一個交點即為最優(yōu)解。,,例1 用圖解法解下列線性規(guī)劃問題,

12、最優(yōu)解 x*=(10,15)T, 最優(yōu)值 z*=50?10+60?15=1400.,,,,,,,,,,,0,1 0 20 30 4 0,1 0 2 0 3 0,x2,x1,,,(1),(2),,,,,(10,15),,可行域有界,有唯一最優(yōu)解,z =0,z =600,,(3),,,,,,,,,,,,,,,,,,,,例2,,,,⑴,⑵,⑶,,,

13、,,,,無窮多最優(yōu)解,x1,x2,,,,例3、,,,,,,,,,,,,,⑴,,⑵,,,,,無有限最優(yōu)解,x1,x2,,,,,,,,,,,,,,,,,,,,,,⑴,,⑵,,,,可行域無界, 有唯一最優(yōu)解,x1,x2,,,,,例4、,,,,,,,,,,,,,,,,,,⑴,⑵,,x1,x2,,,,,可行域為空, 無可行解,例5、,,,,,,,,,,,,,,,,,,,0,1 2 3 4

14、 5 6 7 8,1 2 3 4 5 6,,⑴,⑵,⑶,,⑷,,,,,,,,,,,,,,,,,,x2,x1,(4 2),,,,,課堂練習(xí):用圖解法求解,可行域是空集。可行域存在，則一定是一個凸多邊形.,,無有限最優(yōu)解（可行域一定無界）。最優(yōu)解存在且唯一，則一定在頂點上達(dá)到。最優(yōu)解存在且不唯一，一定存在一個頂點是最

15、優(yōu)解。,2. 圖解法求解兩變量LP問題時可能出現(xiàn)的情況：,,三. 兩變量線性規(guī)劃問題解的性質(zhì),1. 兩變量線性規(guī)劃問題的可行域是若干個半平面的交集，它是一個有界或無界的凸多邊形，并且有有限個頂點。,2. 對于給定的線性規(guī)劃問題，如果它有最優(yōu)解，最優(yōu)解總可以在可行域的某個頂點上達(dá)到。,,第三節(jié) 線性規(guī)劃問題的基本定理,一、可行區(qū)域的幾何結(jié)構(gòu)二、基可行解及線性規(guī)劃的基本定理,一、可行區(qū)域的幾何結(jié)構(gòu),1. 基本假設(shè)2. 凸集及其性質(zhì)3.

16、 可行域的凸性4. 問題,,1. 基本假設(shè),,凸集：設(shè)S是n維歐氏空間的一個點集，若任意兩點X(1)?S, X(2)?S 的連線上的一切點 ?X(1)+ (1- ? )X(2)?S, (0? ? ?1); 則稱S為一個凸集。,,性質(zhì)：任意多個凸集的交集仍然是凸集。,2. 凸集及性質(zhì),頂點：設(shè)S是凸集，X?S；若對任何X(1)?S和 X(2)?S， X(1)? X(2)，以及任何0<? <1，都有 X?

17、? X(1)+ (1- ? )X(2) 則稱X為凸集S的一個頂點（或極點）。,根據(jù)頂點的定義，長方形的四個角點就是長方形區(qū)域的全部頂點，而圓周上的點則是圓形區(qū)域的全部頂點。,在平面區(qū)域中，每個頂點至少是兩條直線的交點。,,3. 可行域的凸性,定理1：若線性規(guī)劃問題的可行域D={X ?Rn|AX=b,X?0}非空，則必為凸集。,可以直接按照凸集的定義證明，也可以按照以下思路證明。,可行域凸性的證明思路,超平面：給定b ?R1及非零向量

18、a ?Rn，稱集合 H={X ?Rn|aTX=b} 是Rn中的一個超平面。,超平面是二維空間中的直線、三維空間中的平面在高維空間中的推廣。超平面是凸集。,由超平面產(chǎn)生的兩個閉的半空間H+={x ?Rn|aTX?b}H-={x ?Rn|aTX?b}都是凸集。,可行域是有限個超平面的交，因此可行域是凸集。,,4. 問題,,可行域頂點的個數(shù)是否有限？最優(yōu)解是否一定在可行域頂點

19、上達(dá)到？如何找到頂點？ 如何從一個頂點轉(zhuǎn)移到另一個頂點？,二、基可行解及線性規(guī)劃的基本定理,基可行解的定義線性規(guī)劃的基本定理問題,1. 基可行解的定義,考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題,基：A是約束方程組的系數(shù)矩陣(設(shè)n>m)，其秩為m，B是A中的一個m階滿秩子方陣，稱B是線性規(guī)劃問題的一個基。B中每一個列向量稱為一個基向量，與基向量對應(yīng)的變量稱為基變量。其余變量稱為非基變量。,不失一般性，設(shè),則Pj（j=1，2…m

20、）是基向量，xj（ j=1，2…m ）是基變量。 xj（ j=m+1，…，n ）是非基變量。,基解：在約束方程組中令所有的非基變量xm+1=x m+2=x n=0，得,此方程組有唯一解XB=(x1，x2，…xm)T，將這個解加上非基變量取0的值有X=(x1，x2，…xm,0,…,0)T,稱X為線性規(guī)劃問題的基解。,顯然，基解中取非零值的變量個數(shù)不超過m，基解的總數(shù)不超過Cnm個。,基可行解：滿足非負(fù)約束的基解稱為基可行解。可行基：對

21、應(yīng)于基可行解的基。,,,基可行解,用矩陣形式表示的基解,考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題：,,例如LP問題,是它的兩個基，對應(yīng)的基解分別為,可見X1是基可行解，故B1是可行基。而X2不是基可行解，故B2不是可行基。,根據(jù)以上定義,,2. 線性規(guī)劃的基本定理,引理：LP問題的可行解X是基可行解的充要條件是它的正分量所對應(yīng)的A中的列向量線性無關(guān)。,定理3：線性規(guī)劃問題的基可行解對應(yīng)可行域的頂點。（X是基可行解?X是可行域的頂點）（基可行解個數(shù)有限

22、）,定理4：若線性規(guī)劃問題有有限最優(yōu)值，則一定存在一個基可行解是最優(yōu)解。,,定理2：若線性規(guī)劃問題有非零可行解，則其必有基可行解。,3. 問題,如何得到第一個基可行解？如何判別一個基可行解是否最優(yōu)？如果當(dāng)前的基可行解不是最優(yōu)，如何從一個基可行解轉(zhuǎn)化到另一個基可行解？,,一、單純形法的求解思路二、單純形法的基本步驟及單純形表,第四節(jié) 單純形法,確定初始基可行解最優(yōu)性檢驗基可行解的改進(jìn),一、單純形法的求解思路,當(dāng)約束條件全部是“

23、?”型不等式且右端常數(shù)非負(fù)（化成標(biāo)準(zhǔn)形后，約束條件系數(shù)矩陣含有單位子矩陣），可按照下列方法找到第一個基可行解。,加上松弛變量，化為標(biāo)準(zhǔn)形式：,1. 確定初始基可行解,其約束條件系數(shù)矩陣為,令其中的單位矩陣作為基，可得初始基可行解,當(dāng)線性規(guī)劃問題的約束條件中含有“=”或“ ?”型約束時，化成標(biāo)準(zhǔn)形式后，約束條件系數(shù)矩陣中不含單位子矩陣，這時需要通過添加人工變量的方法尋找第一個可行基。（本節(jié)第5節(jié)介紹）,,對于線性規(guī)劃問題的標(biāo)準(zhǔn)形式,假設(shè)可

24、行域非空， A為一 m?n實矩陣，r(A)=m<n 。,2 最優(yōu)性檢驗,假設(shè)B是一個可行基，不妨設(shè)B是由A的前m個列向量組成的，即A=(B,N)，則線性規(guī)劃問題的等式約束AX=b 可以化成：,兩端同時左乘B-1，得,令?=B-1b ,則上式可以寫成,上式所對應(yīng)的約束方程稱為對應(yīng)于基B 的典式。,有了典式，就很容易寫出線性規(guī)劃問題的基解,其中,如果??0 ，則典式對應(yīng)的基解X0是基可行解，從而B是可行基。當(dāng)?>0時，該基

25、可行解為非退化的基可行解。,問題：如何判斷一個基可行解是否為最優(yōu)解呢？,目標(biāo)函數(shù) Z=CX 可以化成,將約束方程組化成典式以后，對目標(biāo)函數(shù)做相應(yīng)變換,由于CB-CBB-1B=0,令,則,其中z0是基可行解對應(yīng)的目標(biāo)函數(shù)值，?是將目標(biāo)函數(shù)中基變量消掉以后非基變量的系數(shù)。該系數(shù)是判斷基可行解是否最優(yōu)的依據(jù)，稱為檢驗數(shù)。,,,當(dāng)所有檢驗數(shù)?j≤0時，當(dāng)前的基可行解為最優(yōu)解；如果某個非基變量的檢驗數(shù)?j > 0，而?ij ≤0，則原問

26、題無界；如果某個非基變量的檢驗數(shù)?j > 0，且至少存在一個i，使得?ij >0，則可以找到一個新的基可行解X1，使得CX1>CX。,3. 基可行解的改進(jìn),1) 基的修改：進(jìn)基變量、出基變量的選取準(zhǔn)則。2) 迭代：得到新基對應(yīng)的典式。,基的修改準(zhǔn)則：新基與原有基有m-1 個相同的基變量，只有一個基變量不同。,進(jìn)基變量：從非基變量變?yōu)榛兞康淖兞俊?出基變量：由基變量變?yōu)榉腔兞康淖兞俊?1) 進(jìn)基變量的選取原則：,

27、最優(yōu)性原則：若?k >0,則與?k 相對應(yīng)的變量xk 是非基變量，當(dāng)xk 變?yōu)榛兞繒r，它的值由0變?yōu)檎龜?shù)，比如說xk= ? >0，其余的非基變量仍取值為零。由(3.4)式知，對應(yīng)新解的目標(biāo)函數(shù)值為z=z0+ ? ? K > z0，顯然?越大目標(biāo)函數(shù)值越大。,可行性原則（最小比值原則）： ? 的取值應(yīng)保證新解仍然是基可行解。,2) 出基變量的選取原則,進(jìn)基變量和出基變量的選取準(zhǔn)則,,,,,,,,,,,,0,1 0

28、 20 30 4 0,1 0 2 0 3 0,x2,,,,(10,15),,例10:求解下列線性規(guī)劃問題,x1,添加松弛變量，化成標(biāo)準(zhǔn)形式（典式）,約束條件系數(shù)矩陣含單位矩陣；目標(biāo)函數(shù)中基變量系數(shù)為0。,第一個基可行解X0=(0,0,80,60,45)T目標(biāo)函數(shù)值為0對應(yīng)可行域頂點O(0，0).,,,,,,,,,,,,0,1 0

29、 20 30 4 0,1 0 2 0 3 0,x2,,,,(10,15),,x1,A,B,C,D,讓x2進(jìn)基，不妨假設(shè)x2 ＝?， x1仍為非基變量。目標(biāo)函數(shù)值為 60 ?。從最優(yōu)性角度看，?越大越好,為了保持解的可行性，原先的基變量取值必須滿足,,,綜上得到,x3出基，新的基變量為x2 ，x4，x5 對應(yīng)的典式可以由方程組的初等變換得到,,新的基可行解

30、：X1=(0,20,0,20,45)T, 對應(yīng)的目標(biāo)函數(shù)值為1200。對應(yīng)可行域A點。,取x1為進(jìn)基變量，,x4為出基變量。,新的基可行解：X1=(10,15,0,0,15)T, 對應(yīng)的目標(biāo)函數(shù)值為1400。對應(yīng)可行域B點。,檢驗數(shù)均非正，所以已得到最優(yōu)解。,當(dāng)xk=?? >0成為基變量以后，其余非基變量仍然取值為0。設(shè)新基對應(yīng)的基可行解為X1=(x11,…, xn1)T,則X1應(yīng)滿足約束條件，即,由于xi1必須是非負(fù)的，即,如

31、果?ik?0，顯然只要?>0，就有xi1 = ? i- ? ik? ?0 ，對于?ik>0，就要求,所以?應(yīng)滿足,假定至少有一個ai k>0，i=1,2,…m，并且所有的?i >0,則?0 >0，從最優(yōu)性原則出發(fā)，讓? 取值盡量大，即取,然后把xt從原有的基中取出來，得到一組新的基可行解,X1 使目標(biāo)函數(shù)取值 z1=z0+ ? k ?0 > z0.,迭代（新的基可行解對應(yīng)的典式的確定）,利用線性

32、方程組的等價變換將約束條件和目標(biāo)函數(shù)化成新基對應(yīng)的典式，從而求出新的基可行解及相應(yīng)的檢驗數(shù),,二、單純形法基本步驟及單純形表,Step 1 將線性規(guī)劃問題化成標(biāo)準(zhǔn)形式下的典式,求出各個非基變量的檢驗數(shù).Step 2 判斷所有非基變量的檢驗數(shù)是否非正,若是,則結(jié)束;否則轉(zhuǎn)step 3.Step 3 選取一個檢驗數(shù)大于零的非基變量為進(jìn)基變量;Step 4 若進(jìn)基變量所對應(yīng)的約束條件系數(shù)全為非正數(shù),則原問題無界,結(jié)束;否則,按最小比值原

33、則確定出基變量;Step 5 利用方程組的初等變換得到新的基對應(yīng)的典式，基可行解和檢驗數(shù),轉(zhuǎn)step 2.,單純形表,= -∑ cn+i bi ?j = cj -∑ cn+i,例11 用單純形表求解例1中的線性規(guī)劃問題,解：先化成標(biāo)準(zhǔn)形式,,,最優(yōu)解X*=(10,15,0,0,15)T，最優(yōu)值1400。,例2：利用單純形法求下列線性規(guī)劃問題,將該問題化成標(biāo)準(zhǔn)形式（也是典式）,基變量是：x3 ，x4 ，

34、x5 ，非基變量是x1 x2,填入單純形表求解,,,最優(yōu)解X*=(2,3,2,0,0)T，最優(yōu)值19。,注意：,1. 在選取進(jìn)基變量時，若有幾個非基變量的檢驗數(shù)都是正數(shù)，則可以任意選取一個正檢驗數(shù)對應(yīng)的非基變量作為進(jìn)基變量，一般選取最大正檢驗數(shù)對應(yīng)的非基變量。但實際情況表明這種策略不一定最好。,2. 在選取出基變量時，若有幾個比值同時達(dá)到最小，可以任意選擇一個，但在新的基可行解中這些對應(yīng)分量均為零。從而新的基可行解是一個退化的基可行解。

35、假若問題是非退化的，則不會出現(xiàn)這種情況。,例12：用單純形法求解線性規(guī)劃問題（多解問題）,解: 化成標(biāo)準(zhǔn)形式,填入單純形表求解,,,,最優(yōu)解X1=(1,5,0,8,0)T，最優(yōu)值6。,最優(yōu)解X2=(5,1,8,0,0)T，最優(yōu)值6。,實際上X1與X2的連線上的任意點都是最優(yōu)解.,例13：用單純形法求解線性規(guī)劃問題（無有限最優(yōu)解的情況）,解：化成標(biāo)準(zhǔn)形（典式）,,X2的檢驗數(shù)為正，但約束條件中x2的系數(shù)全為負(fù)，因此該問題無有限最優(yōu)解。,

36、作業(yè)P48 6 、 7 （1）、 8 （1）,,第五節(jié) 單純形法的進(jìn)一步討論,在給定的LP問題的標(biāo)準(zhǔn)形式中，如果約束條件系數(shù)矩陣A中含有一個m階單位矩陣，并且b?0，則我們已經(jīng)找到了一個明顯的基可行解，并且約束方程組已經(jīng)是典式，這時可以直接填入單純形表中進(jìn)行迭代。但是實際問題往往并非如此，因此我們需要尋找第一個基可行解，通常使用兩種常用的方法求解第一個基可行解。,一.大M法二.兩階段法,考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題,一.

37、大M法,原問題,輔助問題,人工變量,,,,,為了得到原問題的一個基可行解，只要將輔助問題的基可行解中的人工變量全部變?yōu)榉腔兞考纯伞榇?，將人工變量加到輔助問題的目標(biāo)函數(shù)中并賦予系數(shù)-M。（M可以看成懲罰系數(shù)）,添加M以后，直接求解輔助問題，可能有兩種情況：,1.輔助問題的最優(yōu)解中人工變量全部是非基變量，此時去掉人工變量直接得到原問題的最優(yōu)解。,2.在輔助問題的最優(yōu)解中某些人工變量是基變量且取值非零，此時原問題無可行解。,例14：用大M

38、法求解下列線性規(guī)劃問題,添加人工變量得輔助問題,,,,例15：用單純形法求解線性規(guī)劃問題,,添加人工變量，化成典式,,所有的檢驗數(shù)都不大于零，人工變量X5 仍留在基變量中且不為零，故原問題無可行解。,,二. 兩階段法,,,第一階段：尋找原問題的一個基可行解,第二階段：求原問題的最優(yōu)解,通過求解一個目標(biāo)函數(shù)只含有人工變量的輔助問題實現(xiàn)。,,原問題,輔助問題,,,第一階段解的情況,1. 第一階段人工變量取值為0，目標(biāo)函數(shù)值也為0。此時得到原

39、問題的第一個基可行解。結(jié)束第一階段，去掉人工變量，進(jìn)入第二階段求原問題的最優(yōu)解。,2. 第一階段最優(yōu)解的基變量中含有人工變量，表明原問題無可行解。,例16：用兩階段法求解下列線性規(guī)劃問題,第一階段的線性規(guī)劃問題為,第一階段：用單純形法求解輔助問題,,,得原問題的基可行解X=(1,3,0,0,0)T。,第二階段：將上表中的人工變量去除，目標(biāo)函數(shù)換成原問題的目標(biāo)函數(shù)，從上表的最后一個單純形表出發(fā)，繼續(xù)計算。,,得原問題的最優(yōu)解X=（0，5/

40、2，3/2，0，0）T，最優(yōu)值是3/2。,單純形法計算小結(jié),,作業(yè): P48 9（2） 10,第六節(jié) 線性規(guī)劃應(yīng)用案例分析,例17 [混合配料問題]　　某糖果廠用原料A,B,C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中A,B,C的含量，原料成本，各種原料的每月限制用量，三種糖果的單位加工費如下表所示．問該廠每月生產(chǎn)這三種牌號的糖果各多少千克，才能獲利最大？,解:　用i=1，2，3代表A,

41、B,C三種原料，用j=1,2,3分別代表甲，乙，丙三種糖果，設(shè)xij為生產(chǎn)第j種糖果使用的第i種原料的質(zhì)量，則問題的數(shù)學(xué)模型為：,sets:U/1..3/:b,Q;V/1..3/:c,d;link(U,V):x;endsetsdata:b=2 1.5 1;Q=2000, 2500,1200;c=0.5 0.4 0.3;d=3.4 2.85 2.25;enddatamax=@sum(V(j):(d(j)-c(j)

42、)*@sum(U(i):x(i,j)))-@sum(U(i):b(i)*@sum(V(j):x(i,j)));@for(U(i):@sum(V(j):x(i,j))0.6*@sum(U(i):x(i,1));x(3,1)0.3*@sum(U(i):x(i,2));x(3,2)<0.5*@sum(U(i):x(i,2));x(3,3)<0.6*@sum(U(i):x(i,3));,Lingo程序,Global opti

43、mal solution found. Objective value: 5450.000 Infeasibilities: 0.000000 Total solver iterations: 6 Vari

44、able Value Reduced Cost X( 1, 1) 580.0000 0.000000 X( 1, 2) 1420.000 0.000000 X( 2, 1) 193.

45、3333 0.000000 X( 2, 2) 2306.667 0.000000 X( 3, 1) 193.3333 0.000000 X( 3, 2) 1006.667

46、0.000000,用單純形法解得：,例18［投資項目的組合問題］興安公司有一筆30萬元的資金，考慮今后3年內(nèi)用于下列項目的投資：［項目一］　三年內(nèi)的每年年初可投資，每年獲利為投資額的20%，其本利可一起用于下一年的投資；［項目二］　只允許第一年初投資，于第二年末收回，本利合計為投資額的150%，但此類投資限額不超過15萬元；［項目三］　允許于第二年初投資，于第三年末收回，本利合計為投資額的160%，但限額投資為20萬元；［項目

47、四］　允許于第三年初投資，年末收回，可獲利40%，但限額為10萬元。試為該公司確定一個使第三年末本利和為最大的投資組合方案。,解：用xij 表示第i 年初投資到第j 項目的資金數(shù)，則可得下列線性規(guī)劃模型,求解得,max=1.2*x31+1.6*x23+1.4*x34;x11+x12=30;x21+x23=1.2*x11;x31+x34=1.2*x21+1.5*x12;x12<15;x23<20;x34<1

48、0;,Global optimal solution found. Objective value: 58.00000 Infeasibilities: 0.000000 Total solver iterations: 6

49、 Variable Value Reduced Cost X31 10.00000 0.000000 X23 20.00000 0.000000 X

50、34 10.00000 0.000000 X11 16.66667 0.000000 X12 13.33333 0.000000 X21 0.0000

51、00 0.6000000E-01,例19 [下料問題]　　工廠要制作100套專用鋼架，每套鋼架需要用長為2.9m、2.1m和1.5m的圓鋼各一根。已知原料每根長7.4米，現(xiàn)考慮應(yīng)如何下料，可使所用原料最省？,解：設(shè)x1 ,x2 ,x3 ,x4 ,x5 ,x6 ,x7 ,x8 分別表示按上述8種方案下料的原料根數(shù)。則：,min=x1+x2+x3+x4+x5+x6+x7+x8;2*x1+x2+x3+x4>100

52、;2*x2+x3+3*x5+2*x6+x7>100;x1+x3+3*x4+2*x6+3*x7+4*x8>100;,Global optimal solution found. Objective value: 90.00000 Infeasibilities: 0.000000 Total so

53、lver iterations: 4 Variable Value Reduced Cost X1 40.00000 0.000000 X2

54、 20.00000 0.000000 X3 0.000000 0.1000000 X4 0.000000 0.000000 X5 0.000000

55、 0.1000000 X6 30.00000 0.000000 X7 0.000000 0.1000000 X8 0.000000 0.2000000

56、,例20 [人員安排問題],某個中型百貨商場對售貨人員（周工資200元）的需求經(jīng)統(tǒng)計如下表,每個人的休息時間為連續(xù)的兩天時間；每天安排的人員數(shù)不得低于需求量，但可以超過需求量。,為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天。問應(yīng)如何安排銷售人員的工作時間，使得所配售貨人員的總費用最??？,解：設(shè)第 i 天開始工作的人員數(shù)為xi　,　 i=1,2,…7.,min=200*(x1+x2+x3+x4+x5+x6+x7);x1+x

57、4+x5+x6+x7>12;x1+x2+X5+x6+x7>15;x1+x2+x3+x6+x7>12;x1+x2+x3+x4+x7>14;x1+x2+x3+x4+x5>16;x2+x3+x4+x5+x6>18;x3+x4+x5+x6+x7>19;,Global optimal solution found. Objective value:

58、 4400.000 Infeasibilities: 0.000000 Total solver iterations: 4 Variable Value Reduced Cost

59、 X1 0.000000 66.66667 X2 3.000000 0.000000 X3 7.000000 0.000000 X4

60、 0.000000 0.000000 X5 8.000000 0.000000 X6 0.000000 0.000000 X7 4.000000