管理運(yùn)籌學(xué)021線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念課件

第

1

節(jié)Linear

ProgrammingL

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

第1節(jié)LinearProgramming1第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念2一、現(xiàn)實(shí)中的線性規(guī)劃問題及數(shù)學(xué)模型二、線性規(guī)劃的標(biāo)準(zhǔn)形式三、線性規(guī)劃的幾何解釋四、線性規(guī)劃的基及基本可行解第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念2一、現(xiàn)實(shí)中的線性規(guī)劃問23一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-1

生產(chǎn)計(jì)劃問題某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如表2-1所示，試用線性規(guī)劃制訂使總利潤(rùn)最大的生產(chǎn)計(jì)劃。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁1.51.01.5200080005000設(shè)備A設(shè)備B設(shè)備C單位產(chǎn)品消耗的機(jī)時(shí)數(shù)產(chǎn)品設(shè)備能力（小時(shí)）利潤(rùn)（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.03一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-1生產(chǎn)計(jì)劃問題第34一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型z

x1

x2x3x4決策變量z=5.24x1

+7.30x2+8.34x3+4.18x4max0目標(biāo)函數(shù)1.5x1

+1.0x2+2.4x3+1.0x4

≤2000①函數(shù)約束非負(fù)性約束s.t.第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念1.0x1

+5.0x2+1.0x3+3.5x4

≤8000②1.5x1

+3.0x2+3.5x3+1.0x4

≤8000③x1，

x2，

x3，

x4≥0④產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁1.51.01.5200080005000設(shè)備A設(shè)備B設(shè)備C單位產(chǎn)品消耗的機(jī)時(shí)數(shù)產(chǎn)品設(shè)備能力（小時(shí)）利潤(rùn)（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.04一現(xiàn)實(shí)中的線性規(guī)劃問題及模型zx145一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：

x1=294.12（件）x2=1500（件） x3=0 （件） x4=58.82（件）

最大利潤(rùn)為

z=12737.06（元）

請(qǐng)注意最優(yōu)解中利潤(rùn)率最高的產(chǎn)品丙在最優(yōu)生產(chǎn)計(jì)劃中不安排生產(chǎn)。說明按產(chǎn)品利潤(rùn)率大小為優(yōu)先次序來安排生產(chǎn)計(jì)劃的方法有很大局限性。尤其當(dāng)產(chǎn)品品種很多，設(shè)備類型很多的情況下，用手工方法安排生產(chǎn)計(jì)劃很難獲得滿意的結(jié)果。5一現(xiàn)實(shí)中的線性規(guī)劃問題及模型第1節(jié)線性規(guī)劃的數(shù)學(xué)56一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-2

配料問題某工廠要用四種合金T1，T2，T3和T4為原料，經(jīng)熔煉成為一種新的不銹鋼G。這四種原料含元素鉻（Cr），錳（Mn）和鎳（Ni）的含量（%），這四種原料的單價(jià)以及新的不銹鋼材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：設(shè)熔煉時(shí)重量沒有損耗，要熔煉成100公斤不銹鋼G，應(yīng)選用原料T1，T2，T3和T4各多少公斤，使成本最小。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念T1

T2

T3

T43.212.045.823.202.104.30CrMnNiG單價(jià)（元/公斤）

1159782764.531.123.062.193.574.271.764.332.73

x1

x2x3x46一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-2配料問題第1節(jié)67第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=115x1

+97x2+82x3+76x4min0.0321x1

+0.0453x2+0.0219x3+0.0176x4

≥3.20s.t.x1，

x2，

x3，

x4≥00.0204x1

+0.0112x2+0.0357x3+0.0433x4

≥2.100.0582x1

+0.0306x2+0.0427x3+0.0273x4

≥4.30

x1

+

x2+

x3+

x4

=100求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：

x1=26.58x2=31.57x3=41.84x4=0

最大利潤(rùn)為

z=9549.87（元）一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型7第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=115x178一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-3

背包問題一只背包最大裝載重量為50公斤?，F(xiàn)有三種物品，每種物品數(shù)量無限。每種物品每件的重量、價(jià)值如下表所示：

要在背包中裝入這三種物品各多少件，使背包中的物品價(jià)值最高。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念物品1物品2物品3

1017重量（公斤/件）價(jià)值（元/件）41722035

x1

x2x38一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-3背包問題第1節(jié)89第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=17x1

+72x2+35x3max10x1

+41x2+20x3

≤50s.t.x1，

x2，

x3≥0且為整數(shù)求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：

x1=1x2=0x3=2

最高價(jià)值為

z=87（元）一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型9第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=17x1+910一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問題

某公司下設(shè)兩個(gè)分工廠，兩個(gè)倉(cāng)庫(kù)及一個(gè)配送中心。其中F1和F2是兩個(gè)工廠，W1和W2是兩個(gè)倉(cāng)庫(kù)。D是一個(gè)分銷中心。由工廠生產(chǎn)的產(chǎn)品經(jīng)由圖所示的運(yùn)輸網(wǎng)絡(luò)運(yùn)往倉(cāng)庫(kù)。每一條路線運(yùn)輸?shù)膯挝怀杀驹诰€段上給出，其中，F(xiàn)1→F2與D→W2路線由于受到路線中的橋梁承重上限的要求，因此有最大運(yùn)輸量限制。其他路線有足夠的運(yùn)輸能力來運(yùn)輸兩個(gè)工廠生產(chǎn)的貨物。需要制訂的決策是關(guān)于每一條路線應(yīng)該運(yùn)輸多少，目標(biāo)是總體的運(yùn)輸成本最小化。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念10一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問1011一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問題

第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念900元/單位x6100元/單位x7最多80單位x4x5x2x3x1300元/單位300元/單位F1需求30單位W1生產(chǎn)40單位F2需求60單位W2200元/單位D最多10單位200元/單位400元/單位圖2-1公司的配送網(wǎng)絡(luò)生產(chǎn)50單位11一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問1112第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=200x1

+400x2+900x3+300x4+100x5+3x6+200x7minx1

+

x2+

x3=50s.t.x1，…，x7≥0-x1

+x4=40-x2-x4+x5=0-x3+

x6

–x7

=-30求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：（x1

，x2，x3，x4，x5，x6，x7

）=（0，40，10，40，80，0，20）

z=49000（元）一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型-x5-

x6+x7

=-60x1

≤10，x5

≤8012第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=200x11213線性規(guī)劃的一般形式

一般LP模型的三類參數(shù)：價(jià)值系數(shù)c

j，消耗系數(shù)a

ij，右端常數(shù)b

i.LP模型的三要素：決策變量，目標(biāo)函數(shù)，約束條件.s.t.max(min)

z=c1x1+c2x2+c3x3+…+cnxn

a11x1

+a12x2+…+a1nxn

≤(=≥)

b1a21x1

+a22x2+…+a2nxn

≤(=≥)

b2

…

am1x1+am2x2+…+amnxn

≤(=≥)

bm

xj≥(或≤)0,

或自由,j=1,2,…,n第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型13線性規(guī)劃的一般形式一般LP模型的三類參數(shù)：s.t.m1314線性規(guī)劃的向量和矩陣的表達(dá)形式記向量和矩陣第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型則線性規(guī)劃問題可以表示為：max（min)z=CX

s.t.AX≤(=≥)bX≥014線性規(guī)劃的向量和矩陣的表達(dá)形式記向量和矩陣第1節(jié)線性規(guī)1415二、線性規(guī)劃的標(biāo)準(zhǔn)形式稱以下線性規(guī)劃的形式為標(biāo)準(zhǔn)形式max

z=c1x1+c2x2+c3x3+…+cnxns.t.a11x1

+a12x2+

…+a1nxn

=

b1(≥0)a21x1

+a22x2+

…+a2nxn

=b2(≥0)

…

…

…am1x1+am2x2+…+amnxn

=

bm(≥0)x1

,

x2,…

,xn≥0簡(jiǎn)記為：maxz=CX

s.t.AX=bX≥0(M1):

(M2):

第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念15二、線性規(guī)劃的標(biāo)準(zhǔn)形式稱以下線性規(guī)劃的形式為標(biāo)準(zhǔn)形式ma1516非標(biāo)準(zhǔn)形LP問題的標(biāo)準(zhǔn)化

一、極小化目標(biāo)函數(shù)的問題

minz=CX令z′=

－

z

maxz′=

－

CX

例：minz=3x1＋

2x2

maxz′=

－

3x1－

2x2

二、約束條件不是等式的問題

⑴bi<0兩邊同時(shí)乘以

-1

⑵約束為≤形式加上松弛變量

⑶約束為≥形式減去剩余變量

三、變量符號(hào)無限制或小于等于零的問題若xk為自由變量,

令xk

=xk′－

xk〞且xk′,xk〞≥0

若xk

≤0,

令xk

=－

xk′,則xk′≥0

第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念二、線性規(guī)劃的標(biāo)準(zhǔn)形式xzzzminz=-zzmaxx*16非標(biāo)準(zhǔn)形LP問題的標(biāo)準(zhǔn)化第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)1617minz=2x1－

3x2＋x3

x1－

x2

＋2

x3

≤32x1＋

3x2

－

x3≥5x1

＋x2

＋

x3=4

x1

≥0,

x2

無約束，

x3

≤

0s.t.第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念例2-5將下述LP問題化成標(biāo)準(zhǔn)形式解：令z′=-z

，x2=

x2′－

x2〞，x3′=

-x3

maxz′=

－

2

x1＋3

x2′-

3x2〞＋x3′

x1－

x2′+

x2〞－2

x3′+

x4

=3

2x1+3x2′－

3x2〞+

x3′

－

x5

=5

x1

+

x2′

－

x2〞

－

x3′

=4

x1

,

x2′,

x2〞,

x3′,

x4

,

x5

≥0s.t.二、線性規(guī)劃的標(biāo)準(zhǔn)形式17minz=2x1－3x2＋x3s.t.第17第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念18minz=

x1＋

2x2

－

3x3

x1＋

2x2

－

x3

≤52x1＋

3x2

－

x3≥6

－

x1

－

x2

＋

x3≥－

2

x1

≥0,

x3

≤

0s.t.解:max

z′=

－

x1

－

2x2

＋

3x3s.t.x1＋

2x2

－

x3

+x4

=5

2x1＋

3x2

－

x3

-

x5

=6x1＋

x2

－

x3

+x6

=2

x1

,

x4

,

x5

,

x6

≥0,

x3

≤

0練習(xí)：將下述LP問題化成標(biāo)準(zhǔn)形二、線性規(guī)劃的標(biāo)準(zhǔn)形式第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念18minz=x118第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念19令x2

=

x2′－

x2〞，且

x2′，x2〞

≥0x3

=

-x3′代入上式中，得

maxz′=

－

x1－

2

x2′+

2

x2〞－

3x3′

x1+2x2′－

2x2〞+

x3′+

x4

=5

2x1+3x2′－

3x2〞+

x3′

－

x5

=6

x1

+

x2′

－

x2〞

+

x3′

+x6

=2

x1

,

x2′,

x2〞,

x3′,

x4

,

x5

,

x6

≥0s.t.二、線性規(guī)劃的標(biāo)準(zhǔn)形式第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念19令x2=x2′19第1節(jié)線性規(guī)劃的基本性質(zhì)20只有兩個(gè)變量的線性規(guī)劃問題

X*=(4,6)Tz*=42

1°畫出可行域圖形

2°畫出目標(biāo)函數(shù)的等值線及其法線

3°確定最優(yōu)點(diǎn)例

max

z=3x1+5x2

x1

≤

8

2

x2≤

123x1+

4

x2≤

36

x1,

x2

≥0s.t.x1x2O(0,0)x1=8A(8,0)2x2=12D(0,6)3x1+4x2=36O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)z=15z=30z法向z*=42邊界方程三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)20只有兩個(gè)變量的線性規(guī)劃問題X20第1節(jié)線性規(guī)劃的基本性質(zhì)21幾點(diǎn)說明實(shí)際運(yùn)用時(shí)還須注意以下幾點(diǎn):(1)若函數(shù)約束原型就是等式,則其代表的區(qū)域僅為一直線,而且問題的整個(gè)可行域R(若存在的話)也必然在此直線上。(2)在畫目標(biāo)函數(shù)等值線時(shí)只須畫兩條就能確定其法線方向,為此,

只須賦給z

兩個(gè)適當(dāng)?shù)闹怠?3)在找出最優(yōu)點(diǎn)后,關(guān)于其坐標(biāo)值有兩種確定方法:①

在圖上觀測(cè)最優(yōu)點(diǎn)坐標(biāo)值②

通過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)21幾點(diǎn)說明三、線性規(guī)劃的幾何解釋21第1節(jié)線性規(guī)劃的基本性質(zhì)22幾種可能結(jié)果一、唯一解

如例1、例2都只有一個(gè)最優(yōu)點(diǎn)，屬于唯一解的情形。s.t.max

z=3x1+4x2

x1≤82x2≤123x1+4x2≤

36

x1，x2≥0

二、多重解z=12z*=36線段BC上無窮多個(gè)點(diǎn)均為最優(yōu)解。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)22幾種可能結(jié)果s.t.maxz22第1節(jié)線性規(guī)劃的基本性質(zhì)23x1x2z*三、無界解3694812x1x2R2R1∩R2=?四、無可行解+∞R1三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)23x1x2z*三、無界解3623第1節(jié)線性規(guī)劃的基本性質(zhì)24相關(guān)定義定義2-1可行域在n維空間中，滿足條件ai1x1+ai2x2+…+ainxn

≤(=≥)

bi且xj≥0的點(diǎn)集。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)24相關(guān)定義O(0,0)x1x2R24第1節(jié)線性規(guī)劃的基本性質(zhì)25定義2-2凸集三、線性規(guī)劃的幾何解釋設(shè)S是n維空間中的一個(gè)點(diǎn)集。若對(duì)任意n維向量X1S，X2S，且X1X2，以及任意實(shí)數(shù)（01），有 X=X1+(1-)X2S則稱S為n維空間中的一個(gè)凸集（ConvexSet）。點(diǎn)X稱為點(diǎn)X1和X2的凸組合。

凸集：非凸集：第1節(jié)線性規(guī)劃的基本性質(zhì)25定義2-2凸集三、線性規(guī)劃的25第1節(jié)線性規(guī)劃的基本性質(zhì)26定義2-3凸集的極點(diǎn)三、線性規(guī)劃的幾何解釋設(shè)S為一凸集，且XS，若X不能用不同的兩點(diǎn)X1S，X2S的線性組合表示為 X=X1+(1-)X2（01）則稱X為S的一個(gè)極點(diǎn)。

運(yùn)用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質(zhì)：（1）若線性規(guī)劃的可行域非空，則可行域必定為一凸集。（2）若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可以在凸集的極點(diǎn)中找到。

這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個(gè)可行解中搜索的問題轉(zhuǎn)化為在其可行域的有限個(gè)極點(diǎn)上搜索的問題。第1節(jié)線性規(guī)劃的基本性質(zhì)26定義2-3凸集的極點(diǎn)三、線性2627第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念基：設(shè)A為線性規(guī)劃模型約束條件系數(shù)矩陣（mn，m<n），而B為其mm子矩陣，若|B|≠0，則稱B為該線性規(guī)劃模型的一個(gè)基?；兞浚夯忻總€(gè)向量所對(duì)應(yīng)的變量稱為基變量。非基變量：模型中基變量之外的變量稱為非基變量?；窘猓ɑ猓毫钅Ｐ椭兴蟹腔兞縓非基=0后，由模型約束方程組 n

aijxj=bi(i=1,2,……,m)得到的一組解。

j=1基本可行解（基可行解）：在基本解中，同時(shí)又是可行解的解稱為基本可行解?？尚谢簩?duì)應(yīng)于基本可行解的基稱為可行基。四、線性規(guī)劃的基、基本可行解27第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念基：設(shè)A為線性規(guī)劃模27-28-Maxz=2x1+3x2st.x1+x23 x1+2x24 x1,x2

0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4

0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T

等。設(shè)B=1001，令，則|B|=1≠0,令x1=x2=0，則x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基變量令B=1110x1x3

，則令x2=x4=0，則x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解標(biāo)準(zhǔn)化第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念四、線性規(guī)劃的基、基本可行解-28-Maxz=2x1+3x2Maxz=2x12829定理2-1線性規(guī)劃的基本可行解就是可行域的極點(diǎn)。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念四、線性規(guī)劃的基、基本可行解Maxz=2x1+3x2s.t.x1+x23 x1+2x24 x1,x2

0Maxz=2x1+3x2+0x3+0x4s.t.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4

0例：標(biāo)準(zhǔn)化A矩陣包含以下六個(gè)2×2的子矩陣：

B1=[p1，p2] B2=[p1，p3] B3=[p1，p4] B4=[p2，p3] B5=[p2，p4] B6=[p3，p4]其中所有的子矩陣行列式值均不等于0，均為非奇異方陣，因此該問題共有6個(gè)基。

29定理2-1線性規(guī)劃的基本可行解就是可行域的極點(diǎn)。第12930第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念四、線性規(guī)劃的基、基本可行解B6=1001，則|B6|=1≠0,x3x4——基變量——基本可行解對(duì)應(yīng)O點(diǎn)令x1=x2=0，則x3=3,x4=4，X6=(0,0,3,4)T同理可以求得B1、B2、B3、B4、B5對(duì)應(yīng)的基本解：X1=(x1，x2，x3，x4)T=(2，1，0，0)T

對(duì)應(yīng)B點(diǎn)X2=(x1，x2，x3，x4)T=(4，0，-1，0)T對(duì)應(yīng)E點(diǎn)X3=(x1，x2，x3，x4)T=(3，0，0，1)T對(duì)應(yīng)C點(diǎn)X4=(x1，x2，x3，x4)T=(0，2，1，0)T對(duì)應(yīng)A點(diǎn)X5=(x1，x2，x3，x4)T=(0，3，0，-2)T對(duì)應(yīng)D點(diǎn)其中X1，

X3，X4是基本可行解。O(0,0)x1x2B(2,1)E(4,0)C(3,0)A(0,2)D(0,3)30第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念四、線性規(guī)劃的基、基30謝謝！謝謝！31

第

1

節(jié)Linear

ProgrammingL

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

第1節(jié)LinearProgramming32第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念33一、現(xiàn)實(shí)中的線性規(guī)劃問題及數(shù)學(xué)模型二、線性規(guī)劃的標(biāo)準(zhǔn)形式三、線性規(guī)劃的幾何解釋四、線性規(guī)劃的基及基本可行解第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念2一、現(xiàn)實(shí)中的線性規(guī)劃問3334一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-1

生產(chǎn)計(jì)劃問題某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如表2-1所示，試用線性規(guī)劃制訂使總利潤(rùn)最大的生產(chǎn)計(jì)劃。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁1.51.01.5200080005000設(shè)備A設(shè)備B設(shè)備C單位產(chǎn)品消耗的機(jī)時(shí)數(shù)產(chǎn)品設(shè)備能力（小時(shí)）利潤(rùn)（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.03一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-1生產(chǎn)計(jì)劃問題第3435一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型z

x1

x2x3x4決策變量z=5.24x1

+7.30x2+8.34x3+4.18x4max0目標(biāo)函數(shù)1.5x1

+1.0x2+2.4x3+1.0x4

≤2000①函數(shù)約束非負(fù)性約束s.t.第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念1.0x1

+5.0x2+1.0x3+3.5x4

≤8000②1.5x1

+3.0x2+3.5x3+1.0x4

≤8000③x1，

x2，

x3，

x4≥0④產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁1.51.01.5200080005000設(shè)備A設(shè)備B設(shè)備C單位產(chǎn)品消耗的機(jī)時(shí)數(shù)產(chǎn)品設(shè)備能力（小時(shí)）利潤(rùn)（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.04一現(xiàn)實(shí)中的線性規(guī)劃問題及模型zx13536一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：

x1=294.12（件）x2=1500（件） x3=0 （件） x4=58.82（件）

最大利潤(rùn)為

z=12737.06（元）

請(qǐng)注意最優(yōu)解中利潤(rùn)率最高的產(chǎn)品丙在最優(yōu)生產(chǎn)計(jì)劃中不安排生產(chǎn)。說明按產(chǎn)品利潤(rùn)率大小為優(yōu)先次序來安排生產(chǎn)計(jì)劃的方法有很大局限性。尤其當(dāng)產(chǎn)品品種很多，設(shè)備類型很多的情況下，用手工方法安排生產(chǎn)計(jì)劃很難獲得滿意的結(jié)果。5一現(xiàn)實(shí)中的線性規(guī)劃問題及模型第1節(jié)線性規(guī)劃的數(shù)學(xué)3637一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-2

配料問題某工廠要用四種合金T1，T2，T3和T4為原料，經(jīng)熔煉成為一種新的不銹鋼G。這四種原料含元素鉻（Cr），錳（Mn）和鎳（Ni）的含量（%），這四種原料的單價(jià)以及新的不銹鋼材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：設(shè)熔煉時(shí)重量沒有損耗，要熔煉成100公斤不銹鋼G，應(yīng)選用原料T1，T2，T3和T4各多少公斤，使成本最小。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念T1

T2

T3

T43.212.045.823.202.104.30CrMnNiG單價(jià)（元/公斤）

1159782764.531.123.062.193.574.271.764.332.73

x1

x2x3x46一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-2配料問題第1節(jié)3738第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=115x1

+97x2+82x3+76x4min0.0321x1

+0.0453x2+0.0219x3+0.0176x4

≥3.20s.t.x1，

x2，

x3，

x4≥00.0204x1

+0.0112x2+0.0357x3+0.0433x4

≥2.100.0582x1

+0.0306x2+0.0427x3+0.0273x4

≥4.30

x1

+

x2+

x3+

x4

=100求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：

x1=26.58x2=31.57x3=41.84x4=0

最大利潤(rùn)為

z=9549.87（元）一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型7第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=115x13839一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-3

背包問題一只背包最大裝載重量為50公斤。現(xiàn)有三種物品，每種物品數(shù)量無限。每種物品每件的重量、價(jià)值如下表所示：

要在背包中裝入這三種物品各多少件，使背包中的物品價(jià)值最高。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念物品1物品2物品3

1017重量（公斤/件）價(jià)值（元/件）41722035

x1

x2x38一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-3背包問題第1節(jié)3940第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=17x1

+72x2+35x3max10x1

+41x2+20x3

≤50s.t.x1，

x2，

x3≥0且為整數(shù)求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：

x1=1x2=0x3=2

最高價(jià)值為

z=87（元）一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型9第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=17x1+4041一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問題

某公司下設(shè)兩個(gè)分工廠，兩個(gè)倉(cāng)庫(kù)及一個(gè)配送中心。其中F1和F2是兩個(gè)工廠，W1和W2是兩個(gè)倉(cāng)庫(kù)。D是一個(gè)分銷中心。由工廠生產(chǎn)的產(chǎn)品經(jīng)由圖所示的運(yùn)輸網(wǎng)絡(luò)運(yùn)往倉(cāng)庫(kù)。每一條路線運(yùn)輸?shù)膯挝怀杀驹诰€段上給出，其中，F(xiàn)1→F2與D→W2路線由于受到路線中的橋梁承重上限的要求，因此有最大運(yùn)輸量限制。其他路線有足夠的運(yùn)輸能力來運(yùn)輸兩個(gè)工廠生產(chǎn)的貨物。需要制訂的決策是關(guān)于每一條路線應(yīng)該運(yùn)輸多少，目標(biāo)是總體的運(yùn)輸成本最小化。第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念10一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問4142一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問題

第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念900元/單位x6100元/單位x7最多80單位x4x5x2x3x1300元/單位300元/單位F1需求30單位W1生產(chǎn)40單位F2需求60單位W2200元/單位D最多10單位200元/單位400元/單位圖2-1公司的配送網(wǎng)絡(luò)生產(chǎn)50單位11一現(xiàn)實(shí)中的線性規(guī)劃問題及模型例2-4最小費(fèi)用流問4243第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=200x1

+400x2+900x3+300x4+100x5+3x6+200x7minx1

+

x2+

x3=50s.t.x1，…，x7≥0-x1

+x4=40-x2-x4+x5=0-x3+

x6

–x7

=-30求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：（x1

，x2，x3，x4，x5，x6，x7

）=（0，40，10，40，80，0，20）

z=49000（元）一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型-x5-

x6+x7

=-60x1

≤10，x5

≤8012第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念z=200x14344線性規(guī)劃的一般形式

一般LP模型的三類參數(shù)：價(jià)值系數(shù)c

j，消耗系數(shù)a

ij，右端常數(shù)b

i.LP模型的三要素：決策變量，目標(biāo)函數(shù)，約束條件.s.t.max(min)

z=c1x1+c2x2+c3x3+…+cnxn

a11x1

+a12x2+…+a1nxn

≤(=≥)

b1a21x1

+a22x2+…+a2nxn

≤(=≥)

b2

…

am1x1+am2x2+…+amnxn

≤(=≥)

bm

xj≥(或≤)0,

或自由,j=1,2,…,n第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型13線性規(guī)劃的一般形式一般LP模型的三類參數(shù)：s.t.m4445線性規(guī)劃的向量和矩陣的表達(dá)形式記向量和矩陣第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念一

現(xiàn)實(shí)中的線性規(guī)劃問題及模型則線性規(guī)劃問題可以表示為：max（min)z=CX

s.t.AX≤(=≥)bX≥014線性規(guī)劃的向量和矩陣的表達(dá)形式記向量和矩陣第1節(jié)線性規(guī)4546二、線性規(guī)劃的標(biāo)準(zhǔn)形式稱以下線性規(guī)劃的形式為標(biāo)準(zhǔn)形式max

z=c1x1+c2x2+c3x3+…+cnxns.t.a11x1

+a12x2+

…+a1nxn

=

b1(≥0)a21x1

+a22x2+

…+a2nxn

=b2(≥0)

…

…

…am1x1+am2x2+…+amnxn

=

bm(≥0)x1

,

x2,…

,xn≥0簡(jiǎn)記為：maxz=CX

s.t.AX=bX≥0(M1):

(M2):

第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念15二、線性規(guī)劃的標(biāo)準(zhǔn)形式稱以下線性規(guī)劃的形式為標(biāo)準(zhǔn)形式ma4647非標(biāo)準(zhǔn)形LP問題的標(biāo)準(zhǔn)化

一、極小化目標(biāo)函數(shù)的問題

minz=CX令z′=

－

z

maxz′=

－

CX

例：minz=3x1＋

2x2

maxz′=

－

3x1－

2x2

二、約束條件不是等式的問題

⑴bi<0兩邊同時(shí)乘以

-1

⑵約束為≤形式加上松弛變量

⑶約束為≥形式減去剩余變量

三、變量符號(hào)無限制或小于等于零的問題若xk為自由變量,

令xk

=xk′－

xk〞且xk′,xk〞≥0

若xk

≤0,

令xk

=－

xk′,則xk′≥0

第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念二、線性規(guī)劃的標(biāo)準(zhǔn)形式xzzzminz=-zzmaxx*16非標(biāo)準(zhǔn)形LP問題的標(biāo)準(zhǔn)化第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)4748minz=2x1－

3x2＋x3

x1－

x2

＋2

x3

≤32x1＋

3x2

－

x3≥5x1

＋x2

＋

x3=4

x1

≥0,

x2

無約束，

x3

≤

0s.t.第1節(jié)線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念例2-5將下述LP問題化成標(biāo)準(zhǔn)形式解：令z′=-z

，x2=

x2′－

x2〞，x3′=

-x3

maxz′=

－

2

x1＋3

x2′-

3x2〞＋x3′

x1－

x2′+

x2〞－2

x3′+

x4

=3

2x1+3x2′－

3x2〞+

x3′

－

x5

=5

x1

+

x2′

－

x2〞

－

x3′

=4

x1

,

x2′,

x2〞,

x3′,

x4

,

x5

≥0s.t.二、線性規(guī)劃的標(biāo)準(zhǔn)形式17minz=2x1－3x2＋x3s.t.第48第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念49minz=

x1＋

2x2

－

3x3

x1＋

2x2

－

x3

≤52x1＋

3x2

－

x3≥6

－

x1

－

x2

＋

x3≥－

2

x1

≥0,

x3

≤

0s.t.解:max

z′=

－

x1

－

2x2

＋

3x3s.t.x1＋

2x2

－

x3

+x4

=5

2x1＋

3x2

－

x3

-

x5

=6x1＋

x2

－

x3

+x6

=2

x1

,

x4

,

x5

,

x6

≥0,

x3

≤

0練習(xí)：將下述LP問題化成標(biāo)準(zhǔn)形二、線性規(guī)劃的標(biāo)準(zhǔn)形式第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念18minz=x149第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念50令x2

=

x2′－

x2〞，且

x2′，x2〞

≥0x3

=

-x3′代入上式中，得

maxz′=

－

x1－

2

x2′+

2

x2〞－

3x3′

x1+2x2′－

2x2〞+

x3′+

x4

=5

2x1+3x2′－

3x2〞+

x3′

－

x5

=6

x1

+

x2′

－

x2〞

+

x3′

+x6

=2

x1

,

x2′,

x2〞,

x3′,

x4

,

x5

,

x6

≥0s.t.二、線性規(guī)劃的標(biāo)準(zhǔn)形式第1章線性規(guī)劃的數(shù)學(xué)模型及相關(guān)概念19令x2=x2′50第1節(jié)線性規(guī)劃的基本性質(zhì)51只有兩個(gè)變量的線性規(guī)劃問題

X*=(4,6)Tz*=42

1°畫出可行域圖形

2°畫出目標(biāo)函數(shù)的等值線及其法線

3°確定最優(yōu)點(diǎn)例

max

z=3x1+5x2

x1

≤

8

2

x2≤

123x1+

4

x2≤

36

x1,

x2

≥0s.t.x1x2O(0,0)x1=8A(8,0)2x2=12D(0,6)3x1+4x2=36O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)z=15z=30z法向z*=42邊界方程三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)20只有兩個(gè)變量的線性規(guī)劃問題X51第1節(jié)線性規(guī)劃的基本性質(zhì)52幾點(diǎn)說明實(shí)際運(yùn)用時(shí)還須注意以下幾點(diǎn):(1)若函數(shù)約束原型就是等式,則其代表的區(qū)域僅為一直線,而且問題的整個(gè)可行域R(若存在的話)也必然在此直線上。(2)在畫目標(biāo)函數(shù)等值線時(shí)只須畫兩條就能確定其法線方向,為此,

只須賦給z

兩個(gè)適當(dāng)?shù)闹怠?3)在找出最優(yōu)點(diǎn)后,關(guān)于其坐標(biāo)值有兩種確定方法:①

在圖上觀測(cè)最優(yōu)點(diǎn)坐標(biāo)值②

通過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)21幾點(diǎn)說明三、線性規(guī)劃的幾何解釋52第1節(jié)線性規(guī)劃的基本性質(zhì)53幾種可能結(jié)果一、唯一解

如例1、例2都只有一個(gè)最優(yōu)點(diǎn)，屬于唯一解的情形。s.t.max

z=3x1+4x2

x1≤82x2≤123x1+4x2≤

36

x1，x2≥0

二、多重解z=12z*=36線段BC上無窮多個(gè)點(diǎn)均為最優(yōu)解。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)22幾種可能結(jié)果s.t.maxz53第1節(jié)線性規(guī)劃的基本性質(zhì)54x1x2z*三、無界解3694812x1x2R2R1∩R2=?四、無可行解+∞R1三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)23x1x2z*三、無界解3654第1節(jié)線性規(guī)劃的基本性質(zhì)55相關(guān)定義定義2-1可行域在n維空間中，滿足條件ai1x1+ai2x2+…+ainxn

≤(=≥)

bi且xj≥0的點(diǎn)集。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)三、線性規(guī)劃的幾何解釋第1節(jié)線性規(guī)劃的基本性質(zhì)24相關(guān)定義O(0,0)x1x2R55第1節(jié)線性規(guī)劃的基本性質(zhì)56定義2-2凸集三、線性規(guī)劃的幾何解釋設(shè)S是n維空間中的一個(gè)點(diǎn)集。若對(duì)任意n維向量X1S，X2S，且X1X2，以及任意實(shí)數(shù)（01），有 X=X1+(1-)X2S則稱S為n維空間中的一個(gè)凸集（ConvexSet）。點(diǎn)X稱為點(diǎn)X1和X2的凸組合。

凸集：非凸集：第1節(jié)線性規(guī)劃的基本性質(zhì)25定義2-2凸集三、線性規(guī)劃的56第1節(jié)線性規(guī)劃的基本性質(zhì)57定義2-3凸集的極點(diǎn)三、線性規(guī)劃的幾何解釋設(shè)