線性規(guī)劃和單純形方法

1、關(guān)于線性規(guī)劃與單純形方法1第一張，PPT共一百二十九頁，創(chuàng)作于2022年6月2第一節(jié) 線性規(guī)劃問題及數(shù)學(xué)模型一、實例二、線性規(guī)劃問題（LP問題）的共同特征三、兩變量線性規(guī)劃問題的圖解法四、線性規(guī)劃問題的標(biāo)準(zhǔn)型五、標(biāo)準(zhǔn)型LP問題解的概念六、可行解、基解和基可行解舉例第二張，PPT共一百二十九頁，創(chuàng)作于2022年6月3一、實例例1 生產(chǎn)計劃問題(書P8)Step 1:明確問題，設(shè)定決策變量 設(shè)I、II兩種產(chǎn)品的產(chǎn)量分別為x1, x2 。Step 2: 確定約束條件產(chǎn)品 I II資源限量設(shè)備 1 2 8臺時原料A 4 0 16公斤原料B 0 4 12公斤 利潤 2 3問應(yīng)如何安排生產(chǎn)使該廠獲利最多？

2、第三張，PPT共一百二十九頁，創(chuàng)作于2022年6月4說明：OBJ 表示Objective; s.t. 表示Subject to Step 3: 給出目標(biāo)函數(shù)Step 4: 整理數(shù)學(xué)模型第四張，PPT共一百二十九頁，創(chuàng)作于2022年6月5例2 下料問題 現(xiàn)要做100套鋼架，每套需2.9米、2.1米和1.5米的圓鋼各一根。已知原料長7.4米，問如何下料，使用的原料最少（余料最少或根數(shù)最少）？分析： 最簡單的做法是：每根7.4米長的原材料各截取三種規(guī)格的元鋼一根，則料頭為0.9米，100套則浪費材料90米。關(guān)鍵是要設(shè)計套裁方案，不能有遺漏。第五張，PPT共一百二十九頁，創(chuàng)作于2022年6月6解：設(shè)

3、x1, x2 , x3, x4 , x5分別代表五種不同的原料用量方案。0.86.6310 x50.37.1021x40.27.2220 x30.17.3102x207.4301x1余料合計1.5米2.1米2.9米方案余料最少的LP模型：第六張，PPT共一百二十九頁，創(chuàng)作于2022年6月7根數(shù)最少的LP模型：料頭最省根數(shù)最少解1: x1=30, x2=10, x4=50; 料頭Z=16, 根數(shù)90?？梢宰?00套鋼架，無圓鋼剩余。與解1相同解2: x1=100, x3=50; 料頭Z=10, 根數(shù)150?？梢宰?00套鋼架, 但余1.5m圓鋼300根。與解1相同第七張，PPT共一百二十九頁，創(chuàng)

4、作于2022年6月8LP是數(shù)學(xué)規(guī)劃的一個重要分支，數(shù)學(xué)規(guī)劃著重解決資源的優(yōu)化配置，一般可以表達(dá)成以下兩個問題中的一個：（1）當(dāng)資源給定時，要求完成的任務(wù)最多；（2）當(dāng)任務(wù)給定時，要求為完成任務(wù)所消耗的資源最少。 若上述問題的目標(biāo)約束都能表達(dá)成變量的線性關(guān)系，則這類優(yōu)化問題稱LP問題。 LP是一種解決在線性約束條件下追求最大或最小的線性目標(biāo)函數(shù)的方法。第八張，PPT共一百二十九頁，創(chuàng)作于2022年6月9 目標(biāo)函數(shù)用決策變量的線性函數(shù)來表示。按問題的不同，要求目標(biāo)函數(shù)實現(xiàn)最大化和最小化。 每一個問題變量都用一組決策變量（x1, x2, , xn）表示某一方案，這組決策變量的值代表一個具體方案，這些

5、變量是非負(fù)且連續(xù)的。 存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。結(jié)論：線性規(guī)劃是研究在一組線性不等式或線性等式約束下，使得某一線性目標(biāo)函數(shù)取最大或最小的極值問題。二、線性規(guī)劃問題（LP問題）的共同特征第九張，PPT共一百二十九頁，創(chuàng)作于2022年6月10Max(Min) Z=c1x1+c2x2+cnxn (1) a11x1+a12x2+a1nxn ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. (2) am1x1+am2x2+amnxn ( =, ) bm xj0, j=1,2, ，n (3)(1)目標(biāo)函數(shù)；(2)約束條件；(3

6、)決策變量非負(fù)n變量個數(shù)； m約束行數(shù)； cj價值系數(shù)；bi右端項或限額系數(shù)； aij技術(shù)系數(shù)；xj決策變量線性規(guī)劃模型的一般形式為：第十張，PPT共一百二十九頁，創(chuàng)作于2022年6月11線性規(guī)劃模型的緊縮形式n變量個數(shù)； m約束行數(shù)； cj價值系數(shù)；bi右端項或限額系數(shù)； aij技術(shù)系數(shù)；xj決策變量第十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月12練習(xí)題：是否為線性規(guī)劃模型？第十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月131.線性不等式的幾何意義 半平面作出LP問題的可行域作出目標(biāo)函數(shù)的等值線移動等值線到可行域邊界得到最優(yōu)點2.圖解法步驟三、兩變量線性規(guī)劃問題的圖解法第十三張

7、，PPT共一百二十九頁，創(chuàng)作于2022年6月144x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30例3 （書P8）：Q2(4,2)Z=2x1+3x2 做目標(biāo)函數(shù)2x1+3x2的等值線，與陰影部分的邊界相交于Q2(4,2)點，表明最優(yōu)生產(chǎn)計劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。Q3第十四張，PPT共一百二十九頁，創(chuàng)作于2022年6月15目標(biāo)函數(shù)z=ax1+bx2的值遞增的方向與系數(shù)a、b有關(guān)a0, b0a0X1X2a0, b0, b0z=ax1+bx2目標(biāo)函數(shù)等值線：ax1+bx2=k移項x2=-a/bx1+k/b目標(biāo)函數(shù)等值線在縱軸上的截距為k/b第十五張，PPT共一百二

8、十九頁，創(chuàng)作于2022年6月16例4Z=36第十六張，PPT共一百二十九頁，創(chuàng)作于2022年6月17例 用圖解法求解線性規(guī)劃問題4x1=164x2=12x1+2x2=8x1x248Q1 4 Q4 30Q2(4,2)Z=2x1+4x2當(dāng)Z值由小變大時，將與Q2Q3重合Q2Q3上任意一點都是最優(yōu)解有無窮多最優(yōu)解（多重解）Q3(2,3)第十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月18例 用圖解法求解線性規(guī)劃問題可行域無界無界解（ “無有限最優(yōu)解”或“最優(yōu)解無界”）約束條件過分寬松x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00可行域無解（不閉合）一定就會出現(xiàn)無界解嗎？第十八

9、張，PPT共一百二十九頁，創(chuàng)作于2022年6月19例 用圖解法求解線性規(guī)劃問題可行域無界唯一最優(yōu)解X*=(1,0)，對應(yīng)于點Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00第十九張，PPT共一百二十九頁，創(chuàng)作于2022年6月20例 用圖解法求解線性規(guī)劃問題可行域無界無窮多最優(yōu)解對應(yīng)于點B沿著OB向右上方發(fā)出的射線上的所有點x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00第二十張，PPT共一百二十九頁，創(chuàng)作于2022年6月21例（書P11）： 無可行解（可行域為空）x14x1=164x2=12x1+2x2=8x248Q1 4Q4 30-2-2x1+x2=4

10、無最優(yōu)解第二十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月223.圖解法的作用 能解決少量問題 揭示了線性規(guī)劃問題的若干規(guī)律解的類型可行域類型唯一最優(yōu)解無窮多最優(yōu)解最優(yōu)解無界（無有限最優(yōu)解）無解（不存在可行域）非空有界無界空集規(guī)律1：第二十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月23規(guī)律2：線性規(guī)劃問題的可行域為凸集線性規(guī)劃問題凸集的頂點個數(shù)是有限的最優(yōu)解可在凸集的某頂點處達(dá)到 第二十三張，PPT共一百二十九頁，創(chuàng)作于2022年6月24 小結(jié)：圖解法的基本步驟：1在直角坐標(biāo)系作出可行域S的區(qū)域（一般是一個凸多邊形）2令目標(biāo)函數(shù)值取一個已知的常數(shù)k，作等值線：c1x1+c2x2=k3

11、對于max問題，讓目標(biāo)函數(shù)值k由小變大，即讓等值線進(jìn)行平移，若它與可行域S最后交于一個點（一般是S的一個頂點），則該點就是所求的最優(yōu)點，若與S的一條邊界重合，此時邊界線上的點均是最優(yōu)點4將最優(yōu)點所在的兩條邊界線所代表的方程聯(lián)立求解，即得最優(yōu)解X*，把最優(yōu)解X*帶入目標(biāo)函數(shù)，得最優(yōu)值Z*=CX*注意：若是求目標(biāo)函數(shù)最小值，等值線向反方向移動第二十四張，PPT共一百二十九頁，創(chuàng)作于2022年6月25四、線性規(guī)劃問題的標(biāo)準(zhǔn)型1.標(biāo)準(zhǔn)型 （1）目標(biāo)函數(shù)：max（2）約束條件：等式（3）變量約束：非負(fù) xj0（4）資源限量：非負(fù)bi 0標(biāo)準(zhǔn)型的構(gòu)成要素第二十五張，PPT共一百二十九頁，創(chuàng)作于2022年6

12、月262.線性規(guī)劃標(biāo)準(zhǔn)型的緊縮形式第二十六張，PPT共一百二十九頁，創(chuàng)作于2022年6月273.線性規(guī)劃標(biāo)準(zhǔn)型的向量和矩陣表達(dá)式矩陣式: Max Z=CTX s.t. AX=b X0 n向量式: Max Z= cjxj j=1 n s.t. Pjxj=b j=1 xj 0, j=1,2, . ,n第二十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月284.所有LP問題均可化為標(biāo)準(zhǔn)型（1）最小轉(zhuǎn)換成最大y1=f(x)y2=-f(x)xyx*y1*y2*第二十八張，PPT共一百二十九頁，創(chuàng)作于2022年6月29（2）不等式約束條件轉(zhuǎn)換成等式約束條件（3）變量約束轉(zhuǎn)換（4）把bi0轉(zhuǎn)換成bi0第二

13、十九張，PPT共一百二十九頁，創(chuàng)作于2022年6月30例5 化標(biāo)準(zhǔn)型可化為1.處理決策變量2.處理目標(biāo)函數(shù)3.約束條件不等式4.處理約束條件右端 常數(shù)項第三十張，PPT共一百二十九頁，創(chuàng)作于2022年6月31例6 化標(biāo)準(zhǔn)型1.處理決策變量2.處理目標(biāo)函數(shù)3.約束條件不等式4.處理約束條件右端 常數(shù)項第三十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月32Max Z =x1+2x2+3x4-3x5+0 x6+0 x7 s.t. x1 - x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j

14、=1,4,5,6,7Max Z =x1+2x2+3(x4-x5)+0 x6+0 x7 s.t. x1 - x2 +(x4 - x5 ) +x6 = 7 x1+x2 +(x4 - x5 ) - x7 = 2 -3x1 -x2+3(x4 -x5) = 5 x20 , xj0, j=1,4,5,6,7最終結(jié)果中間結(jié)果第三十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月33課堂練習(xí)第三十三張，PPT共一百二十九頁，創(chuàng)作于2022年6月34五、標(biāo)準(zhǔn)型LP問題解的概念第三十四張，PPT共一百二十九頁，創(chuàng)作于2022年6月35（1）（2）（3）約束系數(shù)矩陣：x1x2x3x4x5例：第三十五張，PPT共一百

15、二十九頁，創(chuàng)作于2022年6月36約束系數(shù)矩陣：可能的基矩陣是A中任意三個列的組合，共10個。第三十六張，PPT共一百二十九頁，創(chuàng)作于2022年6月37令B = =( P1 , P2 , , Pm ) 且| B | 0 ，則稱Pj (j=1,2,m) 為基向量。與基向量Pj對應(yīng)的變量xj稱為基變量，記為XB = ( x1 , x2 , , xm )T，其余的變量稱為非基變量，記為XN = ( xm+1 , xm+2 , , xn ) T 。第三十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月38第三十八張，PPT共一百二十九頁，創(chuàng)作于2022年6月39第三十九張，PPT共一百二十九頁，創(chuàng)作于

16、2022年6月40B1=(P1,P2)：基令：XB1=(x1,x2)x1=0， x2=2X=(0, 2, 0, 0)XB1=(0, 2)對應(yīng)于B1的基解為也是基可行解第四十張，PPT共一百二十九頁，創(chuàng)作于2022年6月41線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解第四十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月42例7 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0六、可行解、基解和基可行解舉例非基變量基變量圖中的點x4, x5x1=4x2=3x3= -2A基解x3, x5x1=2x2=3x4=8B基可行解

17、x3, x4x1=4x2=2x5=4C基可行解，最優(yōu)解x2, x4x1=4x3=4x5=12D基可行解x2, x3x1=8x4= -16x5=12E基解x1, x5x2=3x3=2x4=16F基可行解x1, x3x2=4x4=16x5= -4G基解x1, x2x3=8x4=16x5=12H基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH標(biāo)準(zhǔn)型第四十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月43例8第四十三張，PPT共一百二十九頁，創(chuàng)作于2022年6月44LP標(biāo)準(zhǔn)型問題解的結(jié)論 根據(jù)LP的圖解法及解的基本概念可知：基解對應(yīng)約束條件的交點；基可行解

18、對應(yīng)可行域的頂點某個基可行解一定是最優(yōu)解，即一定在可行域的頂點上得到最優(yōu)解。第四十四張，PPT共一百二十九頁，創(chuàng)作于2022年6月45第二節(jié) LP問題的基本理論一、基本概念第四十五張，PPT共一百二十九頁，創(chuàng)作于2022年6月46判斷以下圖形哪些是凸集，哪些不是凸集？判斷下列集合是否凸集？第四十六張，PPT共一百二十九頁，創(chuàng)作于2022年6月47定理1 LP問題的可行域為一凸集。 二、基本定理第四十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月48引理 線性規(guī)劃問題的可行解X=(x1, x2, , xn)T是基可行解的充要條件為X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。第四十八張，PPT共一

19、百二十九頁，創(chuàng)作于2022年6月49定理2 線性規(guī)劃問題的基可行解對應(yīng)于可行域的頂點。（即：若X是LP問題的可行解，則“X是LP問題的基可行解”等價于“X是LP問題可行域頂點”）因為X是基可行解，則其對應(yīng)的向量組a1,a2, ,am線性無關(guān)(mm時，有xj=xj(1)= xj(2)= 0.第四十九張，PPT共一百二十九頁，創(chuàng)作于2022年6月50第五十張，PPT共一百二十九頁，創(chuàng)作于2022年6月51第五十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月52第五十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月53定理3 若可行域有界，則LP問題的目標(biāo)函數(shù)一定可以在其可行域的頂點上達(dá)到最優(yōu)。引

20、理 若S是有界凸集，則任何一點XS可表示為S的頂點的凸組合。第五十三張，PPT共一百二十九頁，創(chuàng)作于2022年6月54 線性規(guī)劃問題的可行域是凸集(定理1)；凸集的頂點對應(yīng)于基可行解(定理2)，基可行解(頂點)的個數(shù)是有限的；若線性規(guī)劃有最優(yōu)解，必在可行域某頂點上達(dá)到(定理3)。因此,我們可以在有限個基可行解中尋找最優(yōu)解。 由線性代數(shù)知，對標(biāo)準(zhǔn)形LP問題，用枚舉法可以求出所有基解，再通過觀察找出其中的可行解（基可行解），進(jìn)而找出最優(yōu)解。但如果變量和方程較多，比如m=50，n=100，所有基解有可能達(dá)1029個，即使計算機每秒能求解1億個這樣的方程組，也需要30萬億年！因此，必須尋求有效的算法。

21、 為加快計算速度，算法必須具有兩個功能，一是每得到一個解，就來檢驗是否已經(jīng)最優(yōu)，若是停止。二是若不是最優(yōu)，要保證下一步得到的解不劣于當(dāng)前解。這就是線性規(guī)劃的單純形法。 第五十四張，PPT共一百二十九頁，創(chuàng)作于2022年6月55第三節(jié) 單純形法一、基本思想檢驗解的最優(yōu)性結(jié)束Y樞軸運算（旋轉(zhuǎn)運算）確定另一個基本可行解N化LP問題為標(biāo)準(zhǔn)型，確定一個初始基本可行解 化LP問題為標(biāo)準(zhǔn)型，從可行域的某個基可行解（一個頂點）開始，轉(zhuǎn)換到另一個基可行解（另一個頂點），并使目標(biāo)函數(shù)值得到改善，如此反復(fù)，從而求得問題的最優(yōu)解。其實質(zhì)是逐步迭代（逼近）法。第五十五張，PPT共一百二十九頁，創(chuàng)作于2022年6月56單

22、純形法舉例（P20）化為標(biāo)準(zhǔn)型二、基本原理舉例第五十六張，PPT共一百二十九頁，創(chuàng)作于2022年6月571. 初始基可行解的確定要得到一個初始基可行解，必須找到一個初始可行基。由于典型示例標(biāo)準(zhǔn)化后，x3、x4、x5的系數(shù)列向量構(gòu)成單位矩陣，該矩陣B0是一個基，并且是一個可行基（可以證明，標(biāo)準(zhǔn)化后的單位矩陣一定是可行基）。第五十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月58 令非基變量x10、x2 0，得到基可行解及相應(yīng)的目標(biāo)函數(shù)值，X(0) (0,0,8,16,12)T， Z(0) 0。結(jié)論： （1）在標(biāo)準(zhǔn)化的LP問題的約束系數(shù)矩陣中，只要存在單位矩陣，就可求得初始基可行解； （2）基變

23、量確定后，目標(biāo)函數(shù)和基變量均可表示成非基變量的代數(shù)和形式（如(6)和(5)），從而便于求出基可行解及相應(yīng)的目標(biāo)函數(shù)值。第五十八張，PPT共一百二十九頁，創(chuàng)作于2022年6月592. 最優(yōu)性檢驗 考察變換后的目標(biāo)函數(shù)(6)式，非基變量x1、x2的系數(shù)都為正數(shù)，若讓x1、x2取正值，則目標(biāo)函數(shù)值會增大。因此，應(yīng)將非基變量x1、x2變換成基變量。結(jié)論： 在非基變量的代數(shù)和形式表示的目標(biāo)函數(shù)中，若非基變量的系數(shù)（稱為檢驗數(shù)）為正，則目標(biāo)函數(shù)值還有增加的可能，表明當(dāng)前的基可行解不是最優(yōu)解。第五十九張，PPT共一百二十九頁，創(chuàng)作于2022年6月60 當(dāng)確定x2為換入變量后， x1還是非基變量，故 x10。

24、現(xiàn)在要保證x3、x4、x50，即(5)當(dāng) x2 min（8/2，12/4） =3 （最小比值規(guī)則）可保證 x5 =0則x5為換出變量。新的基變量為x3、x4、x2 ，新的可行基為B1(P3, P4 , P2)確定換入變量：一般選擇正系數(shù)最大的非基變量為換入變量。確定換出變量：（a）保證換出的變量取值為0，變成非基量；（b）其它的變量取值為非負(fù)。3. 確定新的基可行解（基變換）第六十張，PPT共一百二十九頁，創(chuàng)作于2022年6月614. 旋轉(zhuǎn)迭代 基變量確定后，旋轉(zhuǎn)迭代就是把目標(biāo)函數(shù)和基變量均表示成非基變量x1、x5的代數(shù)和形式。可用高斯消去法實現(xiàn)。 令非基變量x10、x5 0，得到新的基可行解

25、及相應(yīng)的目標(biāo)函數(shù)值，X(1) (0,3,2,16,0)T， Z(1) 9。返回至第二步，直至求出最優(yōu)解。第六十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月62這時目標(biāo)函數(shù)的表達(dá)式是z=141.5x30.125x4，當(dāng)將x1定為換入變量后，繼續(xù)利用上述方法確定換出變量，繼續(xù)迭代，再得到一個基可行解X(2)=(2,3,0,8,0)T，這時目標(biāo)函數(shù)的表達(dá)式是z=132x3+1/4x5，再經(jīng)過一次迭代，再得到一個基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30Q2 (4,2)Z=2x1+3x2 Q3 將上述方程組求解過程，用列表形式表

26、達(dá)，即為線性規(guī)劃單純形表。第六十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月63以x2為主元素以x1為主元素例 2x1+ x2+ 2x3=10 (1) 3x1+ 3x2+ x3= 6 (2) x1+ 1/2x2+ x3= 5 (1)0 x1+ 3/2x2-2x3= -9 (2)(2)-(1)3/2, (1)/2 x1+ 0 x2+ 5/3x3= 80 x1+ x2 - 4/3x3= -6(1)-(2) /3, (2) 2/3三、旋轉(zhuǎn)運算結(jié)論：旋轉(zhuǎn)運算就是矩陣的初等變換，是高斯消元第六十三張，PPT共一百二十九頁，創(chuàng)作于2022年6月64結(jié)論：如果LP問題通過單純形法迭代到某步時，所有檢驗數(shù)

27、0,則該LP問題已得到最優(yōu)解。Max Z=CXs.t. AX=b X0若cj-CBB-1Pj=j0, 則ZZ0, Z0即為最優(yōu)解. (基變量的檢驗數(shù)必為0)令A(yù)=(B,N), X= XB ,C=(CB,CN) XN由AX=b (B,N) XB =b BXB+NXN=b B-1BXB+B-1NXN=B-1b XN XB=B-1bB-1NXN (2)將(2)式代入目標(biāo)函數(shù)得Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN)+CNXN XN = CBB-1b+(CN-CBB-1N)XN = Z0 + (cj-CBB-1Pj)xj xj為非基變量 四、檢驗數(shù)公

28、式第六十四張，PPT共一百二十九頁，創(chuàng)作于2022年6月65對于線性規(guī)劃問題：Max Z=CTX AX=b，X0，可用如下三個判別定理來判別線性規(guī)劃問題是否已經(jīng)獲得最優(yōu)解或為無界解。判別定理1 設(shè)X為線性規(guī)劃的一個基可行解，且對于一切jJ（J為非基變量的下標(biāo)集）有j0，則X為線性規(guī)劃的最優(yōu)解。判別定理2 設(shè)X為線性規(guī)劃的一個基可行解，且對于一切jJ（J為非基變量的下標(biāo)集）有j 0，同時有某個非基變量的檢驗數(shù)k=0( kJ)，則該線性規(guī)劃有無窮多最優(yōu)解；設(shè)X為線性規(guī)劃的一個基可行解，且對于一切jJ（J為非基變量的下標(biāo)集）有j 0，則該線性規(guī)劃有唯一最優(yōu)解。判別定理3 設(shè)X為線性規(guī)劃的一個基可行解

29、，若有k0 ( kJ) ，且pk0，即aik 0（i=1,m），則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。第六十五張，PPT共一百二十九頁，創(chuàng)作于2022年6月66一、步驟Step 1. 化LP問題為標(biāo)準(zhǔn)型,建立初始單純形表;Step 2. 若所有檢驗數(shù)0,則最優(yōu)解已達(dá)到。 否則,計算 , 選取k 所對應(yīng)的變量xk 為進(jìn)基變量;Step 3. 計算 ,選取l 所對應(yīng)的變量xl 為出基變量;Step 4. 以alk為主元素進(jìn)行旋轉(zhuǎn)運算,轉(zhuǎn)Step 2;第四節(jié) 單純形法的步驟第六十六張，PPT共一百二十九頁，創(chuàng)作于2022年6月67cj CB XB b x1 x2 xm xm+1 xn j 基可行解

30、： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 01.初始單純形表c1 c2 cm cm+1 cnc1 x1 c2 x2 cm xmb1 b2 bm1 0 0 a1, m+1 a1n0 1 0 a2, m+1 a2n 0 0 1 am, m+1 amn0 0 0 m+1 n-CBTB-1b第六十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月68對于上述單純形表：（1）一個基對應(yīng)一個單純形表，且單純形表中必須有一個初始單位基。（2）從單純形表中，可立即得到一個基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0（3）

31、用檢驗數(shù)的計算公式很容易計算檢驗數(shù)，并可根據(jù)三個判別定理判別上述基可行解是否為最優(yōu)解或線性規(guī)劃問題無最優(yōu)解。第六十八張，PPT共一百二十九頁，創(chuàng)作于2022年6月692.進(jìn)基變量的選擇cj c1 c2 cm cm+1 ck cn CB XB b x1 x2 xm xm+1 xk xn c1 x1 c2 x2 cm xmb1 b2 bm 1 0 0 a1, m+1 a1k a1n 0 1 0 a2, m+1 a2k a2n 0 0 1 am, m+1 amk amnj -CBTB-1b 0 0 0 m+1 k n選取 所對應(yīng)的變量xk 為進(jìn)基變量。第六十九張，PPT共一百二十九頁，創(chuàng)作于2022

32、年6月703.出基變量的選擇cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn c1 x1 cl xl cm xmb1 bl bm 1 0 0 a1, m+1 a1k a1n 0 1 0 al, m+1 alk aln 0 0 1 am, m+1 amk amn1lmj -CBTB-1b 0 0 0 m+1 k n選取 所對應(yīng)的變量xl 為出基變量。第七十張，PPT共一百二十九頁，創(chuàng)作于2022年6月714.旋轉(zhuǎn)運算cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn c1 x1 cl xl cm

33、 xmb1 bl bm 1 0 0 a1,m+1 a1k a1n 0 1 0 al,m+1 alk aln 0 0 1 am,m+1 amk amnj ck xkbl /alk0 1/alk 0 al, m+1/alk1 aln/alk b11 -a1k/alk 0 a1, m+1 0 a1nbm0 -amk/alk1 am, m+1 0 amn第七十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月72二、實例化為標(biāo)準(zhǔn)型第七十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月73單純型表算法 X(0) (0,0,8,16,12)T以1為主元素進(jìn)行旋轉(zhuǎn)運算，x1為換入變量， x3為換出變量 0 q

34、i 3 0 0 x5 x2 x3 x40 x4 x3XB b sj 0 x1CB 2 cj 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)運算，x2為換入變量，x5為換出變量 sj 2 3 0 0 0 qi 8/2 12/44 x2 3主元列主元行 0 0 0 1/43 1 4 0 1 016 0 0 1 1 0 -1/22X(1) (0,3,2,16,0)T 2 0 0 -3/4 016/4 2/1 1第七十三張，PPT共一百二十九頁，創(chuàng)作于202

35、2年6月74此時達(dá)到最優(yōu)解。X*=(4,2), max Z=14。 0 qi 3 0 0 x5 x2 x3 x40 x4 x23 XB b sj x1CB 2 cj 0 qi 3 0 0 x5 x2 x3 x4x23 x1XB b sj 2 x1CB 2 cj 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 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)TX(2) (2,3,0,8,0)T以2為主元素進(jìn)行旋轉(zhuǎn)運算

36、，x5為換入變量，x4為換出變量第七十四張，PPT共一百二十九頁，創(chuàng)作于2022年6月754x1=164x2=12x1+2x2=8x1x2484O三、單純形表與圖解法的對應(yīng)關(guān)系X1=(0,0)T, Z1=0X2=(0,3)T, Z2=9X3=(2,3)T, Z3=13X4=(4,2)T, Z4=14Q1Q2QQ3基可行解 基可行解 迭代 頂點 相鄰的頂點迭代 圖解法：單純形表算法：第七十五張，PPT共一百二十九頁，創(chuàng)作于2022年6月76對于極小化問題，其最優(yōu)解的判定定理和進(jìn)基變量的選取和極大化問題剛好相反，如下所示：判別定理1 設(shè)X為線性規(guī)劃的一個基可行解，且對于一切jJ（J為非基變量的下標(biāo)

37、集）有j0，則X為線性規(guī)劃的最優(yōu)解。判別定理2 設(shè)X為線性規(guī)劃的一個基可行解，且對于一切jJ（J為非基變量的下標(biāo)集）有j0，同時有某個非基變量的檢驗數(shù)k=0( kJ)，則該線性規(guī)劃有無窮多最優(yōu)解；設(shè)X為線性規(guī)劃的一個基可行解，且對于一切jJ（J為非基變量的下標(biāo)集）有j 0，則該線性規(guī)劃有唯一最優(yōu)解。判別定理3 設(shè)X為線性規(guī)劃的一個基可行解，若有k0 ( kJ) ，且pk0，即aik 0（i=1,m），則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。在進(jìn)基可行解的轉(zhuǎn)換過程中，進(jìn)基變量的選取原則是：minj |j 0, 而k對應(yīng)列向量Pk0, 則此LP問題有無界解.第九十六張，PPT共一百二十九頁，創(chuàng)作于

38、2022年6月974.在最優(yōu)表中出現(xiàn)某非基變量檢驗數(shù)為0（無窮多最優(yōu)解）第九十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月98CBXBbx1x2x3x4x50 x340012/3-1/34x260101/203x14100-2/31/3cj -Zj-360000-10 x46003/21-1/24x2301-3/401/43x1810100cj -Zj-360000-1cj034000結(jié)論：若線性規(guī)劃問題存在某非基變量檢驗數(shù)為0,而其對應(yīng)列向量Pk0,仍可判斷線性規(guī)劃問題有無窮多最優(yōu)解。第九十八張，PPT共一百二十九頁，創(chuàng)作于2022年6月99例1 某工廠要用三種原材料D、P、H混合調(diào)配出

39、三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求、單價和原材料的供應(yīng)量、單價。該廠應(yīng)如何安排生產(chǎn)使利潤最大？產(chǎn)品名稱規(guī)格要求單價(元/kg）A原材料D不少于50%原材料P不超過25%50B原材料D不少于25%原材料P不超過50%35C不限25原材料名稱每天最多供應(yīng)量(kg)單價(元/kg)D10065P10025H6035第六節(jié) 應(yīng)用舉例解：設(shè)A中D、P、H的含量為x11、x12、x13 B中D、P、H的含量為x21、x22、x23 C中D、P、H的含量為x31、x32、x33第九十九張，PPT共一百二十九頁，創(chuàng)作于2022年6月100用單純形法計算得結(jié)果：每天生產(chǎn)A產(chǎn)品200kg,分別需要原

40、料:D為100kg;P為50kg;H為50kg. 總利潤收入Z=500元/天.第一百張，PPT共一百二十九頁，創(chuàng)作于2022年6月101max=-15*x11+25*x12+15*x13-30*x21+10*x22+0*x23-40*x31+0*x32-10*x33;x11+x21+x31=100;x12+x22+x32=100;x13+x23+x33=0.50;x12/(x11+x12+x13)=0.25;x22/(x21+x22+x23)=0.50;end第一百零一張，PPT共一百二十九頁，創(chuàng)作于2022年6月102例2華津機器制造廠專為拖拉機廠配套生產(chǎn)柴油機。今年頭四個月收到的訂單數(shù)量分

41、別為2500臺，4500臺，2000臺，5000臺柴油機。該廠正常生產(chǎn)每月可生產(chǎn)柴油機3000臺，利用加班還可以生產(chǎn)1500臺。正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加1500元成本，庫存成本為每臺每月200元。華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低？假設(shè)第一月初和第四月末庫存為0變量意義(生產(chǎn)成本/臺、能力）xi第i月正常生產(chǎn)臺數(shù)(5000、3000)yi第i月加班生產(chǎn)臺數(shù)(6500、1500)zi第i月月初庫存(200/月.臺)需求2500、4500、2000、5000第一百零二張，PPT共一百二十九頁，創(chuàng)作于2022年6月103設(shè)xi為第i月正常生產(chǎn)的柴油機數(shù)，yi為第i月加班生產(chǎn)的

42、柴油機數(shù)，zi為第i月月初柴油機的庫存數(shù)。第一百零三張，PPT共一百二十九頁，創(chuàng)作于2022年6月104min=5000*(x1+x2+x3+x4)+6500*(y1+y2+y3+y4)+200*(z2+z3+z4);x1+y1-z2=2500;x2+y2+z2-z3=4500;x3+y3+z3-z4=2000;x4+y4+z4=5000;x1=3000; x2=3000; x3=3000; x4=3000; y1=1500; y2=1500; y3=1500; y4=1500;一月二月三月四月正常生產(chǎn)臺數(shù)3000300030003000加班生產(chǎn)臺數(shù)0100001000月初庫存數(shù)量050001

43、000第一百零四張，PPT共一百二十九頁，創(chuàng)作于2022年6月105例3 某部門在今后5年內(nèi)連續(xù)給以下項目投資： 項目A，第一年至第四年每年年初投資，次年末回收本利115%； 項目B，第三年初投資，第五年末回收本利125%，最大投資額 不超過4萬元； 項目C，第二年初投資，第五年末回收本利140%，最大投資額 不超過3萬元； 項目D，五年內(nèi)每年初可購買公債，當(dāng)年末歸還，并加利息6%。 該部門現(xiàn)有資金 10萬元，問該如何確定投資方案，使第五年末擁有的資金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D第一百零五張，PPT共一百二十九頁，創(chuàng)作于202

44、2年6月106第一年第二年第三年第四年第五年第一百零六張，PPT共一百二十九頁，創(chuàng)作于2022年6月107max=1.15*x4A+1.4*x2C+1.25*x3B+1.06*x5D;x1A+x1D=100000;x2A+x2C+x2D=1.06*x1D;x3A+x3B+x3D=1.06*x2D+1.15*x1A;x4A+x4D=1.06*x3D+1.15*x2A;x5D=1.06*x4D+1.15*x3A;x3B=40000;x2C=3000;50*x1 +60*x2 +20*x3+10*x4 =55;400*x1 +200*x2 +300*x3+500*x4 =800; Global op

45、timal solution found. Objective value: 10.00000 Total solver iterations: 0 Variable Value Reduced Cost X1 0.000000 10.66667 X2 0.000000 3.333333 X3 3.333333 0.000000 X4 0.000000 1.333333用Lingo求解第一百零九張，PPT共一百二十九頁，創(chuàng)作于2022年6月110例5：產(chǎn)品配套問題 某廠生產(chǎn)一種產(chǎn)品，由兩個B1 零件和三個B2零件配置組裝而成。該廠有A1、A2、A3三種機床可加工上述兩種零件，每種機床的臺數(shù)以及

46、每臺機床每個工作日全部用于加工某一種零件的最大產(chǎn)量（即生產(chǎn)率：件/日）見下表。試求該產(chǎn)品產(chǎn)量最大的生產(chǎn)方案。機床生產(chǎn)率（件/日）機床數(shù)量機床類型零件B2零件B118104A3354520302A23A1難點：1) 同一臺機床加工零件B1和 B2的時間分配；2)零件B1和 B2的配套問題，2:3構(gòu)成一件產(chǎn)品。第一百一十張，PPT共一百二十九頁，創(chuàng)作于2022年6月111解：（1）決策變量 根據(jù)題意，設(shè)每臺Ai (i=1,2,3)機床每個工作日加工Bj(j=1,2)零件的時間為xij(工作日)；Z為零件B1和 B2按2:3比例配套的產(chǎn)品數(shù)量（套/日）。（2）約束條件 工時約束： 機床A1：x11+

47、 x12=1 機床A2：x21+ x22=1 機床A3：x31+ x32=1 配套約束： 零件B1的產(chǎn)量：320 x112 35 x21 4 10 x31 零件B2的產(chǎn)量：330 x122 45 x22 4 18 x32第一百一十一張，PPT共一百二十九頁，創(chuàng)作于2022年6月112非負(fù)約束 xij 0 (i=1,2,3；j=1,2) （3）目標(biāo)函數(shù) max Z=f第一百一十二張，PPT共一百二十九頁，創(chuàng)作于2022年6月113設(shè)每臺Ai (i=1,2,3)機床每個工作日加工Bj(j=1,2)零件的時間為xij(工作日)；Z為零件B1和 B2按2:3比例配套的產(chǎn)品數(shù)量（套/日）。 max Z=

48、f x11+ x12=1 x21+ x22=1 x31+ x32=1 xij 0 (i=1,2,3；j=1,2) 第一百一十三張，PPT共一百二十九頁，創(chuàng)作于2022年6月114 max=f;x11+x12=1;x21+x22=1;x31+x32=1;f=30*x11+35*x21+20*x31;f=70;x2+x3=60;x3+x4=50;x4+x5=20;x5+x6=30;x6+x1=60;end Global optimal solution found. Objective value: 150.0000 Total solver iterations: 4 Variable Valu

49、e Reduced Cost X1 60.00000 0.000000 X2 10.00000 0.000000 X3 50.00000 0.000000 X4 0.000000 0.000000 X5 30.00000 0.000000 X6 0.000000 0.000000第一百一十七張，PPT共一百二十九頁，創(chuàng)作于2022年6月118例7 某快遞公司下設(shè)一個快件分揀部，處理每天到達(dá)和外寄的快件。根據(jù)統(tǒng)計資料及經(jīng)驗預(yù)測，每天各時段快件數(shù)量如表所示時段到達(dá)快件數(shù)時段到達(dá)快件數(shù)10:00前500014:00-15:00300010:00-11:00400015:00-16:00400011:

50、00-12:00300016:00-17:00450012:00-13:00400017:00-18:00350013:00-14:00250018:00-19:002500第一百一十八張，PPT共一百二十九頁，創(chuàng)作于2022年6月119快件分揀由機器操作，分揀效率為每臺500件/h，每臺機器操作時需要配一名職工，共有11臺機器。分揀部一部分是全日制職工，上班時間分別為10:00-18:00,11:00-19:00和12:00-20:00，每人每天工資150元；另一部分是非全日制職工，每天上班5小時，分別是13:00-18:00, 14:00-19:00和15:00-20:00，每人每天工資80元?？旒幚淼囊?guī)則是從每整點起可處理該整點前到達(dá)的快件。因快件有時間性要求，凡是12:00前到達(dá)的快件必須在14:00以前處理完；15:00以前到達(dá)的，必須在17: