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

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

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

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

4、，設(shè)生產(chǎn)利潤(rùn)為z.,利潤(rùn)函數(shù)為：,限制條件：三臺(tái)設(shè)備的使用時(shí)間不超過(guò)可利用機(jī)時(shí)設(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單位，總利潤(rùn)為z.,例2 [ 原料配比問(wèn)題] 某企業(yè)使用三種原料B1,B2,B3配制某種食品，要求食品中蛋白質(zhì)、脂肪、糖

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

6、假定運(yùn)費(fèi)與運(yùn)量成正比例，問(wèn)怎樣才能找到一個(gè)總運(yùn)費(fèi)最省的調(diào)撥計(jì)劃？,丙,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）分別表示從甲乙丙三個(gè)產(chǎn)地運(yùn)往A,B,C,D四個(gè)銷地的物資數(shù)量。,則該問(wèn)題的數(shù)學(xué)模型為,簡(jiǎn)化表達(dá)式,,二、線性規(guī)劃問(wèn)題的結(jié)構(gòu)特征：,（1）都有一組決策變量。（2）都有一組線

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

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

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

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

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

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、,,,,無(wú)窮多最優(yōu)解,x1,x2,,,,例3、,,,,,,,,,,,,,⑴,,⑵,,,,,無(wú)有限最優(yōu)解,x1,x2,,,,,,,,,,,,,,,,,,,,,,⑴,,⑵,,,,可行域無(wú)界, 有唯一最優(yōu)解,x1,x2,,,,,例4、,,,,,,,,,,,,,,,,,,⑴,⑵,,x1,x2,,,,,可行域?yàn)榭? 無(wú)可行解,例5、,,,,,,,,,,,,,,,,,,,0,1 2 3 4

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

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

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

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

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

19、上達(dá)到？如何找到頂點(diǎn)？ 如何從一個(gè)頂點(diǎn)轉(zhuǎn)移到另一個(gè)頂點(diǎn)？,二、基可行解及線性規(guī)劃的基本定理,基可行解的定義線性規(guī)劃的基本定理問(wèn)題,1. 基可行解的定義,考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題,基：A是約束方程組的系數(shù)矩陣(設(shè)n>m)，其秩為m，B是A中的一個(gè)m階滿秩子方陣，稱B是線性規(guī)劃問(wèn)題的一個(gè)基。B中每一個(gè)列向量稱為一個(gè)基向量，與基向量對(duì)應(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，將這個(gè)解加上非基變量取0的值有X=(x1，x2，…xm,0,…,0)T,稱X為線性規(guī)劃問(wèn)題的基解。,顯然，基解中取非零值的變量個(gè)數(shù)不超過(guò)m，基解的總數(shù)不超過(guò)Cnm個(gè)。,基可行解：滿足非負(fù)約束的基解稱為基可行解?？尚谢簩?duì)

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

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

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

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

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

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

27、最優(yōu)性原則：若?k >0,則與?k 相對(duì)應(yīng)的變量xk 是非基變量，當(dāng)xk 變?yōu)榛兞繒r(shí)，它的值由0變?yōu)檎龜?shù)，比如說(shuō)xk= ? >0，其余的非基變量仍取值為零。由(3.4)式知，對(duì)應(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ī)劃問(wèn)題,x1,添加松弛變量，化成標(biāo)準(zhǔn)形式（典式）,約束條件系數(shù)矩陣含單位矩陣；目標(biāo)函數(shù)中基變量系數(shù)為0。,第一個(gè)基可行解X0=(0,0,80,60,45)T目標(biāo)函數(shù)值為0對(duì)應(yīng)可行域頂點(diǎn)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 對(duì)應(yīng)的典式可以由方程組的初等變換得到,,新的基可行解

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

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

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

33、則確定出基變量;Step 5 利用方程組的初等變換得到新的基對(duì)應(yīng)的典式，基可行解和檢驗(yàn)數(shù),轉(zhuǎn)step 2.,單純形表,= -∑ cn+i bi ?j = cj -∑ cn+i,例11 用單純形表求解例1中的線性規(guī)劃問(wèn)題,解：先化成標(biāo)準(zhǔn)形式,,,最優(yōu)解X*=(10,15,0,0,15)T，最優(yōu)值1400。,例2：利用單純形法求下列線性規(guī)劃問(wèn)題,將該問(wèn)題化成標(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í)，若有幾個(gè)非基變量的檢驗(yàn)數(shù)都是正數(shù)，則可以任意選取一個(gè)正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量作為進(jìn)基變量，一般選取最大正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量。但實(shí)際情況表明這種策略不一定最好。,2. 在選取出基變量時(shí)，若有幾個(gè)比值同時(shí)達(dá)到最小，可以任意選擇一個(gè)，但在新的基可行解中這些對(duì)應(yīng)分量均為零。從而新的基可行解是一個(gè)退化的基可行解。

35、假若問(wèn)題是非退化的，則不會(huì)出現(xiàn)這種情況。,例12：用單純形法求解線性規(guī)劃問(wèn)題（多解問(wèn)題）,解: 化成標(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。,實(shí)際上X1與X2的連線上的任意點(diǎn)都是最優(yōu)解.,例13：用單純形法求解線性規(guī)劃問(wèn)題（無(wú)有限最優(yōu)解的情況）,解：化成標(biāo)準(zhǔn)形（典式）,,X2的檢驗(yàn)數(shù)為正，但約束條件中x2的系數(shù)全為負(fù)，因此該問(wèn)題無(wú)有限最優(yōu)解。,

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

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

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

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

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

41、B,C三種原料，用j=1,2,3分別代表甲，乙，丙三種糖果，設(shè)xij為生產(chǎn)第j種糖果使用的第i種原料的質(zhì)量，則問(wèn)題的數(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［投資項(xiàng)目的組合問(wèn)題］興安公司有一筆30萬(wàn)元的資金，考慮今后3年內(nèi)用于下列項(xiàng)目的投資：［項(xiàng)目一］　三年內(nèi)的每年年初可投資，每年獲利為投資額的20%，其本利可一起用于下一年的投資；［項(xiàng)目二］　只允許第一年初投資，于第二年末收回，本利合計(jì)為投資額的150%，但此類投資限額不超過(guò)15萬(wàn)元；［項(xiàng)目三］　允許于第二年初投資，于第三年末收回，本利合計(jì)為投資額的160%，但限額投資為20萬(wàn)元；［項(xiàng)目

47、四］　允許于第三年初投資，年末收回，可獲利40%，但限額為10萬(wàn)元。試為該公司確定一個(gè)使第三年末本利和為最大的投資組合方案。,解：用xij 表示第i 年初投資到第j 項(xiàng)目的資金數(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 [下料問(wèn)題]　　工廠要制作100套專用鋼架，每套鋼架需要用長(zhǎng)為2.9m、2.1m和1.5m的圓鋼各一根。已知原料每根長(zhǎng)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 [人員安排問(wèn)題],某個(gè)中型百貨商場(chǎng)對(duì)售貨人員（周工資200元）的需求經(jīng)統(tǒng)計(jì)如下表,每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間；每天安排的人員數(shù)不得低于需求量，但可以超過(guò)需求量。,為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天。問(wèn)應(yīng)如何安排銷售人員的工作時(shí)間，使得所配售貨人員的總費(fèi)用最??？,解：設(shè)第 i 天開(kā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