運(yùn)籌學(xué)線性規(guī)劃

1、第一章 線性規(guī)劃(Linear Programming, LP),2005年7月 龍子泉,概 述,線性規(guī)劃問題的提出最早是1939年由前蘇聯(lián)數(shù)學(xué)家康托洛維奇在研究鐵路運(yùn)輸?shù)慕M織問題、工業(yè)生產(chǎn)的管理問題時(shí)提出來的。 1947年，美國學(xué)者丹西格（G.B.Dantzig）提出了線性規(guī)劃問題的單純形方法。 線性規(guī)劃理論最為成熟、應(yīng)用最為廣泛,2005年7月 龍子泉,第一節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型,一、問題提出 例1（生產(chǎn)計(jì)劃問題）某企業(yè)利用A、B、C三種資源，在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如下表，問如何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？,決策變量：x1、x2分

2、別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量。 目標(biāo)函數(shù)：max z=50 x1+100 x2 約束條件： x1 + x2300 2x1 + x2400 x2250 即有： max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 稱之為上述問題的數(shù)學(xué)模型。,例2 靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，在兩個(gè)工廠之間有一條流量為200萬m3的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污水分別為2萬m3和1.4萬m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩

3、化工廠處理工業(yè)污水的成本分別為1000元/萬m3和800元/萬m3?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠處理工業(yè)污水的費(fèi)用最小.,決策變量：x1、x2分別代表工廠1和工廠2處理污水的數(shù)量(萬m3)。 則目標(biāo)函數(shù)：min z=1000 x1+800 x2 約束條件： 第一段河流（工廠1工廠2之間）： (2x1)/500 0.2% 第二段河流： 0.8(2x1) +(1.4x2)/7000.2% 此外有： x12； x21.4 化簡(jiǎn)有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1、x20 稱之為上述

4、問題的數(shù)學(xué)模型。,從上述兩個(gè)例子，我們可以總結(jié)出線性規(guī)劃的數(shù)學(xué)模型的一般形式。 max(min) z=c1x1+c2x2+cnxn 目標(biāo)函數(shù) a11x1+a12x2+a1nxn= (,) b1 a21x1+a22x2+a2nxn= (,) b2 約束條件 am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 模型特點(diǎn)：目標(biāo)函數(shù)(Objective function)與約束條件(Constraint)均為線性的；目標(biāo)函數(shù)實(shí)現(xiàn)極大化或極小化。,2005年7月 龍子泉,第二節(jié) 線性規(guī)劃圖解法 (Graphical Solution),一、基本概念 可行解(Feasible Solu

5、tion)任一滿足約束條件的一組決策變量的數(shù)值； 可行域(Feasible Region)所有可行解組成的集合，也稱為可行解集； 目標(biāo)函數(shù)等值線(Objective function line)為于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值； 二、圖解法步驟(Procedure) （1）畫出線性規(guī)劃問題的可行域； （2）畫出兩條目標(biāo)函數(shù)等值線； （3）平行移動(dòng)目標(biāo)函數(shù)等值線，使目標(biāo)函數(shù)在可行域范圍內(nèi)達(dá)到最優(yōu)。,三、圖解法舉例,例1 max Z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,該問題有唯一最優(yōu)解 x1=50；x2=250,例2 max

6、Z=50 x1+50 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,B點(diǎn)和C點(diǎn)所代表的坐標(biāo)同時(shí)為最優(yōu)解，即該問題有無窮多最優(yōu)解,max Z=50 x1+100 x2,例3 max z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 問題有無界解 (unbounded) 例4 min z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 有唯一最優(yōu)解,例4 max z =x1+x2 x1 + 2x21 x1 + x22 x1、x20 問題無可行解 (no feasible solution),2005年7月 龍子泉,直 觀 結(jié) 論,可行域

7、可以是個(gè)凸多邊形，可能無界，也可能為空； 若線性規(guī)劃問題的最優(yōu)解存在，它一定可以在可行域的某一個(gè)頂點(diǎn)上得到； 若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則該兩點(diǎn)連線上的所有點(diǎn)都是最優(yōu)解，即LP有無窮多最優(yōu)解； 若可行域非空有界，則一定有最優(yōu)解。,2005年7月 龍子泉,四、線性規(guī)劃問題的標(biāo)準(zhǔn)形式(Standard form),規(guī)定如下形式的線性規(guī)劃數(shù)學(xué)模型為L(zhǎng)P標(biāo)準(zhǔn)形式。 max z=c1x1+c2x2+cnxn 目標(biāo)函數(shù) a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 約束條件 am1x1+am2x2+amnxn= bm x1，x2，xn0 特點(diǎn)：Zmax；約束條

8、件為等號(hào)；變量非負(fù)；右端常數(shù)項(xiàng)大等于零。 問題：n m why？,2005年7月 龍子泉,上述標(biāo)準(zhǔn)形式的線性規(guī)劃模型還可寫成如下一些形式:,(1) (2),(3),(5),(4),2005年7月 龍子泉,五、化非標(biāo)準(zhǔn)形為標(biāo)準(zhǔn)形,（1）若min f=cX 此時(shí)可令：z =f，則max z=min f =cX，這樣處理所得最優(yōu)解不變； 舉例： min z =x1x2 2x1 + x22 x1 + x21 x1、x20 max f =x1+ x2,(2)約束條件為“”時(shí)， aijxjbi aijxj + xn+i = bi xn+i 松弛變量(slack variable)； (3)約束條件為“”時(shí)

9、， aijxj bi aijxj xn+i = bi xn+i 過剩變量(surplus variable)； 這樣處理所得最優(yōu)解不變； max z =x1+10 x2 x1 + 2x2100 x1、x20,max z =x1+10 x2 x1 + 2x2 + x3=100 x1、x20,（4）若xk為無限制， 則令xk=xk1xk2，其中xk1、xk20 （5）若bi 0 舉例: 化下列線性規(guī)劃為標(biāo)準(zhǔn)形 max z=2x1+2x24x3 x1 + 3x23x3 30 x1 + 2x24x380 x1、x20，x3無限制,max z=2x1+2x24x3+4x3” x1 + 3x23x3+3x

10、3” x4 = 30 x1 + 2x24x3+ 4x3” + x5 = 80 x1、x2 、x3、x3” 、x4、x5 0,2005年7月 龍子泉,第三節(jié) 線性規(guī)劃問題解的性質(zhì) (Properties of Solution of LP),一、線性規(guī)劃問題的基本概念(concepts) 對(duì)于標(biāo)準(zhǔn)形式的線性規(guī)劃： max z=cX （a） AX=b X0 （b） 可行解(feasible solution)滿足約束條件（b）的點(diǎn)X=（x1，x2，xn）T稱為該LP的一個(gè)可行解； 最優(yōu)解(optimal solution)使目標(biāo)函數(shù)值達(dá)到最大的可行解,3基、基變量、非基變量 (base, basi

11、c variable, nonbasic variable),設(shè)約束方程的系數(shù)矩陣A中，有m個(gè)線性無關(guān)的列向量， 且設(shè) B=（P1，P2，Pm）線性無關(guān)，則稱B為該LP的一個(gè)基； 相應(yīng)的 P1，P2，Pm為基向量； 與之對(duì)應(yīng)的變量 x1，x2，xm基變量，記為：XB= （x1，x2，xm）T ； 其余的向量為非基向量，記為：N=（Pm+1，Pm+2，Pn）； 其余的變量為非基變量 ，記為：XN=（xm+1，xm+2，xn）T；,4基本解 (basic solution),將AX=b改寫 （B，N）（XB，XN）T=b 有： BXB=bNXN 令 XN=0 得到 BXB=b 線性方程組。 由于B

12、中各列向量線性無關(guān)，因此解此方程組有唯一解 即： XB= （x10，x20，xm0）T 于是得到AX=b的一個(gè)確定的解： X0=（XB，XN）T =（x10，x20，xm0，0，0，0）T 稱X0為該線性規(guī)劃對(duì)應(yīng)與基B的一個(gè)基本解。,同樣，在A中任選m個(gè)線性無關(guān)的列向量都可以組成一個(gè)基，對(duì)應(yīng)基一個(gè)基本解。對(duì)于一個(gè)LP最多有多少呢？從n個(gè)中選m個(gè)進(jìn)行組合，即： Cnm=n！/（nm）！m！ 因此，基本解是有限的。 舉例：找出下列LP所有的基及其對(duì)應(yīng)的基本解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0

13、 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,2005年7月 龍子泉,二、線性規(guī)劃的基本定理(Theorems),定義 凸集設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)X(1)K，X(2)K的連線上所有的點(diǎn)X=X（1）+（1）X（2）K，（01），則稱K為凸集。 定理1 若線性規(guī)劃存在可行域，則其可行域R=X|AX=b，X0是凸集。 定理2 線性規(guī)劃問題的可行解X=（x1，x2，xn）T為基可行解的充要條件是：X的非零分量所對(duì)應(yīng)的系數(shù)列向量是線性無關(guān)的。 定理3 如果線性規(guī)劃有可行解，則一定有基可行解。 定理4 線性規(guī)劃

14、問題的基可行解對(duì)應(yīng)于可行域的頂點(diǎn)。 定理5 若線性規(guī)劃問題的可行域非空有界，則線性規(guī)劃問題的最優(yōu)解一定可以在其可行域的某個(gè)頂點(diǎn)上得到；,2005年7月 龍子泉,第四節(jié) 單純形法 (simplex method) (教材第五章P162-168),基本思想：在有限的基可行解中尋找最優(yōu)解。即，從初始基可行解出發(fā)，轉(zhuǎn)換到另一個(gè)基可行解，使目標(biāo)值增大，直到達(dá)到最優(yōu)解，或判斷出無最優(yōu)解為止。 一、引例 用單純形方法求解下列線性規(guī)劃 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2

15、 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,（1）找初始可行基：B1=（P3，P4）現(xiàn)成的初始可行基； 此時(shí)， XB=（x3，x4）T，XN=（x1，x2）T 用XN表示Z和XB有： max z=6x1+4x2 x3 =1002x13x2 +x4 =1204x12x2 令 XN=(0,0)T 有 XB=(100,120)T 則有： X（1）=（0，0，100，120）T為對(duì)應(yīng)于基B1的基可行解。 問： X（1）是否最優(yōu)呢？否 因?yàn)椋?x1和x2在目標(biāo)函數(shù)中的系數(shù)為正，當(dāng)x1，z；x2，z。 且： 稱非基變量在目標(biāo)函數(shù)中的系數(shù)為檢驗(yàn)數(shù)。,（2）尋找可行

16、基B2，使其對(duì)應(yīng)的基可行解X（2）能使目標(biāo)函數(shù)值增加。 選： x10 則有： X（2）=（x1，0，x3，x4）T 要使為X（2）基可行解，x3，x4中必有一個(gè)為零，而另一個(gè)大等于零。 只要取 x1=min100/2，120/4=30 就有 x3=40，x4=0 這樣 X（2）=（30，0，40，0）T 因?yàn)?P1，P3線性無關(guān)，因此，B2=（P1，P3）為一個(gè)基 而 X（2）為對(duì)應(yīng)于B2的基可行解 此時(shí) XB=（x1，x3）T，XN=（x2，x4）T 用XN表示Z和XB有： max z=180+2x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1

17、/2）x4 問： X（2）是否最優(yōu)呢？否 因?yàn)椋?x2在目標(biāo)函數(shù)中的系數(shù)為正，當(dāng)x2，z。,（3）尋找可行基B3，使其對(duì)應(yīng)的基可行解X（3）能使目標(biāo)函數(shù)值增加。 選： x20 則有： X（3）=（x1，x2，x3，0）T 要使為X（3）基可行解，x1，x3中必有一個(gè)為零，而另一個(gè)大等于零。 只要取 x2=min30/（1/2），40/2=20 就有 x1=20，x3=0 這樣 X（3）=（20，20，0，0）T 因?yàn)?P1，P2線性無關(guān)，因此，B3=（P1，P2）為一個(gè)基 而 X（3）為對(duì)應(yīng)于B3的基可行解 此時(shí) XB=（x1，x2）T，XN=（x3，x4）T 用XN表示Z和XB有： max

18、z=2001/2）x3（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3 +（1/4）x4 問： X（3）是否最優(yōu)呢？是， 求解過程：從引例可以總結(jié)出求解過程：（1）找出初始基及其基可行解；（2）判斷是否為最優(yōu)解，是停止，否則轉(zhuǎn)下一步；（3）轉(zhuǎn)換可行基，并求出相應(yīng)的基可行解，使目標(biāo)函數(shù)值有所改進(jìn)，轉(zhuǎn)（2）。,2005年7月 龍子泉,二、單純形方法 1檢驗(yàn)數(shù)( evaluation index),檢驗(yàn)數(shù)用非基變量表示目標(biāo)函數(shù)后，非基變量在目標(biāo)函數(shù)中的系數(shù) 設(shè)有標(biāo)準(zhǔn)形式的線性規(guī)劃問題：max z=cX；AX=b，X0； 現(xiàn)假定 A中存在一可行基B 又設(shè) B

19、=（P1，P2，Pm）；且B為單位陣 這樣 AX=b可以描述成如下形式，也就是用非基變量表示基變量 x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm 即 從上述約束方程中可以得到對(duì)應(yīng)于基B的基可行解 X=（b1，b2，bm，0，0）T,用非基變量表示目標(biāo)函數(shù)有： 令 有 式中 j為基可行解X的檢驗(yàn)數(shù)。 更一般性：,2005年7月 龍子泉,2最優(yōu)性檢驗(yàn)(optimality testing),判別定理1：設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切jJ（J為非基變量的下標(biāo)集）有

20、j0，則X為線性規(guī)劃的最優(yōu)解； 判別定理2：設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切jJ（J為非基變量的下標(biāo)集）有j0，同時(shí)有某個(gè)非基變量的檢驗(yàn)數(shù)k=0（kJ），則該線性規(guī)劃有無窮多最優(yōu)解； 判別定理3：設(shè)X為線性規(guī)劃的一個(gè)基可行解，若有k0（kJ），且Pk0，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。,3 單純形表(simplex tableau),對(duì)于線性規(guī)劃：max z=z0 + m+1xm+1 + + nxn x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm x1，

21、x2，xn0 列如下單純形表：,單純形表的說明與功能： （1）一個(gè)基對(duì)應(yīng)一個(gè)單純形表，且單純形表中必須有一個(gè)初始單位基。 （2）從單純表中，可立即得到一個(gè)基可行解，如上表中： X=（b1，b2，bm，0，0）T為基可行解。 （3）很容易計(jì)算檢驗(yàn)數(shù)，并可判別上述基可行解是否為最優(yōu)解或線性規(guī)劃問題無最優(yōu)解。 4. 單純形法計(jì)算步驟 （1）找出初始可行基，建立初始單純形表； （2）計(jì)算檢驗(yàn)數(shù)，若對(duì)于一切jJ有j0，則已得到線性規(guī)劃的最優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)下一步； （3）若有k0（kJ），且Pk0，則該線性規(guī)劃問題具有無界解（無最優(yōu)解），停止計(jì)算，否則轉(zhuǎn)下一步； （4）根據(jù)maxj|j0=k，確定

22、xk為換入變量； 按規(guī)則確定換出變量，即 =bi/aik|aik0=bs/ask，對(duì)應(yīng)的xs為換出變量，轉(zhuǎn)下一步； （5）以ask為主元素進(jìn)行迭代，得新的單純形表，轉(zhuǎn)（2）,2005年7月 龍子泉,三、單純形法解題舉例,例1：用單純形法求解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0 找初始可行基：B1=（P3，P4）現(xiàn)成的初始可行基；,從表中有：X（1）=（0，0，100，1

23、20）T為對(duì)應(yīng)于基B1的基可行解，顯然不是最優(yōu)解； 根據(jù)maxj|j0=1，確定x1為換入變量； 按規(guī)則確定換出變量，即：=bi/aik|aik0=120/4，對(duì)應(yīng)的x4為換出變量；,列初始單純形表,以4為主元素進(jìn)行迭代，得新的單純形表： 從表中有：X（2）=（30，0，40，0）T為對(duì)應(yīng)于基B2的基可行解，顯然不是最優(yōu)解； 根據(jù)maxj|j0=2，確定x2為換入變量； 按規(guī)則確定換出變量，即：=bi/aik|aik0=40/2，對(duì)應(yīng)的x3為換出變量；,表中j0，j=1，4， 因此得最優(yōu)解：X*=（20，20，0，0）T，Z*=200,以2為主元素進(jìn)行迭代，得新的單純形表：,將上述計(jì)算列在一個(gè)

24、表中為：,Cj6400b CB XB x1x2x3x4 0 x3 2310100100/2 0 x4 4201120120/4(min) z 64000 0 x3021-1/24040/2(min) 6 x111/201/43030/(1/2) Z 010-3/8180 4 x2011/2-1/420 6 x110-1/43/820 Z00 -1/2-5/4200,例2：用單純形法求解 max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,例3：用單純形法求解 max z=2x1+x2 x1 + x25 2x15x210 x1、x20 2

25、=6 0，且P20，故該線性規(guī)劃有無界解。,例4：用單純形法求解 max z=6x1+2x2+10 x3+8x4 5x1 + 6x24x34x420 3x13x2 +2x3 + 8x425 4x12x2 + x3 + 3x410 x1、x2、x3、x40 7=340, p70,故該LP有無解解,2005年7月 龍子泉,四、極小化問題(Minimization Problem),若標(biāo)準(zhǔn)形式的線性規(guī)劃問題的目標(biāo)函數(shù)是極小化形式，則問題的判別準(zhǔn)則就會(huì)有所改變。這樣三個(gè)判別定理如下： 判別定理1：設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切jJ（J為非基變量的下標(biāo)集）有j 0，則X為線性規(guī)劃的最優(yōu)解； 判

26、別定理2：設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切jJ（J為非基變量的下標(biāo)集）有j 0，同時(shí)有某個(gè)非基變量的檢驗(yàn)數(shù)k=0（kJ），則該線性規(guī)劃有無窮多最優(yōu)解； 判別定理3：設(shè)X為線性規(guī)劃的一個(gè)基可行解，若有k 0（kJ），且Pk0，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。,2005年7月 龍子泉,上述單純形法的基礎(chǔ)是線性規(guī)劃問題有初始基可行解。有些線性規(guī)劃問題化為標(biāo)準(zhǔn)形式以后，就存在初始可行基，如約束條件全部為“”的線性規(guī)劃問題。對(duì)于標(biāo)準(zhǔn)形式的線性規(guī)劃問題，若約束方程系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則不能簡(jiǎn)單的用上述單純形法，而通常采用所謂的人工變量法。人工變量法一般有大M法和兩階段法。,五

27、、人工變量法(Artificial Variable Method),（一）大M法(Big M method) 對(duì)于標(biāo)準(zhǔn)形式的線性規(guī)劃問題（問題A） max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0 若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則引入所謂的人工變量xn+1，xn+m構(gòu)造如下形式的線性規(guī)劃問題（問題B） max z=c1x1+c2x2+cnxnMxn+1Mxn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a

28、22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0,問題B中M為任意大的正數(shù)。顯然問題B存在現(xiàn)成的單位基，且初始基可行解中，以人工變量為基變量。 關(guān)于問題B的幾點(diǎn)結(jié)論： （1）問題B要實(shí)現(xiàn)極大化，必須將人工變量從基變量中換出，否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)極大化； （2）若在求解問題B的過程中，已將人工變量從基變量中換出，則已得到問題A的一個(gè)基可行解，可繼續(xù)求解，以獲得問題A的最優(yōu)解或判別問題A無最優(yōu)解； （3）若求解問題B已得到最優(yōu)解，但最優(yōu)解的基變量中含有不為零人工變量，則問題A無可行解； （4）若求解問題B

29、已得到最優(yōu)解，且最優(yōu)解的基變量中不含有人工變量，則問題B的最優(yōu)解就是問題A的最優(yōu)解。,例：用單純形法（大M法）求解 max z=3x12x2x3 x1 2x2 + x3 11 4x1 + x2 +2x3 3 2x1 x3 = 1 x1、x2、x30 解：化為標(biāo)準(zhǔn)形式，并引入人工變量，構(gòu)造如下模型： max z=3x12x2x3Mx6Mx7 x12x2 + x3 + x4 = 11 4x1 + x2 +2x3 x5 + x6 = 3 2x1 x3 +x7 = 1 x1、x2、x30 列表計(jì)算：,（二）兩階段法 對(duì)于標(biāo)準(zhǔn)形式的線性規(guī)劃問題（問題A） max z=c1x1+c2x2+cnxn a11

30、x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0 若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則引入所謂的人工變量xn+1，xn+m構(gòu)造如下輔助線性規(guī)劃問題（問題C） min w =xn+1 + + xn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0,關(guān)于問題C的幾點(diǎn)結(jié)論： （1）由于問題C為極小化問題，且目標(biāo)函數(shù)有下界，因此問題C肯定有最優(yōu)解； （2）求解問題C已得到其最優(yōu)解，若問題C最優(yōu)解所對(duì)應(yīng)目標(biāo)函數(shù)值w0，則原問題A無可行解，若問題C所對(duì)應(yīng)目標(biāo)函數(shù)值w =0，則已得到原問題A的一個(gè)基可行解； 因此問題的求解有如下兩