線性規(guī)劃圖解法幾何意

1、關于線性規(guī)劃圖解法幾何意第一張，PPT共五十九頁，創(chuàng)作于2022年6月 1.3線性規(guī)劃問題的標準形式(其中bi0(i=1,2,.,m)稱下列形式為線性規(guī)劃問題的標準形式:目標函數(shù)求極大,約束條件為等式,決策變量及右邊常數(shù)項為非負第二張，PPT共五十九頁，創(chuàng)作于2022年6月線性規(guī)劃問題的幾種表示形式第三張，PPT共五十九頁，創(chuàng)作于2022年6月用向量表示為：第四張，PPT共五十九頁，創(chuàng)作于2022年6月則標準形式的矩陣表示：若令A稱為系數(shù)矩陣b稱為資源向量C稱為價值向量X稱為決策變量向量用矩陣表示為：第五張，PPT共五十九頁，創(chuàng)作于2022年6月非標準形式化為標準形式的方法1.當目標函數(shù)為求極

2、小值,即 min z=c1x1+c2x2+.+cnxn因為求min z 等價于max (-z) 故可令則目標函數(shù)化為:2.當右端項 bim)其秩為m,B是矩陣A中的一個mm階的滿秩子矩陣,稱B是線性規(guī)劃問題的一個基。第十二張，PPT共五十九頁，創(chuàng)作于2022年6月一. 線性規(guī)劃問題解的概念（2）=(P1,P2,.,Pm) B中的每一列向量Pj(j=1,2,.m)稱為基向量 基向量： 與基向量Pj的對應的變量xj 稱為基變量 基變量： 非基變量： 線性規(guī)劃中的其余變量稱為非基向量 5.基解 設X是（LP）的約束方程AX=b的一個解，B是一個基，若X中對應基B的非基變量取值全為零，則稱X為(LP)

3、關于基B的基解，記作X(B) 不妨設基為 基解的個數(shù)不會超過 個第十三張，PPT共五十九頁，創(chuàng)作于2022年6月一. 線性規(guī)劃問題解的概念（3）可證明:一個基唯一地確定一個基解. 6.基可行解：若基解X(B)滿足非負條件X(B)0，則稱基解X(B)為基可行解 7.基最優(yōu)解：若基可行解X(B)是(LP)的最優(yōu)解,則稱X(B)為(LP)的基最優(yōu)解. 最優(yōu)基：基最優(yōu)解對應的可行基B稱為最優(yōu)基. 可行基：基可行解對應的基B稱為可行基. 注:基解沒有X0的限制,故基解不一定是可行解. X(B)=第十四張，PPT共五十九頁，創(chuàng)作于2022年6月一. 線性規(guī)劃問題解的概念（4）8.退化解：若基本可行解X的所

4、有基變量的值均大于0，則稱X是非退化的，否則稱X為退化的。 若(LP)的所有基本可行解都是非退化的, 則稱線性規(guī)劃問題是非退化的. 第十五張，PPT共五十九頁，創(chuàng)作于2022年6月二. 例題考慮線性規(guī)劃問題： 約束方程的系數(shù)矩陣A很顯然A中的后3列是線性無關的，它們構(gòu)成一個基基B1對應的變量x3,x4,x5是基變量, x1,x2是非基變量第十六張，PPT共五十九頁，創(chuàng)作于2022年6月二. 例題（2）若令： 得該解是對應B1的基解，它是基可行解，B1是可行基；如取是（LP）的一個基，若令： 基B2對應的變量x1,x2,x3是基變量， ,x4,x5是非基變量得該解是對應B2的基解，它不是基可行解

5、，B2不是可行基；第十七張，PPT共五十九頁，創(chuàng)作于2022年6月三. 線性規(guī)劃問題解的關系圖AX=b的解 基解若非基變量為0 基可行解 基最優(yōu)解B是A的m階子矩陣基B若|B|0可行基B當B-1b0最優(yōu)基B若基變量取非負若對應目標函數(shù) 值最優(yōu)第十八張，PPT共五十九頁，創(chuàng)作于2022年6月非可行解三. 線性規(guī)劃問題解的關系圖（2）可行解基可行解基解基可行基最優(yōu)基第十九張，PPT共五十九頁，創(chuàng)作于2022年6月第2節(jié) 線性規(guī)劃問題的幾何意義2.1 基本概念2.2 幾個定理第二十張，PPT共五十九頁，創(chuàng)作于2022年6月一.凸集與頂點凸集: 如果集合K中任意兩個點X(1),X(2),其連線上的所有

6、點也都是集合K中的點,則稱集合K為凸集. 或K=X|X=X(1)+(1-)X(2), X(1)K,X(2)K,01 定理: D xRn| Ax=b,x0是凸集頂點:凸集K中滿足下列條件的點X稱為頂點:如果K中不存在任何兩個不同的點X1,X2,使X成為這兩個點連線上的一個點. 定理: 有限個凸集的交集還是凸集凸組合:設是n維歐氏空間中的k個點則稱X是的凸組合第二十一張，PPT共五十九頁，創(chuàng)作于2022年6月凸集的概念：凸集凸集不是凸集頂點不是凸集第二十二張，PPT共五十九頁，創(chuàng)作于2022年6月二.幾個基本定理定理1 若線性規(guī)劃問題存在可行解,則問題的可行域是凸集. 定理2 若線性規(guī)劃問題有非零

7、可行解，則其必有基可行解。定理4 若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。定理3線性規(guī)劃問題的基可行解X對應線性規(guī)劃問題可行域(凸集)的頂點.引理1線性規(guī)劃的可行解X(x1,x2,xn)T為基可行解的充要條件是X的正分量所對應的系數(shù)列向量是線性無關的。第二十三張，PPT共五十九頁，創(chuàng)作于2022年6月第3節(jié) 單 純 形 法第二十四張，PPT共五十九頁，創(chuàng)作于2022年6月一. 單純形法迭代的基本思想 開始于某一個可行基及其對應的基可行解，從一個基可行解迭代到另一個基可行解，并且使目標函數(shù)值不斷增大，經(jīng)過有限步必能求得線性規(guī)劃問題的最優(yōu)解或者判定線性規(guī)劃問題無有界的最優(yōu)解（無界解）

8、。第二十五張，PPT共五十九頁，創(chuàng)作于2022年6月二. 單純形法引例考慮線性規(guī)劃問題： 約束方程的系數(shù)矩陣A很顯然A中的后3列是線性無關的，它們構(gòu)成一個基基B對應的變量x3,x4,x5是基變量，則第二十六張，PPT共五十九頁，創(chuàng)作于2022年6月二. 單純形法引例（2）即： 將它們代入目標函數(shù)中得令非基變量x1=x2=0,得目標值z0 一個基可行解X(0)(0,0,8,16,12)為了使目標函數(shù)能更大，讓x2變成基變量，原基變量的x3，x4，x5要有一個變?yōu)榉腔兞慨攛1=0,由最上式得從上式可看出，當x2=3仍可保證所有變量非負，并使目標函數(shù)增大第二十七張，PPT共五十九頁，創(chuàng)作于2022

9、年6月二. 單純形法引例（3）為了得到以x3,x4,x2為基變量的一個基可行解，則對左邊方程中的x2與x5互換 得再令非基變量x1=x5=0,得目標值z9 一個基可行解X(0)(0,3,2,16,0)為了使目標函數(shù)能更大，讓x1變成基變量，原基變量的x3，x4，x2要有一個變?yōu)榉腔兞磕繕撕瘮?shù)變?yōu)榈诙藦垼琍PT共五十九頁，創(chuàng)作于2022年6月二. 單純形法引例（4）這樣如此下去，可得X(2)(2,3,0,8,0)為了使目標函數(shù)能更大，讓x1變成基變量，原基變量的x3，x4，x2要有一個變?yōu)榉腔兞看藭r目標函數(shù)變?yōu)閄(3)(4,2,0,0,4)由于目標函數(shù)中的變量系數(shù)都小于等于0，所以X(3

10、)（4,2,0,0,4)為最優(yōu)解， 最優(yōu)值z14下面從幾何角度分析一下最優(yōu)解的尋求過程：第二十九張，PPT共五十九頁，創(chuàng)作于2022年6月幾何意義：頂點轉(zhuǎn)移，目標增大第三十張，PPT共五十九頁，創(chuàng)作于2022年6月三. 單純形法原理1.確定初始基可行解：對標準型的LP問題在約束條件(1.1)的變量的系數(shù)矩陣中總會存在一個單位矩陣。(2)當線性規(guī)劃的約束條件都為號時，其松弛變量對應的系數(shù)列向量構(gòu)成的矩陣即為單位陣；(3)當線性規(guī)劃的約束條件為或的情況，引入人工變量后也可實現(xiàn)。(1)系數(shù)矩陣中可以直接觀察得到一個單位子矩陣；第三十一張，PPT共五十九頁，創(chuàng)作于2022年6月三. 單純形法原理（2）

11、2. 從一個基可行解轉(zhuǎn)換為相鄰的基可行解：定義：兩個基可行解稱為相鄰的，如果他們之間變換且僅變換一個基變量。設初始基可行解為：可知：其對應的系數(shù)矩陣的增廣矩陣為：第三十二張，PPT共五十九頁，創(chuàng)作于2022年6月三. 單純形法原理（3）易得： (1.3)+(1.4) (0), 得令：顯然：為使X(1)成為可行解，令：可證明:將(1.6)式代回到X(1)中,X(1) 為基可行解，此時完成了從一個基可行解到另一個與其相鄰的基可行解的轉(zhuǎn)換。第三十三張，PPT共五十九頁，創(chuàng)作于2022年6月三. 單純形法原理（4）證明：將與變量 x1,xl-1,xl+1,xm,xj對應的列向量，經(jīng)重新排列后加上b列有

12、如下形式：因為P1,P2, ,Pl-1，Pj,Pl+1,Pm線性無關，故X(1)為基可行解。第三十四張，PPT共五十九頁，創(chuàng)作于2022年6月三. 單純形法原理（5）3.最優(yōu)性檢驗與解的判別： 將2中的基可行解X(0)與X(1)分別代入目標函數(shù)，得 稱為檢驗數(shù)第三十五張，PPT共五十九頁，創(chuàng)作于2022年6月三. 單純形法原理（6）(1)當所有的j0時 ，現(xiàn)行基可行解為最優(yōu)解；當所有的j0且對應的列向量Pj 0時，該線性規(guī)劃問題有無界解；(4)對線性規(guī)劃問題無可行解的判別將在后面討論。(2)當存在某個j0且對應的列向量Pj 中有正分量時，說明目標函數(shù)值還可以增大，需要進行基變換；第三十六張，P

13、PT共五十九頁，創(chuàng)作于2022年6月第 4 節(jié) 單 純 形 法的計算步驟第三十七張，PPT共五十九頁，創(chuàng)作于2022年6月一. 單純形法的計算步驟第一步：求初始基可行解，列出初始單純形表XB bx1 x2 . xm xm+1 . xj . xnx1x2 .xmb1b2 .bm 1 0 . 0 a1,m+1 . a1j . a1n 0 1 . 0 a2,m+1 . a2j . a2n. . . . . . . . . 0 0 . 1 am,m+1 . amj . amn c c1 c2 . cm cm+1 . cj . cn首先寫出關于價值系數(shù)的表：（非單純形表）第三十八張，PPT共五十九頁，創(chuàng)

14、作于2022年6月一. 單純形法的計算步驟（2）將基變量下方的價值系數(shù)通過變換化為零，得初始單純形表XB bx1 x2 . xm xm+1 . xj . xnx1x2 .xm b1b2 .bm 1 0 . 0 a1,m+1 . a1j . a1n 0 1 . 0 a2,m+1 . a2j . a2n. . . . . . . . . 0 0 . 1 am,m+1 . amj . amn -z 0 0 . 0 . . 第三十九張，PPT共五十九頁，創(chuàng)作于2022年6月一. 單純形法的計算步驟（3）第二步：最優(yōu)性檢驗(1)當所有的j0時 ，現(xiàn)行基可行解為最優(yōu)解；當所有的j0且對應的列向量Pj 0時

15、，該線性規(guī)劃問題有無界解；(3)當存在某個j0且對應的列向量Pj 中有正分量時，說明目標函數(shù)值還可以增大，需要進行基變換。第四十張，PPT共五十九頁，創(chuàng)作于2022年6月一. 單純形法的計算步驟(4)第三步：換基迭代 (1)確定進基變量選擇檢驗數(shù)最大的非基變量為進基變量 k=max j| j0,j=1,2,.,n則xk為進基變量 (2)確定出基變量 根據(jù)下列原則確定出基變量 則l所對應的基變量xl為出基變量元素alk為軸心項(或稱為主元素) (3)以alk為軸心項進行換基迭代 即利用矩陣的初等行變換 把元素alk所在的列化為單位向量.得到新的單純形表 第四十一張，PPT共五十九頁，創(chuàng)作于202

16、2年6月一. 單純形法的計算步驟（5）第四步：重復第二、三步，一直到計算結(jié)束為止。第四十二張，PPT共五十九頁，創(chuàng)作于2022年6月二單純形法 例1(1)例 用單純形法解下列線性規(guī)劃 解:將原問題化為標準形為：得單純形初表為:第四十三張，PPT共五十九頁，創(chuàng)作于2022年6月 XB b x1 x2 x3 x4 x5 x3x4x5 8 16 12 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 z 0 2 3 0 0 0二單純形法 例1(2) T(B1)x3 x4x2-z21 0 1 0 -1/2164 0 0 1 0301 001/4-92 000-3/4 T(B2)第四十四張，P

17、PT共五十九頁，創(chuàng)作于2022年6月 XB b x1 x2 x3 x4 x5 x3x4x2 2 16 3 1 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/4 -z -9 2 0 0 0 -3/4 T(B2)x1x4x2-z21 0 1 0 -1/280 0 -4 1 2301 0 01/4-1300 -201/4 T(B3)二單純形法 例1(3)第四十五張，PPT共五十九頁，創(chuàng)作于2022年6月 XB b x1 x2 x3 x4 x5 x1x4x2 2 8 3 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4 -z -13 0 0 -2 0 1/4 T(

18、B3)x1x5x2-z41 0 0 1/4 040 0 -2 1/2 1201 1/2 -1/8 0-1400-3/2 -1/8 0 T(B4)二單純形法 例1(4)第四十六張，PPT共五十九頁，創(chuàng)作于2022年6月二單純形法 例1(4)在單純形終表中，x3,x4為非基變量，所有非基變量檢驗數(shù)均小于零，故該線性規(guī)劃問題有唯一最優(yōu)解X*=(4,2,0,0,4)T ，最優(yōu)值為 Z*=14。第四十七張，PPT共五十九頁，創(chuàng)作于2022年6月二單純形法 例2(1)例2: 用單純形法解下列線性規(guī)劃 解:將原問題化為標準形為：得單純形初表為:第四十八張，PPT共五十九頁，創(chuàng)作于2022年6月 XB b x

19、1 x2 x3 x4 x5 x3x4x5 4 3 8 1 0 1 0 0 0 1 0 1 0 1 2 0 0 1 -z 0 1 2 0 0 0 T(B1)x3x2x5-z41 0 1 0 030 1 0 1 02100-21-6 100-20 T(B2)二單純形法 例2(2)第四十九張，PPT共五十九頁，創(chuàng)作于2022年6月 XB b x1 x2 x3 x4 x5 x3x2x5 4 3 2 1 0 1 0 0 0 1 0 1 0 1 0 0 -2 1 -z-6 1 0 0 -2 0 T(B2)x3x2x1-z20 0 1 2 -130 1 0 1 02100-21-80000-1 T(B3)二

20、單純形法 例2(3)第五十張，PPT共五十九頁，創(chuàng)作于2022年6月二單純形法 例2(4)在單純形終表中，x4,x5為非基變量，非基變量檢驗數(shù)均小于等于零，且4=0,5=-10時，始終選取下標值為最小的變量為進基變量；(2)當計算值出現(xiàn)兩個以上相同的最小比值時，始終選取下標值為最小的變量為出基變量。按最小比值來確定出基變量時，有時會出現(xiàn)兩個以上相同的最小比值，從而使下一個單純形表中出現(xiàn)一個或多個基變量等于零的退化解。將使得多個基可行解對應同一頂點，可能出現(xiàn)迭代計算的循環(huán)。第五十四張，PPT共五十九頁，創(chuàng)作于2022年6月注：目標函數(shù)求最小的情況(1) 化成標準型，目標函數(shù)求極大；(2)有些書中規(guī)定目標函數(shù)的極小化作為線性規(guī)劃的標準形式，這時只需以所有檢驗數(shù)j0作為判別表中解是否是最優(yōu)的標志。(1)當所有的j0時 ，現(xiàn)行基可行解為最優(yōu)解；當所有的j