運籌學課件郵電經(jīng)濟管理學院

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

2x2adv

2x)

x(2)

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

c2x2約束條件

()

()

m2

,xnn

Zcjxj簡寫為

nn

aijx

()

(i12m)xj

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

pjx ()其中

X XC c1x

a

b1bxXx

Pj

1j

Bn

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

(min)

AX

)X0X0其中

C

c2

cn

a1n

x1

b1bAb

B

amn

n

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

圖解法單純形

三個變量下面我們分析一下簡單的情況——只有兩個決策 Copyright?2013 圖解圖解法的步驟1、在平面上建立直角坐標2、圖示約束條件，找出可3、圖示目標函數(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+可行可行此點是唯一最優(yōu)解且最優(yōu)目標函數(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此點是唯一最 可行maxminoL0：

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

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

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 習題2：maxZ=40x1+ ABC0DX1+ABC0DX1+2x2Z=40x1+80x23x1+2x22x224x1,x20求最優(yōu)解：BC線 Copyright?2013 圖解

習題

maxx13x2xx12 2xx12 3x

3

0、x24

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

Copyright?2013 習題

max 2x1x240x11.5x2

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

Copyright?2013 練習題

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

Copyright?2013 無 無可行

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

c2

...

cna11

...

a1n

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

,x2,..., Copyright?2013 對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ù)學模maxZmaxZcjxjns.tja ixi1,,j0,j1,,特特點目標函數(shù)求最大值（有時求最小值約束條件都為等式方程，且右端常數(shù)項bi都大于或等于決策變量xj為非負 Copyright?2013 線性規(guī)劃問題的數(shù)學模5如何化標準形 5如何化標準形

cj

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

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

x

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

j，可j

xj

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

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

aijx

xni

稱為松弛變aijx

aijx

xni

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

x3為松弛變當約束條件為“≥”時

12x2

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

+x5=xi0(i

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

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

0的變 Copyright?2013 線性規(guī)劃問題的數(shù)學模 x1+x2+x3--x1-x2-x3 Copyright?2013 線性規(guī)劃問題的數(shù)學模min52x2x2min52x2x2x3 x1xx24 331223x2 0,,x3無約束解:（１）因為x3無符號要求，即x3取正值也可取負值，標準

x3，且

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

3x 2(xx

min

2x1

3x3 5x1x2 x1x2x 3x1x

x34x32x3 Copyright?2013Czh

x2

0x3無約束線性規(guī)劃問題的數(shù)學模例1.minZ=-x1+2x2x1+x2+x3x1-x2+x3化 Copyright?2013 線性規(guī)劃問題的數(shù)學模解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 習題習題解練 Copyright?2013 練 練解解 Copyright?2013 練練習題3：將以下線性規(guī)劃問題轉(zhuǎn)化為標準minZ=-3x1+5x2+8 -7 2x1-3x2+5x3+6x4≤4x1+2x2+3x3-9x4≥6x2+2x3+3x4≤-x1,x3,x4≥ Copyright?2013 線性規(guī)劃問題的數(shù)學模k階子式--在m×n矩陣A中，任取k行與k列（k≤m,k≤n），位得的k階行列式，成為矩陣A的k階子式。 Copyright?2013 線性規(guī)劃問題的數(shù)學模矩陣的初等變換對調(diào)矩陣的兩行或兩列以非零數(shù)k乘矩陣的某一行（列）的所有元素 Copyright?2013 線性規(guī)劃問題的數(shù)學模6規(guī)劃問題的解ns.tnj Copyright?2013 線性規(guī)劃問題的數(shù)學模最優(yōu)解：使目標函數(shù)達到最大值的可行解 Copyright?2013 線性規(guī)劃問題的數(shù)學模

a1mB

(

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

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

11110

22

非0101001

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

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

x

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

4x22x1

x

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

0

1 1

biLa Copyright?2013

3x14x2單純形法的計算步

2x1x2 x

x,x,x,

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

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

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

max{

|

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

L

aik

③用換入變量x替換基變量中的換出變量，得到一個新的基。對00/1/10復3）、4）opyright?2013Czhang. .用單純形法求下列線性規(guī)劃的最優(yōu)maxz=2x1+3x2x1+2x284 4x212x1,x20解：化為標準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 練練習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 練練習題 用單純形法求 Copyright?2013 練最優(yōu)解

最優(yōu)值

Copyright?2013 練練習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進基 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 學習學習要點線性規(guī)劃解的概念以及3個基本定熟練掌握單純形法的解題思路及求解步 Copyright?2013 單純形法的進一步討論－人工人工變量法 Copyright?2013 單純形法的進一步討論－人工例1.10用大M法解下列線性規(guī)

3

2

x34x13x2x3xxxx

2

12x2x1

x1、x2、x3解：首先將數(shù)學模型化為標準形

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

j

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

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

2 xj j 其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。 Copyright?2013 pygg單純形法的進一步討論－人工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 單純形法的進一步討論－人工解的判別唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零則線性規(guī)劃具有唯一最優(yōu)解多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解） 解的判別：存在某個基變量為零的基本可行解。（略 Copyright?2013 兩階段s. Copyright?2013s.兩階段 Copyright?2013 兩階段在第一階段中，當人工變量取值為0時，目標函數(shù) Copyright?2013 解題過程第1階段：解輔助問題當進行到最優(yōu)表時①若W=0,則得到原問題的一個基本可行解，轉(zhuǎn)②若W>0,則判定原問題無可行解 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)目標函數(shù)值為Wx可轉(zhuǎn)入第二階段。去除人工變量，以第一階段最優(yōu)解為基可行解 Copyright?2013 去除人工變量，以第一階段的最優(yōu)解為基可行解,求解原問題2000b20100010001000020121210101100001020002023110010001100111000解為：X=(0,3,1,2,0)T目標函數(shù)值為:maxZ=-x1+2x2單純形法小單純性法小結(jié)個數(shù) 右端項不等極大或極兩個以約xj≤bibi<≤=≥求解形令xjx′jxj′≥0xj″令x=-同乘-z′Zmaxz′0- Copyright?2013 單純形法計算步驟框單純形法計算步驟框計算檢驗數(shù)是所有σi

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

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

0)

迭代運xk進

用xk替換min( iai,k0)

列出新的alx離l1

al1

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