運(yùn)籌學(xué)教程胡云權(quán)-第五運(yùn)籌學(xué)-1線性規(guī)劃圖解法

運(yùn)籌學(xué)規(guī)劃論圖論排隊(duì)論存儲(chǔ)論對(duì)策論決策論線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃目標(biāo)規(guī)劃一般線性規(guī)劃特殊線性規(guī)劃運(yùn)籌學(xué)的分支運(yùn)籌學(xué)解決問題的過(guò)程1）提出問題：認(rèn)清問題。2）尋求可行方案：建模、求解。3）確定評(píng)估目標(biāo)及方案的標(biāo)準(zhǔn)或方法、途徑。4）評(píng)估各個(gè)方案：解的檢驗(yàn)、靈敏性分析等。5）選擇最優(yōu)方案：決策。6）方案實(shí)施：回到實(shí)踐中。7）事后評(píng)估：考察問題是否得到完滿解決。

內(nèi)容提要線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃解的概念、圖解法線性規(guī)劃應(yīng)用——建模單純形法原理和Excel求解第一章線性規(guī)劃問題的提出如何合理地利用有限的人、財(cái)、物等資源，得到最好的經(jīng)濟(jì)效果?

線性規(guī)劃問題及數(shù)學(xué)模型

例1.1：某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)見下表：

問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)（元/件）15002500

目標(biāo)函數(shù)maxz=1500x1+2500x2

約束條件s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1

,x2

≥0

這是一個(gè)典型的利潤(rùn)最大化的生產(chǎn)計(jì)劃問題。營(yíng)養(yǎng)配餐問題

假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含的熱量和營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格見下表。問如何選擇才能在滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品的費(fèi)用最?。扛鞣N食物的營(yíng)養(yǎng)成分表9解：設(shè)xj為第j種食品每天的購(gòu)入量，則配餐問題的線性規(guī)劃模型為：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800x1，x2，

x3，x4

0線性規(guī)劃數(shù)學(xué)模型的構(gòu)成三要素決策變量表示某種重要的可變因素，變量的一組數(shù)據(jù)代表一個(gè)解決的方案或措施，用x1,x2,···,xn表示目標(biāo)函數(shù)決策變量的函數(shù)，目標(biāo)可以是最大化或最小化約束條件對(duì)決策變量取值的限制條件，由決策變量

x1,x2,···,xn

的不等式組或方程組構(gòu)成max(min)z=c1x1+c2x2+…+cnxn

Subjectto（s.t.）

a11

x1+a12

x2+…+a1nxn≤(=,≥)b1a21

x1+a22

x2+…+a2nxn≤(=,≥)b2

...

am1

x1+am2x2+…+amnxn≤(=,≥)bmx1

,x2,…,xn≥0線性規(guī)劃的一般形式

線性規(guī)劃的簡(jiǎn)化形式

向量形式C=(c1,c2,…,cn)價(jià)值向量,資源向量變量xj對(duì)應(yīng)的系數(shù)列向量線性規(guī)劃的向量形式

矩陣形式約束條件系數(shù)矩陣線性規(guī)劃的矩陣形式

maxz=c1x1

+c2x2

+…+cnxn

s.t.a11x1

+a12x2

+…+a1nxn=b1a21x1

+a22x2+…+a2nxn=b2

…

…

am1x1+am2x2

+…+amnxn

=bmx1,x2,…,xn≥0其中bi

≥0

，i=1,2,…,m線性規(guī)劃的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式

標(biāo)準(zhǔn)形式：用向量和矩陣表述

目標(biāo)最大化約束為等式?jīng)Q策變量均非負(fù)右端項(xiàng)非負(fù)

對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式。線性規(guī)劃的標(biāo)準(zhǔn)形四個(gè)特點(diǎn)1目標(biāo)函數(shù)求極小時(shí)MinZ=3x1+6x24x1+8x2=9x1,x2≥04x1+8x2=9x1,x2≥0標(biāo)準(zhǔn)形式為:MaxZ=-3x1-6x2-kkZ’Z’’Z=-Z非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形2約束條件≤時(shí)MaxZ=x1+2x2

2x1+2x2=80x1+2x2=4x1,x2≥0標(biāo)準(zhǔn)形為MaxZ=x1+2x2

2x1+2x2≤80x1+2x2≤4x1,x2≥0x3≥0x4≥082x12x2x3X3為松弛變量,經(jīng)濟(jì)意義是沒有被充分利用的資源數(shù)X4也為松弛變量,經(jīng)濟(jì)意義是沒有被充分利用的資源數(shù)+x3+0x3+x4

+0x4

3約束條件≥時(shí)MaxZ=2x1+5x26x1+3x2≥24x1,x2≥0標(biāo)準(zhǔn)形為MaxZ=2x1+5x26x1+3x2=24x1,x2≥0x3≥0-x3+0x3246x13x2x3X3是剩余變量,或負(fù)松弛變量,經(jīng)濟(jì)意義是超用的資源數(shù)4變量取值無(wú)約束時(shí)MaxZ=3x1+7x22x1+6x2=8x1≥0,x2取值無(wú)約束設(shè)x2’≥0,x2’’≥0,令x2=x2’-

x2’’,則MaxZ=3x1+7x2’-7

x2’’

2x1+6x2’-6

x2’’

=8x1≥0,x2’≥0,x2’’≥0

5右端項(xiàng)有負(fù)值的問題在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：

-ai1

x1-ai2x2-…-ainxn

=-bi。6xj

≤

0問題：令xj’=-xj

即可。例：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58

x1,x3

≥0,x4≤0

maxz=3x1–5x2’+5x2”–8x3

-7x4’s.t.2x1–3x2’+3x2”+5x3-6x4’+x5=284x1+2x2’-2x2”+3x3+9x4’-x6=39-6x2’+6x2”-2x3+3x4’-x7

=58

x1

,x2’,x2”,x3

,x4’

,x5

,x6

,x7≥0

minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58

x1,x3

≥0,x4≤0（原問題）(標(biāo)準(zhǔn)型)練習(xí)將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10x3≥1112x1+13x2+14x3≤15x1≥0,x2≤0,x3取值無(wú)約束作業(yè)教材P43習(xí)題1.21.101.13建模1.14建模（1）

§2.線性規(guī)劃的求解

(1)圖解法——只適用兩個(gè)變量（2）單純型法——適用多個(gè)變量

線性規(guī)劃的圖解法

對(duì)于只有兩個(gè)變量的線性規(guī)劃問題，可以二維直角坐標(biāo)平面上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0ox1x2123443212x1+2x2=82x2=4Z=2Z=6最優(yōu)解為:x1=2,x2=2例1MinZ=x1+2x2x1+x2≥1x1-x2≤0x1,x2≥0ox1x21221x1+x2=1x1-x2=0Z=2Z=1.5最優(yōu)解為:x1=0.5,x2=0.5例2

LP問題解的四種情況

——唯一最優(yōu)解32MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0ox1x2123443212x1+2x2=82x2=4Z=2Z=6最優(yōu)解為:x1=2,x2=2[例1]MaxZ=2x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0ox1x2123443212x1+2x2=82x2=4最優(yōu)解有:1x1=2,x2=22x1=4,x