物流運(yùn)籌學(xué) 課件 第2章 線性規(guī)劃

線性規(guī)劃LinearProgramming

線性規(guī)劃（LinearProgramming，簡(jiǎn)稱LP）運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較快、理論上較成熟和應(yīng)用上極為廣泛的一個(gè)分支。

1947年G.B.Dantying提出了一般線性規(guī)劃問(wèn)題求解的方法——單純形法之后，線性規(guī)劃的理論與應(yīng)用都得到了極大的發(fā)展。

60年來(lái)，隨著計(jì)算機(jī)的發(fā)展，線性規(guī)劃已廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、經(jīng)濟(jì)管理和國(guó)防等各個(gè)領(lǐng)域，成為現(xiàn)代化管理的有力工具之一。§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型e.g.1

資源的合理利用問(wèn)題問(wèn)：如何安排生產(chǎn)計(jì)劃，使得既能充分利用現(xiàn)有資源又使總利潤(rùn)最大？

表1

產(chǎn)品資源 甲乙?guī)齑媪?/p>

A 1 3 60 B 1 1 40

單件利潤(rùn)

15 25

某工廠在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，要消耗A、B兩種資源，已知每件產(chǎn)品對(duì)這兩種資源的消耗，這兩種資源的現(xiàn)有數(shù)量和每件產(chǎn)品可獲得的利潤(rùn)如表1。第一章線性規(guī)劃及單純形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

解：

設(shè)x1，x2

為下一個(gè)生產(chǎn)周期產(chǎn)品甲和乙的產(chǎn)量；

約束條件：Subjecttox1+3x2≤60x1

+x2≤40x1，x2≥0目標(biāo)函數(shù)：z=15x1+25x2

表1

產(chǎn)品資源 甲乙?guī)齑媪?/p>

A 1 3 60 B 1 1 40

單件利潤(rùn)

15 25

決策變量§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型e.g.2

營(yíng)養(yǎng)問(wèn)題

假定在市場(chǎng)上可買到B1,B2,…Bnn

種食品，第

i

種食品的單價(jià)是ci,另外有m

種營(yíng)養(yǎng)A1,A2,…Am。設(shè)

Bj內(nèi)含有

Ai

種營(yíng)養(yǎng)數(shù)量為aij

(i=1~m,j=1~n)，又知人們每天對(duì)Ai

營(yíng)養(yǎng)的最少需要量為bi。見(jiàn)表2：

表2

食品最少營(yíng)養(yǎng) B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

單價(jià)

c1c2…cn

試在滿足營(yíng)養(yǎng)要求的前提下，確定食品的購(gòu)買量，使食品的總價(jià)格最低。第一章線性規(guī)劃及單純形法

表2

食品最少營(yíng)養(yǎng) B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

單價(jià)

c1c2…cn

解：

設(shè)xj

為購(gòu)買食品

Bj

的數(shù)量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型三個(gè)基本要素：Note：1、善于抓住關(guān)鍵因素，忽略對(duì)系統(tǒng)影響不大的因素；2、可以把一個(gè)大系統(tǒng)合理地分解成n

個(gè)子系統(tǒng)處理。1、決策變量xj≥0

2、約束條件——一組決策變量的線性等式或不等式3、目標(biāo)函數(shù)——決策變量的線性函數(shù)第一章線性規(guī)劃及單純形法max（min）z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1

a21x1+a22x2+…+a2nxn≤（或=，≥）b2

……am1x1+am2x2+…+amnxn

≤（或=，≥）bm

xj

≥0（j=1,2,…,n） 其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）為已知常數(shù)

線性規(guī)劃問(wèn)題的一般形式：§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

……am1x1+am2x2+…+amnxn

=bm

xj

≥0（j=1,2,…,n）

bi≥0（i=1,2,…,m） 特點(diǎn)：1、目標(biāo)函數(shù)為極大化；2、除決策變量的非負(fù)約束外，所有的約束條件都是等式，且右端常數(shù)均為非負(fù)；3、所有決策變量均非負(fù)。

第一章線性規(guī)劃及單純形法如何轉(zhuǎn)化為標(biāo)準(zhǔn)形式？1、目標(biāo)函數(shù)為求極小值，即為：。

因?yàn)榍髆inz等價(jià)于求max(-z)，令z’=-z，即化為：

2、約束條件為不等式，xn+1≥0松弛變量如何處理？§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

３、右端項(xiàng)bi<0時(shí)，只需將等式兩端同乘（-1）則右端項(xiàng)必大于零

4、決策變量無(wú)非負(fù)約束

設(shè)xj

沒(méi)有非負(fù)約束，若xj≤0，可令xj=-xj’

，則xj’≥0；

又若

xj

為自由變量，即

xj

可為任意實(shí)數(shù)，可令xj

=xj’-xj’’，且xj’,xj’’≥0第一章線性規(guī)劃及單純形法e.g.3試將LP

問(wèn)題minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0

化為標(biāo)準(zhǔn)形式。解：令x3=x4-x5

其中x4、x5

≥0；對(duì)第一個(gè)約束條件加上松弛變量x6

；對(duì)第二個(gè)約束條件減去松弛變量x7

；對(duì)第三個(gè)約束條件兩邊乘以“-1”；令z’=-z

把求minz

改為求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型LP的幾種表示形式：§2線性規(guī)劃問(wèn)題的圖解法定義1在LP問(wèn)題中，凡滿足約束條件(2)、(3)的解x=(x1,x2,…,xn)T

稱為L(zhǎng)P問(wèn)題的可行解，所有可行解的集合稱為可行解集（或可行域）。記作D={x|Ax=b,x≥0}。定義2

設(shè)LP問(wèn)題的可行域?yàn)镈，若存在x*∈D，使得對(duì)任意的x∈D

都有cx*≥cx，則稱x*為L(zhǎng)P問(wèn)題的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記作z*=cx*?！?線性規(guī)劃問(wèn)題的圖解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目標(biāo)函數(shù)變形：x2=-3/5

x1+z/25x2x1最優(yōu)解：

x1=30x2=10最優(yōu)值：zmax=700B點(diǎn)是使z達(dá)到最大的唯一可行點(diǎn)第一章線性規(guī)劃及單純形法LP問(wèn)題圖解法的基本步驟：1、在平面上建立直角坐標(biāo)系；2、圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)；3、圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向；4、尋找最優(yōu)解?！?線性規(guī)劃問(wèn)題的圖解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

綠色線段上的所有點(diǎn)都是最優(yōu)解,即有無(wú)窮多最優(yōu)解。Zman=34.2第一章線性規(guī)劃及單純形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域?yàn)闊o(wú)界區(qū)域，目標(biāo)函數(shù)值可無(wú)限增大，即解無(wú)界。稱為無(wú)最優(yōu)解。可行域?yàn)闊o(wú)界區(qū)域一定無(wú)最優(yōu)解嗎？無(wú)可行解

指找不到一組變量能滿足線性規(guī)劃的所有約束條件的情況，也就是線性規(guī)劃問(wèn)題不存在可行解，或者說(shuō)可行域是空集。例如線性規(guī)劃問(wèn)題：§2線性規(guī)劃問(wèn)題的圖解法由以上兩例分析可得如下重要結(jié)論：1、LP問(wèn)題從解的角度可分為：⑴有可行解⑵無(wú)可行解有唯一最優(yōu)解b.有無(wú)窮多最優(yōu)解C.無(wú)最優(yōu)解2、LP問(wèn)題若有最優(yōu)解，必在可行域的某個(gè)頂點(diǎn)上取到；若有兩個(gè)頂點(diǎn)上同時(shí)取到，則這兩點(diǎn)的連線上任一點(diǎn)都是最優(yōu)解?！?線性規(guī)劃問(wèn)題的圖解法圖解法優(yōu)點(diǎn)：直觀、易掌握。有助于了解解的結(jié)構(gòu)。圖解法缺點(diǎn)：只能解決低維問(wèn)題，對(duì)高維無(wú)能為力。例某工廠經(jīng)市場(chǎng)調(diào)研，決定生產(chǎn)甲、乙兩種產(chǎn)品，其單臺(tái)利潤(rùn)分別為60元和30元，兩種產(chǎn)品共用一種鋼材、一臺(tái)設(shè)備，其資源及獲利情況如下：甲乙現(xiàn)有資源鋼材消耗定額（公斤/臺(tái)）24600公斤臺(tái)時(shí)消耗定額（小時(shí)/臺(tái)）31400小時(shí)配件（件/臺(tái)）20250件利潤(rùn)（元）6030求利潤(rùn)最大的產(chǎn)品結(jié)構(gòu)決策。作業(yè)練習(xí)②確定目標(biāo)函數(shù)及約束條件——建立數(shù)學(xué)模型目標(biāo)函數(shù)：③將不等式變?yōu)榈仁讲⒃趚1－x2坐標(biāo)圖中作出直線④最優(yōu)點(diǎn)在凸邊形的頂點(diǎn)，代入（1）式可得maxP解：①設(shè)變量：設(shè)甲生產(chǎn)x1臺(tái)，乙生產(chǎn)x2臺(tái)，可得最大利潤(rùn)約束條件：05050100100150150200250300350200250300350400x1x2A(0,150)B(100,100)C(125,25)D(125,0)(4)基、基向量、基變量⊙設(shè)r(A)=m,并且B是A的m階非奇異的子矩陣（det(B)

0),則稱矩陣B為線性規(guī)劃問(wèn)題的一個(gè)基?！丫仃嘊=（P1，P2….Pm)，其列向量Pj稱為對(duì)應(yīng)基B的基向量?！雅c基向量Pj

相對(duì)應(yīng)的變量xj就稱為基變量，其余的就稱為非基變量。MaxS=CX（3-6）

s.t.AX=b（3-7）

X

0（3-8）基解.基可行解.可行基⊙對(duì)于某一特定的基B，非基變量取0值的解，稱為基解。⊙滿足非負(fù)約束條件的基礎(chǔ)解，稱為基可行解?！雅c基可行解對(duì)應(yīng)的基，稱為可行基。為了理解基解.基可行解.最優(yōu)解的概念，用下列例子說(shuō)明：例：maxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3-2x1+3x2=63x1-2

x2=6x1+x2=4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3ABx243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0滿足約束條件

-2x1+3x2

63x1-2

x2

6x1+x2

4

與坐標(biāo)系

x1,x2=0的交點(diǎn)（O，A，B，Q1，Q2，Q3，Q4）都是代表基解。注意：點(diǎn)（4，0）（0，4）不滿足約束條件滿足約束條件

-2x1+3x2

63x1-2

x2

6x1+x2

4

且滿足

x1,x2

0的交點(diǎn)（O，Q1，Q2，Q3，Q4）都是代表基可行解。注意：點(diǎn)A，B不滿足x1,x2

0點(diǎn)（O，Q1，Q2，Q3，Q4）剛好是可行域的頂點(diǎn)。x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域本問(wèn)題解的情況：基解：點(diǎn)（O，A，B，Q1，Q2，Q3，Q4）可行解：由點(diǎn)（O，Q1，Q2，Q3，Q4）圍成的區(qū)域?；尚薪猓狐c(diǎn)（O，Q1，Q2，Q3，Q4）最優(yōu)解：

Q3解的集合：非可行解可行解解的集合：基解解的集合：可行解基解基可行解解的集合：可行解基解基最優(yōu)解基可行解線性規(guī)劃（2）-單純形方法單純形方法基本思路：從可行域中某個(gè)基可行解（一個(gè)頂點(diǎn)）開(kāi)始（稱為初始基可行解）。如可能，從可行域中求出具有更優(yōu)目標(biāo)函數(shù)值的另一個(gè)基可行解（另一個(gè)頂點(diǎn)），以改進(jìn)初始解。繼續(xù)尋找更優(yōu)的基可行解，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值。當(dāng)某一個(gè)基礎(chǔ)可行解不能再改善時(shí)，該解就是最優(yōu)解。

由于軍事上的需要，擔(dān)任美國(guó)空軍審計(jì)官的數(shù)學(xué)顧問(wèn)旦茨基博士，根據(jù)在第二次世界大戰(zhàn)中實(shí)際規(guī)劃的經(jīng)歷，從1946年起就開(kāi)始尋找一種方法，想用它較快地計(jì)算出包括進(jìn)度、訓(xùn)練及后勤供應(yīng)在內(nèi)的規(guī)劃問(wèn)題。研究先從建立數(shù)學(xué)模型著手。在研究中，得到了投入—產(chǎn)出模型的啟發(fā)，并在其他數(shù)學(xué)家的支持下，提出了解決線性規(guī)劃問(wèn)題極其有效的單純形方法。單純形法的由來(lái)

旦茨基教授在一次演說(shuō)中，形象而風(fēng)趣地說(shuō)明了單純形解法的奇效：設(shè)給70個(gè)人分配70項(xiàng)任務(wù)，每人一項(xiàng)。如果每人完成各項(xiàng)任務(wù)所需要付出的代價(jià)（時(shí)間、工資）都知道，要尋求代價(jià)最小的方案。所有的可行方案共有70！種。70！比還要大。如果用窮舉法，逐個(gè)來(lái)比較的話，基本是不可能的。而用單純形法軟件，幾秒鐘就可以給出答案。

不僅如此，還能預(yù)測(cè)當(dāng)方案中某因素發(fā)生變化，對(duì)決策目標(biāo)的影響。神奇的單純形法返回目錄

線性規(guī)劃問(wèn)題的可行解有無(wú)窮多個(gè)，與某一凸集上的無(wú)窮多個(gè)點(diǎn)一一對(duì)應(yīng)。要從無(wú)窮多個(gè)可行解中尋找最優(yōu)解，幾乎不可能?？梢宰C明，最優(yōu)解必定能取在凸集的頂點(diǎn)（極點(diǎn)、基本可行解）上，而極點(diǎn)的個(gè)數(shù)是有限的。當(dāng)然，這個(gè)“有限”，數(shù)字往往相當(dāng)可觀，如前面的70！，要逐個(gè)比較的話，也不現(xiàn)實(shí)。而單純形解法，用跨躍的方式，高速地優(yōu)化基本可行解，迅速達(dá)到最優(yōu)。單純形法—跨躍式地尋求最優(yōu)解優(yōu)maxSS=ooABCDE凸集概念：

設(shè)D是n維線性空間Rn的一個(gè)點(diǎn)集，若D中的任意兩點(diǎn)x(1),x(2)的連線上的一切點(diǎn)x仍在D中，則稱D為凸集。凸集（非凸集）

開(kāi)始，用單純形表進(jìn)行換基迭代。后來(lái)的改進(jìn)單純形法，大大減少了計(jì)算量。為利用計(jì)算機(jī)創(chuàng)造了條件。最初使用手搖和電動(dòng)臺(tái)式計(jì)算器，不能完成特大量的計(jì)算。由于線性規(guī)劃應(yīng)用廣泛，大到整個(gè)國(guó)民經(jīng)濟(jì)計(jì)劃，小到一個(gè)車間的生產(chǎn)安排，因此受到重視。解線性規(guī)劃的能力迅速提高。1951年只能解約束條件為十幾個(gè)方程的問(wèn)題?，F(xiàn)在，能解上萬(wàn)個(gè)方程的問(wèn)題。且解題速度大大加快。專家們已經(jīng)用單純形解法開(kāi)發(fā)出了計(jì)算效率極高應(yīng)用軟件。運(yùn)用這個(gè)軟件，輸入數(shù)據(jù)，立即就可以打印出結(jié)果。

單純形解法應(yīng)用的發(fā)展過(guò)程例：一個(gè)企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費(fèi)的加工時(shí)間各不相同，從而獲得的利潤(rùn)也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計(jì)劃，才能使獲得的利潤(rùn)達(dá)到最大？解：數(shù)學(xué)模型

maxS=6x1+4x2s.t.2x1+3x2

1004x1+2x2

120x1,x2

0引進(jìn)松弛變量x3,x4

0數(shù)學(xué)模型標(biāo)準(zhǔn)形式：

maxS=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,

x3,x4

0

A=（P1，P2，P3，P4）

=23104201

X=（x1,x2,x3,x4)B=(P3，P4

）=1001P3，P4線性無(wú)關(guān)，x3和x4是基變量，x1、x2是非基變量。

用非基變量表示的方程：

x3=100-2x1-3x2x4=120-4x1-2x2(I)S=6x1+4x2令非基變量（x1,

x2）t=（0，0）t

得基礎(chǔ)可行解：

x(1)=(0,0,100,120)t

S1=0

經(jīng)濟(jì)含義：不生產(chǎn)產(chǎn)品甲乙，利潤(rùn)為零。分析：S=

6x1+

4x2（分別增加單位產(chǎn)品甲、乙，目標(biāo)函數(shù)分別增加6、4，即利潤(rùn)分別增加6百元、4百元。）

增加單位產(chǎn)品對(duì)目標(biāo)函數(shù)的貢獻(xiàn)，這就是檢驗(yàn)數(shù)的概念。

增加單位產(chǎn)品甲（x1）比乙對(duì)目標(biāo)函數(shù)的貢獻(xiàn)大（檢驗(yàn)數(shù)最大），把非基變量x1換成基變量，稱x1為進(jìn)基變量，而把基變量x4換成非基變量，稱x4為出基變量。確定了進(jìn)基變量x1

，出基變量x4

以后，得到新的系統(tǒng)：

x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)S=180+x2-（3/2）x4令新的非基變量（

x2，x4）=（0，0）t得到新的基礎(chǔ)可行解：x(2)=(30,0,40,0)t

S2=180經(jīng)濟(jì)含義：生產(chǎn)甲產(chǎn)品30個(gè)，獲得利潤(rùn)18000元。

這個(gè)方案比前方案，但是否是最優(yōu)？分析：S=180+x2-（3/2）x4非基變量x2系數(shù)仍為正數(shù)，確定x2為進(jìn)基變量。在保證常數(shù)項(xiàng)非負(fù)的情況下，確定x3為出基變量。得到新的系統(tǒng)：

x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)S=200-（1/2）x3-（5/4）x4

令新的非基變量（x3,x4）t=（0,0）t得到新的基礎(chǔ)可行解：x(3)=(20,20,0,0)t

S3=200經(jīng)濟(jì)含義：分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得利潤(rùn)20000元。分析：S=200-（1/2）x3-（5/4）x4目標(biāo)函數(shù)中的非基變量的系數(shù)無(wú)正數(shù)，S3=200是最優(yōu)值，x(3)=(20,20,0,0)t是最優(yōu)解。該企業(yè)分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得最大利潤(rùn)20000元。X(3)=(20,20,0,0)t相當(dāng)于Q2(20,20)X(1)=(0,0,100,120)t相當(dāng)于O(0,0)X(1)=(0,0,100,120)t相當(dāng)于O(0,0)X(2)=(30,0,40,0)t相當(dāng)于Q1(30,0)X(2)=(30,0,40,0)t相當(dāng)于Q1(30,0)X(3)=(20,20,0,0)t相當(dāng)于Q2(20,20)舉例:求解下列線性規(guī)劃問(wèn)題maxz＝1.5x1+2.4x2+0x3+0x4+0x5S.t.x1+x2+x3=1003x1+2x2+x4=1902x1+3x2+x5=240xj≥0(j=1,2,3…5)解：約束方程的系數(shù)矩陣為：1

1

100

A=(P1，P2，P3

，P4

，P5

）＝3

2

010

23

001初始可行基為：100B＝（P3，P4

，P5

）＝010001用非基變量表達(dá)基變量：

x3=100

－x1－1x2

x4=190

－3x1－2x2

x5=240

－2x1－3x2

將上式代入目標(biāo)函數(shù)得：

z=0+１.５x1+2.4x2令非基變量為零，即令x1＝0，x2＝0得一個(gè)基可行解：x（0）＝（0,0,100,190,240)此時(shí)得z＝0非基變量的系數(shù)都是正數(shù)，因此將非基變量變換成基變量，目標(biāo)函數(shù)的值就可能變大。取x2為入基變量（一般選擇正價(jià)值系數(shù)最大的非基變量為入基變量，而2.4>1.5）于是還要確定基變量x3，x4，x5中的一個(gè)換出來(lái)成為非基變量。下面來(lái)確定換出變量：當(dāng)x1=0時(shí)（先固定x1是兩個(gè)非基變量中的一個(gè)）,x3=100

－1x2≥0x4=190

－2x2≥0x5=240

－3x2≥0要讓x3，x4，x5非負(fù)，且有一個(gè)為0，只有選擇x2≤80時(shí)，才能使x3,x4x5同時(shí)非負(fù)。(此時(shí)x3≥20>0，x4≥30>0，x5≥0)因此只有當(dāng)x2=min(100/1,190/2,240/3)=80時(shí),才能使x3,x4x5非負(fù)的同時(shí)，有一個(gè)原來(lái)的基變量x5取值為0，從而可以換出來(lái)成為非基變量。其中x3=20

>0，

x4=30

>0，

X5=0，取X5為出基變量（所謂的最小比值規(guī)則）x2≤100x2≤

95x2≤80x2≤80用非基變量表達(dá)基變量：

x3+x2=100-x1x3=20

-1/3x1+1/3x5

x4+2x2=190-3x1x4=30-5/3x1+2/3x5

3x2=240-2x1-

x5x2=80

-2／3x1-1/3x5

將上式代入目標(biāo)函數(shù)得：z=192-0.1x1-0.8x5令非基變量為零，即x1＝0，x5＝0得一個(gè)基本可行解：x（1）＝（0,80,20,30,0),z=192由于非基變量的價(jià)值系數(shù)都是負(fù)數(shù)，而x1≥0，x5≥0，因此當(dāng)x1＝0，x5＝0時(shí)，z取得最大值192。所以最優(yōu)解

X*=x（1）＝（0,80,20,30,0),目標(biāo)函數(shù)值z(mì)*=192

c

c1c2cmcm+1cm+2cncBxBx1x2xmxm+1xm+2xnbc1c2cmx1x2xm

100a’1m+1a’1m+2a’1n

010a’2m+1a’2m+2a’2n

001a’mm+1a’mm+2a’mnb’1b’2b’m檢驗(yàn)數(shù)

0

00-z(0)用單純形表求解問(wèn)題例、用單純形表求解LP問(wèn)題解：化標(biāo)準(zhǔn)型表1：列初始單純形表（單位矩陣對(duì)應(yīng)的變量為基變量）

21000

01505100

0

24620100511001

21000

—24/65/1正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的列為主列主元化為1主列單位向量換出換入最小的值對(duì)應(yīng)的行為主行表2：換基（初等行變換，主列化為單位向量，主元為1）

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=主元檢驗(yàn)數(shù)>0確定主列

最小確定主列表3：換基

（初等行變換，主列化為單位向量，主元為1）

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

最優(yōu)解為X=(7/2,3/2,15/2,0,0)目標(biāo)函數(shù)值Z=8.5

2*7/21*3/2+0*15/28.5檢驗(yàn)數(shù)<=0例2、試?yán)脝渭冃伪砬罄?中的最優(yōu)解解：

得初始的單純形表：初始基本可行解，Z=-1，122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C

換入變量，換出變量，２為主元進(jìn)行旋轉(zhuǎn)變換基本可行解，Z=15，1/2

1

1

1/2

04x33151-40-205/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1

最優(yōu)解

最優(yōu)值

換入變量，換出變量，５/２為主元進(jìn)行旋轉(zhuǎn)變換4/1/21/2

1

1

1/2

04x33151-40-203/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C02/513/5-1/517/5x3381/5

0-26/50-9/5-2/516/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ

523-11Cmaxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2++x4=40