第1章：線性規(guī)劃

第一章：線性規(guī)劃1.1線性規(guī)劃(LinearPrograming---L.P.)概述一、L.P.概念：

L.P.是目前應(yīng)用最廣泛的一種系統(tǒng)優(yōu)化方法。其理論已十分成熟，廣泛應(yīng)用于工農(nóng)業(yè)生產(chǎn)和經(jīng)濟管理等領(lǐng)域。以數(shù)學(xué)為工具，在一定資源條件下，如何合理安排，取得最大經(jīng)濟效果。二、發(fā)展史：

30年代末(蘇)康特羅維奇書“生產(chǎn)組織與計劃中的數(shù)學(xué)方法”，為L.P.建立數(shù)學(xué)模型和求解奠定了基礎(chǔ)。

1、(美)庫普曼(T.C.Koopmans)建立了L.P.數(shù)學(xué)模型，獲諾貝經(jīng)濟獎。

2、(美)丹澤(G.B.Dantzig)在1947年提出求解L.P.數(shù)模的通用方法---單純形法。

1946年，世界上第一臺計算機問世，使單純形法處理大規(guī)模L.P.數(shù)模成為可能。三、L.P.問題的求解過程

1、將實際問題轉(zhuǎn)化為數(shù)學(xué)模型(數(shù)學(xué)公式)：建模。

2、求解數(shù)學(xué)模型：

圖解法：適合于2個變量的L.P.數(shù)學(xué)模型。

單純形法：適合于任意個變量的L.P.數(shù)學(xué)模型。

3、利用數(shù)學(xué)模型的最優(yōu)解獲得原問題的最優(yōu)決策方案。11.2線性規(guī)劃及其數(shù)學(xué)模型一、L.P.問題

例：某廠生產(chǎn)甲、乙兩種產(chǎn)品，均需在A、B、C三種不同的設(shè)備上加工，產(chǎn)品加工所需工時、銷售后能獲得的利潤及設(shè)備有效工時數(shù)如下表。問：如何安排生產(chǎn)計劃，才能使該廠獲得總利潤最大？

解:①設(shè)甲、乙產(chǎn)品產(chǎn)量分別為x1、x2公斤———決策變量，簡稱變量

②設(shè)總利潤為Z，則

MaxZ=70x1＋30x2———目標(biāo)函數(shù)

③設(shè)備可用工時數(shù)限制———約束條件

s.t.3x1+9x2≤540A設(shè)備可用工時約束

5x1+5x2≤450B設(shè)備可用工時約束

9x1+3x2≤720C設(shè)備可用工時約束

x1,x2

≥0非負(fù)約束

設(shè)備產(chǎn)品

ABC利潤(元/公斤)

甲乙3955937030限制工時

540450720單耗2二、L.P.數(shù)學(xué)模型的經(jīng)濟含義

1、數(shù)學(xué)模型的三要素:

①.有一組待確定的決策變量。如(x1,x2)為一個具體行動方案。

②.有一個明確的目標(biāo)要求(Max或Min)。如要求利潤最大。

③.存在一組約束條件。如設(shè)備A、B、C三種資源的約束。

2、數(shù)學(xué)模型中系數(shù)的含義:

①.目標(biāo)函數(shù)中決策變量的系數(shù)70,30------叫價值系數(shù)，表單位產(chǎn)品提供的利潤(元/件)；

②.約束條件左邊決策變量的系數(shù)------叫約束條件系數(shù)或單耗(臺時、kg、kg/件)；

③.約束條件右邊常數(shù)540,450,720------叫限制常數(shù)，表現(xiàn)有的資源限量。

三、線性規(guī)劃數(shù)學(xué)模型的解

1、可行解：滿足約束條件②、③、④、⑤的所有解。

2、可行解域：所有可行解的集合，上圖陰影部分。

3、最優(yōu)解：滿足目標(biāo)函數(shù)①的可行解。

4、基本解：所有約束條件直線的交點對應(yīng)的解，即上圖所有的實心點和空心點對應(yīng)的解。

5、基本可行解：既是基本解又是可行解，即上圖所有的實心點對應(yīng)的解。它滿足兩個條件：其一是約束條件直線的交點對應(yīng)的解；其二是可行解，即滿足所有的約束條件，在可行解域內(nèi)。

oX1X2

②③④⑤⑤ahbkMaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤3

1、線性規(guī)劃模型：如果以上數(shù)學(xué)模型中的方程均是線性方程，則該數(shù)模稱為線性規(guī)劃數(shù)模。

2、非線性規(guī)劃模型：如果以上數(shù)學(xué)模型中的方程至少有一個方程是非線性方程，則該數(shù)模稱為非線性規(guī)劃數(shù)模。

四、L.P.的一般形式

Max(Min)Z=c1

x1+c2

x2+---+cn

xn

a11

x1+a12

x2+---+a1n

xn

≤(≥,=)b1

a21

x1+a22

x2+---+a2n

xn≤(≥,=)b2s.t.-----------------------------------------------------

am1

x1+am2

x2+---+amn

xn≤(≥,=)bm

xj≥0,j=1---n

41.3線性規(guī)劃問題的建模確定決策變量；確定目標(biāo)函數(shù)；列出約束條件。一、運輸問題建模:編制最優(yōu)運輸計劃,使總運費最少例：某地有三個有色金屬礦A1、A2、A3，生產(chǎn)同一種金屬礦石，A1礦的年產(chǎn)量為100萬噸，

A2礦為80萬噸，A3礦為50萬噸。礦石全部供應(yīng)四個冶煉廠，B1廠的全部需求量為50萬噸，

B2廠70為萬噸，B3廠為80萬噸，B4廠為30萬噸。產(chǎn)量恰好等于總需求量，礦石由各礦山運到冶煉廠的單位運價已知，如下表。問如何安排運輸，使各礦山的礦石運到冶煉廠，滿足各廠的需要，且運輸費用最小，試建立該問題的數(shù)學(xué)模型？

.確定決策變量:設(shè)

xij

為從第i個礦山到第

j

個冶煉廠的礦石運輸量(萬t)..確定目標(biāo)函數(shù):設(shè)總運費為Z,則

MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34

.確定約束條件:

x11+x12+x13+x14=100s.t.x21+x22+x23+x24=80x31+x32+x33+x34=50x11+x21+x31=50x12+x22+x32=70x13+x23+x33=80x14+x24+x34=30

xij

≥0,i=1~3;j=1~4.5二、合理下料問題建模:尋求最佳下料方式,使余料最少.

例有一批長度為180公分的鋼管,需截成70、52和35公分三種管料。它們的需求量應(yīng)分別不少于

100、150和100個。問應(yīng)如何下料才能使鋼管的余料為最少?

解:

.確定決策變量:

設(shè)xj

為第j種下料方式所用的鋼管根數(shù)..確定目標(biāo)函數(shù):設(shè)總余料為Z,則

MinZ=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8(公分).確定約束條件:

2x1+x2+x3+x4≥100s.t.2x2+x3+3x5+2x6+x7≥150x1+x3+3x4+2x6+3x7+5x8≥100

xj≥0,且為整數(shù).

6三、人員分派問題建模:合理分派人員,使總效率最大.例：設(shè)有四件工作分派給四個人來做，每項工作只能由一人來做，每個人只能做一項工作。希望適當(dāng)安排人選，發(fā)揮各人特長又能使總的效率最大(或完成最快,或費用最少)。表1.5表示各人對各項工作所具有的工作效率。

.確定決策變量:設(shè)xij

為分派第i個人從事第

j

項工作,xij=1,0(分派與否).確定目標(biāo)函數(shù):設(shè)總效率為Z,則

MaxZ=0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24

+0.8x31+1.0x32+0.7x33+0.3x34+0.7x41+0.7x42+0.5x43+0.4x44

.確定約束條件:

x11+x12+x13+x14=1s.t.x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1

xij=1,0,i=1~4;j=1~4.7四、投資方案選擇問題建模:合理選擇方案,使總收益最大.例：某煉油公司為提高煉油能力和增加企業(yè)經(jīng)濟效益,經(jīng)研究有五種技術(shù)改造的投資方案可供選擇，它們所需的投資費用年收益如下表所示。其中:方案1和方案2只能選擇其中一種，不能兼而實現(xiàn)，并且，如選擇方案2，則方案3必須同時選擇，或者都不選擇。

現(xiàn)該公司可供支配的資金總額為：第一年有650萬元，第二年僅有460萬元。技術(shù)改造的結(jié)果要求至少應(yīng)增加出油能力500桶/天，但又不得超過1100桶/天，試確定該公司總經(jīng)濟效益最大的投資方案。8

.確定決策變量:設(shè)xj

為第j方案的取舍，

xj=1,0(取舍).確定目標(biāo)函數(shù):設(shè)總經(jīng)濟效率為Z,則

MaxZ=100x1+200x2+50x3+30x4+20x5(萬元).確定約束條件:

200x1+300x2+150x3+100x4+50x5≤650s.t.200x1+150x2+50x3+70x4+40x5≤460500x1+1000x2+100x3+50x4+20x5≥500500x1+1000x2+100x3+50x4+20x5≤1100x1+x2≤1-x2+x3=0

xj=0,1,j=1~5.9五、選點決策問題:合理選點,使總利率最大.例：某公司擬在A、B、C、D、E五個城市中建立若干產(chǎn)品經(jīng)銷聯(lián)營點，各處設(shè)點都需資金、人力、設(shè)備等，需求量以及能提供的利潤各處不同，有些點可能虧本，但卻能獲得貸款和人力等。假設(shè)數(shù)據(jù)已知，見下表，為使總利潤最大，問廠方應(yīng)作何種最優(yōu)選點決策？

.確定決策變量：要求從五個城市中選擇最優(yōu)產(chǎn)品經(jīng)銷聯(lián)營點，設(shè)決策變量xj(j=1,2,…,5)表示第j個城市的取舍，所以決策變量xj的取值僅有1和0兩種值。.確定目標(biāo)函數(shù)：要求公司總利潤Z最大，則

MaxZ＝4.5x1＋3.8x2＋9.5x3－2x4－1.5x5

.確定約束條件:4x1＋6x2＋12x3－8x4＋x5≤20s.t.5x1＋4x2＋12x3＋3x4－8x5≤15x1＋x2＋x3≤2

xj＝0、1，j=1,…,5

資源城市應(yīng)投資(百萬元)應(yīng)投人力（人）應(yīng)投設(shè)備（套）利潤(萬元)A45145B64138C1212195D-830-2E1-80-1.5資源限量20152101.4線性規(guī)劃圖解法一、適用范圍：

二個變量的數(shù)學(xué)模型。二、求解步驟：

MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤

oX1X2

②③④⑤⑤ahbk7030(75,15)最優(yōu)解為：X*=(75，15)TZ*=5700

第二步：確定可行解域，即所有約束方程圖形的公共部分；

第三步：繪出目標(biāo)函數(shù)直線，根據(jù)目標(biāo)函數(shù)的要求以及與決策變量的關(guān)系，找出直線移動方向。

第五步：確定最優(yōu)解及最優(yōu)目標(biāo)函數(shù)值。

第一步：將所有約束方程用圖形繪出；

第四步：目標(biāo)函數(shù)直線向著可行解域的右上方平行移動，直至與可行解域相切為止，這個切點就是最優(yōu)點，對應(yīng)的解就是最優(yōu)解。

所以，產(chǎn)品甲、乙分別安排產(chǎn)量75Kg、15Kg，可使工廠獲利最大為5700元。11三、LP幾何意義

oX1X2

②③④⑤⑤ahbk

1、閉合的可行解域是凸多邊形(凸集)。

2、可行解域有若干個頂點：O、a、h、k、b。對應(yīng)的解叫基本可行解。

3、最優(yōu)解若唯一存在，則必是頂點中的某一個。12四、特殊的數(shù)學(xué)模型

1、有無窮多個最優(yōu)解：若有兩個最優(yōu)解，則必有無窮多個最優(yōu)解。如下例數(shù)學(xué)模型：MaxZ=x1＋2x2s.t.x1+x2≤6x1+2x2≤8x2≤3x1,x2

≥0

OX1X2Q1Q2Q3Q4此線性規(guī)劃問題的最優(yōu)解在Q2Q3線段上，如上圖所示，即線段Q2Q3上任意一點都使Z取得相同的最大值，這個線性規(guī)劃問題有無窮多最優(yōu)解。因此，若有兩個最優(yōu)解，則必有無窮多個最優(yōu)解。

13四、特殊的數(shù)學(xué)模型

2、解無界：可行解域無界，目標(biāo)值無限增大。如下例數(shù)學(xué)模型：

MaxZ=x1＋x2s.t.-2x1+x2≤4x1-5x2≤2x1,x2

≥0

OX1X2用圖解法求解結(jié)果見上圖所示，從圖中可以看到，該問題可行解域無界，目標(biāo)函數(shù)值可以增大到無究大，稱這種情況為無界解或無最優(yōu)解。

14四、特殊的數(shù)學(xué)模型

3、無可行解域：約束條件相互矛盾。如下例數(shù)學(xué)模型MaxZ=3x1＋4x2s.t.x1+x2

≥6x1≤2x2≤3x1,x2

≥02OX1X2636該問題可行解域為空集，如上圖所示，即無可行解域，當(dāng)然也無最優(yōu)解。151.5線性規(guī)劃單純形法

一、適用范圍

任意個變量的數(shù)學(xué)模型。二、原理從一初始頂點(初始基本可行解)出發(fā)，沿可行解域的邊緣逐個驗算遇到的頂點(基本可行解)，直至找最優(yōu)點(最優(yōu)解)為止。MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤

oX1X2

②③④⑤⑤ahbk最優(yōu)解為：X*=(75，15)TZ*=5700

16三、LP數(shù)模的標(biāo)準(zhǔn)型條件一:具有等式約束方程組；條件二:右邊常數(shù)非負(fù)；條件三:變量非負(fù)；條件四:目標(biāo)函數(shù)為Max型。MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤對設(shè)備A：3x1+9x2

≤540，引入非負(fù)松弛變量x3，加到不等式的左邊得

3x1+9x2+x3

=540

實際使用的

空閑工時(≥0)限制工時

工時數(shù)

(起松弛作用,叫松弛變量)

MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5則原數(shù)模的標(biāo)準(zhǔn)型為：對設(shè)備B：5x1+5x2

≤450，引入非負(fù)松弛變量x4，加到不等式的左邊得

5x1+5x2+x4

=450

實際使用的

空閑工時(≥0)限制工時

工時數(shù)

(起松弛作用,叫松弛變量)

對設(shè)備C：9x1+3x2

≤720，引入非負(fù)松弛變量x4，加到不等式的左邊得

9x1+3x2+x5

=720

實際使用的

空閑工時(≥0)限制工時

工時數(shù)

(起松弛作用,叫松弛變量)

17四、LP數(shù)模的規(guī)范型條件一:具有標(biāo)準(zhǔn)型；條件二:約束方程組系數(shù)矩陣中含有至少一個單位子矩陣(對應(yīng)的變量叫基變量)；條件三:目標(biāo)函數(shù)中不含基變量。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5為基變量則原數(shù)模的規(guī)范型為：MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5

x3x4x539100100A=55010中有B=010=（

3、

4、

5）=E93001001一組基

1

2

3

4

5

x1x2x3x4x5

非基變量基變量基的作用是:可以得到初始基本可行解(即初始頂點--通常是原點O),是單純行迭代的基礎(chǔ)。18五、最優(yōu)解尋求步驟第一步、確定初始基本可行解：利用規(guī)范型數(shù)模，令非基變量x1、x2=0，求出基變量x3、x4、x5。

得初始基本可行解為：

X(1)=（

x1,x2,

x3,x4,x5）T=(0,0,

540,450,720

)T

甲乙設(shè)備A設(shè)備B設(shè)備C→空閑工時

Z(1)=0，利潤為0未生產(chǎn)，資源全部閑置(對應(yīng)原點O)(x1、

x2

為非基變量，x3、x4、x5為基變量)

第二步、判斷X(1)是否最優(yōu)：檢查用非基變量表達(dá)的目標(biāo)函數(shù)中非基變量前的系數(shù)(叫檢驗數(shù))。

MaxZ=70x1+30x2

因為檢驗數(shù)70、30>0，所以當(dāng)x1

和x2從0增大時，Z也會增大。故當(dāng)前解非最優(yōu)。當(dāng)前解須改進，尋求更好的解。

oX1X2

②③④⑤⑤ahbkMaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5為基變量19第三步、確定改進的非基變量及其上界:

選擇使目標(biāo)Z值改變得最快的

非基變量優(yōu)先改進。

(1)、確定非基變量

x1優(yōu)先改進：因為從目標(biāo)函數(shù)MaxZ=70x1+30x2可以看出

x1增加1，可使目標(biāo)Z增加70；x2增加1，目標(biāo)Z能增加30。

(2)、x1增加的上界是80：因為從約束方程組可以得出(從資源最優(yōu)利用考慮，令x3、x4、x5

=0)x1=180-3x2-(1/3)x3=180---目前可用的設(shè)備A臺時數(shù)最多可生產(chǎn)甲產(chǎn)品180Kg。

x1=90-x2-(1/5)x4=90---目前可用的設(shè)備B臺時數(shù)最多可生產(chǎn)甲產(chǎn)品90Kg。

x1=80-(1/3)x2-(1/9)x5=80---目前可用的設(shè)備C臺時數(shù)最多可生產(chǎn)甲產(chǎn)品80Kg。

取最小值即非基變量x1增加的上界是80-----最小比值規(guī)則。此時x2=0。第四步、確定新解：將x1=80，

x2=0代入約束方程組中求出x3、x4、x5的值。得新基本可行解為：

X(2)=（x1,x2,

x3,x4,x5）T=（80,0,300,50,0）T

甲乙設(shè)備A設(shè)備B設(shè)備C→空閑工時(對應(yīng)點a)

Z(2)=5600，利潤為5600(x2、

x5

為非基變量，x1、x3、x4為基變量)MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5為基變量

oX1X2

②③④⑤⑤ahbk20第五步、判斷X(2)是否最優(yōu)：檢查用非基變量表達(dá)的目標(biāo)函數(shù)中非基變量前的系數(shù)(叫檢驗數(shù))。

MaxZ=70x1+30x2=70[80-(1/3)x2-(1/9)x5]

+30x2=5600+(20/3)x2-(70/9)x5

因為檢驗數(shù)20/3>0，所以當(dāng)x2

從0增大時，Z也會增大。故當(dāng)前解非最優(yōu)。當(dāng)前解須改進，尋求更好的解。第六步、確定改進的非基變量及其上界:選擇使目標(biāo)Z值改變得最快的非基變量優(yōu)先改進。

(1)、確定非基變量

x2改進：因為目標(biāo)函數(shù)中只有一個正檢驗數(shù)。

(2)、x2增加的上界是15：因為從約束方程組可以得出(從資源最優(yōu)利用考慮，令x3、x4、x5

=0)x2=60-(1/3)x1-(1/9)x3=60-(1/3)x1→x2=37.5

x2=90-x1-x4=90-x1→x2=15

x2=240-3x1-(1/3)x5=240-3x1→

x1=80-(1/3)x2代入上面二式

取前二式的最小值即非基變量x2增加的上界是15-----最小比值規(guī)則。此時x1=75。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5為基變量

oX1X2

②③④⑤⑤ahbk21第七步、確定新解：將x1=75，

x2=15代入約束方程組中求出x3、x4、x5的值。得新基本可行解為：

X(3)=（

x1,x2,

x3,x4,x5）T=（75,15,

180,0,0）T

甲乙設(shè)備A設(shè)備B設(shè)備C→空閑工時

Z(3)=5700，利潤為5700(x4、

x5

為非基變量，x1、x2、x3為基變量)(對應(yīng)點h)第八步、判斷X(3)是否最優(yōu)：檢查用非基變量表達(dá)的目標(biāo)函數(shù)中非基變量前的系數(shù)(叫檢驗數(shù))。

MaxZ=70x1+30x2=

5700-2x4-(20/3)x5

由5x1+5x2+x4

=4509x1+3x2+x5

=720

解得x1=75+(1/10)x4-(1/6)x5，x2=15-(3/10)x4+(1/6)x5，代入目標(biāo)函數(shù)中得

MaxZ=70x1+30x2=70[75+(1/10)x4-(1/6)x5]

+30[15-(3/10)x4+(1/6)x5]=

5700-2x4-(20/3)x5

因為檢驗數(shù)-2、-20/3<0，所以當(dāng)前解最優(yōu)。最優(yōu)解為：

X*=（75,15,

180,0,0）T，Z*=5700

所以，產(chǎn)品甲、乙分別安排產(chǎn)量75Kg、15Kg，可使工廠獲利最大為5700元。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5為基變量

oX1X2

②③④⑤⑤ahbk22將數(shù)模寫成如下形式：

3x1+9x2+x3

=540

5x1+5x2+x4

=450

9x1+3x2+x5

=720-Z+70x1＋30x2=0

列出以下單純形表進行旋轉(zhuǎn)運算

：六、單純形法表格化-----單純形表MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5為基變量

oX1X2

②③④⑤⑤ahbk23基x1x2x3x4x5b

x339100540x455010450x593001720-Z70300000

70300000001809080x3x4x1-Z11/3001/9800810-1/3300010/301-5/950020/300-70/9-560037.515240x3x2x1-Z0103/10-1/615001-12/51180100-1/101/675000-2-20/3-5700基本可行解X(1)=(0，0，540，450，720)TZ(1)=0對應(yīng)原點OX(2)=(80，0，300，50，0)TZ(2)=5600對應(yīng)頂點aX(3)=(75，15，180，0，0)TZ(3)=5700對應(yīng)頂點h最優(yōu)解為：X*=X(3)=(75，15，180，0，0)TZ*=Z(3)=

5700

007003070將入基列變成單位向量列將入基列變成單位向量列24問題一：若最大檢驗數(shù)有兩個或兩個以上并且相等，應(yīng)如何確定入基變量(可任選)。問題二：若最小比值有兩個或兩個以上并且相等，應(yīng)如何確定出基變量(可任選)。問題三：原問題無解的判斷：入基列元素全部非正?；鵻1x2x3x4x5b

1

2x33910054018060x4550104509090x59300172080240-Z70700000基x1x2x3x4x5b

x33-9100540x450010450x59-3001720-Z70300000基x1x2x3x4x5b

x339100540180x45501045080x59300172080-Z70300000MaxZ=70x1＋30x2s.t.3x1-9x2≤5405x1≤4509x1-3x2≤720x1,x2

≥0b

935131/3025七、單純形的經(jīng)濟信息

MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720

xj

≥0，j=1,～,5；x3,x4,

x5為基變量

1、決策變量的解：x1=75公斤,x2=15公斤，提供最優(yōu)決策方案。

2、松弛變量的解：最優(yōu)決策條件下，提供資源的剩余量。

x3=180,設(shè)備A的閑置臺時。

x4=0,設(shè)備B的閑置臺時。

x5=0,設(shè)備C的閑置臺時。

3、產(chǎn)品相關(guān)價值系數(shù)：改化或約化的價值系數(shù)(新解下的價值系數(shù)---單位產(chǎn)品提供的利潤)。

o:X(1)=(0,0,540,450,720)T；MaxZ=0+70x1+30x2+0x3+0

x4+0

x5a:X(2)=(80,0,300,50,0)T；MaxZ=5600+0x1+

(20/3)x2+0x3+0x4-(90/7)x5h:X(3)=(75,15,180,0,0)T；MaxZ=5700+0x1+0x2-0x3-2x4-(20/3)x5

反映各產(chǎn)品有相互制約作用，起了考慮市場信息和規(guī)劃方案改變對利潤的綜合影響。

oX1X2

②③④⑤⑤ahbk最優(yōu)解為：X*=(75，15)TZ*=5700

26

4、資源影子(潛在)價格

⑴影子價格的概念:最優(yōu)規(guī)劃條件下，單位資源能夠帶來的目標(biāo)增量。是反映資源最優(yōu)利用的一種虛擬價格，也叫資源邊際利潤。

⑵影子價格的計算:最優(yōu)表中松弛變量檢驗數(shù)的相反數(shù)或最優(yōu)目標(biāo)函數(shù)中松弛變量系數(shù)的相反數(shù)?；鵻1x2x3x4x5bx3001-12/51180x20103/10-1/615x1100-1/101/675-Z000-2-20/3-5700檢驗數(shù)：0-2-20/3影子價格：0220/3MaxZ=5700+0x1+0x2-0x3-2x4-(20/3)x5當(dāng)設(shè)備A增加1個臺時，此時x3=-1，則利潤Z增加0元，為5700+0元；當(dāng)設(shè)備B增加1個臺時，此時x4=-1，則利潤Z增加2元，為5700+2元；當(dāng)設(shè)備C增加1個臺時，此時x5=-1，則利潤Z增加20/3元，為5700+20/3元。結(jié)論：設(shè)備A的影子價格為0(元/臺時)，

設(shè)備B的影子價格為2(元/臺時)，

設(shè)備C的影子價格為20/3(元/臺時)。

27⑶影子價格的應(yīng)用①在企業(yè)內(nèi)部：指出挖潛方向。原理：影子價格高的資源潛力大，影子價格低的資源潛力小。設(shè)備A的影子價格為0元/臺時：已有180臺時剩余，缺少180臺時不會造成任何損失，增加數(shù)量

也不會增加利潤，為非關(guān)鍵資源，不應(yīng)對此花費代價。設(shè)備B的影子價格為2元/臺時：缺少

1臺時將造成

2元的損失，增加1

臺時將增加

2元的利潤。

為關(guān)鍵資源，應(yīng)重點挖潛(比如增加數(shù)量)，其重要程度次之。設(shè)備C的影子價格為20/3元/臺時：缺少

1臺時將造成

20/3元的損失，增加1

臺時將增加

20/3

元的利潤。為關(guān)鍵資源，應(yīng)重點挖潛(比如增加數(shù)量)，其重要程度最高。②在企業(yè)外部：制定外單位來料加工時的收費用標(biāo)準(zhǔn)：合計收費0+900+4800=5700元。設(shè)備A的收費用標(biāo)準(zhǔn)為0元/臺時，現(xiàn)有540臺時，共收費0×540=0元(不考慮收費)；

設(shè)備B的收費用標(biāo)準(zhǔn)為2元/臺時，現(xiàn)有450臺時，共收費2×450=900元；

設(shè)備C的收費用標(biāo)準(zhǔn)為20/3元/臺時，現(xiàn)有720臺時，共收費20/3×720=4800元；

衡量資源的使用是否合理：同一種資源在不同的地方和不同的時期，其影子價格不相同。影子價格高的說明使用合理，否則說明使用不合理。應(yīng)建立動態(tài)影子價格體系，物盡其用。

281.6人造基下的單純形法---大M法

一、什么時候會出現(xiàn)人造基

例：求解下列數(shù)模

MinZ=x1－2x2s.t.x1+x2≥2-x1+x2≥1x2≤3x1,x2

≥0當(dāng)數(shù)模的約束條件出現(xiàn)”＝”或”≥”時，要將數(shù)?；癁橐?guī)范型，一般情況下就需要引入人工變量形成人造基。

標(biāo)準(zhǔn)化：引入非負(fù)松弛變量x3、x4、x5

令Z=-D,化成標(biāo)準(zhǔn)型如下

MaxD=-x1+

2x2s.t.x1+x2-x3

=2-x1+x2-x4

=

1x2+x5=3

xj≥0，j=1~5規(guī)范化：引入非負(fù)人工變量x6、x7

化成規(guī)范型如下

MaxD=-x1+

2x2s.t.x1+x2-x3

+x6=2-x1+x2-x4

+x7=

1x2+x5=3

xj≥0，j=1~7，x5,x6,x7為基變量規(guī)范型解基的形成只要三種可能：①由決策變量自然形成的解基：由具體的物理變量組成，可含在最優(yōu)解里，②由添加松弛變量形成的解基：每步迭代后的解均是可行解。③由引入人工變量形成的解基(人造基)：由虛擬人工變量組成，改變了原s.t.。29

二、大M法例：求解下列數(shù)模

MinZ=x1－2x2

…①s.t.x1+x2≥2

…②-x1+x2≥1

…③x2≤3

…④x1,x2

≥0

…⑤

-1o123x1-2-1123x2②③④

abch

規(guī)范化：引入非負(fù)松弛變量x3、x4、x5

和非負(fù)人工變量x6、x7

化成規(guī)范型如下

s.t.x1+x2-x3

+x6=2-x1+x2-x4

+x7=

1x2+x5=3

xj≥0，j=1~7，x5,x6,x7為基變量將目標(biāo)函數(shù)變形為：MinZ=x1-2x2+M(x6+x7)，其中M為很大很大的正常數(shù)。

MinZ=x1-2x2+M(3-2x2+x3+x4)=

3M+x1-(2M+2)x2+Mx3+Mx4

令Z=-D，將目標(biāo)函數(shù)規(guī)范化得：

MaxD=-3M-x1+(2M+2)x2-Mx3-Mx4

單純形表計算如下：30不可行解

X(1)

=(0，0，0，0，3，2，1)TD(1)=-3M(對應(yīng)O點)X(2)

=(0，1，0，0，2，1，0)TD(2)=2-M(對應(yīng)a點)初始基本可行解X(3)

=(1/2,3/2,0,0,3/2,0,0)TD(3)=5/2(對應(yīng)b點)X(4)

=(0，2，0，1，1)TD(4)=4(對應(yīng)C點)X(5)

=(0，3，1，2，0)TD(5)=6(對應(yīng)h點)X*

=(0，3，1，2，0)TZ*=-D(5)=-6311.7線性規(guī)劃數(shù)學(xué)模型計算機求解

一、求解軟件QSB介紹

QSB是專門用來求解運籌學(xué)模型的軟件。數(shù)學(xué)模型不需要標(biāo)準(zhǔn)化和規(guī)范化，直接將原始數(shù)學(xué)模型輸入計算機即可求解。

二、求解舉例

MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤32

一、靈敏度分析的概念

1、可用資源的數(shù)量發(fā)生變化，會使得右邊限制常數(shù)bi發(fā)生變化。2、由于市場條件發(fā)生變化，會使得價值系數(shù)Cj

發(fā)生變化。3、由于生產(chǎn)工藝的改進，會使得單耗(約束條件系數(shù)或叫技術(shù)系數(shù))aij發(fā)生變化。4、為使資源得到充分利用，增加生產(chǎn)項目，會增加變量個數(shù)。5、為提高產(chǎn)品質(zhì)量，增加資源種類或生產(chǎn)工藝，會增加約束條件個數(shù)。各類因素發(fā)生變化：對原規(guī)劃問題最優(yōu)解(原最優(yōu)決策方案)的影響分析；這些因素在什么范圍內(nèi)變化時，原規(guī)劃問題最優(yōu)解或最優(yōu)基不變。各類因素發(fā)生變化分為以下兩種情況：第一種情況：多種因素同時發(fā)生變化，原最優(yōu)解可能發(fā)生變化，一般從頭開始迭代計算，求出新最優(yōu)解。第二種情況：單種因素單方面發(fā)生變化，原最優(yōu)解可能發(fā)生變化，此時不必從頭開始迭代計算，只要在原最優(yōu)表中進行分析計算，即可求出新最優(yōu)解。

以下只討論第二種情況。第二章：靈敏度分析33二、單純形表的逆矩陣及各表之間的運算關(guān)系

基x1x2x3x4x5bx339100540x455010450x593001720-Z70300000x30810-1/3300x4010/301-5/950x111/3001/980-Z020/300-70/9-5600x3001-12/51180x20103/10-1/615x1100-1/101/675-Z000-2-20/3-5700非基區(qū)

基區(qū)

表的逆矩陣(基區(qū)的系數(shù)構(gòu)成的矩陣)34三、單純形表的逆矩陣及各表之間的運算關(guān)系

39100540550104509300172070300000最優(yōu)表

初始表001-12/511800103/10-1/615100-1/101/675000-2-20/3-57001-12/51003/10-1/600-1/101/600-2-20/31=

×

最優(yōu)表逆矩陣B-1-1/63/1001-12/511/6-1/100001=

×

539，