第一章 線性規(guī)劃

1、線線 性性 規(guī)規(guī) 劃劃(Linear Programming)線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃的單純形法線性規(guī)劃的單純形法線性規(guī)劃的圖解法線性規(guī)劃的圖解法單純形法計算步驟單純形法計算步驟單純形法的進一步討論單純形法的進一步討論線性規(guī)劃模型的應(yīng)用線性規(guī)劃模型的應(yīng)用一、線性規(guī)劃問題及其數(shù)學模型一、線性規(guī)劃問題及其數(shù)學模型 例例1 1 某廠生產(chǎn)兩種產(chǎn)品，下某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤單位產(chǎn)品利潤 問：應(yīng)如何安排生產(chǎn)計劃，才問：應(yīng)如何安排生產(chǎn)計劃，才能使總利潤最大？能使總利潤最大？ （一）問題的提出（一）問題的提出解：解：

2、1.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的的 產(chǎn)量分別為產(chǎn)量分別為 x1、x22.2.目標函數(shù)：設(shè)總利潤為目標函數(shù)：設(shè)總利潤為z z，則，則 max z = 2 x1 + x23.3.約束條件：約束條件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x20s.t. 設(shè)設(shè) 備備產(chǎn)產(chǎn) 品品 A B C D利潤利潤（元）（元） 2 1 4 0 2 2 2 0 4 3有有 效效 臺臺 時時 12 8 16 12 例例2 已知資料已知資料如右表所示，問如右表所示，問如何安排生產(chǎn)才如何安排生產(chǎn)才能使利潤最大？能使利潤最大？或如何考慮利潤或如何考慮利潤大，產(chǎn)品好銷。大，產(chǎn)

3、品好銷。解解max Z Z = 2x1 + 3x2 s.t. x1 , x2 0 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 121.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的產(chǎn)量分別為的產(chǎn)量分別為 x1、x22.2.目標函數(shù)：設(shè)總利潤為目標函數(shù)：設(shè)總利潤為Z Z，則：則：3.3.約束條件：約束條件： 例例3 3 某廠生產(chǎn)三種藥物，這些某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中藥物可以從四種不同的原料中提取。下表給出了單位原料可提取。下表給出了單位原料可提取的藥物量提取的藥物量 要求：生產(chǎn)要求：生產(chǎn)A A種藥物至少種藥物至少160160單單位，位，B

4、 B種藥物恰好種藥物恰好200200單位，單位，C C種藥物不超過種藥物不超過180180單位，且使單位，且使原料總成本最小。原料總成本最小。解：解：1.1.決策變量：設(shè)四種原料的使用決策變量：設(shè)四種原料的使用 量分別為：量分別為：x1、x2 、x3 、x42.2.目標函數(shù)：設(shè)總成本為目標函數(shù)：設(shè)總成本為z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.3.約束條件：約束條件： 藥物藥物原料原料A AB BC C單位成本單位成本（元噸）（元噸）甲甲1 12 23 35 5乙乙2 20 01 16 6丙丙1 14 41 17 7丁丁1 12 22 28 8 x1 + 2x

5、2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 + x3 +2 x4 180 x1、x2 、x3 、x4 0s.t.1 1 問題中總有未知的變量，需要我們?nèi)ソ鉀Q。問題中總有未知的變量，需要我們?nèi)ソ鉀Q。 要求：有目標函數(shù)及約束條件，一般有非負條件要求：有目標函數(shù)及約束條件，一般有非負條件存在，由此組成規(guī)劃數(shù)學模型。存在，由此組成規(guī)劃數(shù)學模型。 如果在規(guī)劃問題的數(shù)學模型中，變量是連續(xù)的如果在規(guī)劃問題的數(shù)學模型中，變量是連續(xù)的（數(shù)值取實數(shù)）其（數(shù)值取實數(shù)）其目標函數(shù)是目標函數(shù)是有關(guān)變量的有關(guān)變量的線性函數(shù)線性函數(shù)（一次方），（一次方），約束條件是約束條件是有關(guān)變

6、量的有關(guān)變量的線性等式或不等線性等式或不等式式，這樣，規(guī)劃問題的數(shù)學模型是，這樣，規(guī)劃問題的數(shù)學模型是線性線性的。反之，就的。反之，就是非線性的規(guī)劃問題（其中一個條件符合即可）。是非線性的規(guī)劃問題（其中一個條件符合即可）。（二）數(shù)學模型（二）數(shù)學模型 （二）數(shù)學模型（二）數(shù)學模型 例例4 4 某工廠生產(chǎn)某工廠生產(chǎn)A A、B B兩種產(chǎn)品，兩種產(chǎn)品，有關(guān)資料如下表所示：有關(guān)資料如下表所示：設(shè)：總成本為設(shè)：總成本為Z，A、B產(chǎn)品產(chǎn)品銷量為銷量為x1、x2，產(chǎn)品，產(chǎn)品C C的銷售的銷售量為量為x3，報廢量為，報廢量為x4，則：，則： max z = 4 x1 + 10 x2 + 3 x3 2 x4 2

7、x1 + 3x2 12 3x1 + 4x2 24 - 4x2 +x3 + x4 = 0 x3 5 x1、x2 、x3 、x40s.t.解：解：（二）數(shù)學模型（二）數(shù)學模型 船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號航線號合同貨運量合同貨運量12002400航線號航線號船隊船隊類型類型編隊形式編隊形式貨運成本貨運成本（千元隊）（千元隊）貨運量貨運量（千噸）（千噸）拖輪拖輪A型型駁船駁船B型型駁船駁船1112362521436202322472404142720問：應(yīng)如何編隊，才能既完成合同任務(wù)，又使總貨運成本問：應(yīng)如何編隊，才能既完成合同任務(wù)，又使總貨運

8、成本為最??？為最??？例例5 5 某航運局現(xiàn)有船只種類、數(shù)量以及計劃期內(nèi)各條航線的某航運局現(xiàn)有船只種類、數(shù)量以及計劃期內(nèi)各條航線的貨運量、貨運成本如下表所示：貨運量、貨運成本如下表所示：解：設(shè)解：設(shè)x xj j為第為第j j號類型船隊的隊數(shù)（號類型船隊的隊數(shù)（j = 1j = 1，2 2，3 3，4 4），）， z z 為總貨運成本為總貨運成本則則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1+20 x2 200 40 x3+20 x4400 xj 0 （

9、j = 1,2,3,4）s.t.船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號航線號合同貨運量合同貨運量1200240000 12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcZ)()(min)max目標函數(shù)：目標函數(shù)：約束條件：約束條件：2 2、線性規(guī)劃數(shù)學模型的一般形式、線性規(guī)劃數(shù)學模型的一般形式 模型特點模型特點1 1 都用一組決策變量都用一組決策變量X = (x1,x2,xn)T表示某一方案，表示某一方案，且決策變量取值非負；且決策變量取值非負；滿足以上三個條件的滿足以上三個條件的數(shù)學模型數(shù)學模型稱

10、為稱為線性規(guī)劃線性規(guī)劃2 2 都有一個要達到的目標，并且目標要求可以表示成都有一個要達到的目標，并且目標要求可以表示成決策變量的線性函數(shù)；決策變量的線性函數(shù)；3 3 都有一組約束條件，這些約束條件可以用決策變量都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等式來表示。的線性等式或線性不等式來表示。也可以記為如下形式也可以記為如下形式：)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 目標函數(shù)：目標函數(shù)：約束條件：約束條件：如將上例用表格表示如下：如將上例用表格表示如下：設(shè)變量設(shè)變量)21( njxj 產(chǎn)產(chǎn) 品品 j 設(shè)設(shè) 備備

11、i 有效臺時有效臺時 利潤利潤 mnmijnaaaaa 1111n 2 1m 2 1 mbbb 21nccc 21jcib向向 量量 形形 式：式： ) (21ncccC nxxX1 mjjjaap1 mbbb1 0).( (min) max1XbxpCXZnjjj矩陣和向量形式：矩陣和向量形式： mnmnaaaaA1111 0 )( (min) maxXbAXCXZ（三）線性規(guī)劃模型的標準形式（三）線性規(guī)劃模型的標準形式 )n 2 1(j 0 m) 2 1(i jijijjjxbxaxcZmax1 1、標準形式標準形式 將模型的一般形式變成標準形式，再根據(jù)標準型將模型的一般形式變成標準形式，

12、再根據(jù)標準型模型，從可行域中找一個基本可行解，并判斷是否是模型，從可行域中找一個基本可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個基本可行解，當目標函數(shù)達到最大時，得到最優(yōu)解。個基本可行解，當目標函數(shù)達到最大時，得到最優(yōu)解。 目標函數(shù)為求極大值，也可以用求極小值；目標函數(shù)為求極大值，也可以用求極小值； 所有約束條件（非負條件除外）都是等式，所有約束條件（非負條件除外）都是等式，右端常數(shù)項為非負；右端常數(shù)項為非負； 變量為非負。變量為非負。3、轉(zhuǎn)換方式：、轉(zhuǎn)換方式： 目標函數(shù)的轉(zhuǎn)換目標函數(shù)的轉(zhuǎn)換 如果是求極小值即如果是求極小值即

13、 ，則可將目標函，則可將目標函數(shù)乘以（數(shù)乘以（1 1），可化為求極大值問題。），可化為求極大值問題。 jjxcZmin也就是：令也就是：令 ，可得到下式，可得到下式ZZ 即即=jjxcZaxm2、特征：、特征：(3) (3) 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式 。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量 (2)(2)常數(shù)項常數(shù)項b bi i0 0的轉(zhuǎn)換：約束方程兩邊乘以（的轉(zhuǎn)換：約束方程兩邊乘以（1 1）。）。(4) (4) 變量的變換變量的變換 若存在取值無約

14、束的變量若存在取值無約束的變量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx。顯然，令00jjjjx，xxx若若 例1：將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0 解：首先,將目標函數(shù)轉(zhuǎn)換成極大化：令 z= -f = -3.6x1+5.2x2-1.8x3 其次考慮約束，有2個不等式約束，引進松弛變量x4，x5 0。于是，我們可以得到以下標準形式的線性

15、規(guī)劃問題： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 0例例2 ：將下列線性規(guī)劃問題化為標準形式：將下列線性規(guī)劃問題化為標準形式 ,0,52324 7 532min321321321321321xxxxxxxxxxxxxxxZ為無約束（無非負限制）為無約束（無非負限制） 解解: : 用用 替換替換 ，且，且 ， 54xx 3x0,54 xx76, xx引入變量引入變量將第將第3 3個約束方程兩邊乘以個

16、約束方程兩邊乘以（1 1）將極小值問題反號，變?yōu)榍髽O大值將極小值問題反號，變?yōu)榍髽O大值標準形式如下：標準形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ一一 般般 有有兩種方法兩種方法圖圖 解解 法法單純形法單純形法兩個變量、直角坐標兩個變量、直角坐標三個變量、立體坐標三個變量、立體坐標適用于任意變量、但需將適用于任意變量、但需將一般形式變成標準形式一般形式變成標準形式線性規(guī)劃問題的求解方法線性規(guī)劃問題的求解方法 二、圖二、圖 解解 法法（一）解題步驟（一）解題步驟4 4

17、 將最優(yōu)解代入目標函數(shù)，求出最優(yōu)值。將最優(yōu)解代入目標函數(shù)，求出最優(yōu)值。1 1 在直角平面坐標系中畫出所有的約束等式，并找出所在直角平面坐標系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中的點稱有約束條件的公共部分，稱為可行域，可行域中的點稱為可行解。為可行解。 2 2 標出目標函數(shù)值增加的方向。標出目標函數(shù)值增加的方向。3 3 若求最大（?。┲?，則令目標函數(shù)等值線沿（逆）目若求最大（小）值，則令目標函數(shù)等值線沿（逆）目標函數(shù)值增加的方向平行移動，找與可行域最后相交的標函數(shù)值增加的方向平行移動，找與可行域最后相交的點，該點就是最優(yōu)解。點，該點就是最優(yōu)解。例：例： 0,0

18、124 16 482122232max2121212121xxxxxxxxxxZ 01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 圖圖 最最 優(yōu)優(yōu) 解：解：x1 = 4 x2 = 2有惟一最優(yōu)解有惟一最優(yōu)解x2 x1(4 2) 00124 16 4821222322121212121xxxxxxxxxxZ,max最最 優(yōu)優(yōu) 值值：Z = 14（二）線性規(guī)劃問題解的情況（二）線性規(guī)劃問題解的情況惟惟 一一 解解無無 窮窮 解解無無 界界 解解無可行解無可行解01 2 3 4 5 6 7 8 1 2 3 4 5 6 例：例：x2 x1 00124 16 48212222212121

19、2121x,xxxxxxxxxZmax無窮多最優(yōu)解無窮多最優(yōu)解 例：例：無窮多最優(yōu)解無窮多最優(yōu)解無界解無界解x1x1x2 x2 例：例： 012221212121x,xxxxxxxZmax 0,02 1223622max212212121xxxxxxxxxZ 0,6321 23min2121211xxxxxxxxZx1x2 無可行解無可行解例例（三）由圖解法得到的啟示（三）由圖解法得到的啟示(1)(1)線性規(guī)劃問題解的情況：惟一最優(yōu)解；無窮線性規(guī)劃問題解的情況：惟一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解多最優(yōu)解；無界解；無可行解 (3)(3)最優(yōu)解一定是在凸集的某個頂點最優(yōu)解一定是在凸集的某個

20、頂點(2)(2)線性規(guī)劃問題的可行域是凸集（凸多邊形）線性規(guī)劃問題的可行域是凸集（凸多邊形） (4) (4)解題思路解題思路是，先找出凸集的任一頂點，計算是，先找出凸集的任一頂點，計算 其目標函數(shù)值，再與周圍頂點的目標函數(shù)值比其目標函數(shù)值，再與周圍頂點的目標函數(shù)值比 較，如不是最大，繼續(xù)比較，直到找出最大為較，如不是最大，繼續(xù)比較，直到找出最大為 止。止。（一）線性規(guī)劃問題解的概念（一）線性規(guī)劃問題解的概念 可行解可行解：滿足約束條件：滿足約束條件、的解的解 X=(x1, x2 ， ，xn)T為可行解。其中使目標函數(shù)達為可行解。其中使目標函數(shù)達 到最大值的可行解稱為最優(yōu)解。所有解的集合到最大值

21、的可行解稱為最優(yōu)解。所有解的集合 為可行解的集或可行域。為可行解的集或可行域。三、線性規(guī)劃的單純形法三、線性規(guī)劃的單純形法11max(1),1,2,(2)0,1,2,(3)njjjnijjijjzc xa xb imxjn（一）線性規(guī)劃問題解的概念（一）線性規(guī)劃問題解的概念 (2) (2) 基基：B B是系數(shù)矩陣是系數(shù)矩陣A A（m mn n階）中的一個階）中的一個m mm m階的滿秩子矩陣階的滿秩子矩陣(B0)(B0)，稱，稱B B是一個基。是一個基。) (211111mmmmmpppaaaaB 則稱則稱 Pj ( j = 1 2 m) 為基向量為基向量。 Xj 為基變量，否則為非基變量。為

22、基變量，否則為非基變量。三、線性規(guī)劃的單純形法三、線性規(guī)劃的單純形法 基解基解：滿足條件：滿足條件，但不滿足條件，但不滿足條件的的 所有解，最多為所有解，最多為 個。個。Cmn 基可行解基可行解：滿足非負約束條件的基解，：滿足非負約束條件的基解， 簡稱基可行解。簡稱基可行解。 可行基可行基：對應(yīng)于基可行解的基稱為可行基。：對應(yīng)于基可行解的基稱為可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解 例3: 考慮線性規(guī)劃模型 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5

23、= 75 x1 , x2 , x3 , x4 , x5 0 注意，線性規(guī)劃的基本解、基本可行 解（極點）和可行基只與線性規(guī)劃問 題標準形式的約束條件有關(guān)。 3 2 1 0 0A = P1 ,P2 ,P3 ,P4 ,P5 = 2 1 0 1 0 0 3 0 0 1 A矩陣包含以下10個33的子矩陣： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 B3=p1 ，p2 ，p5 B4=p1 ，p3 ，p4 B5=p1 ，p3 ，p5 B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5 其中B B4= 0

24、，因而B B4不是該線性規(guī)劃問題的基。其余均為非奇異方陣，因此該問題共有9個基。 對于基B B3=p1 ，p2 ，p5 ，令非基變量x3 3 = 0， x4 = 0，在等式約束中令x3 = 0，x4 = 0，解線性方程組： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，對應(yīng)的基本可行解： x=(x1 ，x2 ，x3 ，x4 ，x5)T=(15，10，0，0，45)T。于是對應(yīng)的基B B3是一個可行基。 類似可得到 x(2) = (5,25,0,5,0)T

25、（對應(yīng)B2） x(7) = (20,0,5,0,75)T （對應(yīng)B5） x(8) = (0,25,15,15,0)T （對應(yīng)B7） x(9) = (0,0,65,40,75)T （對應(yīng)B10） 是基本可行解； 而x(3)= (0,32.5,0,7.5,-22.5)T（對應(yīng)B9） x(4)= (65/3,0,0,-10/3,75)T （對應(yīng)B6） x(5)= (7.5,25,-7.5,0,0)T （對應(yīng)B1） x(6) = (0,40,-15,0,-45)T （對應(yīng)B8） 是基本解。 因此，對應(yīng)基本可行解（極點）的B2 B3 B5 B7 B10都是可行基。 這里指出了一種求解線性規(guī)劃問題的可能途

26、徑，就是先確定線性規(guī)劃問題的基，如果是可行基，則計算相應(yīng)的基本可行解以及相應(yīng)解的目標函數(shù)值。由于基的個數(shù)是有限的（最多個），因此必定可以從有限個基本可行解中找到最優(yōu)解。 （二）凸集及其頂點（二）凸集及其頂點 凸集凸集：設(shè)設(shè)K是是n n維歐氏空間的一點集，若任意兩點維歐氏空間的一點集，若任意兩點 X(1)K，X(2)K的的連線上的所有點連線上的所有點X(1)+(1- )X(2)K，(01)；則稱則稱K K為凸集。為凸集。 任何兩個凸集的交集是凸集 頂點頂點：設(shè)K是凸集，XK；若X不能用不同的兩點X(1)K和X(2)K的線性組合表示為X=X(1)+(1-)X(2)，(01) 則稱X為K的一個頂點(

27、或極點)。 圖中0，Q1,2,3,4都是頂點推論 若K是有界凸集，則任何一點XK可表示為K的頂點的凸組合。 幾個基本定理 定理1 若線性規(guī)劃問題存在可行域，則其可行域是凸集 njjjjxbxPXD10,證：為了證明滿足線性規(guī)劃問題的約束條件njjjjnjxbxP1, 2 , 1, 0,的所有點(可行解)組成的集合是凸集，只要證明D中任意兩點連線上的點必然在D內(nèi)即可。設(shè)是D內(nèi)的任意兩點；X(1)X(2)。TnTnxxxXxxxX222212112111,則有 njjjjnjjjjnjxbxPnjxbxP122111, 2 , 1, 0, 2 , 1, 0, 令 X=(x1，x2，xn)T為 x(

28、1),x(2)連線上的任意一點，即 X=X(1)+(1-)X(2) (01) X 的每一個分量是 21)1 (jjjxxx，將它代入約束條件， 得到 bbbbxPxPxPxxPxPnjnjjjjjnjjjnjnjjjjjj11221111211又因 01 , 0, 0,21jjxx，所以 xj0，j=1,2,n。 由此可見 XD，D 是凸集。 證畢。 引理 1 線性規(guī)劃問題的可行解 X= (x1, x2, ，xn)T 為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。 定理定理2 2 線性規(guī)劃問題的基可行解X對應(yīng)于可行 D的頂點。定理定理3 3 若可行域有界，線性規(guī)劃問題的目標函

29、數(shù)一定若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。可以在其可行域的頂點上達到最優(yōu)。證證 設(shè)X(1),X(2)，X(k)是可行域的頂點，若X(0)不是頂點，且目標函數(shù)在X(0)處達到最優(yōu)z*=CX(0)(標準型是z*=max z)。因X(0)不是頂點，所以它可以用D的頂點線性表示為 kikiiiiiixX1101, 0,定理定理33 若線性規(guī)劃問題有最優(yōu)解，一定存在一個若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解?；尚薪馐亲顑?yōu)解。代入目標函數(shù)得 kikiiiiiCXXCCX110 在所有的頂點中必然能找到某一個頂點X(m)，使CX(m)是所有CX(i)中最大

30、者。并且將X(m)代替(*)式中的所有X(i)，這就得到（*） mkimikiiiCXCXCX11由此得到 CX(0)CX(m)根據(jù)假設(shè)CX(0)是最大值，所以只能有 CX(0)=CX(m)即目標函數(shù)在頂點X(m)處也達到最大值。 有時目標函數(shù)可能在多個頂點處達到最大;這時在這些頂點的凸組合上也達到最大值。稱這種線性規(guī)劃問題有無限多個最優(yōu)解。 假設(shè) 是目標函數(shù)達到最大值的頂點，若是這些頂點的凸組合，即 kikiiiiiXX111, 0,于是 kiiikiiiXCXCXC11 kimXCi, 2 , 1,設(shè)：于是：mmXCkii1綜上所述綜上所述, ,我們在理論上得到了線性規(guī)劃問題的以我們在理論

31、上得到了線性規(guī)劃問題的以下結(jié)論：下結(jié)論： 線性規(guī)劃問題的可行域是一凸集（包括有界凸集和無界凸集）；線性規(guī)劃問題的每個基本可行解對應(yīng)著可行域的一個極點（頂點）；若線性規(guī)劃問題有最優(yōu)解,必在可行域的某一極點上得到。由此可見,我們只需在基本可行解中尋求最優(yōu)解。如何有效地尋求最優(yōu)解,這就是下節(jié)要介紹的單純形法。 基本思路：基本思路：將模型的一般形式變成標準形式，再根將模型的一般形式變成標準形式，再根據(jù)標準型模型，從可行域中找一個基可行解，并判據(jù)標準型模型，從可行域中找一個基可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個基可行解，當目標函

32、數(shù)達到最大時，轉(zhuǎn)換到另一個基可行解，當目標函數(shù)達到最大時，得到最優(yōu)解。得到最優(yōu)解。（四）單純形法迭代原理（四）單純形法迭代原理例例: 0,124 16 482122232max2121212121xxxxxxxxxxZ變成標準型變成標準型 0 12 4 16 4 8 2 21 220000326543216251421321654321x,x,x,x,x,xxxxxxxxxxxxxxxxxZmax 約束方程約束方程的系數(shù)矩陣的系數(shù)矩陣 654321100040010004001021000122ppppppA IppppB100001000010000165436543 xxxx,21xx ,

33、為基變量為基變量為非基變量為非基變量I I 為單位矩陣且線性獨立為單位矩陣且線性獨立確定初始基確定初始基B B令：令：12x 16x 8x 12x 0654321 xx則：則： 基可行解為基可行解為（0 0 12 8 16 120 0 12 8 16 12）T T 此時，此時，Z = 0Z = 0 找另一個基可行解。找另一個基可行解。即將非基變量換入基變量即將非基變量換入基變量中，但保證其余的非負中，但保證其余的非負。如此循環(huán)下去，直到找如此循環(huán)下去，直到找到最優(yōu)解為止。到最優(yōu)解為止。 注意注意：為盡快找到最優(yōu)解，在換入變量時有一定：為盡快找到最優(yōu)解，在換入變量時有一定的要求。如將目標系數(shù)大的

34、先換入等。的要求。如將目標系數(shù)大的先換入等。確定新的基（換基）確定新的基（換基）找出一個初始可行解找出一個初始可行解 是否最優(yōu)是否最優(yōu)轉(zhuǎn)移到另一個目標函數(shù)轉(zhuǎn)移到另一個目標函數(shù)（找更大的基可行（找更大的基可行 解）解）最優(yōu)最優(yōu) 解解是是否否循循環(huán)環(huán)直到找出為止，直到找出為止，核心核心是：是：變量迭代變量迭代結(jié)結(jié) 束束其步驟總結(jié)如下：其步驟總結(jié)如下：當當 時，時， 為換入變量為換入變量 01x2x0 4120 160 2 802122652423 xxxxxxx確定換出變量確定換出變量3)412 28 212min( 2x6x為換出變量為換出變量接下來有下式：接下來有下式： 4 124 3 416

35、 2 82 1 212 2 6215124123xxxxxxxxxx 用高斯法，將用高斯法，將 的系數(shù)列向量換為單位列向量，的系數(shù)列向量換為單位列向量，其步驟是：其步驟是：2x(3)(3,)(42-2)()(2,)(42-(1)(1 ,4)4()4( 結(jié)果是：結(jié)果是：621561461341 3 416 21 2 2126 xxxxxxxxxx 1 2 3 4 4 12 4 3 416 2 8 2 1 212 2 6215124123xxxxxxxxxx 代入目標函數(shù)：代入目標函數(shù)：616143294392xxxxZ 有正系數(shù)表明：還有潛力可挖，沒有達到最大值；有正系數(shù)表明：還有潛力可挖，沒有

36、達到最大值；此時：令此時：令 得到另一個基可行解得到另一個基可行解 （0，3，6，2，16，0）T1x 有負系數(shù)表明：若要剩余資源發(fā)揮作用，就必須有負系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費用。當支付附加費用。當 時，即不再利用這些資源。時，即不再利用這些資源。6x06 x9 , 061 Zxx如此循環(huán)進行，直到找到最優(yōu)為止。如此循環(huán)進行，直到找到最優(yōu)為止。本例最優(yōu)解為：本例最優(yōu)解為：（4，2，0，0，0，4）T14maxZ 81231454 xxz一般線性規(guī)劃問題的求解 初始基可行解的確定為了確定初始基可行解，要首先找出初始可行基，其方法如下。 (1)直接觀察 (2)加松弛變量 (3

37、)加非負的人工變量(1)直接觀察njxbxPxczjnjjjnijjj, 2 , 10211201max1若線性規(guī)劃問題 從Pj(j=1,2,n)中一般能直接觀察到存在一個初始可行基111,21mPPPB(2)加松弛變量 對所有約束條件是“”形式的不等式，可以利用化為標準型的方法，在每個約束條件的左端加上一個松弛變量。 經(jīng)過整理，重新對xj及aij (i=1, 2,m; j=1,2,n)進行編號，則可得下列方程組其中x1,x2,xm 為松弛變量njxbxaxaxbxaxaxbxaxaxjmnmmmmmnnmmnnmm, 2 , 1, 022111,2211, 221111, 11于是含有mm單

38、位矩陣，以B作為可行基。 111,21mPPPB將(1-22)式每個等式移項得令xm+1=xm+2=xn=0，由(1-23)式可得 xi=bi (i=1,2,m)nmmmmmmnnmmnnmmxaxabxxaxabxxaxabx11,211, 222111, 111231得到一個初始基可行解 又因bi0(在1-3節(jié)中已做過規(guī)定)，所以得到一個初始基可行解 X=(x1,x2,xm,0，0)T n-m個 =(b1,b2,bm,0，0)T n-m個(3)加非負的人工變量 對所有約束條件是“”形式的不等式及等式約束情況，若不存在單位矩陣時，就采用人造基方法。 即對不等式約束減去一個非負的剩余變量后，再

39、加上一個非負的人工變量； 對于等式約束再加上一個非負的人工變量，總能得到一個單位矩陣。關(guān)于這個方法將在本章第5節(jié)中進一步討論。3.33.3最優(yōu)性檢驗與解的判別最優(yōu)性檢驗與解的判別 對線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況， 為此需要建立對解的判別準則。一般情況下，經(jīng)過迭代后(1-23)式變成 1,1,2,1 24niiijjj mxba xim 將 代入目標函數(shù)(1-20)式，整理后得251)(11111111111111111 minmjjmiijijiinmjjjnmjjijmiimiiinmjjjnmjjijmiimiiinmjjjminmjji

40、jiiminmjjjiinjjjxaccbcxcxacbcxcxacbcxcxabcxcxcxcznmjmijxijaibix1), 2 , 1,(令mimiijijiinmjaczbcz110, 1,nmjjjjxzczz10)261 (于是nmjzcjjj, 1設(shè)27110nmjjjxzz1最優(yōu)解的判別定理 若 為對應(yīng)于基B的一個基可行解，且對于一切j=m+1,n，有j0，則X(0)為最優(yōu)解。稱j為檢驗數(shù)。 TmbbbX0,0,210當所有非基變量的j0時，由（1-27）式可知已不存在任一可換入的非基變量，使目標函數(shù)繼續(xù)增大。所以以j0，為最優(yōu)解的判別準則。27110nmjjjxzz2.無

41、窮多最優(yōu)解判別定理 若 為一個基可行解，對于一切j=m+1，,n，有j0，又存在某個非基變量的檢驗數(shù)m+k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。證: 只需將非基變量xm+k換入基變量中，找到一個新基可行解X(1)。因m+k=0，由(1-27)知z=z0，故X(1)也是最優(yōu)解。由凸組合的性質(zhì)可知X(0)，X(1)連線上所有點都是最優(yōu)解。 Tm,b ,b ,bX002103無界解判別定理若 為一基可行解，有一個m+k0，并且對i=1,2,，m，有存在。 那么該線性規(guī)劃問題具有無界解(或稱無最優(yōu)解)。 TmbbbX0,0,210,0i mka證: 構(gòu)造一個新的解 X(1)，它的分量為 kmjnmjxx

42、abxjkmkmiii并且, 1; 0011,1因 ，所以對任意的0都是可行解，把x(1)代入目標函數(shù)內(nèi)得z=z0+m+k因m+k0，故當+，則z+，故該問題目標函數(shù)無界。0,kmia 以上討論都是針對標準型，即求目標函數(shù)極大化時的情況。當求目標函數(shù)極小化時，一種情況如前所述，將其化為標準型。 如果不化為標準型，只需在上述1，2點中把j0改為j0，第3點中將m+k0改寫為m+k0即可。 二、單純形法的矩陣描述二、單純形法的矩陣描述 在線性規(guī)劃問題的標準型：在線性規(guī)劃問題的標準型： Max TzC X0. .XbAXts中，不妨設(shè)中，不妨設(shè) 是一個可行基，則系數(shù)是一個可行基，則系數(shù)矩陣可分塊為（

43、，）。對應(yīng)于的基變量為矩陣可分塊為（，）。對應(yīng)于的基變量為 非基變量為非基變量為令，其中為基變量令，其中為基變量 的系數(shù)列向的系數(shù)列向量。量。N=于是原問題可化為于是原問題可化為NBTNTBTXXCCXCZMax),(),(21mpppBTmBxxxX),(21TnmmNxxxX),(21),(21nmmppp),(TNTBTCCCTBCBX0,),(. .NBNBXXbXXNBts 即 對約束方程兩邊同左乘以 ， 得 = ， 并代入目標函數(shù)，得NTNBTBTXCXCXCZMax0,. .NBNBXXbNXBXts1BNNXBbB11BXNTBTNTBXNBCCbBCZ)(11 令非基變量 =

44、0得 = , 從而相應(yīng)的基本可行解為 目標函數(shù)取值為 又由于 ,故有 NXBXbB101bBXXXNBbBCZTB101BBCCTBTBNTBTNBTBTBTBXNBCCXBBCCbBCZ)()(111XABCCbBCTBTB)(11將 及Z的表達式又可寫成令 則又有 + = +BX1111()BNTTTNBNBXB NXB bZCC B N XC B bNBCCTBTNN1ABCCTB1bBCZTB1NNXbBCTB1XAjcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc lklk ik

45、 iiabaab=)0min(=四、單純形法計算步驟四、單純形法計算步驟單純形表單純形表1-1根據(jù)max(j0)=kjcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0lklk ik iiabaab=)0min(=四、單純形法計算步驟四、單純形法計算步驟單純形表單純形表1-11,11mmii micc a1mniinicc a根據(jù)max(j0)=k單純形表的說明 XB列中填入基變量，這里是x1，x2,，xm； CB列中填入基變量的價值系數(shù)，這里是c1,c2,cm；它們是與基變量相對應(yīng)的； b列中填入約束方程組

46、右端的常數(shù)； cj行中填入基變量的價值系數(shù)c1,c2,cn； i列的數(shù)字是在確定換入變量后，按規(guī)則計算后填入； 最后一行稱為檢驗數(shù)行，對應(yīng)各非基變量xj的檢驗數(shù)是1,1,2,mjjiijicc ajn4.2 4.2 計算步驟計算步驟 表1-2稱為初始單純形表，每迭代一步構(gòu)造一個新單純形表。 計算步驟： (1) 按數(shù)學模型確定初始可行基和初始基可行解，建立初始單純形表。 (2) 計算各非基變量xj的檢驗數(shù)， 檢查檢驗數(shù)，若所有檢驗數(shù) 則已得到最優(yōu)解，可停止計算。否則轉(zhuǎn)入下一步。 miijijjacc1,njj, 2 , 1, 0 (3) 在j0,j=m+1,n中，若有某個k對應(yīng)xk的系數(shù)列向量P

47、k0，則此問題是無界，停止計算。 否則，轉(zhuǎn)入下一步。 (4) 根據(jù)max(j0)=k，確定xk為換入變量，按規(guī)則計算lklikikiabaab0min (5) 以alk為主元素進行迭代(即用高斯消去法或稱為旋轉(zhuǎn)運算)，把xk所對應(yīng)的列向量 將XB列中的xl換為xk，得到新的單純形表。重復(fù)(2)-(5)，直到終止。行第變換laaaaPmklkkkk010021 0 12 4 16 4 8 2 21 220000326543216251421321654321x,x,x,x,x,xxxxxxxxxxxxxxxxxZmax例例 題：題：判定標準：判定標準： zc zcacz zcjjjjijijjj

48、j)0:(min0:max= cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1Z i2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x6000 x3x4x5 Z i3x23010001/42620100-1/210010 0-1/216 40 0 0 1 020000-3/4 cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60003x3x4x5

49、x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4Z i2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412Z 0 0 0 -2 0 1/4icj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0

50、0 0 0 -4 4 1 0 0 1 -1/2 1 0 0 Z 0 0 -1/2 -1 0 0i 0 0 0 -2 0 1/4Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cjicj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0Z

51、0 0 0 -3/2 -1/8 0i 0 0 0 -2 0 1/4Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cji最優(yōu)解最優(yōu)解： X=（4，2，0，0，0，4）T 最優(yōu)值最優(yōu)值： Z=14（一）模型情況（一）模型情況 變變 量：量：xj0 xj0 xj無約束無約束 結(jié)結(jié)1、組成、組成 約束條件：約束條件： = b 目標函數(shù)：目標函數(shù)： max min 果果2 、變量、變量 xj0 令令 xj= -xj ， xj

52、0 xj0 不處理不處理 xj 無約束無約束 令令xj = xj xj, xj0 , xj0 惟一最優(yōu)解惟一最優(yōu)解無窮最優(yōu)解無窮最優(yōu)解無界解無界解無可行解無可行解 五、單純形法的進一步討論五、單純形法的進一步討論3 3、約束、約束 條件：條件：bxpbxpbxpjjjjjj 加入松弛變量加入松弛變量加入人工變量加入人工變量先減去先減去 再加上再加上axaxsxsx例：例： x,x,xx xxxxxx x xxxZmax0123241123321313213213214 4、目標函數(shù)：、目標函數(shù)：max (min) 設(shè)規(guī)劃模型約束條件為設(shè)規(guī)劃模型約束條件為 ，需加入人工變，需加入人工變量量 ，而

53、得到一個，而得到一個mm的單位矩陣，即基變量組合。的單位矩陣，即基變量組合。因人工變量為因人工變量為虛擬變量虛擬變量，且存在于初始基可行解中，需要，且存在于初始基可行解中，需要將它們從基變量中替換出來。若基變量中將它們從基變量中替換出來。若基變量中不含有非零的人不含有非零的人工變量工變量，表示原問題有解。若當，表示原問題有解。若當 ，還有人工變，還有人工變量（非零）時，則表示原問題無可行解。量（非零）時，則表示原問題無可行解。axbxpJJ 0 jjzc123123 123131257467max3 2 11 42 3 2 1 ,0 Zxxxxxxxxxxxxxxxxxx， ， 加入人工變量后

54、，目的是找到一個單位向量，叫人加入人工變量后，目的是找到一個單位向量，叫人工基。其目標價值系數(shù)要確定，但不能影響目標函數(shù)的工基。其目標價值系數(shù)要確定，但不能影響目標函數(shù)的取值。一般可采用兩種方法處理：取值。一般可采用兩種方法處理：大大M法法和和兩階段法兩階段法。 即假定人工變量在目標函數(shù)中的系數(shù)為即假定人工變量在目標函數(shù)中的系數(shù)為M（任意大正數(shù)），（任意大正數(shù)），如果是求極大值，需加如果是求極大值，需加- -M；如果；如果是求極小值，需加是求極小值，需加M。如基變量中還存在。如基變量中還存在M，就不能，就不能實現(xiàn)極值。實現(xiàn)極值。 003 003 如上例：76543217654321MxMxxx

55、xxxZminMxMxxxxxxZmax 或或：大大M法法：來判斷計算過程如下：用 zcjj0cj3-1-100-M-McBxBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z3-6M-1+M-1+3M0-M00cBxBbx1x2x3x4x5x6x70 x4103-20100-1-Mx610100-11-21-1x31-2010001Z1-1+M00-M0-3M+1iimiijijjacc1,cj3-1-100-M-McBxBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-

56、1x31-2010001Z1000-1-M+1-M-1cBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z000-1/3-1/3-M+1/3-M+2/3ii最優(yōu)解為最優(yōu)解為（4 1 9 0 0 0 0）T，Z = 2 用計算機處理數(shù)據(jù)時，只能用很大的用計算機處理數(shù)據(jù)時，只能用很大的 數(shù)代替數(shù)代替M, ,可能造成計算機上的錯誤，故多采用兩可能造成計算機上的錯誤，故多采用兩 階段法。階段法。 第一階段第一階段(先求解一個只包含人工變量的先求解一個只包含人工變量的LP) 在原線性規(guī)劃問題中加入人工變

57、量，構(gòu)造如下模型：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型： 0 0011111111111mnmmnnmnmnnnnmnnxxbxxaxabxxaxaxxxxmin（2）兩階段法：兩階段法： 對上述模型求解（單純形法），若對上述模型求解（單純形法），若=0,=0,說明問說明問題存在基可行解，可以進行第二個階段；否則，原問題存在基可行解，可以進行第二個階段；否則，原問題無可行解，停止運算。題無可行解，停止運算。 第二階段：第二階段：在第一階段的最終表中，去掉人工變在第一階段的最終表中，去掉人工變量，將目標函數(shù)的系數(shù)換成原問題的目標函數(shù)系數(shù)，量，將目標函數(shù)的系數(shù)換成原問題的目標函數(shù)系數(shù)，作為

58、第二階段計算的初始表（用單純形法計算）。作為第二階段計算的初始表（用單純形法計算）。32143217624112xxxxxxxxxminl 第一階段目的是為原問題求初始基可行解；或明確第一階段目的是為原問題求初始基可行解；或明確 原問題無解。原問題無解。l第二階段再在此基可行解的基礎(chǔ)上對原目標函數(shù)進第二階段再在此基可行解的基礎(chǔ)上對原目標函數(shù)進 行優(yōu)化，或者明確有無界解。行優(yōu)化，或者明確有無界解。1231234 123513127max3 2 11 42 3 2 1 ,0 Zxxxxxxxxxxxxxxxx， 上例：上例： x,x,xx xxxxxx x xxxZmax0123241123321

59、313213213216 x7 x x,x,x x x x xx xxx xxx x xxmin 01232411272173165321432176，第一階段第一階段的線性規(guī)劃問題可寫為：的線性規(guī)劃問題可寫為：第一階段單純形法迭代的過程見下表第一階段單純形法迭代的過程見下表（注意：化為標準形式，即極大化問題）（注意：化為標準形式，即極大化問題）cj00000-1-1cBxBbx1x2x3x4x5x6x70 x4111-21100011-1x63-4120-1103/2-1x71-20100011-6130-1000 x4103-20100-1-1x610100-11-210 x31-2010

60、0010100-10-3i0 x4123001-22-50 x210100-11-20 x31-201000000000-1-1cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z1000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z000-1/3-1/3i第二階段第二階段： 最優(yōu)解為（最優(yōu)解為（4 1 9 0 04 1 9 0 0）T T，目標函數(shù)，目標函數(shù) Z = 2Z = 254321003xxxxxZmax3231 323x , 3 :052122 xxxbbii，變變換換有有：