1.線性規(guī)劃及單純形法ppt課件

1、第一章第一章線性規(guī)劃及其單純形法線性規(guī)劃及其單純形法第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法 第一節(jié) 線性規(guī)劃問題及數(shù)學(xué)模型 Linear Programming , LP1939年 蘇 康托洛維奇1941年 美 Hichook1947年 G. B. Dantzig 單純形法1979年 蘇 哈奇安算法1984年 Karmarkar算法 LPLP是數(shù)學(xué)規(guī)劃的一個重要分支，數(shù)學(xué)規(guī)劃著重解決資源的是數(shù)學(xué)規(guī)劃的一個重要分支，數(shù)學(xué)規(guī)劃著重解決資源的優(yōu)化配置，一般可以表達(dá)成以下兩個問題中的一個：優(yōu)化配置，一般可以表達(dá)成以下兩個問題中的一個：（1 1當(dāng)資源給定時，要求完成的任務(wù)最多；當(dāng)資源給定時，

2、要求完成的任務(wù)最多；（2 2當(dāng)任務(wù)給定時，要求為完成任務(wù)所消耗的資源最少。當(dāng)任務(wù)給定時，要求為完成任務(wù)所消耗的資源最少。 若上述問題的目標(biāo)若上述問題的目標(biāo)約束都能表達(dá)成變量的線性關(guān)系，約束都能表達(dá)成變量的線性關(guān)系，則這類優(yōu)化問題稱則這類優(yōu)化問題稱LPLP問題。問題。LPLP是一種解決在線性約束條件下追求最大或最小的線性目是一種解決在線性約束條件下追求最大或最小的線性目標(biāo)函數(shù)的方法。標(biāo)函數(shù)的方法。一、實(shí)例一、實(shí)例例例1 生產(chǎn)計劃問題生產(chǎn)計劃問題 (書書P8，典型示例，典型示例)Step 1:Step 1:明確問題，設(shè)定決策變量明確問題，設(shè)定決策變量設(shè)設(shè)I I、IIII兩種產(chǎn)品的產(chǎn)量分別為兩種產(chǎn)品

3、的產(chǎn)量分別為x1, x2 x1, x2 。Step 2: Step 2: 確定約束條件確定約束條件 產(chǎn)品產(chǎn)品 I II資源限量資源限量 設(shè)設(shè) 備備 1 2 8臺時臺時 原料原料A 4 0 16公斤公斤 原料原料B 0 4 12公斤公斤 利潤利潤 2 38221 xx工工時時約約束束：1604A21 xx約約束束：原原料料1240B21 xx約約束束：原原料料0021 xx，變變量量非非負(fù)負(fù)約約束束： 0124164823221212121x,xxxxx. t . sxxZmax:OBJ闡明：闡明：OBJ OBJ 表示表示Objective;Objective; s.t. s.t. 表示表示Su

4、bject to Subject to Step 3: Step 3: 給出目標(biāo)函數(shù)給出目標(biāo)函數(shù)2132xxZmax Step 4: Step 4: 整理數(shù)學(xué)模型整理數(shù)學(xué)模型例例2 污水處理問題污水處理問題 (書書P9)環(huán)保要求：環(huán)保要求：(污水量污水量/河水量河水量)0.2%， 河流自凈力：河流自凈力：20%500萬m3200萬m31.4萬m3，800元/萬m3 o工廠2 2萬m3 ，1000元/萬m3 o工廠1設(shè)設(shè)x1x1x2x2為工廠為工廠1 12 2 的日污水處理量。建的日污水處理量。建立該問題的數(shù)學(xué)模型立該問題的數(shù)學(xué)模型為：為： 0,4 . 10 . 26 . 18 . 00 . 1

5、. .8001000min:212121121xxxxxxxtsxxZOBJ二、總結(jié)二、總結(jié) 目標(biāo)函數(shù)用決策變量的線性函數(shù)來表示。按問題目標(biāo)函數(shù)用決策變量的線性函數(shù)來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化和最小化。的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化和最小化。線性規(guī)劃問題線性規(guī)劃問題LP問題的共同特征：問題的共同特征： 每一個問題變量都用一組決策變量每一個問題變量都用一組決策變量x1, x2, , xn表表示某一方案，這組決策變量的值代表一個具體方案，這示某一方案，這組決策變量的值代表一個具體方案，這些變量是非負(fù)的且在某范圍內(nèi)連續(xù)取值。些變量是非負(fù)的且在某范圍內(nèi)連續(xù)取值。 存在一定的約束條件，這

6、些約束條件可以用一組存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。線性等式或線性不等式來表示。三、線性規(guī)劃問題的一般形式三、線性規(guī)劃問題的一般形式mibmnnjxbxaxaxabxaxaxabxaxaxatsxcxcxcZijmnmnmmnnnnnn,2,1,0),( : :,2,1,0),(),(),(),(.max(min)221122222121112121112211 約約束束條條件件個個數(shù)數(shù)。變變量量個個數(shù)數(shù)；四、兩變量線性規(guī)劃問題的圖解法四、兩變量線性規(guī)劃問題的圖解法1.線性不等式的幾何意義線性不等式的幾何意義 半平面半平面作出作出LP問題的可行域問題的可行

7、域作出目標(biāo)函數(shù)的等值線作出目標(biāo)函數(shù)的等值線移動等值線到可行域邊界移動等值線到可行域邊界得到最優(yōu)點(diǎn)得到最優(yōu)點(diǎn)2.圖解法步驟圖解法步驟 0,12416482.32max:21212121xxxxxxtsxxZOBJ例例1 （典型示例）：（典型示例）：4x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0) Q2(4,2)Z=2x1+3x2 做目標(biāo)函數(shù)做目標(biāo)函數(shù)2x1+3x2的等值線，與陰影部分的的等值線，與陰影部分的邊界相交于邊界相交于Q(4,2)點(diǎn)，表明最優(yōu)生產(chǎn)計劃為：生產(chǎn)點(diǎn)，表明最優(yōu)生產(chǎn)計劃為：生產(chǎn)I產(chǎn)品產(chǎn)品4件，生產(chǎn)件，生產(chǎn)II產(chǎn)品產(chǎn)品2件。件。

8、Q1(4,0)Q3(2,3)Q5(4,3)圖解法意義不大，但可直觀揭示有關(guān)概念。圖解法意義不大，但可直觀揭示有關(guān)概念。3.LP解的類型解的類型有有4類：類：（1唯一最優(yōu)解唯一最優(yōu)解 如例如例1的的Q2點(diǎn)。點(diǎn)。（2無窮多最優(yōu)解多重解）無窮多最優(yōu)解多重解）（3無界解無界解（4無可行解無可行解0 4 8 12 x1 9 6 3 可行域可行域Z=364, 6此線段上的點(diǎn)均為最優(yōu)點(diǎn)x2當(dāng)例當(dāng)例1 的目標(biāo)函數(shù)變?yōu)榈哪繕?biāo)函數(shù)變?yōu)?max Z =2x1+4x2 多重解示例多重解示例 8, 3x2可行域不閉合Z增大方向x1無界解示例無界解示例 產(chǎn)生原因：缺少約束條件產(chǎn)生原因：缺少約束條件 注注 意：可行域不閉合

9、不一定就會出現(xiàn)無界意：可行域不閉合不一定就會出現(xiàn)無界解，這要看目標(biāo)函數(shù)的性質(zhì)。若目解，這要看目標(biāo)函數(shù)的性質(zhì)。若目標(biāo)函數(shù)是標(biāo)函數(shù)是min，則有最優(yōu)解。無論，則有最優(yōu)解。無論有無最優(yōu)解，一定有可行解。有無最優(yōu)解，一定有可行解。 無可行解示例無可行解示例 無公共區(qū)域(可行域)產(chǎn)生原因： 有相互矛盾的約束條件。x2x14. 圖解法的作用圖解法的作用LPLP問題問題有可行解有可行解有最優(yōu)解有最優(yōu)解唯一解唯一解無窮多解無窮多解無最優(yōu)解可行域?yàn)闊o界）無最優(yōu)解可行域?yàn)闊o界）無可行解無解）無可行解無解）（1規(guī)律：規(guī)律： 揭示了線性規(guī)劃問題有關(guān)規(guī)律和結(jié)論。揭示了線性規(guī)劃問題有關(guān)規(guī)律和結(jié)論。（2結(jié)論：若結(jié)論：若LP

10、問題有最優(yōu)解，則要么最優(yōu)解唯一對問題有最優(yōu)解，則要么最優(yōu)解唯一對應(yīng)其中一個頂點(diǎn)），要么有無窮多最優(yōu)解應(yīng)其中一個頂點(diǎn)），要么有無窮多最優(yōu)解對應(yīng)其中兩個頂點(diǎn)連線上的所有點(diǎn)）。對應(yīng)其中兩個頂點(diǎn)連線上的所有點(diǎn)）。五、五、 線性規(guī)劃問題的標(biāo)準(zhǔn)型線性規(guī)劃問題的標(biāo)準(zhǔn)型1. 標(biāo)準(zhǔn)型的構(gòu)成要素標(biāo)準(zhǔn)型的構(gòu)成要素（1目標(biāo)函數(shù)：目標(biāo)函數(shù)：max（2約束條件：等式約束條件：等式（3變量約束：非負(fù)變量約束：非負(fù) xj0（4資源限量：非負(fù)資源限量：非負(fù)bi 0技技術(shù)術(shù)系系數(shù)數(shù)右右端端項(xiàng)項(xiàng)，價價值值系系數(shù)數(shù)約約束束行行數(shù)數(shù)變變量量個個數(shù)數(shù): ;,2, 1,0: : ;: ;:,2, 1,0.max22112222212111

11、2121112211ijiijjmnmnmmnnnnnnamibbcmnnjxbxaxaxabxaxaxabxaxaxatsxcxcxcZ 2. 標(biāo)準(zhǔn)型的表示方法標(biāo)準(zhǔn)型的表示方法（1解析式解析式簡寫的解析式簡寫的解析式 , 2 , 10, 2 , 1.max11 ）（）（njxmibxatsxcZjijnjijjnjj 0.maxXbAXtsCXZ亦可寫成：亦可寫成：0max XbAXCXZ，其中：其中： nmnmnmmnncccCbbbbxxxXaaaaaaaaaA212121212222111211 （2矩陣式矩陣式X決策變量列向量。決策變量列向量。 b約束條件右端常數(shù)資源列向量。約束條件

12、右端常數(shù)資源列向量。C目標(biāo)函數(shù)價值系數(shù)行向量。目標(biāo)函數(shù)價值系數(shù)行向量。 Amn約束條件左端系數(shù)矩陣。約束條件左端系數(shù)矩陣。 ),2 , 1(0.max12121222211121121njxbxPtsCXZPPPAaaaaaaaaaAaaaPjnjjjnmnmmnnnjjjj則則）（可可寫寫成成：矩矩陣陣時時，當(dāng)當(dāng)（3向量和矩陣符號式向量和矩陣符號式的的最最優(yōu)優(yōu)目目標(biāo)標(biāo)函函數(shù)數(shù)值值。問問題題函函數(shù)數(shù)值值變變號號即即為為最最小小化化最最大大化化問問題題的的最最優(yōu)優(yōu)目目標(biāo)標(biāo)。求求出出最最優(yōu)優(yōu)解解后后，可可轉(zhuǎn)轉(zhuǎn)換換成成令令，小小化化問問題題根根據(jù)據(jù)這這一一原原理理，對對于于最最，最最優(yōu)優(yōu)值值絕絕對對

13、值值相相同同。同同為為上上述述例例子子中中，最最優(yōu)優(yōu)解解相相CXZZZCXZx maxmin*3. 非標(biāo)準(zhǔn)型的標(biāo)準(zhǔn)化非標(biāo)準(zhǔn)型的標(biāo)準(zhǔn)化（1最小轉(zhuǎn)換成最大最小轉(zhuǎn)換成最大y1=f(x)y2=-f(x)xyx*y1*y2*成成一一個個約約束束。這這樣樣就就把把兩兩個個約約束束轉(zhuǎn)轉(zhuǎn)換換，則則此此時時，則則，令令若若；，無無限限制制，令令若若，則則，令令若若abxxabxxaxxbxaxxxxxxxxxxnjjjjjjjjjjjjjjjj 3000;00 為為剩剩余余變變量量若若為為松松弛弛變變量量若若0,0,2211ninjijijijninjijijijxbxxabxaxbxxabxa（2不等式約束條

14、件轉(zhuǎn)換成等式約束條件不等式約束條件轉(zhuǎn)換成等式約束條件（3變量約束轉(zhuǎn)換變量約束轉(zhuǎn)換。，即即方方程程兩兩邊邊同同乘乘以以則則，即即若若1000 ijijijijibxabxab（4把把bi0轉(zhuǎn)換成轉(zhuǎn)換成bi0例例1 0,12416482.32max21212121xxxxxxtsxxZ )5 , 1( 01241648200032max524132154321jxxxxxxxxxxxxxZj可化為可化為例例2 化標(biāo)準(zhǔn)型化標(biāo)準(zhǔn)型型型即即可可得得到到該該問問題題的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)改改為為求求，把把求求令令以以滿滿足足非非負(fù)負(fù)約約束束條條件件；號號兩兩端端同同乘乘以以在在第第三三個個約約束束條條件件號號的的左

15、左端端減減去去剩剩余余變變量量在在第第二二個個約約束束不不等等式式號號的的左左端端加加入入松松弛弛變變量量在在第第一一個個約約束束不不等等式式；，令令其其中中令令;maxmin, 1;0;0, 0,7622254543ZZZZxxxxxxxxxx 無無約約束束321321321321321,0,053327.32minxxxxxxxxxxxxtsxxxZ 0;4 ,2,1,0417431432.42max;842max4040,2343321321321321434333xjxxxxxxxxxtsxxxZxxxZxxxxxxj即即所所以以，滿滿足足且且；則則有有解解：令令課堂作業(yè)課堂作業(yè)1 6

16、2 , 0,25432032.42max321321321321xxxxxxxxxtsxxxZ六、標(biāo)準(zhǔn)型六、標(biāo)準(zhǔn)型LPLP問題的解問題的解 )3(0 )2(.)1(maxXbAXtsXCZT1. 基本概念基本概念）的的解解；）、（滿滿足足（可可行行解解32,21 ncccC其中，其中，,21 nxxxX,212222111211 mnmmnnaaaaaaaaaAmArnm )(,并假定：并假定：問問題題的的一一個個基基。為為），則則稱稱非非奇奇異異子子矩矩陣陣（的的為為問問題題的的系系數(shù)數(shù)矩矩陣陣，為為設(shè)設(shè)基基LP0,)(LPBBABmArAmmnm 問題的最優(yōu)解；問題的最優(yōu)解；）的可行解，為

17、）的可行解，為滿足（滿足（最優(yōu)解最優(yōu)解LP1。，一一般般個個數(shù)數(shù)為為問問題題，基基的的最最大大個個決決策策變變量量的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)個個約約束束條條件件，對對于于CCmnmnnm LP 4 , 3 , 2 , 1, 0105342.max42132121jxxxxxxxtsxxZj例例：,10530121 A，分分別別是是：基基的的最最大大可可能能個個數(shù)數(shù)為為624 CCmn， 53211B， 03112B， 13013B， 05124B， 15025B 10016B問問題題的的基基。均均為為根根據(jù)據(jù)基基的的定定義義，LP61BB ）（令令mmmmmmmPPPaaaaaaaaaB,212122221

18、11211 問問題題的的一一個個基基。為為，則則且且LP0BB 。中中的的組組成成基基的的向向量量。如如基基向向量量mPPPB,21。，記記為為如如基基向向量量所所對對應(yīng)應(yīng)的的變變量量?；冏兞苛縏mBmxxxXxxx),(,2121 。，記為，記為基變量之外的變量。如基變量之外的變量。如非基變量非基變量TnmNnmxxXxx),(,11 時時，如如在在上上例例中中，當(dāng)當(dāng)基基為為 05124B為為非非基基變變量量。、為為一一組組基基變變量量，、則則對對應(yīng)應(yīng)的的4132xxxx為為非非基基變變量量。、為為一一組組基基變變量量，、時時，則則對對應(yīng)應(yīng)的的而而當(dāng)當(dāng)基基為為432115321xxxxB

19、 化化。而而是是隨隨著著基基的的變變化化而而變變一一成成不不變變的的，問問題題中中，基基變變量量并并不不是是由由此此可可見見，同同一一個個 LP，則則，求求得得一一組組基基變變量量的的值值令令解解本本基基BNXX0)( 為為基基本本解解。），（），（TBTNBXXXX0 點(diǎn)點(diǎn)。，如如典典型型示示例例圖圖解解法法中中的的71Q,QO解解。既既是是基基本本解解，又又是是可可行行（頂頂點(diǎn)點(diǎn)）可可行行解解本本基基)(點(diǎn)點(diǎn)。如如典典型型示示例例圖圖解解法法中中的的4321Q,Q,Q,Q,O解解。目目標(biāo)標(biāo)函函數(shù)數(shù)值值達(dá)達(dá)到到最最優(yōu)優(yōu)的的既既是是基基可可行行解解，又又是是使使基基最最優(yōu)優(yōu)解解 點(diǎn)點(diǎn)。如如典典

20、型型示示例例圖圖解解法法中中的的2Q基基可可行行解解對對應(yīng)應(yīng)的的基基。可可行行基基 基基最最優(yōu)優(yōu)解解對對應(yīng)應(yīng)的的基基。最最優(yōu)優(yōu)基基 4x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0) Q2(4,2)Q1(4,0)Q3(2,3)Q5(4,3)基變量基變量非非 基基 變變 量量圖中的點(diǎn)及對應(yīng)圖中的點(diǎn)及對應(yīng)的解的解x3=8x4=16x5=12x1，x2O 基可行解基可行解x1=4x3=4x5=12x2，x4Q1 基可行解基可行解x1=4x2=2x5=5x3，x4Q2 基可行解基可行解 最優(yōu)解最優(yōu)解x1=2x2=3x4=8x3，x5Q3 基可行解基可

21、行解x2=3x3=2x4=16x1，x5Q4 基可行解基可行解x1=4x2=3x3=2x4，x5Q5 基解基解x2=4x4=16x5=4x1，x3Q6 基解基解x1=8x4=16x5=12x2，x3Q7 基解基解x1=2, x2=2, x3=2, x4=8, x5=4K 可行解可行解K2. 可行解、基解和基可行解舉例可行解、基解和基可行解舉例 典型示例標(biāo)準(zhǔn)化后有典型示例標(biāo)準(zhǔn)化后有3個約束條件、個約束條件、5個決策變量，個決策變量，基的最大個數(shù)可達(dá)基的最大個數(shù)可達(dá)C53=10個，但實(shí)際上只有個，但實(shí)際上只有8個。個。約束方程的約束方程的解空間解空間基解基解可行解可行解非可行解非可行解基可基可行解

22、行解3. LP標(biāo)準(zhǔn)型問題解的關(guān)系標(biāo)準(zhǔn)型問題解的關(guān)系4. LP標(biāo)準(zhǔn)型問題解的結(jié)論標(biāo)準(zhǔn)型問題解的結(jié)論 根據(jù)根據(jù)LP的圖解法及解的基本概念可知：的圖解法及解的基本概念可知：基解對應(yīng)約束條件的交點(diǎn)；基解對應(yīng)約束條件的交點(diǎn)；基可行解對應(yīng)可行域的頂點(diǎn)基可行解對應(yīng)可行域的頂點(diǎn)最優(yōu)解一定是基可行解，一定在可行域的頂點(diǎn)上得到。最優(yōu)解一定是基可行解，一定在可行域的頂點(diǎn)上得到。第二節(jié)第二節(jié) 單純形法單純形法 Simplex MethodSimplex Method 由線性代數(shù)知，對LP標(biāo)準(zhǔn)型問題，理論上可以求出所有基解枚舉法），再通過觀察找出其中基可行解，進(jìn)而找出最優(yōu)解。但如果變量和方程較多，比如m=50，n=10

23、0，所有基解有可能達(dá)1029個，即使計算機(jī)每秒能求解1億個這樣的方程組，也需要30萬億年！因此，必須尋求有效的算法。 為加快計算速度，算法必須具有兩個功能，一是每得到一個基可行解，就能檢驗(yàn)是否已經(jīng)最優(yōu)，若是，停頓。二是若不是最優(yōu)，要保證下一步得到的基可行解不劣于當(dāng)前解。基于線性代數(shù)原理，并將上述功能貫穿于算法過程，這就是線性規(guī)劃的單純形法。 一、基本思想一、基本思想化化LP問題為標(biāo)準(zhǔn)型，問題為標(biāo)準(zhǔn)型，確定一個初始基可行解確定一個初始基可行解檢驗(yàn)解的檢驗(yàn)解的最優(yōu)性最優(yōu)性終了終了Y旋轉(zhuǎn)運(yùn)算樞軸運(yùn)算）旋轉(zhuǎn)運(yùn)算樞軸運(yùn)算）確定另一個基可行解確定另一個基可行解N基本思路：化基本思路：化LP問題為標(biāo)準(zhǔn)型，從

24、可行域問題為標(biāo)準(zhǔn)型，從可行域的某個基可行解一個頂點(diǎn)開場，轉(zhuǎn)換到另一的某個基可行解一個頂點(diǎn)開場，轉(zhuǎn)換到另一個基可行解另一個頂點(diǎn)），并使目標(biāo)函數(shù)值得個基可行解另一個頂點(diǎn)），并使目標(biāo)函數(shù)值得到改善，如此反復(fù)，從而求得問題的最優(yōu)解。到改善，如此反復(fù)，從而求得問題的最優(yōu)解。其實(shí)質(zhì)是逐步迭代逼近法。其實(shí)質(zhì)是逐步迭代逼近法。二、基本原理舉例二、基本原理舉例 ) 4() 5 , 1( 0) 3(124) 2(164) 1 (82) 0(00032max524132154321jxxxxxxxxxxxxxZj以以典典型型示示例例為為例例：1. 初始基可行解的確定初始基可行解的確定要得到一個初始基可行解，必須找到

25、一個初始可行基。要得到一個初始基可行解，必須找到一個初始可行基。由于典型示例標(biāo)準(zhǔn)化后，由于典型示例標(biāo)準(zhǔn)化后，x3、x4、x5的系數(shù)列向量構(gòu)成單的系數(shù)列向量構(gòu)成單位矩陣，該矩陣位矩陣，該矩陣B0是一個基，并且是一個可行基可以證是一個基，并且是一個可行基可以證明，標(biāo)準(zhǔn)化后的單位矩陣一定是可行基）。明，標(biāo)準(zhǔn)化后的單位矩陣一定是可行基）。) 6(320412) 5(41628212514213xxZxxxxxxx 令非基變量令非基變量x10、x2 0，得到基可行解及相應(yīng)的目標(biāo)，得到基可行解及相應(yīng)的目標(biāo)函數(shù)值，函數(shù)值，X(0) (0,0,8,16,12)T， Z(0) 0。結(jié)論：結(jié)論： （1在標(biāo)準(zhǔn)化的在

26、標(biāo)準(zhǔn)化的LP問題的約束系數(shù)矩陣中，只要存在單問題的約束系數(shù)矩陣中，只要存在單位矩陣，就可求得初始基可行解；位矩陣，就可求得初始基可行解； （2基變量確定后，目標(biāo)函數(shù)和基變量均可表示成非基基變量確定后，目標(biāo)函數(shù)和基變量均可表示成非基變量的代數(shù)和形式如變量的代數(shù)和形式如(6)和和(5)），從而便于求出基可行解及），從而便于求出基可行解及相應(yīng)的目標(biāo)函數(shù)值。相應(yīng)的目標(biāo)函數(shù)值。2. 最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) 考察變換后的目標(biāo)函數(shù)考察變換后的目標(biāo)函數(shù)(6)式，非基變量式，非基變量x1、x2的系數(shù)都的系數(shù)都為正數(shù)，若讓為正數(shù)，若讓x1、x2取正值，則目標(biāo)函數(shù)值會增大。因此，取正值，則目標(biāo)函數(shù)值會增大。因此，應(yīng)將

27、非基變量應(yīng)將非基變量x1、x2變換成基變量。變換成基變量。結(jié)論：結(jié)論： 在非基變量的代數(shù)和形式表示的目標(biāo)函數(shù)中，若非基變在非基變量的代數(shù)和形式表示的目標(biāo)函數(shù)中，若非基變量的系數(shù)稱為檢驗(yàn)數(shù)為正，則目標(biāo)函數(shù)值還有增加的可量的系數(shù)稱為檢驗(yàn)數(shù)為正，則目標(biāo)函數(shù)值還有增加的可能，表明當(dāng)前的基可行解不是最優(yōu)解。能，表明當(dāng)前的基可行解不是最優(yōu)解。3. 確定新的基可行解基變換）確定新的基可行解基變換） 單純形法在尋找新的可行基時，是以當(dāng)前的可行基為基礎(chǔ)單純形法在尋找新的可行基時，是以當(dāng)前的可行基為基礎(chǔ)的，即把當(dāng)前的可行基中某一列用非基向量替換，從而形成的，即把當(dāng)前的可行基中某一列用非基向量替換，從而形成新的可行

28、基。新的可行基。確定換入變量：一般選擇正系數(shù)最大的非基變量為換入變量。確定換入變量：一般選擇正系數(shù)最大的非基變量為換入變量。 本例為非基變量本例為非基變量x2。確定換出變量：其依據(jù)是確定換出變量：其依據(jù)是a保證換出的變量取值為保證換出的變量取值為0，變，變 成非基量；（成非基量；（b其它的變量取值為非負(fù)。其它的變量取值為非負(fù)。4120412) 7(016280282254223 xxxxxxx 當(dāng)確定當(dāng)確定x2為換入變量后，為換入變量后， x1還是非基變量，故還是非基變量，故 x10。現(xiàn)?，F(xiàn)在要保證在要保證x3、x4、x50，即，即(5)當(dāng)當(dāng) x2 min8/2，12/4） =3 （最小比值規(guī)

29、則）（最小比值規(guī)則）可保證可保證 x5 =0則則x5為換出變量。為換出變量。新的基變量為新的基變量為x3、x4、x2 ，新的可行基為，新的可行基為B1(P3, P4 , P2)4. 旋轉(zhuǎn)迭代旋轉(zhuǎn)迭代 基變量確定后，旋轉(zhuǎn)迭代就是把目標(biāo)函數(shù)和基變量均表基變量確定后，旋轉(zhuǎn)迭代就是把目標(biāo)函數(shù)和基變量均表示成非基變量示成非基變量x1、x5的代數(shù)和形式?？捎酶咚瓜シ▽?shí)現(xiàn)。的代數(shù)和形式?？捎酶咚瓜シ▽?shí)現(xiàn)。) 9(4329413) 8(416212515214513xxZxxxxxxx 令非基變量令非基變量x10、x5 0，得到新的基可行解及相應(yīng)的，得到新的基可行解及相應(yīng)的目標(biāo)函數(shù)值，目標(biāo)函數(shù)值，X(1)

30、 (0,3,2,16,0)T， Z(1) 9。返回至第二步，。返回至第二步，直至求出最優(yōu)解。直至求出最優(yōu)解。 將上述方程組求解過程，用列表形式表達(dá)，即為線性規(guī)劃將上述方程組求解過程，用列表形式表達(dá)，即為線性規(guī)劃單純形法。單純形法。三、最優(yōu)性檢驗(yàn)及解的判別三、最優(yōu)性檢驗(yàn)及解的判別1. 檢驗(yàn)數(shù)公式檢驗(yàn)數(shù)公式代代入入目目標(biāo)標(biāo)函函數(shù)數(shù)將將數(shù)數(shù)和和形形式式：可可表表示示成成非非基基變變量量的的代代變變量量個個變變量量為為基基變變量量，則則基基程程中中，前前不不失失一一般般性性，設(shè)設(shè)迭迭代代過過)1()1(), 2 , 1(1mixabxxmjnmjijiii 課堂作業(yè)課堂作業(yè)2： 請給出教科書請給出教科

31、書p23 公式公式1-25的推導(dǎo)過程。的推導(dǎo)過程。)2()()()1()1(), 2 , 1(11111111111111 mijnmjmiijijiinmjjjmimijnmjijiiinmjjjmijnmjijiinmjjjmiiinjjjjnmjijiixaccbcxcxacbcxcxabcxcxcxcZmixabx代代入入目目標(biāo)標(biāo)函函數(shù)數(shù)將將力力，故故稱稱其其為為檢檢驗(yàn)驗(yàn)數(shù)數(shù)。問問題題是是否否達(dá)達(dá)到到最最優(yōu)優(yōu)的的能能具具有有判判別別由由于于可可進(jìn)進(jìn)一一步步簡簡化化成成：則則再再令令數(shù)數(shù)和和形形式式?？煽杀肀硎臼境沙煞欠腔冏兞苛康牡拇肀砻髅髂磕繕?biāo)標(biāo)函函數(shù)數(shù)可可寫寫成成：令令LP)

32、4()3()3()3()()2(, 1,1010110jjnmjjjjjjjnmjjmimiijijiixZZZcZxZcZZnmjacZbcZ 2. 最優(yōu)性檢驗(yàn)與解的判別最優(yōu)性檢驗(yàn)與解的判別 設(shè)設(shè)X(0)=(b1, b2, ,bm,0, ,0)T為對應(yīng)于基為對應(yīng)于基B的一個的一個基可行解?；尚薪狻τ谧畲蠡瘑栴}，最優(yōu)性檢驗(yàn)與解的判別如下：對于最大化問題，最優(yōu)性檢驗(yàn)與解的判別如下：（1唯一最優(yōu)解唯一最優(yōu)解 對于一切對于一切 j=m+1, ,n，有，有 j0，則，則X(0)為唯一最優(yōu)解。為唯一最優(yōu)解。（2無窮多最優(yōu)解無窮多最優(yōu)解 對于一切對于一切 j=m+1, ,n，有，有 j0，且至少有一個

33、，且至少有一個 m+k=0，則該則該LP問題有無窮多最優(yōu)解，問題有無窮多最優(yōu)解，X(0)為其中之一。為其中之一。（3無界解無界解 在在 j=m+1, ,n中，至少有一個中，至少有一個 m+k0，且對，且對i=1, ,m，有有ai,m+k0，則該，則該LP問題具有無界解。問題具有無界解。四、基變換四、基變換1. 換入變量的確定換入變量的確定2. 換出變量的確定換出變量的確定則第則第l個約方程對應(yīng)的基變量個約方程對應(yīng)的基變量xl為換出變量。為換出變量。),2, 1(0minmiabaablklikikiil 若若 為為換換入入變變量量所所對對應(yīng)應(yīng)變變量量，選選取取若若kkjjjkx 0|max 五

34、、迭代運(yùn)算五、迭代運(yùn)算系系數(shù)數(shù)為為主主元元素素的的以以中中的的基基變變量量為為中中的的基基變變量量，為為設(shè)設(shè)例例：133221121)1()2()1(6102332)2()1(xxxxxxxxx 為為主主元元素素系系數(shù)數(shù)的的以以2/3)4()4()3(9520233223221112/ )1( ,)1()2(23xxxxxxx 60803342133521)4( , 3)4()3(32xxxxxx第三節(jié)第三節(jié) 單純型法的步驟單純型法的步驟1. 化化LP問題為標(biāo)準(zhǔn)型問題為標(biāo)準(zhǔn)型,建立初始單純型表建立初始單純型表;步步；則則，轉(zhuǎn)轉(zhuǎn)第第，則則最最優(yōu)優(yōu)解解已已達(dá)達(dá)到到，否否若若所所有有檢檢驗(yàn)驗(yàn)數(shù)數(shù)30

35、. 2 )(. 3基基變變換換確確定定換換入入和和換換出出變變量量步步。轉(zhuǎn)轉(zhuǎn)第第為為主主元元素素進(jìn)進(jìn)行行旋旋轉(zhuǎn)轉(zhuǎn)迭迭代代以以2,. 4lka一、步驟一、步驟 為為換換入入變變量量；對對應(yīng)應(yīng)的的非非基基變變量量，選選取取按按kkjjjkx 0|max ;0|min為為換換出出變變量量對對應(yīng)應(yīng)的的基基變變量量，選選取取計計算算lllklikikiilxabaab 0,121684243221221121xxxxxxxxMaxZ化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj二、實(shí)例二、實(shí)例單純型表算法單純型表算法

36、X(0) (0,0,8,16,12)T O點(diǎn)點(diǎn)以以1為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x1為換入變量，為換入變量， x3為換出變?yōu)閾Q出變量量cj 2 3 0 0 0 iCBXB b x1 x2 x3 x4 x50 x3 0 x4 j x1 cj x2 x3 x4 x5 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 2 3 0 0 0 b816 12 XB x3 x4 x5 CB 0 0 0以以4為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x2為換入變量，為換入變量，x5為換出變?yōu)閾Q出變量量 j 2 3 0 0 0 i 8/2 12/44 miijijjacc1 x2 3

37、主元列主元列主元行主元行 0 0 0 1/43 1 4 0 1 016 0 0 1 1 0 -1/22X(1) (0,3,2,16,0)T Q4點(diǎn)點(diǎn) 2 0 0 -3/4 016/4 2/1 1此時達(dá)到最優(yōu)解。此時達(dá)到最優(yōu)解。X*=(4,2), max Z=14。cj 2 3 0 0 0 iCBXB b x1 x2 x3 x4 x5 0 x4 3 x2 j cj 2 3 0 0 0 iCBXB b x1 x2 x3 x4 x52 x1 3x2 j 0 0 0 1/43 10 -2 0 1/4 0 x1 2 0 1 1 0 -1/22 2 0-4 128 08/2 12 x50 0 -2 1/2

38、 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0X(3) (4,2,0,0,4)T Q2點(diǎn)點(diǎn)X(2) (2,3,0,8,0)T Q3點(diǎn)點(diǎn)以以2為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x5為換入變量，為換入變量，x4為換出變?yōu)閾Q出變量量一、最小化問題最優(yōu)界判別一、最小化問題最優(yōu)界判別第四節(jié)第四節(jié) LP問題的進(jìn)一步討論問題的進(jìn)一步討論 前面討論的前面討論的LP問題都是以最大化目標(biāo)函數(shù)作為標(biāo)準(zhǔn)型的，問題都是以最大化目標(biāo)函數(shù)作為標(biāo)準(zhǔn)型的，但也有用最小化目標(biāo)函數(shù)作為但也有用最小化目標(biāo)函數(shù)作為LP問題標(biāo)準(zhǔn)型的構(gòu)成要素的情問題標(biāo)準(zhǔn)型的構(gòu)成要素的情況。二者

39、的區(qū)別如下：況。二者的區(qū)別如下：標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 比較條目比較條目 max Z=CX AX=b，X 0 min Z=CX AX=b，X 0最優(yōu)解的最優(yōu)解的 j 0 0 換入變量換入變量xkmax j| j 0min j| j 0換出變量換出變量xl按最小比值規(guī)則按最小比值規(guī)則 0.maxXbAXtsCXZ 0,. .maxSSXXbIXAXtsCXZ二、人工變量法二、人工變量法化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型 化標(biāo)準(zhǔn)型時，若找不到單位矩陣，可人為添加非負(fù)變化標(biāo)準(zhǔn)型時，若找不到單位矩陣，可人為添加非負(fù)變量人工變量湊成單位矩陣。量人工變量湊成單位矩陣。 因人工變量是虛擬的變量，無任何物理意義，它們的因人工變量是虛

40、擬的變量，無任何物理意義，它們的取值最終必須為零，才能保證約束方程不發(fā)生變化。取值最終必須為零，才能保證約束方程不發(fā)生變化。 為此，必須把人工變量從基變量中替換出去而變成非為此，必須把人工變量從基變量中替換出去而變成非基變量，則基變量，則LP問題有解；若最優(yōu)解中含有人工變量，則問題有解；若最優(yōu)解中含有人工變量，則LP問題無可行解。這是問題無可行解。這是LP問題無解的判別條件。問題無解的判別條件。 0,12324112.3min32131321321321xxxxxxxxxxxtsxxxZ例例： 7, 2 , 1; 012324112.00003min7316532143217654321jxx

41、xxxxxxxxxxxtsxxxxxxxZj加入松弛變量加入松弛變量x4;剩余變量剩余變量x5;人工人工變量變量x6,x7（1） 基本思路基本思路（2目標(biāo)函數(shù)的處理目標(biāo)函數(shù)的處理 iiiVMCXZVMVMCXZmin)(max為為人人工工變變量量，為為（3） 計算計算1. 大大M法法(M為任意大的正數(shù)為任意大的正數(shù)) 7, 2 , 1; 012324112.003min7316532143217654321jxxxxxxxxxxxxxtsxMxMxxxxxZjcj-31100MMCBXBbx1x2x3x4x5x6x70 x4111-21100011Mx63-4120-1103/2Mx71-20

42、100011-3+6M1-M1-3M0M000 x4103-20100-1-Mx610100-11-211x31-2010001-11-M00M03M-1i j j 結(jié)果得結(jié)果得: X*=(4,1,9,0,0) T Z*=-2cj-31100MMCBXBbx1x2x3x4x5x6x70 x4123001-22-541x210100-11-2-1x31-2010001-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3M-2/3j i j 即即認(rèn)認(rèn)為為達(dá)達(dá)到到了了最最優(yōu)優(yōu)解解。所所有有

43、檢檢驗(yàn)驗(yàn)數(shù)數(shù)此此時時,0, j（接上表）（接上表）將將LP問題分成兩個階段來考慮問題分成兩個階段來考慮 第第I 階段階段: 不考慮原問題是否存在可行解，給原不考慮原問題是否存在可行解，給原LP問題問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求最加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求最小化；然后用單純型法求解，若得小化；然后用單純型法求解，若得W=0，則進(jìn)行第二階段，則進(jìn)行第二階段計算，否則無可行解。計算，否則無可行解。 第第II 階段：將第一階段得到的最終表除去人工變量，將階段：將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問題的系數(shù)，作為第二階段的初目標(biāo)函數(shù)行的

44、系數(shù)換為原問題的系數(shù)，作為第二階段的初始表。始表。2. 兩階段法兩階段法 0,12324112.3min32131321321321xxxxxxxxxxxtsxxxZ例例：加入松弛變量加入松弛變量x4;剩余變量剩余變量x5;人工人工變量變量x6,x7 7, 2 , 1; 012324112.)(min73165321432176jxxxxxxxxxxxxxtsIxxWj用單純形法求解第一階段的結(jié)果得：用單純形法求解第一階段的結(jié)果得：cj0000011CBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-201000116-1-30100

45、0 x4103-20100-1-1x610100-11-210 x31-2010001-0-1001030 x4123001-22-540 x210100-11-2-0 x31-2010000-0000011i j j j 此時，達(dá)到第一階段的最優(yōu)解，此時，達(dá)到第一階段的最優(yōu)解，W=0cj-31100CBXBbx1x2x3x4x50 x4123001-241x210100-1-1x31-20100-10001-3x141001/3-2/31x210100-11x390012/3-4/30001/31/3i j 由于人工變量由于人工變量x6 =x7=0,所以所以0,1,1,12,0T是該線性規(guī)劃

46、問題的基可行解。于是轉(zhuǎn)入第二階段運(yùn)算：是該線性規(guī)劃問題的基可行解。于是轉(zhuǎn)入第二階段運(yùn)算：此時達(dá)到該此時達(dá)到該LP問題的最優(yōu)解：問題的最優(yōu)解： X*=(4,1,9,0,0) T; 目標(biāo)函數(shù)值目標(biāo)函數(shù)值Z*=-2。j 三、單純型法中存在的問題三、單純型法中存在的問題1. 存在兩個以上的最大正檢驗(yàn)數(shù)。選擇存在兩個以上的最大正檢驗(yàn)數(shù)。選擇任何變量對應(yīng)最大正檢驗(yàn)數(shù)作為換任何變量對應(yīng)最大正檢驗(yàn)數(shù)作為換入變量。入變量。2. 最小比值相同。最小比值相同。LP問題出現(xiàn)退化現(xiàn)象，即基變量取值為問題出現(xiàn)退化現(xiàn)象，即基變量取值為0 0,10321122109841.6212043max4321343214321432

47、1xxxxxxxxxxxxxtsxxxxZ例例： 7 , 2 , 1;010321122109841.0006212043max7364321543217654321jxxxxxxxxxxxxxtsxxxxxxxZjcj 3/4 -20 1/2 -6 0 0 0 CBXBbx1x2x3x4x5x6x70 x501/4-8-191000 x601/2-12-1/230100 x71001000103/4-201/2-6000j cj 3/4 -20 1/2 -6 0 0 0 CBXBbx1x2x3x4x5x6x73/4x101-32-4364000 x60043/2-150100 x710010

48、0010047/221-300j 選取選取x1為換入變量；按為換入變量；按Bland算法，算法，選取下標(biāo)最小的選取下標(biāo)最小的x5為換出變量，得下表：為換出變量，得下表：此時換出變量為此時換出變量為x1，換入變量為，換入變量為x4，迭代后，迭代后目標(biāo)函數(shù)值不變，繼而出現(xiàn)了循環(huán)現(xiàn)象，達(dá)目標(biāo)函數(shù)值不變，繼而出現(xiàn)了循環(huán)現(xiàn)象，達(dá)不到最優(yōu)解。不到最優(yōu)解。解決退化的方法有：解決退化的方法有：“攝動法攝動法”、“辭典序法辭典序法”、 Bland規(guī)則等規(guī)則等1974年年Bland提出提出Bland算法規(guī)則：算法規(guī)則：為為換換出出變變量量。選選取取下下標(biāo)標(biāo)最最小小的的基基變變量量個個以以上上的的最最小小比比值值時

49、時，規(guī)規(guī)則則計計算算存存在在兩兩個個和和兩兩當(dāng)當(dāng)按按）（量量。所所對對應(yīng)應(yīng)的的變變量量為為換換入入變變則則選選取取 2,0|min)1(kjjk 3. 最小比值原則失效最小比值原則失效問問題題有有無無界界解解。則則此此對對應(yīng)應(yīng)列列向向量量，而而存存在在某某問問題題迭迭代代到到某某步步時時，當(dāng)當(dāng)用用單單純純型型法法求求解解LP, 00LP kkka 4 , 3 , 2 , 1; 0432.32max42132121jxxxxxxxtsxxZj例例：cj2300CBXBbx1x2x3x40 x36-20113x24-3101cj-Zj-121100-3經(jīng)過一次迭代后可得右表經(jīng)過一次迭代后可得右表

50、ZZZmiabxxxaxZZZmixabxxkkikiijkikkjnmjjjnmjijiii 當(dāng)當(dāng)此此時時則則其其余余非非基基變變量量非非基基變變量量令令行行解解），即即新新的的可可行行解解（不不是是基基可可其其時時可可構(gòu)構(gòu)造造一一個個且且其其非非基基變變量量的的若若代代數(shù)數(shù)和和形形式式：也也可可表表示示成成非非基基變變量量的的目目標(biāo)標(biāo)函函數(shù)數(shù)數(shù)數(shù)和和形形式式：可可表表示示成成非非基基變變量量的的代代基基變變量量中中，一一般般情情況況下下，迭迭代代過過程程說說明明：0), 2 , 1(00, 0, 0, 0), 2 , 1(01014. 在最優(yōu)表中出現(xiàn)某在最優(yōu)表中出現(xiàn)某非基變量檢驗(yàn)數(shù)為非基變

51、量檢驗(yàn)數(shù)為0 0,36431228.43max21212121xxxxxxtsxxZ例：例：CBXBbx1x2x3x4x50 x340012/3-1/34x260101/203x14100-2/31/3cj-Zj-360000-10 x46003/21-1/24x2301-3/401/43x1810100cj-Zj-360000-1cj-Zj0340001 ,0;)1(*)2()1(* XXX)0 , 0 , 4 , 6 , 4(*)1( X)0 ,6 ,0 ,3 ,8(*)2( X結(jié)論：若線性規(guī)劃問題存在某非基變量檢驗(yàn)數(shù)為結(jié)論：若線性規(guī)劃問題存在某非基變量檢驗(yàn)數(shù)為0,而其對而其對應(yīng)列向量應(yīng)列

52、向量Pk0,仍可判斷線性規(guī)劃問題有無窮多最優(yōu)解。仍可判斷線性規(guī)劃問題有無窮多最優(yōu)解。式中的式中的X* 是否能全部由單純形法求得？是否能全部由單純形法求得？ 1 ,0;)1(*)2()1(* XXX 課堂作業(yè)課堂作業(yè)3 第五節(jié)第五節(jié) 應(yīng)用舉例應(yīng)用舉例應(yīng)用應(yīng)用1：下料問題書：下料問題書P38 例例10） 現(xiàn)要做現(xiàn)要做100套鋼架，每套需套鋼架，每套需2.9米、米、2.1米米和和1.5米的圓鋼各一根。已知原料長米的圓鋼各一根。已知原料長7.4米，米，問如何下料，使用的原料最少余料最少或問如何下料，使用的原料最少余料最少或根數(shù)最少）？根數(shù)最少）？分析：分析： 最簡單的做法是：每根最簡單的做法是：每根7

53、.4米長的原材料各截取三種規(guī)格米長的原材料各截取三種規(guī)格的元鋼一根，則料頭為的元鋼一根，則料頭為0.9米，米，100套則浪費(fèi)材料套則浪費(fèi)材料90米。關(guān)鍵是米。關(guān)鍵是要設(shè)計套裁方案，不能有遺漏。要設(shè)計套裁方案，不能有遺漏。解：設(shè)解：設(shè) x1, x2 , x3, x4 , x5分別代表五種不同的原料用量方案。分別代表五種不同的原料用量方案。方案方案2.9米米2.1米米1.5米米合計合計余料余料x11037.40 x22017.30.1x30227.20.2x41207.10.3x50136.60.8 0,100)(323100)(22100)(2.8 . 03 . 02 . 01 . 00:543

54、21532154342154321xxxxxxxxxxxxxxxtsxxxxxMinZOBJ余料最少的余料最少的LP模型：模型：根數(shù)最少的根數(shù)最少的LP模型：模型：料頭最省料頭最省根數(shù)最少根數(shù)最少= =解解1：x1=30，x2=10， x4=50； 料頭料頭Z=16，根數(shù)，根數(shù)90。與解與解1相同相同解解2: x1=100，x3=50； 料頭料頭Z=10，根數(shù)，根數(shù)150。與解與解1相同相同 0,100)(323100)(22100)(2.:54321532154342154321xxxxxxxxxxxxxxxtsxxxxxMinZOBJ應(yīng)用應(yīng)用2：配料問題書：配料問題書P38 例例11） 某

55、工廠要用三種原材料某工廠要用三種原材料C、P、H混合調(diào)混合調(diào)配出三種不同規(guī)格的產(chǎn)品配出三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)。已知產(chǎn)品的規(guī)格要求、單價和原材料的供應(yīng)量、單品的規(guī)格要求、單價和原材料的供應(yīng)量、單價。該廠應(yīng)如何安排生產(chǎn)使利潤最大？價。該廠應(yīng)如何安排生產(chǎn)使利潤最大？產(chǎn)品名稱產(chǎn)品名稱規(guī)格要求規(guī)格要求單價單價(元元/kg）A原材料原材料C不少于不少于50%原材料原材料P不超過不超過25%50B原材料原材料C不少于不少于25%原材料原材料P不超過不超過50%35D不限不限25原材料名稱原材料名稱每天最多供每天最多供應(yīng)量應(yīng)量(kg)單價單價(元元/kg)C10065P10025H6035限限量

56、量、含含量量、變變量量約約束束條條件件有有三三類類：原原料料、的的含含量量為為、中中、的的含含量量為為、中中、的的含含量量為為、中中設(shè)設(shè)333231232221131211xxxHPCDxxxHPCBxxxHPCA解：根據(jù)題意，可將問題簡化成如下表格形式：解：根據(jù)題意，可將問題簡化成如下表格形式：產(chǎn)品名稱產(chǎn)品名稱原料原料規(guī)格要求規(guī)格要求/決策變量決策變量原料限量原料限量(kg）單價單價(元元/kg）ABDC 50%/x11 25%/x21/ x3110065P 25%/ x12 50%/ x22/ x3210025H/ x13/ x23/ x336035產(chǎn)品單價產(chǎn)品單價(元元/kg）50352

57、5 用單純型法計算得結(jié)果：每天只生產(chǎn)用單純型法計算得結(jié)果：每天只生產(chǎn)A產(chǎn)品產(chǎn)品200kg。分別需要原料：分別需要原料：C為為100kg；P為為50kg；H為為50kg。 總利潤收入總利潤收入Z=500元元/天天.3 , 2 , 1,; 0%50%5060%25100%25100.13121111232221223323132322212132221213121113312111 jixxxxxxxxxxxxxxxxxxxxxxxxxxtsij3332312322211312113323133222123121113332312322211312111004001030152515)(35)(2

58、5)(65)(25)(35)(50 xxxxxxxxxxxxxxxxxxxxxxxxxxxMaxZ 例例1：某企業(yè)擬用：某企業(yè)擬用m種資源種資源(i=1,2,m)生產(chǎn)生產(chǎn)n種產(chǎn)品種產(chǎn)品(j=1,2,n) 。已知第。已知第i種資源的數(shù)量種資源的數(shù)量為為bi，其單價為，其單價為Pi；第；第j種單位產(chǎn)品的產(chǎn)值為種單位產(chǎn)品的產(chǎn)值為Vj，消耗第，消耗第i種資源的數(shù)量為種資源的數(shù)量為aij，合同量為，合同量為ej，最高需求為最高需求為dj。問企業(yè)應(yīng)如何擬定生產(chǎn)計劃？。問企業(yè)應(yīng)如何擬定生產(chǎn)計劃？解：根據(jù)題意，設(shè)解：根據(jù)題意，設(shè)xj (j=1,2,n)為第為第j種產(chǎn)品的生產(chǎn)量。種產(chǎn)品的生產(chǎn)量。應(yīng)用應(yīng)用3：生產(chǎn)

59、計劃問題：生產(chǎn)計劃問題 njijijjjjjnjjjnjjmiijijnjjijmiinjjjmibxanjdxnjextsxcxaPVxaPxVZZZ111111121),2,1(),2,1(),2,1(.)(max例例2 （書（書P41 例例12）市場要求：市場要求： 1) 產(chǎn)品數(shù)量和品種；產(chǎn)品數(shù)量和品種； 2) 產(chǎn)品交貨期不同。產(chǎn)品交貨期不同。生產(chǎn)要求：生產(chǎn)要求： 1) 設(shè)備均衡且滿負(fù)荷生產(chǎn)；設(shè)備均衡且滿負(fù)荷生產(chǎn)； 2) 生產(chǎn)技術(shù)準(zhǔn)備需要時間。生產(chǎn)技術(shù)準(zhǔn)備需要時間。底底前前完完成成全全年年計計劃劃。種種產(chǎn)產(chǎn)品品要要求求二二月月第第兩兩種種產(chǎn)產(chǎn)品品下下半半年年投投產(chǎn)產(chǎn)，、假假設(shè)設(shè)第第種種產(chǎn)

60、產(chǎn)品品的的數(shù)數(shù)量量月月內(nèi)內(nèi)計計劃劃生生產(chǎn)產(chǎn)表表示示；臺臺時時類類設(shè)設(shè)備備的的生生產(chǎn)產(chǎn)能能力力月月內(nèi)內(nèi)第第表表示示類類設(shè)設(shè)備備的的臺臺時時數(shù)數(shù)類類產(chǎn)產(chǎn)品品需需要要的的第第表表示示加加工工單單位位類類產(chǎn)產(chǎn)品品全全年年的的計計劃劃量量表表示示第第種種產(chǎn)產(chǎn)品品表表示示工工廠廠生生產(chǎn)產(chǎn)的的第第類類設(shè)設(shè)備備表表示示工工廠廠的的第第設(shè)設(shè)：48512, 2 , 1)(), 2 , 1(), 2 , 1(jkxkikbijajdnjjjmiiijkikijj 種種產(chǎn)產(chǎn)品品全全年年的的產(chǎn)產(chǎn)量量為為第第一一月月份份：jdxnjdxmibxaxxtsbxaZjjjjinjjijmiiminjjij;0);, 2 ,