第四章線性規(guī)劃的標(biāo)準(zhǔn)型及單純形法課件

運(yùn)籌學(xué)

碩士生導(dǎo)師

OperationsResearch1精選課件ppt第４章

線性規(guī)劃的標(biāo)準(zhǔn)型及單純形法2精選課件ppt3精選課件ppt線性規(guī)劃的標(biāo)準(zhǔn)型（SLP）

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2

……am1x1+am2x2+…amnxn=bmx1,x2,…,xn≥04精選課件ppt標(biāo)準(zhǔn)型的特征目標(biāo)函數(shù)極大化約束條件為等式?jīng)Q策變量非負(fù)5精選課件ppt線性規(guī)劃的標(biāo)準(zhǔn)型代數(shù)式

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bm

x1,x2,…,xn≥0（xj≥0

j=1,2,…,n）

6精選課件ppt線性規(guī)劃的標(biāo)準(zhǔn)型和式：7精選課件ppt線性規(guī)劃的標(biāo)準(zhǔn)型向量式：8精選課件ppt線性規(guī)劃的標(biāo)準(zhǔn)型矩陣式：9精選課件ppt非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化：

minZ=-max(-Z)，一個(gè)數(shù)的極小化等價(jià)于其相反數(shù)的極大化。不等式約束的轉(zhuǎn)化：∑aijxj≤bi加入松弛變量

∑aijxj≥bi減去剩余變量非正變量：即xk≤0則令x’k=-xk

自由變量：即xk無約束，令xk=x’k-x”k10精選課件ppt非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2≤2004X1+5X2+x4=2003X1+10X2≤3003X1+10X2+x5=300X1≥0X2≥0X1≥0X2≥0X3≥0x4

≥0x5≥0

11精選課件ppt非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之二minZ=x1+2x2-3x3maxZ’=x’1-2x2+3(x’3-x”3)

x1+x2+x3

≤9-x’1+x2+x’3-x”3+x4=9-x1-2x2+x3≥2x’1-2x2+x’3-

x”3-x5=23x1+x2-3x3=5-3x’1+x2-3(x’3-

x”3)=5x1≤0x2≥0x3無約束

x’1≥0x2≥0x’3≥0x”3≥0x4≥0

x5≥0

12精選課件ppt非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之三minZ=-3x1-x2+4x3-x1+2x2+x3

=5x1-x2+x3≥-6x1≤0x2≥0x3無約束13精選課件ppt非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之三minZ=-3x1-x2+4x3maxZ’=-3x’1+x2-4(x’3-x”3)

-x1+2x2+x3

=5x’1+2x2+x’3-x”3=5

x1-x2+x3≥-6x’1+x2-（x’3-

x”3）+x4=6x1≤0x2≥0x3無約束

x’1≥0x2≥0x’3≥0x”3≥0x4≥014精選課件ppt基可行解秩基基可行解15精選課件ppt秩設(shè)m×n矩陣A中有一個(gè)r階子式D不等于零，而所有r+1階子式（如果存在的話）全等于零，則稱D為矩陣A的最高階非零子式，稱數(shù)r為矩陣A的秩，記作R(A)=r。零矩陣的秩為零。m×n矩陣A的秩R(A)≤min{m,n}假設(shè)：約束方程組的系數(shù)矩陣A的秩為m（R(A)=m）,m<n16精選課件ppt基基的概念：如前所述LP標(biāo)準(zhǔn)型和式：maxZ=∑cjxj

∑aijxj=bi

xj≥0

j=1,2,…,n

矩陣式：maxZ=CXAX=bX≥0

約束方程的系數(shù)矩陣A的秩為m，且m<n。設(shè)A=B+N，B是A中mxm階非奇異子矩陣，則稱B是LP的一個(gè)基，即：B是A中m個(gè)線性無關(guān)向量組。17精選課件ppt基解不失一般性,設(shè)B是A的前m列,即B=(p1,p2,…,pm）,其相對(duì)應(yīng)的變量XB=(x1,x2,…,xm)T,稱為基變量；其余變量XN=(Xm+1,…,Xn)T稱為非基變量。

令所有非基變量等于零,

則X=（x1,x2,…xm,0,…,0)T稱為基解。18精選課件ppt基可行解基可行解：基解可正可負(fù)，負(fù)則不可行，故稱滿足非負(fù)性條件的基解為基可行解。相應(yīng)的基為可行基。退化的基可行解：若某個(gè)基變量取值為零，則稱之為退化的基可行解?；獾臄?shù)目：最多Cmn=n!/m!(n-m)!19精選課件ppt例題6基可行解說明

maxZ=70X1+120X2P1P2P3P4P59X1+4X2+X3=360941004X1+5X2+x4=200A=450103X1+10X2+x5=300310001Xj≥0j=1,2,…,5這里m=3,n=5。Cmn=1020精選課件ppt例題6基可行解說明基（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，則基變量x2=30,x3=240,x4=50,可行解（P21圖）21精選課件ppt（SLP）的基可行解對(duì)應(yīng)于其可行域的頂點(diǎn)（極點(diǎn)）若（SLP）有最優(yōu)解，則必有最優(yōu)基可行解可行基解——迭代——更優(yōu)的可行基解——最優(yōu)基解（單純形法的原理）22精選課件ppt單純形法最優(yōu)性檢驗(yàn)：LP經(jīng)過若干步迭代，成為如下形式：X1++a’1m+1xm+1+…+a’1nxn=b’1

x1=b’1-∑a’1jxj

x2++a’2m+1xm+1+…+a’2nxn=b’2x2=b’2-∑a’2jxj……………..……………..

xm+a’mm+1xm+1+…+a’mnxn=b’mxm=b’m-∑a’mjxj23精選課件ppt單純形法24精選課件ppt單純形法基變換若σj≥0，則取max{σj}=σK

，相應(yīng)之非基變量XK若非零，將使Z增加,故令XK

進(jìn)基。令XK≠0其余非基變量保持為零，XK

原是非基變量，取零值，XK≠0將迫使某個(gè)原基變量為零，當(dāng)XK取值超過任意b’i/a’ik

時(shí),將破壞非負(fù)性條件,于是令θ=min{b’i/a’ik

，a’ik>0}=b’L/a’Lk

。這時(shí)原基變量XL=0，由基變量變成非基變量a’Lk處在變量轉(zhuǎn)換的交叉點(diǎn)上，稱之為樞軸元素25精選課件ppt單純形法解題舉例單純形表的格式：CjC1C2…CN

θiCBXBbX1x2….Xn

C1C2

…CMX1X2…XMb1B2…bma11a12…a1na21a22…a2n………am1am2…amnθ1θ2…θmσjσ1σ2…σn26精選課件ppt產(chǎn)品A產(chǎn)品B資源限制勞動(dòng)力設(shè)備原材料9434510360工時(shí)200臺(tái)時(shí)300公斤單位產(chǎn)品利潤（元）70120某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：27精選課件ppt問題：如何安排生產(chǎn)計(jì)劃，使得獲利最多？步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：人力約束9X1+4X2≤360

設(shè)備約束4X1+5X2≤200

原材料約束3X1+10X2≤300

非負(fù)性約束X1≥0X2≥028精選課件pptCj70120000CBXBbX1

X2

X3X4X5θi000X3X4X536020030094100

45010310001904030σj0

7012000000120X3X4X224050

307.8010-0.42.5001-0.50.31000.130.7620100σj360034000-12070120X3X1X2842024001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.229精選課件pptCj3-305-1CBXBbX1

X2

X3X4X5θi3-3-1X1X2X51212710-2[2]001-20000-43112/2=6-27/3=9600-4205-3