1、第 3 章 線性規(guī)劃模型的單純形法,3.1 線性規(guī)劃數(shù)學(xué)模型的結(jié)構(gòu)及特征 3.2 線性規(guī)劃模型的標(biāo)準(zhǔn)形式 3.3 基、基本解、基本可行解 3.4 單純形表的數(shù)學(xué)原理 3.5 從一個基本可行解轉(zhuǎn)化為相鄰的基本可行解 3.6 最優(yōu)性檢驗和解的判別 3.7 單純形表法 3.8 人工變量法和兩階段法 3.9 計算機軟件QM求解,線性規(guī)劃模型的一般形式為,3.1 線性規(guī)劃數(shù)學(xué)模型的結(jié)構(gòu)及特征,線性規(guī)劃模型的特征：一組決策變量，一組約束條件和一個目標(biāo)函數(shù)，目標(biāo)函數(shù)和約束條件都是線性的。,3.2 線性規(guī)劃模型的標(biāo)準(zhǔn)形式,3.2.1 標(biāo)準(zhǔn)形式 標(biāo)準(zhǔn)形式定義為：,標(biāo)準(zhǔn)形式模型的 特征： 1.約束條件為線 性等式

2、； 2.所有變量全部 大于等于0； 3.右端常數(shù)項大 于等于0； 4.目標(biāo)函數(shù)求最 大值。,簡寫為,用矩陣表示,C價值向量 b資源向量 X決策向量,用向量表示,線性規(guī)劃模型的一般形式為,3.2.2 一般形式的線性規(guī)劃模型變換為標(biāo)準(zhǔn)形式,線性規(guī)劃模型的標(biāo)準(zhǔn)形式為,1.目標(biāo)函數(shù)為求極小值，即為：,因為求minz等價于求max(-z)，令z=-z， 即轉(zhuǎn)換為：,約束方程為 在“”左端加入一個非負松弛變量，把原“” 的不等式變?yōu)榈仁健?2.約束條件為不等式，,約束方程為 在“”左端減去一個非負剩余變量，把原“”的不等式變?yōu)榈仁健?.右端項bi0時，只需將等式兩端同乘（-1），則 右端項必大于零,4.決

3、策變量無非負約束,設(shè)xj沒有非負約束， 若xj0，可令xj=-xj，則xj0；,若xj為自由變量，即xj可為任意實數(shù)， 可令xj=xj-xj，且xj,xj0,5.決策變量xj有上界或者下界，即xju或者xjv 若xju，可令xj=xj-u，xj0； 若xjv，可令xj=v-xj，xj0；,【例3-2】將下面的線性規(guī)劃問題化為標(biāo)準(zhǔn)型：,將下面的線性規(guī)劃問題化為標(biāo)準(zhǔn)型：,（2）對于“”約束 9x+3y 360，引入松弛變量 x1，得到,（3）對于“”約束 3x+10y 300，引入剩余變量 x2，得到,解,（1）對目標(biāo)函數(shù)，令,則,（4）對于 y 無非負約束，令 yy(1)-y(2)，且y(1)

4、0，y(2) 0.,（5）統(tǒng)一變量，令 x=x3，y(1)=x4，y(2)=x5，得到該線性規(guī)劃問題的標(biāo)準(zhǔn)形式：,3.3 基、基本解、基本可行解,3.3.1 基、基本解、基本可行解的定義,基：若B是矩陣A中mn階非奇 異子矩陣（），則 B是線性規(guī)劃問題的一個基。,基向量：中的每一個列向量（j=1，2，,m） 基變量：與基向量對應(yīng)的變量，用XB表示。 非基變量：線性規(guī)劃模型的決策變量中除基變量以外 的變量，用XN表示。,基解：設(shè)B為某一個基，A=（B,N),則有BXB+NXN=b 令XN=0，則得一個滿足AX=b式的解,這個解稱為基解。,基可行解：若 為一個基解，且,則得到一個滿足AX=b、X0

5、的 可行解，稱為基可行解。,可行基：對應(yīng)基可行解的基稱為可行基。,注意兩點： B在A中是任意取的。故A中有很多基B。 基變量是針對B而言的，不同B，其對應(yīng)的基變量和非基變量是不同的。,3.3.2 基本解和基本可行解的計算與幾何解釋,通過【例3-3】說明線性規(guī)劃模型的基、對應(yīng)的基本解、基本可行解。,將模型化為標(biāo)準(zhǔn)型：,X2、X3、X5不能構(gòu)成B的一組基變量。,X1、X3、X4不能構(gòu)成B的一組基變量。,該模型所對應(yīng)的基、基本解、基本可行解，如下表：,x1,(0,0),(2,3),(0,3),(0,4),(4,3),(4,0),(4,2),(8,0),9 8 7 6 5 4 3 2 1 0,| 12

6、3456789,x1,x1 + 2x2 8,4x1 16,可行域,A,B,C,D,O,E,F,G,約束條件的交點有8個，基本解就有8個；可行域頂點有5個：基可行解就有5個： ：（0，0）、（0，3）、(2,3)、（4，2）和（4，0），其中E為最優(yōu)解。,該模型所對應(yīng)的基、基本解、基本可行解，如下圖：,可行解： 滿足約束條件AX=b與X0的解X 基本解： 對于某一特定的基B，非基變量取0值的 解，即 基本可行解：滿足非負約束條件的基礎(chǔ)解，即 最優(yōu)解： 滿足目標(biāo)函數(shù)MaxZ = CX的可行解X 基本最優(yōu)解：滿足目標(biāo)函數(shù)MaxZ = CX的基本可行解X,3.3.3 線性規(guī)劃模型解之間的關(guān)系,基本解,

7、可行解,最優(yōu)解,基本最優(yōu)解,基本可行解,基,最優(yōu)基,可行基,線性規(guī)劃模型解、基的關(guān)系圖,定義1：如果集合C中任意兩個點X1、X2，其連線上所有點都是集合C中的點，那么稱C為凸集。即: 則稱為C凸集。,定義2：凸集C中滿足下述條件的點X稱為頂點；如果C中不存在任何兩個不同的點X1、X2，使X成為這兩個點連線上的一個點。即對于任何 ，不存在 ，則稱X是凸集C的頂點。,3.4 單純形表的數(shù)學(xué)原理,定理1：若線性規(guī)劃問題存在可行解域，則其可行解域,是凸集。,定理2：線性規(guī)劃問題的可行解 為基可行解的充要條件是，X的正分量所對應(yīng) 的系數(shù)列向量是線性無關(guān)。,定理3：線性規(guī)劃問題的基可行解X對應(yīng)于可行域 D

8、的頂點。,定理4：一個標(biāo)準(zhǔn)的線性規(guī)劃模型，如果有可行解， 則至少有一個基本可行解 定理5：一個標(biāo)準(zhǔn)的線性規(guī)劃模型，如果有有限的最優(yōu) 值，則一定存在一個基本可行解是最優(yōu)解,由上述線性規(guī)劃的基本定理，得以下結(jié)論： 線性規(guī)劃問題的可行解域是凸集； 基可行解是可行域的頂點，可行域的頂點即是基可 行解，因此，每個基可行解對應(yīng)可行域的一個頂 點； 3. 可行解域的頂點個數(shù)是有限的，不超過 個。 4 . 若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解必在某個頂點 上得到。,3.5 從一個基本可行解轉(zhuǎn)化為相鄰的基本可行解,定義3 兩個基本可行解稱為相鄰的，如果 它們之間變換且僅變換一個基變量。,3.6.1 最優(yōu)性判別準(zhǔn)則

9、線性規(guī)劃問題的標(biāo)準(zhǔn)型為：,3.6 最優(yōu)性檢驗和解的判別,原線性規(guī)劃可以化為：,原線性規(guī)劃問題等價于：,定理6（最優(yōu)解判別定理）,(1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。 （2）唯一最優(yōu)解判別定理：若所有 則存在唯一最有解。,3.6.2 無界解和無窮多最優(yōu)解判別準(zhǔn)則,（3）無窮多最優(yōu)解判定定理：若： 且存在某一個非基變量 ，則存在 無窮多最優(yōu)解。 （4）無界解判定定理：若 有某一個非基變量 并且對應(yīng)的非基變量的系數(shù) 則具有無界解。,單純形法的基本思想 即從可行域的一個頂點（基本可行解）開始，轉(zhuǎn)移到另一個頂點（另一個基本可行解）的迭代過程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（

10、逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達到最優(yōu)值時，問題也就得到了最優(yōu)解。,3.7 單純形表法,根據(jù)線性規(guī)劃問題的可行域是凸多邊形或凸多面體，一個線性規(guī)劃問題有最優(yōu)解，就一定可以在可行域的頂點上找到。 于是，若某線性規(guī)劃只有唯一的一個最優(yōu)解，這個最優(yōu)解所對應(yīng)的點一定是可行域的一個頂點；若該線性規(guī)劃有多個最優(yōu)解，那么肯定在可行域的頂點中可以找到至少一個最優(yōu)解。,【例3-4】求解下列線性規(guī)劃模型,9 400 350 300 250 200 150 100 50 0,| 50100150200250300350400,x1,B,C,A,D,可行域,x2,9 400 350 300 250 200 150 100 5

11、0 0,| 50100150200250300350400,x1,B,C,A,D,可行域,可行域頂點有五個,有三個非角點可行解。兩條邊界線產(chǎn)生一個角點可行解，每個角點可行解有兩個相鄰的角點可行解，如（0，0），相鄰的角點可行解為（0，250）、和（200，0）。,x2,9 400 350 300 250 200 150 100 50 0,| 50100150200250300350400,x1,B,C,A,D,可行域,求解 起始步驟：選擇（0，0）作為初始可行解 最優(yōu)性檢驗：（0，0）不是最優(yōu)解：z=0 迭代1： 由(0,0)沿x2移動至A。解得可行解 （0，250），最優(yōu)性檢驗非最優(yōu)值。,目

12、標(biāo)函數(shù)： maxz=50 x1+100 x2,x2,9 400 350 300 250 200 150 100 50 0,x1,B,C,A,D,可行域,迭代2： 由(0,250)沿x2=250移動至B。解得可行解（50，250），最優(yōu)性檢驗是最優(yōu)值（無相鄰的角點可行解優(yōu)于它）。,x2,| 50100150200250300350400,以【例3-4】來討論它的求解過程， 其標(biāo)準(zhǔn)型為：,轉(zhuǎn)換一般的線性規(guī)劃模型為標(biāo)準(zhǔn)型，并寫出A，C，b,（1）確定一個初始基可行解（頂點）。 取A中所含的單位矩陣作為一個基，即B=I，XB=(x3，x4，x5)T，XN=(x1,x2)T。則可得一初始基可行解X(0)

13、=(0，0，300，400，250)T,其目標(biāo)函數(shù)值 Z0=0。,（2）最優(yōu)解檢驗。 最優(yōu)解必在某一基可行解（頂點）上達到。,考察目標(biāo)函數(shù)Z=0+50 x1+100 x 2,由于x1=x 2 =0，所以 Z（0）=0。,若將非基變量變換成基變量，目標(biāo)函數(shù)的值就可能增大，所以只要目標(biāo)函數(shù)中存在正系數(shù)的非基變量，目標(biāo)函數(shù)還有增大的可能。,目標(biāo)函數(shù)是以X（0）的非基變量表示的， 不會有X（0）的基變量。,（3）確定入基（換入）變量 任意選擇x1,x2中的一個作為入基變量都會使目標(biāo)值增加。一般選擇最大正系數(shù)所對應(yīng)的非基變量為入基變量。,由目標(biāo)函數(shù)Z=0+50 x1+100 x 2，故選擇x2作為入基變

14、量。,（4）確定出基（換出）變量 當(dāng)x2定為入基變量后，必須從X（0）的基變量x3， x4， x5 中換出一個，并保證它們都是非負的（可行解所要求）。即x3， x4， x5 0。,當(dāng) x1作為非基變量等于 0 時，得,只有選擇,上式才能成立。,當(dāng)x2=250時， x5=0，決定用x2替換x5，故基變量x5出基,這個規(guī)則稱為規(guī)則。,入基變量所能取的最大值，由它們各自的正系數(shù)去除右邊常數(shù)，然后取最小者。,規(guī)則用來確定出基變量。,（5）確定一個新的基可行解 當(dāng)x2替換x5（即 x2由非基變量 基變量， x5由基變量 非基變量）后，則確定了以x2， x3， x4作為基變量 ，以x1， x5作為非基變量

15、而組成的一個新的可行基，需求出新的基可行解。,新的基可行解X（1）=（0，250，50，150，0）T Z（1）=25000,目標(biāo)函數(shù)Z=50 x1+100（250-x 5）=25000+50 x1-100 x5,用高斯消去法將式中x2的系數(shù)列向量變換成單位向量。,（6）重復(fù)上述的第2步，對X(1)進行最優(yōu)化檢驗， 由于X(1)的非基變量x1 的系數(shù)為正數(shù)，故X(1)不是最優(yōu) 解。確定x1 為入基變量， x5 仍為非基變量，求出新的 基可行解。,x5=0，且x2， x3， x40，則,從式上式可知，只有選擇,此式 才能成立。,當(dāng)x1=50時，基變量x3=0，故基變量x3為出基變量。故又得到一個

16、以基變量為x1， x2，x4，非基變量為x3 ，x5而構(gòu)成的一個新的可行基。,用高斯消去法將式中x1的系數(shù)列向量變換成單位向量。,這個新的可行基的基變量為x1， x2，x4，非基變量為x3 ，x5，故得此可行基的基可行解 X（2）=（50，250，0，50，0）T，Z（2）=27500,重復(fù)第二步，X（2）進行最優(yōu)化檢驗。X（2）的 非基變量x3 ，x5的系數(shù)均為負數(shù)，故x3 ，x5均不能確 定為入基變量（否則目標(biāo)函數(shù)會變?。蔢（2）為 最優(yōu)解，此時，整個單純形法過程結(jié)束。,以X（2）的非基變量表示的目標(biāo)函數(shù)，不含有X（2） 的基變量。,目標(biāo)函數(shù)為：Z=25000+50(50-x3+x5)

17、x1-100 x5 =27500-50 x3-50 x5,分析單純形法過程，共獲得了三個基可行解 X（0）、X（1）、X（2），它們各自所對應(yīng)的基變量和非 基變量是：（B1，B2，B3）,出基 入基,X（0）：基變量（x3 ，x4 ，x5） 非基變量（x1 ，x2）。,出基 入基,X（1）：基變量（x2 ，x3 ，x4） 非基變量（x1，x5）。,X（2）：基變量（x1 ，x2，x4） 非基變量（x3，x5）。,X（0）、X（1）、X（2）所對應(yīng)的基變量求解出來。只要令它們各自的非基變量等于0，即可求出各自的基可行解。,X（0）、X（1）、X（2）各自的非基變量表示的目標(biāo)函數(shù)（不含有它們各自的

18、基變量）這些目標(biāo)函數(shù)的系數(shù)稱為檢驗數(shù)。由檢驗數(shù)判定各自的基可行解是否是最優(yōu)解，并由檢驗數(shù)確定入基變量。,歸納單純形法的性質(zhì)： 是從一個基可行解變換到另一個基可行解的過程，著個過程實際上就是確定進基變量和出基變量的過程。 對每一個基可行解，均需解出其基變量。 一個基可行解是否最優(yōu)要由該基可行解的檢驗數(shù)來判斷。（檢驗數(shù)是該基可行解的非基變量所表示的目標(biāo)函數(shù)中的系數(shù)）。,4. 入基變量由檢驗數(shù)確定。 5. 出基變量由規(guī)則確定。,確定一初始基可行解,N,求線性規(guī)劃問題時，為了方便起見，可以設(shè)計一張表來代替所研究的線性規(guī)劃問題表達式，其功能與解線性方程組的增廣矩陣類似，稱為單純形表。開始建立的單純形表稱為初始單純形表。單純形法的迭代運算可以在單純形表上進行。,3.7.1 單純形表的定義,設(shè)標(biāo)準(zhǔn)形為,表格設(shè)計依據(jù)：,將-Z看作不參與基變換的基變量，把目標(biāo)函數(shù)表達式改寫成方程的形式，和原有的m個約束方程組成一個具有n+m+1個變量、m+1個方程的方程組：,取出系數(shù)寫成增廣矩陣的形式：,-Z X1 X2 Xn Xn+1 Xn+2 Xn+m b,-Z，Xn+1，Xn+m所對應(yīng)的系數(shù)列向量構(gòu)成一個基,用矩陣的初等行變換將該基變成單位陣,這時,變成0，相應(yīng)的增廣矩陣變成如下形式：,其中，j=1，2，n ，,增廣矩陣的最后一行就是用非基變量表示目標(biāo)函數(shù)的表