運(yùn)籌學(xué)課件郵電經(jīng)濟(jì)管理學(xué)院

線性規(guī)劃與單純形郵電大學(xué)經(jīng)濟(jì)管理學(xué)： Copyright?2013 Chapter1線性規(guī)(Linear本章主要內(nèi)容本章主要內(nèi)容單純形單純形法的進(jìn)一步討論－人工變量LP模型的應(yīng) Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模規(guī)劃問線性規(guī)劃通常解決下列兩類問題用最少的資源（如 線性規(guī)劃通常解決下列兩類問題最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大.） Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模x例1.1如圖所示，如何截取x使鐵皮所圍成的容積最xv

2x2adv

2x)

x(2)

2x)2x6 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模例1.2生產(chǎn)計(jì)劃問 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模生產(chǎn)方案2生產(chǎn)20個(gè)桌子，10個(gè)椅子，木工仍剩余10小 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模資源使用利用產(chǎn)品數(shù)使用資剩余資收桌椅木油木油100203 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模目標(biāo)函 Maxz約束條 4x1+3x2≤2x1+x2≤x1,x2 Copyright?2013 例1.3:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙設(shè)備32設(shè)備21設(shè)備03利潤(rùn)（元/件問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn) Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模解：設(shè)變量為第種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)＝，2）。根據(jù)題意，我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力（機(jī)時(shí)數(shù)）的限制。 是我們可以得到不等式：3x1+2x2≤65； 是我們可以得到不等式：2x1+x2≤40； Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模 是我們可以得到不等式：3x2≤75；另外，產(chǎn)品數(shù)不可能為負(fù)，即x1,x2≥0。 x2。綜合上述討論，在加工時(shí)間以及利潤(rùn)與 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模目標(biāo)函 Maxz 約束條 3x1+2x2≤2x1+x2≤3x2≤75x1,x2 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模練習(xí)某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分設(shè)產(chǎn)ABCD利潤(rùn)（元甲2乙8 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為 Z=2x1+2x1+2x2≤x1+ ≤ ≤ ≤x1≥0,x2≥ Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模 Decisionvariables目標(biāo)函 Objective約束條 問題都用一組決策變量表示某個(gè)方 Copyright?2013 在管理中一些典型的線性規(guī)劃合理利用線材問題：如何在保證生產(chǎn)的條件下，下料最配料問題：在原料供應(yīng)量的限制下如何獲取最大利投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最 Copyright?2013 練 班時(shí)所需人16：00——210：00——314：00——418：00——522：00——62：00—— Copyright?2013 解：設(shè)xi表示第i班次時(shí)開始上班的 目標(biāo)函數(shù) x1+x2+x3+x4+x5+約束條件+≥+≥+≥+≥+≥+≥x1,x2,x3,x4,x5,x6≥ Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模cn線性規(guī)劃數(shù)學(xué)模型cn目標(biāo)函數(shù)：max(min)

c2x2約束條件

()

()

m2

,xnn

Zcjxj簡(jiǎn)寫為

nn

aijx

()

(i12m)xj

(j12n) Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模向量形式

pjx ()其中

X XC c1x

a

b1bxXx

Pj

1j

Bn

m Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模矩陣形式：

(min)

AX

)X0X0其中

C

c2

cn

a1n

x1

b1bAb

B

amn

n

mxx Copyright?2013 圖解線性規(guī)劃問題的求解方坐兩個(gè)變量、直角坐坐—般有

圖解法單純形

三個(gè)變量下面我們分析一下簡(jiǎn)單的情況——只有兩個(gè)決策 Copyright?2013 圖解圖解法的步驟1、在平面上建立直角坐標(biāo)2、圖示約束條件，找出可3、圖示目標(biāo)函數(shù)和尋找最 Copyright?2013 圖解例1.6用圖解法求解線性規(guī)劃問maxZ=2X1+X1+1.9X2≥3.8X1-1.9X2≤s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0 Copyright?2013 圖解 Z=2X1+ X1+1.9X2=11=

X1-1.9X2=-3.817.2=2X1++4=2X1+ 20=2X1+可行可行此點(diǎn)是唯一最優(yōu)解且最優(yōu)目標(biāo)函數(shù)maxmaxZminZoLo：0=2X1+

X1+1.9X2=

X1-1.9X2= Copyright?2013 圖解max

X1+1.9X2=10.2可行

X1-1.9X2=-maxZ=34.2是唯一的。maxo

X1+1.9X2=X1-1.9X2=3.8L0：

34.2= Copyright?2013 圖解min X1+1.9X2=10.2DD此點(diǎn)是唯一最 可行maxminoL0：

X1+1.9X2=X1-1.9X2=3.8 Copyright?2013 8例1.7maxZ=2x14x22x1+x28-2x1+x2 x1,x2 解2無(wú)有限最優(yōu)0

-2x1+ 2x1+ Copyright?2013 -0--0-max-x1-x2x1,x2無(wú)無(wú)可行 Copyright?2013 習(xí)題1：maxZ=40x1x1+2x23x1+2x22x224x1,x20 Copyright?2013 解：(1)、建立坐標(biāo)、確定可行

X1+2X2maxZ=40x1+3X1+2X2x1+2x2x1+2x2x1+2x2x1+2x2(0,15)2

+2x2

2X2 2x,22x1,x23x13x1+2x2(0,30) 2x22x2x1x1 x1=0(縱x2 x2=0(橫

Copyright?2013 、求最優(yōu)

maxZ=40x1+x1+2x2x2=-

+2x22x2C

x1,x23x1+2x2

解：x1解：x1x2=maxZ

Copyright?2013 習(xí)題2：maxZ=40x1+ ABC0DX1+ABC0DX1+2x2Z=40x1+80x23x1+2x22x224x1,x20求最優(yōu)解：BC線 Copyright?2013 圖解

習(xí)題

maxx13x2xx12 2xx12 3x

3

0、x24

解(無(wú)最優(yōu)解maxZminZ

Copyright?2013 習(xí)題

max 2x1x240x11.5x2

30x1x250 x10,x2 無(wú)可行解(即無(wú)最優(yōu)解 Copyright?2013 習(xí)題習(xí)題 z=2x1+3x2x1+2x284x14x212 Copyright?2013 1o.建立平面直角坐標(biāo)系；3o.畫出目標(biāo)函數(shù)的等值線；4o.向著目標(biāo)函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與可行域的最后交點(diǎn)，這種點(diǎn)就對(duì)應(yīng)最優(yōu)解。 z=2x1 z=2x1+3x2x1+2x284x14x212 3

Copyright?2013 練習(xí)題

最優(yōu)+最優(yōu)- 可行x1≥0,可行4- 目標(biāo)目標(biāo)函數(shù) Copyright?2013 解解無(wú)無(wú)可行 Copyright?2013 解解無(wú)無(wú)可行 Copyright?2013 解 解無(wú)無(wú)可行

Copyright?2013 無(wú) 無(wú)可行

Copyright?2013 學(xué)習(xí)要點(diǎn)通過圖解法了解線性規(guī)劃有幾種解的形（唯一最優(yōu)解；無(wú)窮多最優(yōu)解 解；無(wú)可行解作圖的關(guān)鍵有三點(diǎn)可行解區(qū)域要畫正目標(biāo)函數(shù)增加的方向不能畫目標(biāo)函數(shù)的直線怎樣平行移 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模線性規(guī)劃問題的標(biāo)準(zhǔn)形max

c2

...

cna11

...

a1n

x x... 2n x x... m2

,x2,..., Copyright?2013 對(duì)max(min)

cxc

c

max(min)Zcjxax x

()

j

nnj

aijx

()

(i12m)am1

am2

amn

()

xj

(j12n)

xnmax

c2

...

cn

...

a21

a22

...

a2n

am2

...

amn

maxZcjxjnsmaxZcjxjns.tja ixi1,,j0,j1,,

C C線性規(guī)劃問題的數(shù)學(xué)模maxZmaxZcjxjns.tja ixi1,,j0,j1,,特特點(diǎn)目標(biāo)函數(shù)求最大值（有時(shí)求最小值約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于決策變量xj為非負(fù) Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模5如何化標(biāo)準(zhǔn)形 5如何化標(biāo)準(zhǔn)形

cj

則可將目標(biāo)函數(shù)乘以(-可化為求極大值問題 maxzzcjx也就是：令z

z，可得到上式 Copyright?2013 minZ=2x1+5x2+6x3maxZ’=-Z=-2x1–5x2-6x3-返返 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模jj 變量x 的變 jjjxj

x

x 變量的變?nèi)舸嬖谌≈禑o(wú)約束的變量

j，可j

xj

Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模3x1+2x2例令x1x1x1x1"0

x1–4x2令x2x2'3x1'-3x1"-2x2'8x1' x1"+4x2'x1',x1",x2' Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式aijxj

aijx

xni

稱為松弛變aijx

aijx

xni

稱為剩余變 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模約束條當(dāng)約束條件為“≤”時(shí)

x3為松弛變當(dāng)約束條件為“≥”時(shí)

12x2

x4為剩余變未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)，所以引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模例maxZ=2x1+ +0·x3例6x1+2x2x1+

+x5=xi0(i

松弛變 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模例minZ=2x15x2+6x3-4x1+6x2+-x1+ x2+7x3+5x42x2+xi0(i

+0x5+0x6- -x7剩余變 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模可在等式兩端乘可在等式兩端乘以“-1”。當(dāng)出現(xiàn)一，這點(diǎn)將在以后討論bi=0時(shí)，表示出

0的變 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模 x1+x2+x3--x1-x2-x3 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模min52x2x2min52x2x2x3 x1xx24 331223x2 0,,x3無(wú)約束解:（１）因?yàn)閤3無(wú)符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)

x3，且

Copyright?2013 minZ2minZ2x1x23x35x1x2x3x 41233x 2123x1x20x3無(wú)約束””第一個(gè)約束條件是“≤”號(hào)，在””左端加入松馳變量x，x≥0,化為 式第二個(gè)約束條件是“≥”號(hào)，在左端減去剩余變量x，x Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模標(biāo)準(zhǔn)形式如下maxZ'2x 3(xx)0x 0x

3x 2(xx

min

2x1

3x3 5x1x2 x1x2x 3x1x

x34x32x3 Copyright?2013Czh

x2

0x3無(wú)約束線性規(guī)劃問題的數(shù)學(xué)模例1.minZ=-x1+2x2x1+x2+x3x1-x2+x3化 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模解x3=x4松弛變量

minZ=-x1+2x2xx1+x2+x37x1-x2+x3Z'=maxZ'=x1–2x2-3x4+3x5+0x6x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,x2,x4,…,x70 Copyright?2013 習(xí)題習(xí)題解練 Copyright?2013 練 練解解 Copyright?2013 練練習(xí)題3：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)minZ=-3x1+5x2+8 -7 2x1-3x2+5x3+6x4≤4x1+2x2+3x3-9x4≥6x2+2x3+3x4≤-x1,x3,x4≥ Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模k階子式--在m×n矩陣A中，任取k行與k列（k≤m,k≤n），位得的k階行列式，成為矩陣A的k階子式。 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模矩陣的初等變換對(duì)調(diào)矩陣的兩行或兩列以非零數(shù)k乘矩陣的某一行（列）的所有元素 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模6規(guī)劃問題的解ns.tnj Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模

a1mB

(

pm mmB中每個(gè)列向量Pjj12m為基向量。與基向量Pj對(duì)應(yīng)的變量xj為基變量。除基變量以外的變量為非基變量。 Copyright?2013 2x1+3x2-x3≤18x1-x2+x3≤3 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模maxZ= x1,x2,x3,x4,x5,x6,≥0100 100 10.非11331100010 23 123 1 基

Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模maxZ= x1,x2,x3,x4,x5,x6,≥0121 12133 1

11110

22

非0101001

ht?2013 線性規(guī)劃問題的數(shù)學(xué)?！瑼= … …Pn …基向 非基向 基陣非基矩…X= … …xn)T=(XB…基變 非基變 Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模設(shè)XB是對(duì)應(yīng)于基的基變XB=（x1,x2,現(xiàn)若令上式的非基變量xm+1=xm+2=…=xn=0,這時(shí)變量的 XB=（x1,x2,…,xm,0,…,0）T Cn值的個(gè)數(shù)不大于方程數(shù)m，基解的總數(shù)不超 Cn Copyright?2013 線性規(guī)劃問題的數(shù)學(xué)模 Copyright?2013 例 2x1+3x2-x3≤18x1-x2+x3 化為標(biāo)準(zhǔn)

x1,x2,x3,x4,x5,x6,≥0 Copyright?2013 基變量x1、x2、x3，非基變量x4、x5、基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為 Copyright?2013 基變量x1、x2、x4，非基變量x3、x5、基礎(chǔ)解（x1，x2，x3，x4，x5，x6）=（27/5，12/，0，2/，0，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為 Copyright?2013 基變量x1、x2、x5，非基變量x3、x4、基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，3，0）是基礎(chǔ)解，但不是可行解，不是一個(gè)極點(diǎn)。 Copyright?2013 基變量x1、x2、x6，非基變量x3、x4、基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為 Copyright?2013 基變量x2、x3、x4，非基變量x1、x5、基礎(chǔ)解（x1，x2，x3，x4，x5，x6）=（0，21/，27/2，30，0，0）是基礎(chǔ)解，但不是可行解。 Copyright?2013 基變量x2、x3、x5，非基變量x1、x4、基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為 Copyright?2013 基變量x2、x3、x6，非基變量x1、x4、基礎(chǔ)解（x1，x2，x3，x4，x5，x6）=（0，1/，3/，0，0，10）是基礎(chǔ)解但不是可行解。 Copyright?2013 凸凸不凸凸不是凸 Copyright?2013 Copyright?2013 單純形單純形法的思找出找出一個(gè)初始基可行最優(yōu)是否最最優(yōu)否循否轉(zhuǎn)移到另一個(gè)轉(zhuǎn)移到另一個(gè)基本可行（找出更大的目標(biāo)函數(shù)值是：變量迭 Copyright?2013 用表格法求解LP問題，規(guī)范的表 單純形表如下所……b……10……00………………0…1…0…0…cj行——價(jià)值系數(shù)，b列——列——下面一行——檢驗(yàn)數(shù)，中間主要部分—— Copyright?2013 單純形法的計(jì)算步例1.12用單純形法求下列線性規(guī)劃的最優(yōu)maxZ3x14x22x1

x

x,x，加入松馳變，加入松馳變量x3、x4為解：1）將問題化

4x22x1

x

x,x,x, Copyright?2013 maxZ3maxZ3x14x22x1x2x13x2x,x,x,x4 00b3213400b3213434000010檢驗(yàn)1c1(c3a11c4a21)3(0 0jci Copyright?2013 maxmaxZ3x1 x,x,x,xxx2x1x242將3將3化為換入 換換行 基變

0

1 1

biLa Copyright?2013

3x14x2單純形法的計(jì)算步

2x1x2 x

x,x,x,

b0211001301j3400 400b0404010100maxZmaxZ3x14x22x1x2xx,x,x,124 001044013b0043 Copyright?2013 單純形法的計(jì)算步將問題化 求出線性規(guī)劃的初始基可行解，列出初始單純形表 Copyright?2013 單純形法的計(jì)算步進(jìn)行最優(yōu)性檢①如果表中所有檢驗(yàn)

0，則表中的基可行解就是題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步②如果表中所有檢驗(yàn)

0，且某非基變量檢驗(yàn)數(shù)為零則此問題含有無(wú)窮多最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步③如果表中某非基變量的檢驗(yàn) ，且對(duì)于系數(shù)矩中換入列中的所有系數(shù)都小于等于0無(wú)法 ），則問題無(wú)可行解。計(jì)算停止。否則繼續(xù)下一步 Copyright?2013 單純形法的計(jì)算步 確定換入基的變量。選擇j0，對(duì)應(yīng)的變量xj作為換入kk

max{

|

，其對(duì)應(yīng)的xk作為換入 確定換出變量。根據(jù)下式計(jì)算并選擇θ，選最小的θ對(duì)應(yīng)變量作為換出變

L

aik

③用換入變量x替換基變量中的換出變量，得到一個(gè)新的基。對(duì)00/1/10復(fù)3）、4）opyright?2013Czhang. .用單純形法求下列線性規(guī)劃的最優(yōu)maxz=2x1+3x2x1+2x284 4x212x1,x20解：化為標(biāo)準(zhǔn)maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3 =8 4 x1,…x5 Copyright?2013 2300023000 b000814020(4)100010001423000X(0)=(0，0，8，16，12)T，z023000 b0032314000110001024-20002300023000 b00323(14000110001024-200023000 b20328310000110010-4000 Copyright?2013 2300023000 b20328310000110010(200023000 b2034421000010010000X(3)=(4，2，0，04)Tz3=14（最優(yōu)解 Copyright?2013 練練習(xí)2.用單純形法求解線性規(guī)劃問

x4x1x2

5x

xx 4xx,x2,x3,x4解：原問題化

z

x1x2

5x

x

x Copyright?2013 練z3xz3x15x2x1x25x1246x347,x2,x73501000θb011101000510-0100500-1001σj=cj- Copyright?2013 θ–θ–σj=cj-X2入基3501000X6出3501000b011101000510-0100500-1001 Copyright?2013 3501000θb0-0111-05510-010–05001-0015σj=cj--0060-00-0201--9551-0011–1500-1001–σj=cj--0600-09-00--1531001-001-σj=cj--000---練3501000θb09-010--531001-001-σj=cj--000---最優(yōu)解作業(yè)

最優(yōu)值

Copyright?2013 練練習(xí)題 用單純形法求 Copyright?2013 練最優(yōu)解

最優(yōu)值

Copyright?2013 練練習(xí)4.用單純形法求解線性規(guī)劃問max

2x1 5x26x2x x1

x2 x1,x2 Copyright?2013 練解 maxz=2x解 x1+x2 Copyright?2013 maxmax x1+x2 2、列初始單純形表θbσj=cj- Copyright?2013 maxmax x1+ 21000bθ00510 06201 05110015σj=cj-21000X1σj=cj-21000 Copyright?2013 練2121000b020100511001σj=cj-005100

σj=cj-

Copyright?2013 練3、列新單純形表 θ σj=cj- σj=cj-

- - -

3X2進(jìn)基 X5出基 Copyright?2013 練2121000b00510024100 σj=cj-

- 005100241001010-σj=cj- Copyright?2013 21000θb005100241001010-σj=cj-0051002100-1010-σj=cj-0001-2100-1010-σj=cj- Copyright?2013 練4、列新單純形表21000θb0001-2100-1010-σj=cj-000--解為：X=(7/2,3/2,15/2,0,0)T Copyright?2013 學(xué)習(xí)學(xué)習(xí)要點(diǎn)線性規(guī)劃解的概念以及3個(gè)基本定熟練掌握單純形法的解題思路及求解步 Copyright?2013 單純形法的進(jìn)一步討論－人工人工變量法 Copyright?2013 單純形法的進(jìn)一步討論－人工例1.10用大M法解下列線性規(guī)

3

2

x34x13x2x3xxxx

2

12x2x1

x1、x2、x3解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形

系數(shù)矩陣中不存xx22x

j

立初始單純形表 Copyright?2013 單純形法的進(jìn)一步討論－人工故人為添加兩個(gè)單位向量，得

人工變量單純形法數(shù)學(xué)模型

2 xj j 其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。 Copyright?2013 pygg單純形法的進(jìn)一步討論－人工pygg332-00--b-4-31-010401-201005-12-1000113----3-50-0108-30010-12-1000—5-0-002100—0001-010—j5000020101231001-0010000--→→練最優(yōu)解

,9,

最優(yōu)值

Copyright?2013 單純形法的進(jìn)一步討論－人工解的判別唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零則線性規(guī)劃具有唯一最優(yōu)解多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零則線則性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解） 解的判別：存在某個(gè)基變量為零的基本可行解。（略 Copyright?2013 兩階段s. Copyright?2013s.兩階段 Copyright?2013 兩階段在第一階段中，當(dāng)人工變量取值為0時(shí)，目標(biāo)函數(shù) Copyright?2013 解題過程第1階段：解輔助問題當(dāng)進(jìn)行到最優(yōu)表時(shí)①若W=0,則得到原問題的一個(gè)基本可行解，轉(zhuǎn)②若W>0,則判定原問題無(wú)可行解 Copyright?2013 例 maxZ=-x1x1+x2-x1+x2x2x1x2 maxZ=-x1x1+x2--x1

+x7 x1…x50,x6,x7增加人工變 Copyright?2013 minW=x6x1+x2- -x1+x2 +x7=1 x1…x70000011θb1211-0010211-10-001103010010030211000 Copyright?2013 0000011b1211-0010111-0-00030100100110-01-1100010-01-10-00102100110--01-002010-0-001--0000-1--0000011解為：X=(1/2,3/2,0,0,3/2,0,0)目標(biāo)函數(shù)值為Wx可轉(zhuǎn)入第二階段。去除人工變量，以第一階段最優(yōu)解為基可行解 Copyright?2013 去除人工變量，以第一階段的最優(yōu)解為基可行解,求解原問題2000b20100010001000020121210101100001020002023110010001100111000解為：X=(0,3,1,2,0)T目標(biāo)函數(shù)值為:maxZ=-x1+2x2單純形法小單純性法小結(jié)個(gè)數(shù) 右端項(xiàng)不等極大或極兩個(gè)以約xj≤bibi<≤=≥求解形令xjx′jxj′≥0xj″令x=-同乘-z′Zmaxz′0- Copyright?2013 單純形法計(jì)算步驟框單純形法計(jì)算步驟框計(jì)算檢驗(yàn)數(shù)是所有σi

最優(yōu)對(duì)某一 有Pi否

無(wú)可行 無(wú)窮最優(yōu)

0)

迭代運(yùn)xk進(jìn)

用xk替換min( iai,k0)

列出新的alx離l1

al1

1）對(duì)主元素行（第l行2)其他行bi＝bi－aibaia Copyright?2013 一般而言，一個(gè)經(jīng)濟(jì)、管理問題凡是滿足以下條存在著多種方 Copyright?2013 線性規(guī)劃在管理人力資源分配問例 某晝