第02章-單純形法120404

1、1第第2 2章章線性規(guī)劃概念、建線性規(guī)劃概念、建模與求解模與求解本章內(nèi)容重點本章內(nèi)容重點 線性規(guī)劃模型結(jié)構(gòu)線性規(guī)劃模型結(jié)構(gòu) 線性規(guī)劃解的基本概念與性質(zhì)線性規(guī)劃解的基本概念與性質(zhì) 線性規(guī)劃單純形法線性規(guī)劃單純形法 線性規(guī)劃應(yīng)用線性規(guī)劃應(yīng)用-建模建模 某工廠擁有某工廠擁有A A、B B、C C 三種類型的設(shè)備，三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三設(shè)備可利用的時數(shù)如下表所示：利潤以及三設(shè)備可利用的時數(shù)如下表所示：問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總問題：工廠

2、應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？利潤？例例4模型模型解：設(shè)變量解：設(shè)變量 xi 為第為第 i 種（甲、乙）產(chǎn)品種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（的生產(chǎn)件數(shù)（i1，2）。）。目標(biāo)函數(shù)目標(biāo)函數(shù) Max z =1500 x1+2500 x2約束條件約束條件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 5線性規(guī)劃的一般模型結(jié)構(gòu)：線性規(guī)劃的一般模型結(jié)構(gòu)：目標(biāo)函數(shù)：目標(biāo)函數(shù)： Max(Min) z = c1x1 + c2x2 + + cnxn約束條件：約束條件： a11x1+a12x2+a1nxn( =, )b1 a21x1+a22x2+a2nxn( =, )b

3、2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 06 a11x1+a12x2+ +a1n xn b1 a21x1+a22x2+ +a2n xn b2 . . . am1x1+am2x2 +amnxn bm x1 ，x2 ， ，xn 02.3.1 線性規(guī)劃問題的規(guī)范形式和標(biāo)準(zhǔn)形式線性規(guī)劃問題的規(guī)范形式和標(biāo)準(zhǔn)形式(1) 線性規(guī)劃規(guī)范形式線性規(guī)劃規(guī)范形式目標(biāo)函數(shù)：目標(biāo)函數(shù)： Max z = c1x1 + c2x2 + + cnxn約束條件：約束條件：7 線性規(guī)劃規(guī)范形式的特點線性規(guī)劃規(guī)范形式的特點規(guī)范形式有如下四個特點：規(guī)范形式有如下四個特點：目標(biāo)最大

4、化目標(biāo)最大化約束為小于等于的不等式約束為小于等于的不等式?jīng)Q策變量均非負(fù)決策變量均非負(fù)右端項非負(fù)右端項非負(fù)。 0.xbAxtsxczMaxT8Max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)：目標(biāo)函數(shù)： 約束條件：約束條件：9 線性規(guī)劃標(biāo)準(zhǔn)形式的特點線性規(guī)劃標(biāo)準(zhǔn)形式的特點標(biāo)準(zhǔn)形式有如下四個特點：標(biāo)準(zhǔn)形式有如下四個特點： 目標(biāo)最大化目標(biāo)

5、最大化 約束為等式約束為等式 決策變量均非負(fù)決策變量均非負(fù) 右端項非負(fù)右端項非負(fù)。 對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，總可以通過以下變換，將其轉(zhuǎn)問題，總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式: :10設(shè)目標(biāo)函數(shù)為設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + + cnxn 則可以令則可以令z-f ，該極小化問題與下面的極，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即大化問題有相同的最優(yōu)解，即 Max z = -c1x1 - c2x2 - - cnxn 但必須注意，盡管以上兩個問題的最優(yōu)但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目

6、標(biāo)函數(shù)值卻相解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即差一個符號，即 Min f - Max z 線性規(guī)劃標(biāo)準(zhǔn)形式的轉(zhuǎn)化：線性規(guī)劃標(biāo)準(zhǔn)形式的轉(zhuǎn)化： 極小化目標(biāo)函數(shù)的問題：極小化目標(biāo)函數(shù)的問題：11設(shè)約束條件為設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個新的變量可以引進(jìn)一個新的變量s ，使它等于，使它等于約束右邊與左邊之差約束右邊與左邊之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即s0， 這時新的約束條件成為這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn

7、+s = bi 約束條件不是等式（約束條件不是等式（）的問題）的問題12當(dāng)約束條件為當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時，類似地令時，類似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即s0，這時新的約束條件成為這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi約束條件不是等式（約束條件不是等式（）的問題）的問題13 為了使約束由不等式成為等式而為了使約束由不等式成為等式而引進(jìn)的變量引進(jìn)的變量 s 稱為稱為“松弛變量松弛變量”。 如果原問題中有若干個非等式約如

8、果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量。對各個約束引進(jìn)不同的松弛變量。14Min f = 3.6 x1 - 5.2 x2 + 1.8 x3s.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 例例2.6 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式解：首先解：首先, ,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令令 z= -f = -3.6x1+5.2x2-1.8x3 1

9、5 x4，x5 0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：性規(guī)劃問題： Max Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.t. 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 2個不等式約束，引進(jìn)個不等式約束，引進(jìn)松弛變量松弛變量16 當(dāng)某一個變量當(dāng)某一個變量xj沒有非負(fù)約束時，沒有非負(fù)約束時，可以令可以令 xj = xj- xj”其中其中 xj0，xj”

10、0即用兩個非負(fù)變量之差來表示一個無符即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然號限制的變量，當(dāng)然xj的符號取決于的符號取決于xj和和xj”的大小。的大小。變量無符號限制的問題變量無符號限制的問題 在標(biāo)準(zhǔn)形式中，必須每一個變量均在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。有非負(fù)約束。17 當(dāng)某一個右端項系數(shù)為負(fù)時，如當(dāng)某一個右端項系數(shù)為負(fù)時，如果果 bi m， 秩秩(A) = m，b Rm 。約束等式實質(zhì)上是一個由約束等式實質(zhì)上是一個由m個方程個方程n個變個變量構(gòu)成的方程組，有無窮多組解。記：量構(gòu)成的方程組，有無窮多組解。記： x = (x1，x2，xn)T 25 如果令其中如果令其中n

11、-m個變量為零，當(dāng)其個變量為零，當(dāng)其他他 m個變量在線性方程組中有唯一解時，個變量在線性方程組中有唯一解時，則這則這 n個變量的值構(gòu)成此方程組的一個個變量的值構(gòu)成此方程組的一個解。若進(jìn)一步有這解。若進(jìn)一步有這 n 個變量的值都非負(fù)個變量的值都非負(fù)時，這個解就是線性規(guī)劃可行域的一個時，這個解就是線性規(guī)劃可行域的一個極點。極點。 根據(jù)以上分析，我們建立以下概念根據(jù)以上分析，我們建立以下概念 基；基； 基變量、非基變量基變量、非基變量 基本解、基本可行解（極點）基本解、基本可行解（極點） 可行基、最優(yōu)基可行基、最優(yōu)基(1) 線性規(guī)劃的基：線性規(guī)劃的基： 對于線性規(guī)劃的約束條件對于線性規(guī)劃的約束條件

12、Ax=b， x0 設(shè)設(shè)B是是A矩陣中的一個非奇異矩陣中的一個非奇異（可逆）的（可逆）的mm子矩陣，則稱子矩陣，則稱B為線性規(guī)劃的一個基。為線性規(guī)劃的一個基。 A=( p1 ，p2 ，pn ) ，其中，其中 pj=( a1j ，a2j ，amj )T Rm ， 任取任取 A 中的中的 m 個線性無關(guān)列向量個線性無關(guān)列向量構(gòu)成矩陣構(gòu)成矩陣那么那么B為線性規(guī)劃的一個基。為線性規(guī)劃的一個基。 稱對應(yīng)于基稱對應(yīng)于基B的變量的變量為為基變量基變量；其余變量稱為；其余變量稱為非基變量非基變量。27mjjjjRPpppBim ),(21mjjjxxx,21矩陣描述矩陣描述 設(shè)設(shè)B是線性規(guī)劃的一個基，則是線性規(guī)

13、劃的一個基，則A可以可以表示為表示為 A= B , N x 也可相應(yīng)地分成也可相應(yīng)地分成 xB 和和 xN 其中其中xB為為m維列向量，它的各分量維列向量，它的各分量稱為基變量，與基稱為基變量，與基B的列向量對應(yīng)；的列向量對應(yīng)；xN為為n-m列向量，它的各分量稱為非基變列向量，它的各分量稱為非基變量，與非基矩陣量，與非基矩陣N的列向量對應(yīng)。的列向量對應(yīng)。(2) 線性規(guī)劃問題的基本可行解：線性規(guī)劃問題的基本可行解：對應(yīng)于基對應(yīng)于基B，約束等式，約束等式 Ax = b 可表示為可表示為 xB B,N = b 或或 BxB + NxN = b xN則基變量則基變量 xB = B-1b - B-1Nx

14、N 當(dāng)取當(dāng)取 xN = 0，這時有，這時有xB = B-1b 。稱。稱這類特別的解為這類特別的解為基本解基本解。30 進(jìn)一步，若得到的基變量進(jìn)一步，若得到的基變量的值均非負(fù)，即的值均非負(fù)，即 B-1 b 0 ，則稱為則稱為基本可行解基本可行解，同時稱這，同時稱這個基個基 B 為為可行基可行基。例例2.8 把例把例2.1的線性規(guī)劃模型標(biāo)準(zhǔn)化，的線性規(guī)劃模型標(biāo)準(zhǔn)化，引入松馳變量引入松馳變量 x3 ，x4 ，x5 0，得到，得到Max z = 1500 x1 + 2500 x2s.t. 3x1+2x2+x3 = 65 (A) 2x1+ x2 +x4 = 40 (B) 3x2 +x5= 75 (C)

15、x1 , x2 , x3 , x4 , x5 0 用用(D), (E), (F), (G), (H) 分別表示分別表示 x1=0、x2=0、x3=0、x4=0、x5=0 這里一共有這里一共有8 8個約束條件，其中個約束條件，其中 3 3 個等式約束。對此，任意固定兩個變個等式約束。對此，任意固定兩個變量為零，通過解等式構(gòu)成的方程組（量為零，通過解等式構(gòu)成的方程組（相當(dāng)于求解由其中相當(dāng)于求解由其中 5 5 個方程構(gòu)成的方個方程構(gòu)成的方程組），可解得一個點。程組），可解得一個點。 由于當(dāng)由于當(dāng) x2 = x5 = 0 時，即由時，即由(A), (B), (C), (E), (H)構(gòu)成的方程組無解。

16、構(gòu)成的方程組無解。故總故總共可求得共可求得9 9個點。個點。33 問題圖示中的約束直線交點與此對應(yīng)問題圖示中的約束直線交點與此對應(yīng)34約束條件約束條件(A)、(B)、(C)、(F)、(G)的解的解對應(yīng)于對應(yīng)于直線直線A、B的交點的交點，即：，即： x(1) = (15,10,0,0,45)T約束條件約束條件(A)、(B)、(C)、(F)、(H)的的解對應(yīng)于解對應(yīng)于直線直線A、C的交點的交點，即：，即： x(2) = (5,25,0,5,0)T約束條件約束條件(A)、(B)、(C)、(D)、(F)的解的解對應(yīng)于對應(yīng)于直線直線A、D的交點的交點，即：，即： x(3) = (0,32.5,0,7.5

17、,-22.5)T35約束條件約束條件(A)、(B)、(C)、(E)、(F)的解對的解對應(yīng)于應(yīng)于直線直線A、E的交點的交點，即：，即： x(4) = (65/3,0,0,-10/3,75)T約束條件約束條件(A)、(B)、(C)、(G)、(H)的解對的解對應(yīng)于應(yīng)于直線直線B、C的交點的交點，即：，即： x(5) = (7.5,25,-7.5,0,0)T約束條件約束條件(A)、(B)、(C)、(D)、(G)的解對的解對應(yīng)于應(yīng)于直線直線B、D的交點的交點，即：，即： x(6) = (0,40,-15,0,-45)T36約束條件約束條件(A)、(B)、(C)、(E)、(G)的解的解對應(yīng)于對應(yīng)于直線直線

18、B、E的交點的交點，即：，即： x(7) = (20,0,5,0,75)T約束條件約束條件(A)、(B)、(C)、(D)、(H)的解的解對應(yīng)于對應(yīng)于直線直線C、D的交點的交點，即：，即： x(8) = (0,25,15,15,0)T約束條件約束條件(A)、(B)、(C)、(D)、(E)的解的解對應(yīng)于對應(yīng)于直線直線D、E的交點的交點，即：，即： x(9) = (0,0,65,40,75)T37 如果交點的坐標(biāo)如果交點的坐標(biāo) (x1 , x2 , x3 , x4 , x5 )T均非負(fù)，則該交點就對應(yīng)于線性規(guī)劃均非負(fù)，則該交點就對應(yīng)于線性規(guī)劃可行域的極點可行域的極點 ( 約束多邊形的頂點，約束多邊形

19、的頂點，如圖中如圖中A, B; A, C; B, E; C, D和和D, E的的交點交點)；否則，該交點不在可行域內(nèi)。；否則，該交點不在可行域內(nèi)。 我們令我們令2個決策變量為零，可以將個決策變量為零，可以將 5 個線性方程組個線性方程組的求解轉(zhuǎn)化為的求解轉(zhuǎn)化為 3 個方個方程組程組的求解，簡便且更有價值。的求解，簡便且更有價值。例如，例如，A、B交點對應(yīng)于交點對應(yīng)于x3 = 0， x4 = 0；在等式約束中令在等式約束中令x3 = 0，x4 = 0，解，解3個等個等式約束方程：式約束方程：可得到可得到 x1 =15，x2 = 10，x5 = 45。即。即A, B交點對應(yīng)的極點交點對應(yīng)的極點 x

20、 = (15, 10, 0, 0, 45)T。 由于所有分量都為非負(fù)，因此由于所有分量都為非負(fù)，因此A, B交點是可行域的極點交點是可行域的極點 ( 頂點頂點 )。 7534026523522121xxxxxx39又知，又知，B, C交點對應(yīng)于交點對應(yīng)于 x4= 0，x5= 0，在等式約束中令在等式約束中令x4 = 0，x5 = 0，求，求得到得到 x1 =7.5, x2 = 25, x3 = -7.5。即。即B, C交點對應(yīng)于點交點對應(yīng)于點 x = ( 7.5, 25, -7.5, 0, 0 )T。B, C交點不是可行域的極點。交點不是可行域的極點。 同樣可以討論其他交點的情況同樣可以討論其

21、他交點的情況 7534026523221321xxxxxx40可以證明：可以證明：線性規(guī)劃的基本可行解就是線性規(guī)劃的基本可行解就是可行域的極點可行域的極點。 這個結(jié)論被稱為這個結(jié)論被稱為線性規(guī)劃的基本定線性規(guī)劃的基本定理理，重要性在于，重要性在于下列的聯(lián)系：下列的聯(lián)系： 可行域極點可行域極點 幾何概念幾何概念 最優(yōu)解特征最優(yōu)解特征 基本可行解基本可行解 代數(shù)概念代數(shù)概念 可代數(shù)求解可代數(shù)求解 為求解線性規(guī)劃問題提供有效途徑為求解線性規(guī)劃問題提供有效途徑41例例2.9考慮例考慮例2.82.8的線性規(guī)劃模型的線性規(guī)劃模型 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 +

22、2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 注意，注意，線性規(guī)劃的基本解、基本可行線性規(guī)劃的基本解、基本可行 解（極點）和可行基解（極點）和可行基只與線性規(guī)劃問只與線性規(guī)劃問 題標(biāo)準(zhǔn)形式的約束條件有關(guān)題標(biāo)準(zhǔn)形式的約束條件有關(guān)。42 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

23、 ，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） 43 其中其中 B4 = 0，因而，因而B4不是該線性規(guī)劃不是該線性規(guī)劃問題的基。其余均為非奇異方陣，因此該問題的基。其余均為非奇異方陣，因此該問題共有問題共有9個基。個基。 例：對于基例：對于基B3=p1 ，p2 ，p5，令非基，令非基變量變量x3 = 0， x4 = 0，解等式約束構(gòu)成的線，解等式約束構(gòu)成的線性方程組：性方程組： 3 x1 + 2 x2 +

24、 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 44 得到得到 x1 =15，x2 = 10，x5 = 45，對應(yīng)，對應(yīng)的基本可行解：的基本可行解：x = (15, 10, 0, 0, 45)T。于是，它對應(yīng)的基于是，它對應(yīng)的基B3是一個可行基。是一個可行基。類似可得到類似可得到 x(2) = (5,25,0,5,0)T （對應(yīng)（對應(yīng)B2） x(7) = (20,0,5,0,75)T （對應(yīng)（對應(yīng)B5） x(8) = (0,25,15,15,0)T （對應(yīng)（對應(yīng)B7） x(9) = (0,0,65,40,75)T （對應(yīng)（對應(yīng)B10

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

26、可行基，則計算相應(yīng)的基本可若是可行基，則計算相應(yīng)的基本可行解以及相應(yīng)解的目標(biāo)函數(shù)值；行解以及相應(yīng)解的目標(biāo)函數(shù)值； 比較各基本可行解的目標(biāo)函數(shù)值，比較各基本可行解的目標(biāo)函數(shù)值，求得最優(yōu)解。求得最優(yōu)解。 由于基的個數(shù)是有限的由于基的個數(shù)是有限的( ( 個個),),因此必定可以從有限個基本可行解中因此必定可以從有限個基本可行解中找到最優(yōu)解。找到最優(yōu)解。mnC 472.4 2.4 線性規(guī)劃單純形法線性規(guī)劃單純形法2.4.12.4.1單純形法的基本思路及其實現(xiàn)單純形法的基本思路及其實現(xiàn)、單純形法的基本思路、單純形法的基本思路 通過求線性規(guī)劃問題基本可行解通過求線性規(guī)劃問題基本可行解( (極點極點) )尋

27、找最優(yōu)解的方法稱尋找最優(yōu)解的方法稱窮舉法窮舉法，計算量非常，計算量非常大，造成困難。大，造成困難。 一種很自然的想法是，能否不求所有的一種很自然的想法是，能否不求所有的基本可行解，按照一定規(guī)則只求部分基本基本可行解，按照一定規(guī)則只求部分基本可行解來達(dá)到最優(yōu)解呢？可行解來達(dá)到最優(yōu)解呢？ 單純形法提供了單純形法提供了一種這樣的思路和準(zhǔn)則一種這樣的思路和準(zhǔn)則。48單純形法的基本思路單純形法的基本思路 首先找到一個基本可行解首先找到一個基本可行解( (極點極點) )； 利用給定準(zhǔn)則判斷該極點的最優(yōu)性：利用給定準(zhǔn)則判斷該極點的最優(yōu)性： 若該極點是最優(yōu)解，或得出無有限最優(yōu)解的若該極點是最優(yōu)解，或得出無有限

28、最優(yōu)解的結(jié)論則停止；否則，結(jié)論則停止；否則， 沿著可行域的邊界搜索一個相鄰的極沿著可行域的邊界搜索一個相鄰的極點：點：要求新極點的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值要求新極點的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差；差； 再對新極點進(jìn)行最優(yōu)性判斷。重復(fù)再對新極點進(jìn)行最優(yōu)性判斷。重復(fù)此過程。此過程。49單純形法單純形法計算流程計算流程3個問題：初始基本可行解的確定？判斷？個問題：初始基本可行解的確定？判斷？ 求新的基本可行解？求新的基本可行解？初始基本可行解初始基本可行解是否最優(yōu)解或是否最優(yōu)解或無限最優(yōu)解無限最優(yōu)解? ?結(jié)束結(jié)束沿邊界找新沿邊界找新的基本可行解的基本可行解NY單純形法的基本原理單純形法的基本原理

29、對于一個基，當(dāng)非基變量確定以后，基變對于一個基，當(dāng)非基變量確定以后，基變量和目標(biāo)函數(shù)的值也隨之確定?？梢缘玫搅亢湍繕?biāo)函數(shù)的值也隨之確定?？梢缘玫接梅腔兞勘硎镜幕兞亢湍繕?biāo)函數(shù)的表用非基變量表示的基變量和目標(biāo)函數(shù)的表達(dá)式，這時非基變量是自由變量。特別稱達(dá)式，這時非基變量是自由變量。特別稱這時的目標(biāo)函數(shù)為這時的目標(biāo)函數(shù)為典式典式。 對應(yīng)的基本可行解對應(yīng)的基本可行解中非基變量均為零中非基變量均為零。 換基換基：從一個極點沿可行域邊界移動到相：從一個極點沿可行域邊界移動到相鄰的極點時，所有非基變量中只有一個變鄰的極點時，所有非基變量中只有一個變量的值從量的值從0 0增加，其他非基變量的值都保持增加，

30、其他非基變量的值都保持0 0不變，直至有一個基變量下降為不變，直至有一個基變量下降為0 0。502 2、線性規(guī)劃的典式形式、線性規(guī)劃的典式形式 考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題：51 Max z = c1x1 + c2x2 + + cnxn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . . . . am1 x1 + am2 x2 + + amn xn = bm x1 , x2 , , xn 0 x1 c1 b1 a11 a12 . a1n x2 c2 b2 a21 a22

31、 . a2nx = . c = . B = . A = . . . . . . . . . xn cn bm am1 am2 . amn 一些符號表示：一些符號表示： 通過運算，所有的基變量都可以用非基變通過運算，所有的基變量都可以用非基變量來表示：量來表示：52矩陣矩陣A可表示為：可表示為：A = ( p1 ，p2 ，pn ) ， 其中其中 pj = ( a1j ，a2j ，amj )T Rm。若找到一個可行基，無防設(shè)若找到一個可行基，無防設(shè) B = ( p1 ，p2 ，pm ) ，則則m個基變量為個基變量為 x1 , x2 , , xm，n-m個非基變個非基變量為量為 xm+1 ，xm+2

32、 ，xn ?；兞颗c目標(biāo)函數(shù)的表達(dá)式基變量與目標(biāo)函數(shù)的表達(dá)式 我們把由非基變量表示的目標(biāo)函數(shù)形式稱我們把由非基變量表示的目標(biāo)函數(shù)形式稱為基為基B B相應(yīng)的目標(biāo)函數(shù)相應(yīng)的目標(biāo)函數(shù)典式典式。53 x1=b1 (a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2 (a2m+1xm+1+a2m+2xm+2+a2nxn） . . . xm=bm (amm+1xm+1+amm+2xm+2+amnxn） 把它們代入目標(biāo)函數(shù)，得把它們代入目標(biāo)函數(shù)，得 z = z+ m+1xm+1+ m+2xm+2+ nxn其中其中 j = cj (c1a1j + c2a2j + + cm amj )基變量與目標(biāo)

33、函數(shù)表達(dá)式的矩陣形式基變量與目標(biāo)函數(shù)表達(dá)式的矩陣形式 矩陣形式：矩陣形式： 向量形式：向量形式：54NTBTNTBNBxNBccbBczNxBbBx)(1111 nmjjjTBjTBnmjjjBxpBccbBczxpBbBx111111)(55、初始基本可行解、初始基本可行解 初始基本可行解應(yīng)該初始基本可行解應(yīng)該容易得到容易得到。 對規(guī)范形式的線性規(guī)劃問題，確定初始基本可行對規(guī)范形式的線性規(guī)劃問題，確定初始基本可行解的方法是：解的方法是：以松馳變量為基變量，其余以松馳變量為基變量，其余變量為非基變量。變量為非基變量。 說明：在化標(biāo)準(zhǔn)形式時，在每個約束條件的左端說明：在化標(biāo)準(zhǔn)形式時，在每個約束條

34、件的左端增加了一個松馳變量，這些松馳變量的系數(shù)構(gòu)成了增加了一個松馳變量，這些松馳變量的系數(shù)構(gòu)成了一組單位向量，令非基變量（原變量）全部為零，一組單位向量，令非基變量（原變量）全部為零，求解約束線性方程組，各松馳變量的取值就是其對求解約束線性方程組，各松馳變量的取值就是其對應(yīng)的右端項的值，而右端項非負(fù)，所以這一基本解應(yīng)的右端項的值，而右端項非負(fù)，所以這一基本解是可行解，即極點。是可行解，即極點。、單純形法的基本步驟、單純形法的基本步驟(1) (1) 尋找一個初始的可行基和相應(yīng)尋找一個初始的可行基和相應(yīng)基本可行解（極點），基本可行解（極點），確定基變量確定基變量、非基變量以及基變量、非基變量、非基

35、變量以及基變量、非基變量（全部等于（全部等于0 0）和目標(biāo)函數(shù)的值，并）和目標(biāo)函數(shù)的值，并將目標(biāo)函數(shù)和基變量分別用非基變將目標(biāo)函數(shù)和基變量分別用非基變量表示量表示; ;56(2) 在目標(biāo)函數(shù)典式表達(dá)式中，我們稱非在目標(biāo)函數(shù)典式表達(dá)式中，我們稱非基變量基變量 xj 的系數(shù)為檢驗數(shù)記為的系數(shù)為檢驗數(shù)記為 j 。 若若 j 0，那么相應(yīng)的非基變量，那么相應(yīng)的非基變量 xj 的的值從當(dāng)前值值從當(dāng)前值0開始增加時，目標(biāo)函數(shù)值隨開始增加時，目標(biāo)函數(shù)值隨之增加。這個選定的非基變量之增加。這個選定的非基變量 xj 稱為稱為“進(jìn)基變量進(jìn)基變量”，轉(zhuǎn)，轉(zhuǎn)(3)； 如果任何一個非基變量的值增加都不如果任何一個非基變

36、量的值增加都不能使目標(biāo)函數(shù)值增加，即所有能使目標(biāo)函數(shù)值增加，即所有 j 非正，非正，則當(dāng)前的基本可行解就是最優(yōu)解，計算則當(dāng)前的基本可行解就是最優(yōu)解，計算結(jié)束；結(jié)束；57 (3) 觀察非基變量表示的基變量表達(dá)式觀察非基變量表示的基變量表達(dá)式:當(dāng)進(jìn)基變量增加時，若有基變量的取值當(dāng)進(jìn)基變量增加時，若有基變量的取值下降，確定這些基變量的值在進(jìn)基變量下降，確定這些基變量的值在進(jìn)基變量增加過程中首先減少到增加過程中首先減少到0的變量的變量xr ，令，令 = min bi /aij aij 0 = br /arj這個基變量這個基變量xr稱為稱為“出基變量出基變量”。當(dāng)進(jìn)。當(dāng)進(jìn)基變量的值增加到基變量的值增加到

37、 時，出基變量時，出基變量xr的的值降為值降為0時，當(dāng)前極點就移動到了相鄰的時，當(dāng)前極點就移動到了相鄰的基本可行解（極點），轉(zhuǎn)基本可行解（極點），轉(zhuǎn)(4) ；58 如果當(dāng)進(jìn)基變量的值增加時，所有如果當(dāng)進(jìn)基變量的值增加時，所有基變量的值都不減少，即所有基變量的值都不減少，即所有aij 非正，非正，則表示可行域是不封閉的，且目標(biāo)函數(shù)則表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無限增加，此值隨進(jìn)基變量的增加可以無限增加，此時，時，不存在有限最優(yōu)解不存在有限最優(yōu)解，計算結(jié)束；，計算結(jié)束；(4) (4) 將進(jìn)基變量作為新的基變量，出基將進(jìn)基變量作為新的基變量，出基變量作為新的非基變量，確定新

38、的基本變量作為新的非基變量，確定新的基本可行解和新的目標(biāo)函數(shù)值。在新的基變可行解和新的目標(biāo)函數(shù)值。在新的基變量、非基變量的基礎(chǔ)上重復(fù)量、非基變量的基礎(chǔ)上重復(fù)(1)(1)。59例例 用單純形法的基本思路解線性規(guī)劃問題用單純形法的基本思路解線性規(guī)劃問題60 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 061第一次迭代：第一次迭代：（1）取初始可行基）取初始可行基B10= (p3 , p4 , p5)，那么，那么x3 ，x4

39、 ，x5為基變量，為基變量，x1 ，x2為非基變量。將基為非基變量。將基變量和目標(biāo)函數(shù)用非基變量表示：變量和目標(biāo)函數(shù)用非基變量表示： z =1500 x1+2500 x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2當(dāng)非基變量當(dāng)非基變量x1，x2=0時，相應(yīng)的基變量和目時，相應(yīng)的基變量和目標(biāo)函數(shù)值為標(biāo)函數(shù)值為x3=65，x4=40，x5= 75，z = 0，得到當(dāng)前的基本可行解：得到當(dāng)前的基本可行解：x=(0,0,65,40,75)T，z = 0 。這個解對應(yīng)于。這個解對應(yīng)于2.3.2中相應(yīng)圖中的中相應(yīng)圖中的D、E交點。交點。

40、62（2）選擇）選擇進(jìn)基變量進(jìn)基變量。在目標(biāo)函數(shù)在目標(biāo)函數(shù)z = 1500 x1 + 2500 x2中，非基變量中，非基變量x1，x2的系數(shù)都是正數(shù)，因此的系數(shù)都是正數(shù)，因此 x1 ，x2進(jìn)基進(jìn)基都可以使目標(biāo)函數(shù)都可以使目標(biāo)函數(shù)z增大，但增大，但x2的系數(shù)的系數(shù)為為2500，絕對值比，絕對值比x1的系數(shù)的系數(shù)1500大，大，因此把因此把x2作為進(jìn)基變量可以使目標(biāo)函作為進(jìn)基變量可以使目標(biāo)函數(shù)數(shù)z增加更快。選擇增加更快。選擇x2為進(jìn)基變量，使為進(jìn)基變量，使x2的值從的值從0開始增加，另一個非基變量開始增加，另一個非基變量x1保持零值不變。保持零值不變。63（3）確定）確定出基變量出基變量。在約束條

41、件在約束條件 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2中，由于進(jìn)基變量中，由于進(jìn)基變量x2在在3個約束條件中的系個約束條件中的系數(shù)都是負(fù)數(shù)，當(dāng)數(shù)都是負(fù)數(shù)，當(dāng)x2的值從的值從0開始增加時，基開始增加時，基變量變量x3 、x4 、x5的值分別從當(dāng)前的值的值分別從當(dāng)前的值65、40和和75開始減少，當(dāng)開始減少，當(dāng)x2增加到增加到25時，時，x5首首先下降為先下降為0成為非基變量。這時，新的基變成為非基變量。這時，新的基變量為量為x3 、x4 、x2 ，新的非基變量為新的非基變量為x1 、x5 ，當(dāng)前的基本可行解和目標(biāo)函數(shù)值為：當(dāng)

42、前的基本可行解和目標(biāo)函數(shù)值為：x = (0，25，15，15，0)T，z = 62500。這個。這個解對應(yīng)于圖中的解對應(yīng)于圖中的C、D交點。交點。64第二次迭代：第二次迭代： （1）當(dāng)前的可行基為）當(dāng)前的可行基為B7 = (p2 , p3 , p4)，那么那么x2 ，x3 ，x4為基變量，為基變量，x1 ，x5為非為非基變量。將基變量和目標(biāo)函數(shù)用非基變基變量。將基變量和目標(biāo)函數(shù)用非基變量表示：量表示： z = 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3)

43、 x5 65 （2）選擇進(jìn)基變量。在目標(biāo)函數(shù)）選擇進(jìn)基變量。在目標(biāo)函數(shù)z = 62500 + 1500 x1 (2500/3) x5 中，非基變中，非基變量量x1的系數(shù)是正數(shù)，因此的系數(shù)是正數(shù)，因此 x1進(jìn)基可以使目標(biāo)進(jìn)基可以使目標(biāo)函數(shù)函數(shù)z增大，于是選擇增大，于是選擇x1進(jìn)基，使進(jìn)基，使x1的值從的值從0開始增加開始增加, 另一個非基變量另一個非基變量x5保持零值不保持零值不變。變。 (3)確定出基變量。在約束條件確定出基變量。在約束條件 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 66中，由于進(jìn)基

44、變量中，由于進(jìn)基變量x1在兩個約束條件中的系在兩個約束條件中的系數(shù)都是負(fù)數(shù)，當(dāng)數(shù)都是負(fù)數(shù)，當(dāng)x1的值從的值從0開始增加時，基變開始增加時，基變量量x3 、x4的值分別從當(dāng)前的值的值分別從當(dāng)前的值15、15開始減開始減少，當(dāng)少，當(dāng)x1增加到增加到5時，時，x3首先下降為首先下降為0成為非成為非基變量。這時，新的基變量為基變量。這時，新的基變量為x1 、x2 、x4 ，新的非基變量為新的非基變量為x3 、x5 ，當(dāng)前的基本可行解當(dāng)前的基本可行解和目標(biāo)函數(shù)值為：和目標(biāo)函數(shù)值為：x = (5，25，0，5，0)T，z = 70000。這個解。這個解對應(yīng)于圖中的對應(yīng)于圖中的A、C交點。交點。 67第三次

45、迭代：第三次迭代： （1）當(dāng)前的可行基為）當(dāng)前的可行基為B2 = (p1 , p2 , p4 )，那么，那么x1 ，x2 ，x4為基變量，為基變量，x3 ，x5為非基變量。將基變量和目標(biāo)函為非基變量。將基變量和目標(biāo)函數(shù)用非基變量表示：數(shù)用非基變量表示： z = 70000 500 x3 500 x5 x1 = 5 (1/3) x3 + (2/9) x5 x2 = 25 (1/3) x5 x4 = 5 + (2/3) x3 (1/9) x5 68 （2）選擇進(jìn)基變量。在目標(biāo)函數(shù)）選擇進(jìn)基變量。在目標(biāo)函數(shù) z = 70000 500 x3 500 x5 中，非基變量中，非基變量x3 、x5的系數(shù)均

46、不是正數(shù)，因的系數(shù)均不是正數(shù)，因此進(jìn)基都不可能使目標(biāo)函數(shù)此進(jìn)基都不可能使目標(biāo)函數(shù)z增大，于是得增大，于是得到最優(yōu)解，到最優(yōu)解， x* = (5，25，0，5，0)T，最優(yōu)目標(biāo)值為最優(yōu)目標(biāo)值為 z* = 70000。 這個解對應(yīng)于圖這個解對應(yīng)于圖2-7的的A、C交點。我們也交點。我們也稱相應(yīng)的基稱相應(yīng)的基B2 = (p1 , p2 , p4)為最優(yōu)基。計算結(jié)束。為最優(yōu)基。計算結(jié)束。 692.4.2 單純形法的表格計算單純形法的表格計算 考慮規(guī)范形式的線性規(guī)劃問題考慮規(guī)范形式的線性規(guī)劃問題, ,為了避為了避免退化情況，設(shè)免退化情況，設(shè) bi 0 i = 1 , , m Max z = c1 x1

47、+ c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 . . am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 070加入松弛變量化為標(biāo)準(zhǔn)形式加入松弛變量化為標(biāo)準(zhǔn)形式 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 . . am1 x1 + am2 x2 + + amn

48、 xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0顯然，顯然，xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是基本可行解是基本可行解, , 對對應(yīng)的基是單位矩陣。應(yīng)的基是單位矩陣。71初始單純形表：初始單純形表：mm m m其中其中 f = - cn+i bi j = cj - cn+i aij 為檢驗數(shù)為檢驗數(shù) i = i =1 cn+i = 0 i= 1,m an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m722.4.3 單純形法計算實例單純形法計算實例 例例 Max z =

49、1500 x1+2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 化標(biāo)準(zhǔn)形式：化標(biāo)準(zhǔn)形式： Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 073求解求解單純形表單純形表74 在單純形法計算過程中在單純形法計算過程中1、運算中使用矩陣初等行變換；、運算中使用矩陣初等行變換；2、表中矩陣總含各單位向量（表明當(dāng)前、表中矩陣總含各單位向量（表明當(dāng)前為基本解）；為基本解）；3

50、、表中第、表中第3列的數(shù)總應(yīng)保持非負(fù)（表明列的數(shù)總應(yīng)保持非負(fù)（表明當(dāng)前基本解可行）；當(dāng)前基本解可行）；4、當(dāng)所有檢驗數(shù)均非正（、當(dāng)所有檢驗數(shù)均非正（ 0）時，得）時，得到最優(yōu)單純形表。到最優(yōu)單純形表。注意：注意：75多解情況多解情況 線性規(guī)劃問題可能存在無窮多解的情線性規(guī)劃問題可能存在無窮多解的情況，利用單純形表亦可求出。況，利用單純形表亦可求出。例例 Max z = x1 + 5x2 + 4x3 - x5 - 2x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2

51、, x3 , x4 , x5 , x6 076用單純形法求解用單純形法求解得到解為得到解為 x ( 0, 15/7, 25/7, 52/7, 0 , 0 )T由于由于 x1 的檢驗數(shù)為零，可繼續(xù)迭代，的檢驗數(shù)為零，可繼續(xù)迭代，77繼續(xù)求解繼續(xù)求解另一解為另一解為 x” ( 25/3, 10/3, 0, 11, 0 , 0 )T于是于是 x，x” 線段上的任一點均為最優(yōu)解。線段上的任一點均為最優(yōu)解。 此線性規(guī)劃的最優(yōu)解可表示為：此線性規(guī)劃的最優(yōu)解可表示為： x = x + (1- ) x” ，其中其中 0 178練習(xí)：練習(xí)：2.18 單純形法計算實例單純形法計算實例 例例 Max z =1500

52、 x1+1000 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 化標(biāo)準(zhǔn)形式：化標(biāo)準(zhǔn)形式： Max z =1500 x1 + 1000 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 079求解求解單純形表單純形表80無有限最優(yōu)解的情況無有限最優(yōu)解的情況 線性規(guī)劃問題可能存在無有限最優(yōu)線性規(guī)劃問題可能存在無有限最優(yōu)解解(目標(biāo)函數(shù)取向目標(biāo)函數(shù)取向 + )的情況，利用單的情況，利用單純形表亦可得出此結(jié)論。純形表亦可得出此結(jié)

53、論。 例例 Max z = 15x1 + 18x2 2x3 +5x5 s.t. x1 - 1/3x3 + 2/3x5 = 7 -2/3x3 + x4 + 1/9x5 = 5 x2 - 1/6x5 = 5 x1 , x2 , x3 , x4 , x5 081用單純形法求解得到用單純形法求解得到表中表中 x3 的檢驗數(shù)大于零，而其的檢驗數(shù)大于零，而其對應(yīng)的約束矩陣元素均非正，說明對應(yīng)的約束矩陣元素均非正，說明此線性規(guī)劃無有限最優(yōu)解。此線性規(guī)劃無有限最優(yōu)解。拿到題目后先化為標(biāo)準(zhǔn)形式用表格法計算（迭代方法太復(fù)雜）表格法計算停止后，寫出如下結(jié)論：最優(yōu)解&最優(yōu)值，并注明是唯一最優(yōu)解還是有無窮多最優(yōu)

54、解還是無有限最優(yōu)解。作業(yè)作業(yè)P51-52 1-(3)， 3-(3)83842.4.4 2.4.4 一般線性規(guī)劃問題的處理一般線性規(guī)劃問題的處理 一般情況下，初始基本可行解不一般情況下，初始基本可行解不明顯。常用的方法是通過引入人工明顯。常用的方法是通過引入人工變量，得到初始約束矩陣中含有各變量，得到初始約束矩陣中含有各單位向量，然后考慮如何使引入的單位向量，然后考慮如何使引入的人工變量取值為人工變量取值為0。 考慮一般問題：考慮一般問題： bi 0 i = 1 , , m85Max z = c1x1 + c2x2 + + cnxn s.t. a11x1+a12x2 +a1nxn = b1 a2

55、1x1+a22x2 +a2nxn = b2 . . . am1x1+am2x2+amnxn = bm x1 ，x2 ， ，xn 0大大M法：法：引入引入人工變量人工變量 xn+i 0 （i = 1 , , m）及）及充分大正數(shù)充分大正數(shù) M 。得到：。得到：Max z = c1x1 +c2x2 +cnxn -Mxn+1 -Mxn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 . . . am1 x1 + am2 x2 + + amn xn + xn+m = bm x1，x

56、2，xn，xn+1，xn+m 086注意區(qū)分： 人工變量 松弛變量88顯然，顯然，xj = 0 j =1 , , n ; xn+i = bi i =1 , , m 是基本可行解。是基本可行解。對應(yīng)的基是單位矩陣。對應(yīng)的基是單位矩陣。 結(jié)論：若得到的最優(yōu)解滿足結(jié)論：若得到的最優(yōu)解滿足 xn+i = 0, i = 1 , , m 則是原問題的最優(yōu)解；否則，原問則是原問題的最優(yōu)解；否則，原問題無可行解。題無可行解。兩階段法：兩階段法：引入人工變量引入人工變量 xn+i 0，i = 1 , m；構(gòu)造構(gòu)造: Max z = - xn+1 - xn+2 - - xn+m s.t. a11x1+ a12x2+ + a1nxn+xn+1 = b1 a21x1+ a22x2+ + a2nxn+xn+2 = b2 . . . am1x1+am2x2+ +amnxn+xn+m = bm x1,x2 . xn ,xn+1,xn+m 08990第一階段：求解上述問題：第一階段：求解上述問題： 顯然顯然 xj = 0 j =1,n ; xn+i = bi i =1,m 是基本可行解是基本可行解, 對應(yīng)的基是由單位向量對應(yīng)的基是由單位向量構(gòu)成的矩陣。構(gòu)成的矩陣。結(jié)論：若得到的最優(yōu)解滿足結(jié)論：若得到的最優(yōu)解滿足 xn+i = 0 , i =1 , , m 則是原問題的基本可行解則是原問題的基本可行解;否則，原問