線性規(guī)劃運(yùn)籌學(xué)

線性規(guī)劃線性規(guī)劃問題可行區(qū)域與基本可行解單純形算法初始可行解對(duì)偶理論靈敏度分析計(jì)算軟件案例分析運(yùn)籌學(xué)課件※結(jié)束♂返回線

性

規(guī)

劃

問

題線性規(guī)劃實(shí)例

生產(chǎn)計(jì)劃問題

運(yùn)輸問題線性規(guī)劃模型

一般形式

規(guī)范形式

標(biāo)準(zhǔn)形式

形式轉(zhuǎn)換

概念

運(yùn)籌學(xué)課件♂返回線性規(guī)劃某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，試制訂總利潤最大的生產(chǎn)計(jì)劃單位產(chǎn)品所需原料數(shù)量（公斤）產(chǎn)品Q1產(chǎn)品Q2產(chǎn)品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000單位產(chǎn)品的利潤（千元）354運(yùn)籌學(xué)課件線性規(guī)劃

問題分

析運(yùn)籌學(xué)課件線性規(guī)劃

模

型運(yùn)籌學(xué)課件線性規(guī)劃運(yùn)

輸

問

題運(yùn)籌學(xué)課件線性規(guī)劃問

題

分

析運(yùn)籌學(xué)課件線性規(guī)劃模型♂返回運(yùn)籌學(xué)課件線性規(guī)劃線

性

規(guī)

劃

問

題線性規(guī)劃的三要素：目標(biāo)函數(shù)：MaxF或MinF約束條件：s.t.(subjectto)滿足于決策變量：用符號(hào)來表示可控制的因素一般地，在一組線性等式或不等式的約束下，求一個(gè)線性函數(shù)的最大值或最小值的問題稱為線性規(guī)劃問題。一

般

形

式目標(biāo)函數(shù)約束條件運(yùn)籌學(xué)課件線性規(guī)劃注

釋♂返回運(yùn)籌學(xué)課件線性規(guī)劃規(guī)

范

形

式♂返回運(yùn)籌學(xué)課件線性規(guī)劃標(biāo)

準(zhǔn)

形

式♂返回運(yùn)籌學(xué)課件線性規(guī)劃概

念運(yùn)籌學(xué)課件線性規(guī)劃模

型

標(biāo)

準(zhǔn)

化變量轉(zhuǎn)換

目標(biāo)轉(zhuǎn)換約束轉(zhuǎn)換實(shí)例♂返回運(yùn)籌學(xué)課件線性規(guī)劃不

等

式

變

等

式♂返回剩余變量運(yùn)籌學(xué)課件線性規(guī)劃例：把問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式♂返回運(yùn)籌學(xué)課件線性規(guī)劃可

行

區(qū)

域

與

基

本

可

行

解

圖解法

可行域的幾何結(jié)構(gòu)

基本可行解與基本定理♂返回運(yùn)籌學(xué)課件線性規(guī)劃圖

解

法運(yùn)籌學(xué)課件線性規(guī)劃例2.2.1運(yùn)籌學(xué)課件線性規(guī)劃運(yùn)籌學(xué)課件線性規(guī)劃注

釋線性規(guī)劃解的的情況：

可行域是空集（問題無解）無界

唯一的最優(yōu)解，（一定在可行域頂點(diǎn)上達(dá)到）有無窮多最優(yōu)解，（一定存在可行域的頂點(diǎn)是最優(yōu)解）♂返回運(yùn)籌學(xué)課件線性規(guī)劃可

行

域

的

幾

何

結(jié)

構(gòu)基本假設(shè)凸集可行域的凸性♂返回運(yùn)籌學(xué)課件線性規(guī)劃基

本

假

設(shè)♂返回運(yùn)籌學(xué)課件線性規(guī)劃凸集♂返回運(yùn)籌學(xué)課件線性規(guī)劃問題♂返回運(yùn)籌學(xué)課件線性規(guī)劃基本可行解與基本定理定義基本定理問題♂返回運(yùn)籌學(xué)課件線性規(guī)劃♂返回運(yùn)籌學(xué)課件線性規(guī)劃基

本

可

行

解

定

義基

本

可

行

解

定

義運(yùn)籌學(xué)課件線性規(guī)劃♂返回運(yùn)籌學(xué)課件線性規(guī)劃基

本

定

理♂返回運(yùn)籌學(xué)課件線性規(guī)劃說

明♂返回運(yùn)籌學(xué)課件線性規(guī)劃單純形法單純形法的基本思路：從可行域中某一個(gè)頂點(diǎn)(即基本可行解)開始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是,則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)(基本可行解)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。算

例運(yùn)籌學(xué)課件線性規(guī)劃初

始

單

純

形

表運(yùn)籌學(xué)課件線性規(guī)劃迭

代

1運(yùn)籌學(xué)課件線性規(guī)劃迭

代

2運(yùn)籌學(xué)課件線性規(guī)劃♂返回運(yùn)籌學(xué)課件線性規(guī)劃§圖解法的靈敏度分析

靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個(gè)或多個(gè)參數(shù)（系數(shù)）ci,aij

,bj

變化時(shí)，對(duì)最優(yōu)解產(chǎn)生的影響。例:Maxz=50x1+100x2

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標(biāo)值z=27500x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE線性規(guī)劃的標(biāo)準(zhǔn)化：——引入松馳變量（含義是資源的剩余量）例

中引入s1，s2，s3模型化為目標(biāo)函數(shù)：Maxz=50x1+100x2+0s1+0s2+0s3

約束條件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0對(duì)于最優(yōu)解

x1=50x2=250，s1=0s2=50s3=0

說明：生產(chǎn)50單位Ⅰ產(chǎn)品和250單位Ⅱ產(chǎn)品將消耗完所有可能的設(shè)備臺(tái)時(shí)數(shù)及原料B，但對(duì)原料A則還剩余50千克。靈敏度分析目標(biāo)函數(shù)中的系數(shù)ci

的靈敏度分析：ci的變化只影響目標(biāo)函數(shù)等值線的斜率，目標(biāo)函數(shù)z=50x1+100x2

在250=x2(x2=z斜率為0

)

300=x1+x2(x2=-x1+z斜率為-1

)之間時(shí)，原最優(yōu)解x1=50，x2=100仍是最優(yōu)解。一般情況：

z=c1x1+c2x2

寫成斜截式x2=-(c1/c2)x1+z/c2

目標(biāo)函數(shù)等值線的斜率為-(c1/c2)，當(dāng)-1-(c1/c2)0（*）時(shí)，原最優(yōu)解仍是最優(yōu)解。假設(shè)產(chǎn)品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

100假設(shè)產(chǎn)品Ⅰ的利潤50元不變，即c1=50，代到式（*）并整理得

50c2

+假若產(chǎn)品Ⅰ、Ⅱ的利潤均改變，則可直接用式（*）來判斷。假設(shè)產(chǎn)品Ⅰ、Ⅱ的利潤分別為60元、55元，則

-2-(60/55)

-1

那么，最優(yōu)解為

300=x1+x2

和

400=2x1+x2

的交點(diǎn)x1=100，x2=200?！?圖解法的靈敏度分析假設(shè)產(chǎn)品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

100假設(shè)產(chǎn)品Ⅰ的利潤50元不變，即c1=50，代到式（*）并整理得

50c2

+假若產(chǎn)品Ⅰ、Ⅱ的利潤均改變，則可直接用式（*）來判斷。假設(shè)產(chǎn)品Ⅰ、Ⅱ的利潤分別為60元、55元，則

-2-(60/55)

-1

那么，最優(yōu)解為

300=x1+x2

和

400=2x1+x2

的交點(diǎn)x1=100，x2=200?！?圖解法的靈敏度分析2約束條件中右邊系數(shù)bj

的靈敏度分析當(dāng)約束條件中右邊系數(shù)bj

變化時(shí)，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化?？紤]上例的情況：假設(shè)設(shè)備臺(tái)時(shí)增加10個(gè)臺(tái)時(shí)，即b1變化為310，這時(shí)可行域擴(kuò)大，最優(yōu)解為

x2=250

和

x1+x2=310

的交點(diǎn)x1=60，x2=250。變化后的總利潤-變化前的總利潤=增加的利潤(50×60+100×250)-(50×50+100×250)=500，500/10=50元說明在一定范圍內(nèi)每增加（減少）1個(gè)臺(tái)時(shí)的設(shè)備能力就可增加（減少）50元利潤，稱為該約束條件的對(duì)偶價(jià)格。

假設(shè)原料A增加10千克時(shí)，即b2變化為410，這時(shí)可行域擴(kuò)大，但最優(yōu)解仍為

x2=250

和

x1+x2=300

的交點(diǎn)x1=50，x2=250。此變化對(duì)總利潤無影響，該約束條件的對(duì)偶價(jià)格為0。

解釋：原最優(yōu)解沒有把原料A用盡，有50千克的剩余，因此增加10千克值增加了庫存，而不會(huì)增加利潤。在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加1個(gè)單位時(shí)（1）若約束條件的對(duì)偶價(jià)格大于0，則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）；（2）若約束條件的對(duì)偶價(jià)格小于0，則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）；（3）若約束條件的對(duì)偶價(jià)格等于0，則最優(yōu)目標(biāo)函數(shù)值不變。注釋1.對(duì)偶價(jià)格表示其對(duì)應(yīng)的資源每增加一個(gè)單位，將改進(jìn)多少個(gè)單位的最優(yōu)值。

2.當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量稱之為影子價(jià)格。在求目標(biāo)函數(shù)最大時(shí)，當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值增加的數(shù)量就為改進(jìn)的數(shù)量，所以影子價(jià)格等于對(duì)偶價(jià)格；在求目標(biāo)函數(shù)值最小時(shí)，改進(jìn)的數(shù)量就是減少的數(shù)量，所以影子價(jià)格即為負(fù)的對(duì)偶價(jià)格。計(jì)

算

軟

件LinGomatlab♂返回Matlab求解線性規(guī)劃基本模型

函數(shù)調(diào)用格式：§1人力資源分配的問題

例1．某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：

設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作8小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?§1人力資源分配的問題解：設(shè)xi

表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6

約束條件：s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0

注解該問題本質(zhì)上是個(gè)整數(shù)規(guī)劃問題，放松的線性規(guī)劃的最優(yōu)解是個(gè)整數(shù)解，所以兩規(guī)劃等價(jià)。♂返回配料問題某化工廠要用三中原料混合配置三種不同規(guī)格的產(chǎn)品各產(chǎn)品的規(guī)格單價(jià)如表1，產(chǎn)品規(guī)格單價(jià)（元/公斤）A原料Ⅰ不少于50%原料Ⅱ不超過25%50B原料Ⅰ不少于25%原料Ⅱ不超過50%35C不限25

問如何安排生產(chǎn)使得生產(chǎn)利潤最大？原料日最大供應(yīng)量單價(jià)(元/公斤)Ⅰ10065Ⅱ10025Ⅲ6035原料的單價(jià)與每天最大供應(yīng)量如表2配

料

問

題

案

例問題問題分析模型求解結(jié)果分析問題分析變量約束條件目標(biāo)函數(shù)變量生產(chǎn)計(jì)劃就是要確定每天生產(chǎn)三種產(chǎn)品的數(shù)量以及非中產(chǎn)品中三中原料的數(shù)量。而由于每種產(chǎn)品的數(shù)量等于三種原料數(shù)量之和，所以只要確定每天生產(chǎn)三種產(chǎn)品分別含有的原料數(shù)量即可。所以變量就是每天生產(chǎn)三種產(chǎn)品所用的約

束

條

件規(guī)格約束等價(jià)于資源約束目

標(biāo)

函

數(shù)總產(chǎn)值總成本總利潤=總產(chǎn)值-總成本=模型套裁

下料

問題

某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最省？

解：共可設(shè)計(jì)下列5種下料方案，見下表設(shè)x1,x2,x3,x4,x5分別為上面5種方案下料的原材料根數(shù)。得線性規(guī)劃模型為：Minx1+x2+x3+x4+x5

s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0求解結(jié)果：x=12.330127.669917.669932.33010fv=90.0000用軟件計(jì)算得出最優(yōu)下料方案：按方案1下料12根；按方案2下料28根；按方案3下料18根，按方案4下料32根。只需90根原材料就可制造出100套鋼架。注意：1.在建立此類型數(shù)學(xué)模型時(shí)，約束條件用大于等于號(hào)比用等于號(hào)要好。因?yàn)橛袝r(shí)在套用一些下料方案時(shí)可能會(huì)多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號(hào)，這一方案就不是可行解了。2.目標(biāo)函數(shù)也可用：使剩余料頭最少。投資

問題

某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元。據(jù)測定每萬元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：問：a）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最??？

解：

1）確定決策變量：連續(xù)投資問題設(shè)xij(i=1～5，j=1～4)表示第i年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項(xiàng)目的金額。這樣我們建立如下的決策變量：

Ax11x21x31x41x51Bx12x22x32x42Cx33Dx242）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是

x11+x12=200；第二年：B次年末才可收回投資，故第二年年初有資金1.1x11，于是

x21+x22+x24=1.1x11；第三年：年初有資金

1.1x21+1.25x12，于是

x31+x32+x33=1.1x21+1.25x12；第四年：年初有資金

1.1x31+1.25x22，于是

x41+x42=1.1x31+1.25x22；第五年：年初有資金

1.1x41+1.25x32，于是

x51=1.1x41+1.25x32；

B、C、D的投資限制：

xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目標(biāo)函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24

s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(i=1、2、3、4)，