1、OR1,1,第一章 線性規(guī)劃與單純形法,重點(diǎn)與難點(diǎn)： 1、線性規(guī)劃的概念和模型，線性規(guī)劃問題的標(biāo)準(zhǔn)型，線性規(guī)劃問題的標(biāo)準(zhǔn)化； 2、線性規(guī)劃問題解的概念，圖解法(解的幾何表示)，基本可行解的幾何意義，線性規(guī)劃求解思路(單純形法思想)； 3、單純形法的一般描述，表格單純形法，一般線性規(guī)劃問題的處理，單純形迭代過程中的注意事項(xiàng)； 4、線性規(guī)劃建模，決策變量，約束不等式、等式，目標(biāo)函數(shù)，變量的非負(fù)限制。,OR1,2,第一章 線性規(guī)劃與單純形法,1.1 LP(linear programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法。 LP有一組有待

2、決策的變量，（決策變量） 一個(gè)線性的目標(biāo)函數(shù)， 一組線性的約束條件。,OR1,3,1.1.1 LP的數(shù)學(xué)模型 例題1：生產(chǎn)計(jì)劃問題,某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：?jiǎn)栴}：如何安排生產(chǎn)計(jì)劃，使得獲利最多？,OR1,4,例題1建模,步驟： 1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg 2、確定目標(biāo)函數(shù)：maxZ=70X1+120X2 3、確定約束條件：人力約束 9X1+4X2360 設(shè)備約束 4X1+5X2 200 原材料約束3X1+10X2 300 非負(fù)性約束X10 X20 綜上所述，該問題的數(shù)學(xué)模型表示為：,OR1,5,例題

3、2:營(yíng)養(yǎng)配餐問題,有A、B兩種食品，含有每天必須得營(yíng)養(yǎng)成分C、D，每天至少需要營(yíng)養(yǎng)成分C和D分別為2和3個(gè)單位。食品A、B的成分和單價(jià)如下表，試做花錢最少的食譜，并求其費(fèi)用。,OR1,6,例題2建模,1、確定決策變量：設(shè)A、B兩種食品每天的購買量分別為x1,x2單位。 2、確定目標(biāo)函數(shù)：minW=0.9x1+0.8x2 3、確定約束條件：x1+2x2 2 3x1+x2 3 x1 0,x2 0 綜上所述，該問題的數(shù)學(xué)模型表示為：,OR1,7,例題3：人員安排問題,醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí)。不同時(shí)段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計(jì)：,請(qǐng)問該醫(yī)院至少需要多少名護(hù)士？,OR1,8,例題3建模,目

4、標(biāo)函數(shù)：min Z=x1+x2+x3+x4+x5+x6 約束條件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 非負(fù)性約束：xj 0,j=1,2,6,OR1,9,例題4：運(yùn)輸問題,三個(gè)加工棉花的加工廠，并且有三個(gè)倉庫供應(yīng)棉花，各供應(yīng)點(diǎn)到各工廠的單位運(yùn)費(fèi)以及各點(diǎn)的供應(yīng)量與需求量分別如下表所示：?jiǎn)柸绾芜\(yùn)輸才能使總的運(yùn)費(fèi)最小？,OR1,10,例題4建模,設(shè)Xij為第i個(gè)倉庫運(yùn)到底j座工廠的運(yùn)輸量。 目標(biāo)函數(shù)：總運(yùn)費(fèi)最?。簃inZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33 約束條件： 供給要求：x11+x12+

5、x13 50需求要求：x11+x21+x31=40 x21+x22+x23 30 x12+x22+x32=15 x31+x32+x33 10 x13+x23+x33=35 非負(fù)要求： Xij 0,OR1,11,例題5：項(xiàng)目投資問題,某部門有一批資金用于甲、乙、丙、丁、戊五個(gè)工程項(xiàng)目的投資，已知用于各個(gè)工程項(xiàng)目時(shí)所得之凈收益(投入資金的百分比)，如下表所示。 由于某種原因，決定用于項(xiàng)目甲的投資不大于其他各項(xiàng)投資之和；而用于項(xiàng)目乙和戊的投資之和不小于項(xiàng)目丙的投資。試確定使該部門收益最大的投資分配方案。,OR1,12,例題5建模,設(shè)Xj表示用于第j個(gè)項(xiàng)目的投資百分比。 目標(biāo)函數(shù)：maxZ=0.1x1

6、+0.08x2+0.06x3+0.05x4+0.09x5 約束條件： 全投資要求：x1+x2+x3+x4+x5=1 對(duì)甲的要求：x1-x2-x3-x4-x50 對(duì)乙、戊的要求： x2-x3+x50 非負(fù)要求：xj0 (j=1,2,3,4,5),OR1,13,例題6：連續(xù)投資問題（書P42頁）,某投資者有資金10萬元，考慮在今后5年內(nèi)給下列4個(gè)項(xiàng)目進(jìn)行投資，已知： 項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115。 項(xiàng)目B：第三年初需投資，到第五年末能回收本利125。但規(guī)定投資額不超過4萬元。 項(xiàng)目C：第二年初需要投資，到第五年末能回收本利140，但規(guī)定最大投資額不超過3萬元。

7、 項(xiàng)目D：5年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6。 問該投資者應(yīng)如何安排他的資金，確定給這些項(xiàng)目每年的投資額，使到第五年末能擁有的資金本利總額為最大？,OR1,14,建模,解：記xiA,xiB,xiC,xiD(i=1,2,3,4,5)分別表示第i年年初給項(xiàng)目A,B,C,D的投資額，它們都是決策變量，為了便于書寫數(shù)學(xué)模型，我們列表如下：,OR1,15,例題7：合理下料問題,將長(zhǎng)8m的圓鋼，截取成長(zhǎng)2.5m的毛坯100根、長(zhǎng)1.3m的毛坯200根，問應(yīng)該怎樣選擇下料方式，才能既滿足需要，又使總的用料最少? 各種搭配方案如下：,OR1,16,例題7建模,設(shè)Xj表示采用第j種方案下料的根數(shù)。

8、 目標(biāo)函數(shù)：minZ=x1+x2+x3+x4 約束條件：3x1+2x2+x3 100 2x2+4x3+6x4 200 xj 0且為整數(shù) (j=1,2,3,4),OR1,17,課堂練習(xí)：營(yíng)養(yǎng)配餐問題,養(yǎng)海貍鼠 飼料中營(yíng)養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表:,OR1,18,建 模,設(shè)抓取飼料I x1kg;飼料II x2kg;飼料III x3kg 目標(biāo)函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x5 約束條件：3x2+2x2+x3+6x4+18x5 700 營(yíng)養(yǎng)要求： x1+0.5x2+0.2x3+2x4+0.5

9、x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200 用量要求： x1 50,x2 60,x3 50,x4 70,x5 40 非負(fù)性要求：x1 0,x2 0,x3 0,x4 0,x5 0,OR1,19,總 結(jié),從以上7個(gè)例子可以看出，它們都屬于優(yōu)化問題，它們的共同特征： 1、每個(gè)問題都用一組決策變量表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的。 2、存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。 3、都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)（稱為目標(biāo)函數(shù)）來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。 滿足

10、以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。,OR1,20,線性規(guī)劃模型的一般模式,目標(biāo)函數(shù)：max(min)Z=c1x1+c2x2+c3x3+cnxn 約束條件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bm 非負(fù)性約束：x1 0,x2 0,xn 0 .,OR1,21,線性規(guī)劃的標(biāo)準(zhǔn)型,代數(shù)式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm

11、 xj 0 j=1,2,n,OR1,22,線性規(guī)劃的標(biāo)準(zhǔn)型,和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n,j=1,n,n,j=1,OR1,23,線性規(guī)劃的標(biāo)準(zhǔn)型,向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) T,n,j=1,OR1,24,線性規(guī)劃的標(biāo)準(zhǔn)型,矩陣式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amn,OR1,25,標(biāo)準(zhǔn)型的特征,目標(biāo)函數(shù)極大化（

12、也有的版本選擇極小化） 約束條件為等式 決策變量非負(fù),OR1,26,非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型,目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minZ=max(Z) ，一個(gè)數(shù)的極小化等價(jià)于其相反數(shù)的極大化。 不等式約束的轉(zhuǎn)化： aijxjbi 加入松弛變量 aijxjbi 減去剩余變量 非正變量：即xk 0 則令xk = xk 自由變量：即xk無約束，令xk= xkx”k,OR1,27,非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之一,maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +X4=200 3X1+10X2 300 3X1+10X

13、2+X5 =300 X10 X20 Xj0 j=1,2,5,OR1,28,非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之二,minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3無約束 x1 0 x2 0 x3 0 x”3 0 x40 x50,OR1,29,課堂練習(xí)：將下列非標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型,1、minZ=x1-2x2+3x3 2，maxZ=x1+x2 s.t. x1+x2+x3 7 s.

14、t. x1-x2 0 x1-x2+x3 2 3x1-x2 -3 -3x1+x2+2x3= -5 x1,x2 0 x1,x2 0,x3無約束。,OR1,30,1.1.2線性規(guī)劃問題的圖解法,一、圖解法的步驟 1、在平面上建立直角坐標(biāo)系； 2、圖示約束條件，找出可行域； 3、圖示目標(biāo)函數(shù)，即為一直線； 4、將目標(biāo)函數(shù)直線沿其法線方向其最優(yōu)化方向平移，直至與可行域第一次相切為止，這個(gè)切點(diǎn)就是最優(yōu)點(diǎn)。 二、幾種可能結(jié)局： 1、有唯一最優(yōu)解，2、有無窮多個(gè)最優(yōu)解，3、無界解，4、無解。,OR1,31,線性規(guī)劃圖解法例題（唯一最優(yōu)解）,maxZ=70X1+120X2 s.t. 9X1+4X2360 4X1

15、+5X2 200 3X1+10X2 300 X10 X20,OR1,32,線性規(guī)劃圖解法例題（無窮多最優(yōu)解）,OR1,33,線性規(guī)劃圖解法例題（無界解）,OR1,34,線性規(guī)劃圖解法例題（無解）,OR1,35,利用圖解法的常識(shí),1、若存在唯一最優(yōu)解，則此最優(yōu)解在可行域的頂點(diǎn)上取得。 2、若存在無窮多最優(yōu)解，則最優(yōu)解在可行域的邊界上取得。 3、若可行域?yàn)榭占?，則沒有可行解，也就沒有最優(yōu)解。 4、若可行域無界，目標(biāo)函數(shù)取值可以增大到無窮大，稱這種情況為無界解或無最優(yōu)解。 5、若有可行解，則可能有最優(yōu)解，也可能無最優(yōu)解（最優(yōu)解無界）。,OR1,36,1.1.3解的概念,概念： 1、可行解：滿足所有約

16、束條件的解。 2、可行域：即可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。 3、凸集：集合內(nèi)任意兩點(diǎn)的連線上的點(diǎn)均屬于這個(gè)集合。如：實(shí)心球、三角形。,OR1,37,凸 集,線性規(guī)劃的可行域是凸集。 若線性規(guī)劃問題存在最優(yōu)解，它一定在可行域的某個(gè)頂點(diǎn)得到，若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的任意點(diǎn)都是最優(yōu)解，即有無窮多最優(yōu)解。（P11）,OR1,38,基的概念,基：如前所述LP標(biāo)準(zhǔn)型 和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩陣式：maxZ=CX AX=b X 0 約束方程的系數(shù)矩陣A的秩為m，且mn。設(shè)

17、A=B+N ，B是A中mm階滿秩子矩陣，則稱B是該LP問題的一個(gè)基，即：B是A中m個(gè)線性無關(guān)向量組。,n,j=1,n,j=1,OR1,39,基本概念,秩：mn矩陣A的所有不為零的子式的最高階數(shù)稱為矩陣A的秩。記作R(A)。 線性無關(guān)向量組：對(duì)于向量組a1,a2,an，如果存在一組不全為零的實(shí)數(shù)k1,k2,kn,使 k1 a1+k2 a2+knan=0,則稱向量組a1,a2,an線性相關(guān)，否則稱它們線性無關(guān)。（向量線性無關(guān)的充要條件是向量組的秩等于向量組所含向量個(gè)數(shù)。）,OR1,40,基解的概念,不失一般性，設(shè)B是A的前m列,即B=(p1,p2,pm）,其相對(duì)應(yīng)的變量XB=(x1,x2,xm)T

18、,稱為基變量；其余變量XN=(Xm+1,Xn)T稱為非基變量。令所有非基變量等于零時(shí)得出的解, 即X=（x1,x2,xm,0,0)T稱為基解 。 （注：基解不一定就是可行解，因?yàn)榛獠灰欢M足非負(fù)的約束條件。也即基解中可能存在負(fù)值的情況。）,OR1,41,基可行解的概念,基可行解：基解可正可負(fù)，負(fù)則不可行（違背非負(fù)性約束條件），滿足非負(fù)約束條件的基解為基可行解。 對(duì)應(yīng)于基可行解的基稱為可行基。 退化的基可行解：若某個(gè)基變量取值為零，則稱之為退化的基可行解。 基解的數(shù)目：最多Cmn=n!/m!(n-m)!,OR1,42,幾種解之間的關(guān)系,部分基解是非可行解。,OR1,43,例題8 基可行解說明,

19、maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj0 j=1,2,5 這里m=3,n=5。 Cmn=10,OR1,44,例題8 基可行解說明,基（p3,p4,p5） ，令非基變量x1,x2=0，則基變量x3=360, x4=200, x5=300, 可行解 基（p2,p4,p5）,令非基變量x1=0,x3=0基變量x2=90,x4=250,x5=600. 非可行解 基（ p2,p3,p4 ），令非基變量x1,x5=0

20、，則基變量x2=30, x3=240, x4=50,可行解,OR1,45,基本定理介紹,定理1：若線性規(guī)劃問題存在可行域，則其可行域D 是凸集。 引理1：LP問題的可行解X（x1,x2,xn）T 為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。,OR1,46,基本定理介紹,定理2：LP問題的基可行解X對(duì)應(yīng)于可行域的頂點(diǎn)。 頂點(diǎn)：設(shè)K是凸集，X屬于K；若X不能用不同的兩點(diǎn) 的線性組合表示為 則稱X為K的一個(gè)頂點(diǎn)（或極點(diǎn)）。 引理2：若K是有界凸集。則任何一點(diǎn)X屬于K可表示為K的頂點(diǎn)的凸組合。,OR1,47,基本定理介紹,定理3 若可行域有界，LP問題的目標(biāo)函數(shù)一定可以在其可行域的

21、頂點(diǎn)上達(dá)到最優(yōu)。 另外，若可行域?yàn)闊o界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上得到。,OR1,48,1.2單純形法,2.2.1單純形法的初步討論 如： maxZ=70X1+120X2 s.t. 9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20,OR1,49,1.2.1單純形法的初步討論,第一步：將原問題化為標(biāo)準(zhǔn)模型 第二步：求出初始可行解 第三步：最優(yōu)性檢驗(yàn) 第四步：換基迭代 第五步：繼續(xù)優(yōu)化,OR1,50,第二步：求出初始可行解,方法：對(duì)已經(jīng)標(biāo)準(zhǔn)化的線性規(guī)劃模型，設(shè)法在約束矩陣 Am n中構(gòu)造出一個(gè)m階單位矩陣作為初始可行基，求出用非基變量

22、表示基變量及目標(biāo)函數(shù)的表示式。我們稱之為線性規(guī)劃問題的典式。通過典式我們可以求出初始基本可行解。,OR1,51,第三步：最優(yōu)性檢驗(yàn),方法：在目標(biāo)函數(shù)的典式中，若至少有一個(gè)非基變量前的系數(shù)為正數(shù)，則當(dāng)前解就不是最優(yōu)解；若所有的非基變量前的系數(shù)均為非正數(shù)，則當(dāng)前解就是最優(yōu)解。將目標(biāo)函數(shù)的典式中非基變量前的系數(shù)為檢驗(yàn)數(shù)，故對(duì)最大化問題，當(dāng)所有的檢驗(yàn)數(shù)0時(shí)，當(dāng)前解即為最優(yōu)解。,OR1,52,第四步：換基迭代,方法：若當(dāng)前解不是最優(yōu)解，則要進(jìn)行基變換迭代到下一個(gè)基本可行解： 首先從當(dāng)前解的非基變量中選一個(gè)作進(jìn)基變量。選擇原則是：目標(biāo)函數(shù)的典式中，最大的檢驗(yàn)數(shù)所屬的非基變量作進(jìn)基變量。 再從當(dāng)前解的基變量

23、中選一個(gè)作出基變量。選擇方法：在用非基變量表示基變量的典式中，除了進(jìn)基變量外，讓其余非基變量取值為零，再按最小比值準(zhǔn)則確定出基變量。 這樣就得到一組新的基變量與非基變量。然后求出新基矩陣的LP問題的典式。在新的典式中可求出新基本可行解及目標(biāo)函數(shù)的值。,OR1,53,1.2.2單純形表,單純形表的格式：,OR1,54,OR1,55,單純形法的計(jì)算步驟 (P30),1、找到初始可行基，建立單純形表 2、計(jì)算檢驗(yàn)數(shù)，若所有j 0 則得最優(yōu)解，結(jié)束。否則轉(zhuǎn)下步。 若某K 0而PK 0 ，則最優(yōu)解無界，結(jié)束。否則轉(zhuǎn)下步。 3、根據(jù)max j = K 原則確定XK 進(jìn)基變量；根據(jù)規(guī)則 ： = min bi

24、 / aik aik 0 = bL/ aLk 確定XL為出基變量。 4、以aLk 為樞軸元素進(jìn)行迭代，回到第二步。,OR1,56,解的判別定理(P24),1、最優(yōu)解的判別定理：若X(0)為對(duì)應(yīng)于基B的一個(gè)基可行解，且對(duì)于一切非基變量，有 ，則 X*為最優(yōu)解。稱 為檢驗(yàn)數(shù)。 2、無窮多最優(yōu)解的判別定理：若X(0)為對(duì)應(yīng)于基B的一個(gè)基可行解，且對(duì)于一切非基變量，有 ，又存在某個(gè)非基變量的檢驗(yàn)數(shù)為0，則稱該LP問題有無窮多最優(yōu)解。,OR1,57,解的判別定理,3、無界解的判別：若X(0)為對(duì)應(yīng)于基B的一個(gè)基可行解，有某個(gè)正檢驗(yàn)數(shù)的非基變量對(duì)應(yīng)的列向量其分量均為非正，則該問題便無界（無最優(yōu)解）。,OR

25、1,58,1.3單純形法的進(jìn)一步探討,2.3.1極小化LP的解法。 2.3.2人工變量法之一：大M法。 2.3.3人工變量法之二：兩階段法。,OR1,59,1.3.1極小化LP問題的解法,方法一：將最小化問題化為最大化問題，再對(duì)該最大化問題進(jìn)行求解。 方法二：最小化問題直接求解：檢驗(yàn)數(shù)的判別由所有j (cj-zj)0 即為最優(yōu)，變?yōu)樗衘 0則為最優(yōu)。(選擇最小的負(fù)的j 所對(duì)應(yīng)的變量為進(jìn)基變量。其余同最大化求解方法。),OR1,60,極小化問題的直接解法,例：求解線性規(guī)劃問題：,OR1,61,解：該規(guī)劃的基變量為x1,x3,x6。直接按最小問題單純形法的求解過程如下：,cj,1,-1,1,0,

26、-3,0,cB,xB,b,x1,x2,x3,x4,x5,x6,1 0 0,2 1 2,0 1 0,-2 -1 1,0 2 3,0 0 1,5 6 8,x1 x3 x6,1 1 0,z,11,1,3,1,-3,2,0,0,-4,0,3,-5,0,3 8/3, ,x1 x3 x5,1 1 -3,1 0 0,2 -1/3 2/3,0 1 0,-2 -5/3 1/3,0 0 1,0 -2/3 1/3,5 2/3 8/3,5/2,0,0,-2/3,0,14/3,0,5/3,x2 x3 x5, 1/6 -1/3,1 0 0,0 1 0,-1 -2 1,0 0 1,0 -2/3 1/3,5/2 3/2 1,

27、0,0,4,0,5/3,4,-1 1 -3,OR1,62,1.3.2人工變量法之一：大M法,首先看下面例題：,OR1,63,大M法,對(duì)于這種無初始可行基的問題可以大M法求解。方法：化為標(biāo)準(zhǔn)型的同時(shí)，將以及的約束條件中，加入人工變量（虛擬變量），將目標(biāo)函數(shù)中，虛擬變量的系數(shù)定為M。 注：當(dāng)目標(biāo)函數(shù)為最大化時(shí)，虛擬變量的系數(shù)為M,當(dāng)目標(biāo)函數(shù)為最小化時(shí)，虛擬變量的系數(shù)為+M。(目的是迫使人工變量為0）該問題的解法同LP問題的一般解法。例同上。解法見書P33。,OR1,64,解法,解:在上述問題的約束條件中加入松弛變量，剩余變量，人工變量，得到：,OR1,65,用單純形表計(jì)算：,cj,-3,1,1,0,0,M,M,x1,x2,x3,x4,x5,x6,x7,cB,XB,b,1 -4 -2,-2 1 0,1 2 1,1 0 0,0 -1 0,0 1 0,0 0 1,x4 x6 x7,0 M M,11 3 1,-3+6M,1-M,1-3M,0,M,0,0,11 3/2 1,x4 x6 x3,0 M 1,3 0 -2,-2 1 0,0 0 1,1 0 0,0 -1 0,0 1 0,-1 -2 1,10 1 1,-1,1-M,0,0,M,0,3M-1,1,x1 x2 x3,-3 1 1,1 0 0,0 1 0,0 0 1,