運籌學教程胡云權-第五運籌學-1線性規(guī)劃圖解法

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

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

線性規(guī)劃問題及數學模型

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

問題：工廠應如何安排生產可獲得最大的總利潤？

產品甲產品乙設備能力（h）設備A3265設備B2140設備C0375利潤（元/件）15002500

目標函數maxz=1500x1+2500x2

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

x1

,x2

≥0

這是一個典型的利潤最大化的生產計劃問題。營養(yǎng)配餐問題

假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最小？各種食物的營養(yǎng)成分表9解：設xj為第j種食品每天的購入量，則配餐問題的線性規(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ī)劃數學模型的構成三要素決策變量表示某種重要的可變因素，變量的一組數據代表一個解決的方案或措施，用x1,x2,···,xn表示目標函數決策變量的函數，目標可以是最大化或最小化約束條件對決策變量取值的限制條件，由決策變量

x1,x2,···,xn

的不等式組或方程組構成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ī)劃的簡化形式

向量形式C=(c1,c2,…,cn)價值向量,資源向量變量xj對應的系數列向量線性規(guī)劃的向量形式

矩陣形式約束條件系數矩陣線性規(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ī)劃的標準形式標準形式

標準形式：用向量和矩陣表述

目標最大化約束為等式決策變量均非負右端項非負

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

2x1+2x2=80x1+2x2=4x1,x2≥0標準形為MaxZ=x1+2x2

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

+0x4

3約束條件≥時MaxZ=2x1+5x26x1+3x2≥24x1,x2≥0標準形為MaxZ=2x1+5x26x1+3x2=24x1,x2≥0x3≥0-x3+0x3246x13x2x3X3是剩余變量,或負松弛變量,經濟意義是超用的資源數4變量取值無約束時MaxZ=3x1+7x22x1+6x2=8x1≥0,x2取值無約束設x2’≥0,x2’’≥0,令x2=x2’-

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

x2’’

2x1+6x2’-6

x2’’

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

5右端項有負值的問題在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數為負時，如bi<0，則把該等式約束兩端同時乘以-1，得到：

-ai1

x1-ai2x2-…-ainxn

=-bi。6xj

≤

0問題：令xj’=-xj

即可。例：將以下線性規(guī)劃問題轉化為標準形式

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（原問題）(標準型)練習將下列線性規(guī)劃問題化為標準形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10x3≥1112x1+13x2+14x3≤15x1≥0,x2≤0,x3取值無約束作業(yè)教材P43習題1.21.101.13建模1.14建模（1）

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

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

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

對于只有兩個變量的線性規(guī)劃問題，可以二維直角坐標平面上作圖表示線性規(guī)劃問題的有關概念，并求解。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