第2講線性規(guī)劃與LINGO編程

1、華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模創(chuàng)新實(shí)踐基地系列課件華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模創(chuàng)新實(shí)踐基地系列課件第第2 2講講 線性規(guī)劃與線性規(guī)劃與LINGOLINGO編編程程華中農(nóng)業(yè)大學(xué)華中農(nóng)業(yè)大學(xué)內(nèi)容說明內(nèi)容說明 以下內(nèi)容在以下內(nèi)容在數(shù)學(xué)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)建模與數(shù)學(xué)實(shí)驗(yàn)（第二版）（第二版） （汪曉銀（汪曉銀 ，周保，周保平主編）第平主編）第3章章2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃2.3 敏感性分析敏感性分析2.4 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃2.5 0-1規(guī)劃規(guī)劃內(nèi)容說明內(nèi)容說明 數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃俗稱最優(yōu)化俗稱最優(yōu)化, ,首先是一種理首先是一種理念念, ,其次才是一種方法其次才是一種方法

2、, ,它所追求的是一種它所追求的是一種“至善至善”之道之道, ,一種追求卓越的精神一種追求卓越的精神. .2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃 小明同學(xué)，燒一壺水要小明同學(xué)，燒一壺水要8分鐘，灌開水分鐘，灌開水要要1分鐘，取牛奶和報(bào)紙要分鐘，取牛奶和報(bào)紙要5分鐘，整理書包分鐘，整理書包要要6分鐘，為了盡快做完這些事，怎樣安排分鐘，為了盡快做完這些事，怎樣安排才能使時(shí)間最少？最少需要幾分鐘？才能使時(shí)間最少？最少需要幾分鐘？ 十個(gè)人各提一只水桶，同時(shí)到水龍頭十個(gè)人各提一只水桶，同時(shí)到水龍頭前打水。設(shè)水龍頭注滿第一個(gè)人的桶需要前打水。設(shè)水龍頭注滿第一個(gè)人的桶需要1分鐘，注滿第二個(gè)人的桶需要分鐘，注滿

3、第二個(gè)人的桶需要2分鐘，依此分鐘，依此類推，注滿第幾個(gè)人的桶就需要幾分鐘，類推，注滿第幾個(gè)人的桶就需要幾分鐘，如果只有一只水龍頭，適當(dāng)安排這如果只有一只水龍頭，適當(dāng)安排這10個(gè)人個(gè)人的順序，就可以使每個(gè)人所費(fèi)的時(shí)間總和的順序，就可以使每個(gè)人所費(fèi)的時(shí)間總和盡可能小，問這個(gè)總費(fèi)時(shí)至少是幾分鐘？盡可能小，問這個(gè)總費(fèi)時(shí)至少是幾分鐘？ 2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃 數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃(最優(yōu)化最優(yōu)化)作為一門學(xué)科孕育于作為一門學(xué)科孕育于20世世紀(jì)的紀(jì)的30年代年代,誕生于第二次世界大戰(zhàn)彌漫的硝煙誕生于第二次世界大戰(zhàn)彌漫的硝煙中。中。 數(shù)學(xué)規(guī)劃指在一系列客觀或主觀限制條件數(shù)學(xué)規(guī)劃指在一系列客觀或主觀限

4、制條件下，尋求合理分配有限資源使所關(guān)注的某個(gè)或多下，尋求合理分配有限資源使所關(guān)注的某個(gè)或多個(gè)指標(biāo)達(dá)到最大（或最?。┑臄?shù)學(xué)理論和方法個(gè)指標(biāo)達(dá)到最大（或最?。┑臄?shù)學(xué)理論和方法，是運(yùn)籌學(xué)里一個(gè)十分重要的分支。是運(yùn)籌學(xué)里一個(gè)十分重要的分支。 2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃最優(yōu)化問題的最優(yōu)化問題的數(shù)學(xué)模型的一般形式數(shù)學(xué)模型的一般形式為：為： xfzopt skjiRDxnkxtmjxglixhts , 1, 0 , 1, 0 , 1, 0 .（1）（2）三個(gè)要素：三個(gè)要素：決策變量決策變量decision bariable，目標(biāo)函數(shù)目標(biāo)函數(shù)objective function，約束條件約束條件co

5、nstraints。 2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃 約束條件（約束條件（2）所確定的）所確定的x的范圍稱為的范圍稱為可行域可行域feasible region，滿足（，滿足（2）的解）的解x稱為稱為可行解可行解feasible solution，同時(shí)滿足（，同時(shí)滿足（1）（）（2）的解）的解x稱為稱為最優(yōu)解最優(yōu)解Optimal solution，整個(gè)可行域上的最優(yōu)解，整個(gè)可行域上的最優(yōu)解稱為稱為全局最優(yōu)解全局最優(yōu)解global optimal solution，可行域中，可行域中某個(gè)領(lǐng)域上的最優(yōu)解稱為某個(gè)領(lǐng)域上的最優(yōu)解稱為局部最優(yōu)解局部最優(yōu)解local optimal solution

6、。最優(yōu)解所對(duì)應(yīng)的目標(biāo)函數(shù)值稱為。最優(yōu)解所對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值最優(yōu)值optimum。 2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃（一）（一）按有無約束條件按有無約束條件（2）可分為：）可分為：1.無約束優(yōu)化無約束優(yōu)化unconstrained optimization。2.約束優(yōu)化約束優(yōu)化constrained optimization。大部分實(shí)際問題都是約束優(yōu)化問題。大部分實(shí)際問題都是約束優(yōu)化問題。 優(yōu)化模型的分類優(yōu)化模型的分類2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃（二）（二）按決策變量取值是否連續(xù)按決策變量取值是否連續(xù)可分為：可分為：1.數(shù)學(xué)規(guī)劃或連續(xù)優(yōu)化。數(shù)學(xué)規(guī)劃或連續(xù)優(yōu)化。可繼續(xù)劃分為可繼

7、續(xù)劃分為線性規(guī)劃線性規(guī)劃(LP)Linear programming和和非線性規(guī)劃非線性規(guī)劃(NLP) Nonlinear programming。在。在非線性規(guī)劃中有一種規(guī)劃叫做非線性規(guī)劃中有一種規(guī)劃叫做二次規(guī)劃二次規(guī)劃(QP)Quadratic programming，目標(biāo)為二次函數(shù)，目標(biāo)為二次函數(shù)，約束為線性函數(shù)。約束為線性函數(shù)。2.離散優(yōu)化或組合優(yōu)化。離散優(yōu)化或組合優(yōu)化。包含：包含：整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)Integer programming，整數(shù)，整數(shù)規(guī)劃中又包含很重要的一類規(guī)劃：規(guī)劃中又包含很重要的一類規(guī)劃：0-1（整數(shù)）規(guī)（整數(shù)）規(guī)劃劃Zero-one programming，

8、這類規(guī)劃問題的決策，這類規(guī)劃問題的決策變量只取變量只取0或者或者1。2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃（三）（三）按目標(biāo)的多少按目標(biāo)的多少可分為：可分為：1.單目標(biāo)規(guī)劃。單目標(biāo)規(guī)劃。2.多目標(biāo)規(guī)劃。多目標(biāo)規(guī)劃。（四）（四）按模型中參數(shù)和變量是否具有不確定性按模型中參數(shù)和變量是否具有不確定性可分為：可分為：1.確定性規(guī)劃。確定性規(guī)劃。2.不確定性規(guī)劃。不確定性規(guī)劃。（五）（五）按問題求解的特性按問題求解的特性可分為：可分為：1.目標(biāo)規(guī)劃。目標(biāo)規(guī)劃。2.動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃。3.多層規(guī)劃。多層規(guī)劃。4.網(wǎng)絡(luò)優(yōu)化。網(wǎng)絡(luò)優(yōu)化。5.等等。等等。2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃 LINGO軟件和軟件和

9、MATLAB軟件。軟件。 對(duì)于對(duì)于LINGO軟件，線性優(yōu)化求解程序通常使用軟件，線性優(yōu)化求解程序通常使用單純形法單純形法simplex method，單純形法雖然在實(shí)際應(yīng)用，單純形法雖然在實(shí)際應(yīng)用中是最好最有效的方法，但對(duì)某些問題具有指數(shù)階的中是最好最有效的方法，但對(duì)某些問題具有指數(shù)階的復(fù)雜性，為了能解大規(guī)模問題，也提供了復(fù)雜性，為了能解大規(guī)模問題，也提供了內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法interior point method備選（備選（LINGO中一般稱為障礙中一般稱為障礙法，即法，即barrier），非線性優(yōu)化求解程序采用的是），非線性優(yōu)化求解程序采用的是順序順序線性規(guī)劃法線性規(guī)劃法，也可用，也可用順

10、序二次規(guī)劃法順序二次規(guī)劃法，廣義既約梯度，廣義既約梯度法，另外可以使用多初始點(diǎn)（法，另外可以使用多初始點(diǎn)（LINGO中稱中稱multistart）找多個(gè)局部最優(yōu)解增加找全局最優(yōu)解的可能，還具有找多個(gè)局部最優(yōu)解增加找全局最優(yōu)解的可能，還具有全局求解程序全局求解程序分解原問題成一系列的分解原問題成一系列的凸規(guī)劃凸規(guī)劃。求解優(yōu)化問題常用的軟件求解優(yōu)化問題常用的軟件2.1 什么是數(shù)學(xué)規(guī)劃什么是數(shù)學(xué)規(guī)劃線性規(guī)劃的一般形式：線性規(guī)劃的一般形式： njjjxczz1)max(min或njxmibxatsjijij, 1, 0 , 1,)( n1j.或或2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃 一般線性規(guī)劃問題都

11、可以通過引入非負(fù)的松弛一般線性規(guī)劃問題都可以通過引入非負(fù)的松弛變量變量slack variable與非負(fù)的剩余變量與非負(fù)的剩余變量surplus v-ariable的方法化為的方法化為標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式（約束全是等約束）。（約束全是等約束）。 線性規(guī)劃問題的可行域線性規(guī)劃問題的可行域feasible region是一個(gè)凸是一個(gè)凸集集convex set（任意兩點(diǎn)的連線上的點(diǎn)都在區(qū)域內(nèi)部，（任意兩點(diǎn)的連線上的點(diǎn)都在區(qū)域內(nèi)部，可以看作是沒有凹坑的凸多面體），所以最優(yōu)解可以看作是沒有凹坑的凸多面體），所以最優(yōu)解Optimal solution/point在凸多面體的某個(gè)頂點(diǎn)上達(dá)在凸多面體的某個(gè)頂點(diǎn)上達(dá)

12、到到 求解方法：?jiǎn)渭冃嗡惴ㄇ蠼夥椒ǎ簡(jiǎn)渭冃嗡惴╯implex method。 2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃1.比例性比例性：每個(gè)決策變量對(duì)目標(biāo)函數(shù)以及右端項(xiàng)：每個(gè)決策變量對(duì)目標(biāo)函數(shù)以及右端項(xiàng)的貢獻(xiàn)與該決策變量的取值成正比。的貢獻(xiàn)與該決策變量的取值成正比。2.可加性可加性：每個(gè)決策變量對(duì)目標(biāo)函數(shù)以及右端項(xiàng)：每個(gè)決策變量對(duì)目標(biāo)函數(shù)以及右端項(xiàng)的貢獻(xiàn)與其他決策變量的取值無關(guān)。的貢獻(xiàn)與其他決策變量的取值無關(guān)。3.連續(xù)性連續(xù)性：每個(gè)決策變量的取值都是連續(xù)的。：每個(gè)決策變量的取值都是連續(xù)的。 連續(xù)線性規(guī)劃問題的性質(zhì)連續(xù)線性規(guī)劃問題的性質(zhì)要解決的問題的目標(biāo)可以用數(shù)值指標(biāo)反映要解決的問題的目標(biāo)可以用數(shù)值

13、指標(biāo)反映對(duì)于要實(shí)現(xiàn)的目標(biāo)有多種方案可選擇對(duì)于要實(shí)現(xiàn)的目標(biāo)有多種方案可選擇有影響決策的若干約束條件有影響決策的若干約束條件2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃。問問如如何何調(diào)調(diào)運(yùn)運(yùn)使使運(yùn)運(yùn)費(fèi)費(fèi)最最低低如如下下公公里里單單位位距距離離兩兩個(gè)個(gè)糧糧庫(kù)庫(kù)到到三三個(gè)個(gè)糧糧站站的的噸噸大大米米分分別別為為三三個(gè)個(gè)糧糧站站至至少少需需要要噸噸噸噸為為兩兩個(gè)個(gè)糧糧庫(kù)庫(kù)現(xiàn)現(xiàn)存存大大米米分分別別調(diào)調(diào)運(yùn)運(yùn)大大米米向向三三個(gè)個(gè)糧糧站站有有兩兩個(gè)個(gè)糧糧庫(kù)庫(kù),):(,5 , 4 , 2,8 ,4, 32121BBBAA例例1 運(yùn)輸問題運(yùn)輸問題2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃解解 設(shè)設(shè)A1,A2調(diào)運(yùn)到三個(gè)糧站的大米分別

14、為調(diào)運(yùn)到三個(gè)糧站的大米分別為x1，x2， x3， x4， x5， x6噸。噸。題設(shè)量可總到下表：題設(shè)量可總到下表：2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃結(jié)合存量限制和需量限制得數(shù)學(xué)模型結(jié)合存量限制和需量限制得數(shù)學(xué)模型：65432124123082412minxxxxxxf 0,54284.654321635241654321xxxxxxxxxxxxxxxxxxts2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃程序編寫程序編寫1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6 ;x1+x2+x34 ;x4+x5+x62 ;x2+x54 ;x3+x65 ;end提示：課

15、件中的程提示：課件中的程序請(qǐng)先粘貼在記事序請(qǐng)先粘貼在記事本中再本中再轉(zhuǎn)帖于轉(zhuǎn)帖于lingo軟件軟件中中2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃運(yùn)行結(jié)果運(yùn)行結(jié)果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 0 Variable Value Reduced Cost X1 2.000000 0.000000 X2 0.000000 28.00000 X3 2.000000 0.000000 X4 0.000000 2.000000 X5 4.000000 0.000000 X6 3.

16、000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.000002.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃84庫(kù)庫(kù)存存量量x23x22x21A2542需要量需要量x13x12x11A1B3B2B1糧庫(kù)糧庫(kù)糧站糧站距離及運(yùn)量距離及運(yùn)量12122430824變量更換為：變量更換為：2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃2322211

17、3121124123082412xxxxxxf min 054284232221131211231322122111232221131211xxxxxxxxxxxxxxxxxxts,.模型模型:2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃程序編寫程序編寫MODEL:TITLE 調(diào)運(yùn)大米的運(yùn)輸問題程序調(diào)運(yùn)大米的運(yùn)輸問題程序3;!定義集合段定義集合段;SETS:LIANGKU/1.2/:A;!定義糧庫(kù)的集合定義糧庫(kù)的集合;LIANGZHAN/1.3/:B;!定義糧站的集合定義糧站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定義運(yùn)量和距離定義運(yùn)量和距離;ENDSETSDATA:!

18、糧庫(kù)到糧站的距離糧庫(kù)到糧站的距離;C= 12 24 8 30 12 24;2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃!糧庫(kù)的限量糧庫(kù)的限量;A=4 8 ;!糧站的限量糧站的限量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!糧庫(kù)上限的約束糧庫(kù)上限的約束;FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃程序的調(diào)試程序的調(diào)試1.直接點(diǎn)擊運(yùn)行，如果出錯(cuò)會(huì)彈出錯(cuò)誤提示，根直接點(diǎn)擊運(yùn)行，如果出錯(cuò)會(huì)彈出錯(cuò)誤提示，根據(jù)提示做相應(yīng)的修改；據(jù)提示做相應(yīng)的修改；2.可以用可以用“！”把約束變成說明語

19、句，而把這條把約束變成說明語句，而把這條語句屏蔽掉，縮小尋找出錯(cuò)的范圍；語句屏蔽掉，縮小尋找出錯(cuò)的范圍；3.可以邊寫程序邊運(yùn)行，保證每行書寫都是正確可以邊寫程序邊運(yùn)行，保證每行書寫都是正確的程序；的程序；2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃例例2 階段生產(chǎn)問題階段生產(chǎn)問題 某公司生產(chǎn)某產(chǎn)品某公司生產(chǎn)某產(chǎn)品,最大生產(chǎn)能力為最大生產(chǎn)能力為10000單位單位,每每單位存儲(chǔ)費(fèi)單位存儲(chǔ)費(fèi)2元元,預(yù)定的銷售量與單位成本如下預(yù)定的銷售量與單位成本如下:月份單位成本(元) 銷售量1234 70 6000 72 7000 80 12000 76 6000求一生產(chǎn)計(jì)劃求一生產(chǎn)計(jì)劃,使使 1)滿足需求滿足需求; 2

20、)不超過生產(chǎn)能力不超過生產(chǎn)能力;3)成本成本(生產(chǎn)成本與存儲(chǔ)費(fèi)之和生產(chǎn)成本與存儲(chǔ)費(fèi)之和)最低最低.2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃 1 je 解解 假定假定1月初無庫(kù)存月初無庫(kù)存,4月底買完月底買完,當(dāng)月生產(chǎn)的不庫(kù)當(dāng)月生產(chǎn)的不庫(kù)存存,庫(kù)存量無限制庫(kù)存量無限制.為為單單位位成成本本，為為存存儲(chǔ)儲(chǔ)費(fèi)費(fèi)，為為銷銷售售量量，月月產(chǎn)產(chǎn)量量，為為第第：設(shè)設(shè)模模型型iiiicedix jiijiidx11 31j 41jjjxc fmin 4 ,23, 11000003 , 2 , 1.414111ixdxjdxtsiiiiijijiii2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃model:title 生產(chǎn)計(jì)

21、劃程序生產(chǎn)計(jì)劃程序1;Sets:yuefen/1.4/:c,x,e,d;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000;e=2 2 2 2 ;a=10000;enddatamin=sum(yuefen:c*x)+ sum(yuefen(j)|j#lt#4: sum(yuefen(i)|i#le#j:x-d)*e(j+1);for(yuefen(j)|j#lt#4: sum(yuefen(i)|i#le#j:x) sum(yuefen(i)|i#le#j:d);sum(yuefen:x)= sum(yuefen:d);for(yuefen:xa)

22、;end 2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃.iiiiisicedix月月初初的的庫(kù)庫(kù)存存量量為為為為單單位位成成本本，設(shè)設(shè)第第為為存存儲(chǔ)儲(chǔ)費(fèi)費(fèi)，為為銷銷售售量量，月月產(chǎn)產(chǎn)量量，為為第第：設(shè)設(shè)模模型型 4141miniiiiiisexcf.ts 1is, iiidxs 4 , 3 , 2 , 1 i0051 ss432104321100000， isixii2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃Model:Title 生產(chǎn)計(jì)劃程序生產(chǎn)計(jì)劃程序2;Sets:yuefen/1.4/:c,x,e,d,s;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000

23、;e=2 2 2 2 ;a=10000;enddatamin=sum(yuefen:c*x+e*s);for(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i);s(4)+x(4)-d(4)=0;s(1)=0;for(yuefen:xa);End2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃.,:月月的的銷銷售售量量示示的的第第表表存存儲(chǔ)儲(chǔ)費(fèi)費(fèi)之之和和月月賣賣出出時(shí)時(shí)的的生生產(chǎn)產(chǎn)成成本本與與生生產(chǎn)產(chǎn)的的產(chǎn)產(chǎn)品品在在第第月月表表示示第第月月賣賣出出的的數(shù)數(shù)量量月月生生產(chǎn)產(chǎn)的的產(chǎn)產(chǎn)品品在在第第表表示示第第設(shè)設(shè)化化為為運(yùn)運(yùn)輸輸問問題題模模型型jdjicjixjijij 月份單位成本(

24、元) 銷售量1234 70 6000 72 7000 80 12000 76 60002.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃76827676-80-7472-747270生產(chǎn)月10000100001000010000產(chǎn)量產(chǎn)量600041200070006000銷量銷量4321321需求月費(fèi)用cij2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃且且為為整整數(shù)數(shù)010000.min41,411 ijijijjijijjjiijijxxdxtsxcf建立模型如下：建立模型如下：2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃model:title 生產(chǎn)計(jì)劃程序生產(chǎn)計(jì)劃程序3;sets:yuefen/1.4/:a,d,xx;

25、!定義上三角矩陣定義上三角矩陣;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70 72 74 76 71 73 75 80 82 76;d=6000 7000 12000 6000;a=10000 10000 10000 10000;enddatamin=sum(link:c*x);for(yuefen(i):sum(yuefen(j)|j#ge#i:x(i,j)d(j););!得到每個(gè)月的生產(chǎn)量得到每個(gè)月的生產(chǎn)量;for(yuefen(i):xx=sum(yuefen(j)|j#ge#i:x(i,j);End2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)

26、劃Model Title: :生產(chǎn)計(jì)劃程序生產(chǎn)計(jì)劃程序1 Variable Value Reduced Cost A 10000.00 0.000000 C( 1) 70.00000 0.000000 C( 2) 71.00000 0.000000 C( 3) 80.00000 0.000000 C( 4) 76.00000 0.000000 X( 1) 10000.00 0.000000 X( 2) 10000.00 0.000000 X( 3) 5000.000 0.000000 X( 4) 6000.000 0.000000 E( 1) 2.000000 0.000000 E( 2) 2

27、.000000 0.000000 E( 3) 2.000000 0.000000 E( 4) 2.000000 0.000000 D( 1) 6000.000 0.000000 D( 2) 7000.000 0.000000 D( 3) 12000.00 0.000000 D( 4) 6000.000 0.000000 2.2 連續(xù)性線性規(guī)劃連續(xù)性線性規(guī)劃 設(shè)有兩個(gè)工廠設(shè)有兩個(gè)工廠A、B，產(chǎn)量都是，產(chǎn)量都是10萬個(gè)，工廠萬個(gè)，工廠有三個(gè)倉(cāng)庫(kù)有三個(gè)倉(cāng)庫(kù)x，y，z，產(chǎn)品都先送到倉(cāng)庫(kù)?，F(xiàn)有四，產(chǎn)品都先送到倉(cāng)庫(kù)?，F(xiàn)有四個(gè)顧客分別為甲，乙，丙，丁，需求量分別為個(gè)顧客分別為甲，乙，丙，丁，需求量分別為3，

28、5，4，5萬個(gè)。工廠到倉(cāng)庫(kù)、倉(cāng)庫(kù)到顧客的運(yùn)費(fèi)單價(jià)萬個(gè)。工廠到倉(cāng)庫(kù)、倉(cāng)庫(kù)到顧客的運(yùn)費(fèi)單價(jià)（元（元/個(gè)）見下表所示。試求總運(yùn)費(fèi)最少的運(yùn)輸方個(gè)）見下表所示。試求總運(yùn)費(fèi)最少的運(yùn)輸方案以及總運(yùn)費(fèi)。案以及總運(yùn)費(fèi)。 AB甲乙丙丁x43571020y2196715z5220674課后訓(xùn)練課后訓(xùn)練model:title 轉(zhuǎn)運(yùn)問題轉(zhuǎn)運(yùn)問題;sets: Plant /A, B/: produce; Warhouse /x, y, z/; Customer /1.4/: require; LinkI ( Plant, Warhouse): cI, xI; LinkII ( Warhouse, Customer): c

29、II, xII;endsetsdata: produce = 10, 10; require = 3, 5, 4, 5; cI = 4, 2, 5, 3, 1, 2; cII = 5, 7, 10, 20, 9, 6, 7, 15, 20, 6, 7, 4;enddata課后練習(xí)課后練習(xí)OBJ min = sum( LinkI: cI * xI) + sum( LinkII: cII * xII);! The supply constraints;for( Plant(i): SUP sum( Warhouse(j): xI(i,j) = produce(i);! 運(yùn)進(jìn)倉(cāng)庫(kù)的量等于運(yùn)出的量運(yùn)進(jìn)

30、倉(cāng)庫(kù)的量等于運(yùn)出的量;for( Warhouse(j): MID sum( Plant(i): xI(i,j)=sum( Customer(k): xII(j,k);! The demand constraints;for( Customer(k): DEM sum( Warhouse(j): xII(j,k) = require(k);課后練習(xí)課后練習(xí)連續(xù)投資連續(xù)投資10萬元萬元A：從第：從第1年年 到第到第4年每年初要投資，次年末回收年每年初要投資，次年末回收本利本利1.15B：第第3年初投資，到第年初投資，到第5年末回收年末回收1.25，最大投資，最大投資4萬元萬元C：第第2年初投資，到

31、第年初投資，到第5年末回收年末回收1.40，最大投資，最大投資3萬元萬元D：每年初投資，每年末回收每年初投資，每年末回收1.11。求：求：5年末總資本最大。年末總資本最大。練習(xí)練習(xí)2 2 連續(xù)投資連續(xù)投資課后練習(xí)課后練習(xí)第1年第2年第3年第4年第5年Ax1Ax1Ax1Ax1ABx3BCx2CDx1Dx1Dx1Dx1Dx1D練習(xí)練習(xí)2解答解答變量設(shè)置變量設(shè)置課后練習(xí)課后練習(xí)模型建立模型建立 423511222123331234423534max1.151.401.251.11101.1131.151.1141.151.111.151.11,0,15ACBDADACDDCABDADBADADDAD

32、iAiBiCiDfxxxxxxxxxxxxxxxxxxxxxxxxxxxxi 課后練習(xí)課后練習(xí)程序編寫程序編寫model:title 投資問題投資問題;max=1.15*x4a+1.40*x2c+1.25*x3b+1.06*x5d;x1a+x1d=100000;x2a+x2c+x2d=1.06*x1d;x3a+x3b+x3d=1.15*x1a+1.06*x2d;x4a+x4d=1.15*x2a+1.06*x3d;x5d=1.15*x3a+1.06*x4d;x3b=40000;x2c=30000;課后練習(xí)課后練習(xí)運(yùn)行結(jié)果運(yùn)行結(jié)果Global optimal solution found. Obj

33、ective value: 143750.0 Total solver iterations: 2 Model Title: 投資問題投資問題 Variable Value Reduced Cost X4A 45000.00 0.000000 X2C 30000.00 0.000000 X3B 40000.00 0.000000 X5D 0.000000 0.000000 X1A 71698.11 0.000000 X1D 28301.89 0.000000 X2A 0.000000 0.000000 X2D 0.000000 0.3036000E-01 X3A 0.000000 0.0000

34、00 X3D 42452.83 0.000000 X4D 0.000000 0.2640000E-01課后練習(xí)課后練習(xí) 例例3 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題某工廠計(jì)劃安排生產(chǎn)某工廠計(jì)劃安排生產(chǎn)，兩種產(chǎn)品，已知每?jī)煞N產(chǎn)品，已知每種單位產(chǎn)品的利潤(rùn)，生產(chǎn)單位產(chǎn)品所需設(shè)備臺(tái)時(shí)及種單位產(chǎn)品的利潤(rùn)，生產(chǎn)單位產(chǎn)品所需設(shè)備臺(tái)時(shí)及A,B兩種原材料的兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺(tái)時(shí)的定額如表所示，問：消耗，現(xiàn)有原材料和設(shè)備臺(tái)時(shí)的定額如表所示，問：）怎么安排生產(chǎn)使得工廠獲利最大？）怎么安排生產(chǎn)使得工廠獲利最大？）產(chǎn)品）產(chǎn)品的單位利潤(rùn)降低到的單位利潤(rùn)降低到1.8萬元，要不要改變生產(chǎn)計(jì)劃，如果萬元，要不要改變生產(chǎn)計(jì)劃

35、，如果降低到降低到1萬元呢？萬元呢？）產(chǎn)品）產(chǎn)品的單位利潤(rùn)增大到的單位利潤(rùn)增大到5萬元，要不要改變生產(chǎn)計(jì)劃？萬元，要不要改變生產(chǎn)計(jì)劃？）如果產(chǎn)品）如果產(chǎn)品，的單位利潤(rùn)同時(shí)降低了的單位利潤(rùn)同時(shí)降低了1萬元，要不要改變生產(chǎn)萬元，要不要改變生產(chǎn)計(jì)劃？計(jì)劃？ 產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品最大資源量最大資源量設(shè)備設(shè)備128臺(tái)時(shí)臺(tái)時(shí)原材料原材料A4016kg原材料原材料B0412kg單位產(chǎn)品利潤(rùn)單位產(chǎn)品利潤(rùn)232.3 敏感性分析敏感性分析2.3 敏感性分析敏感性分析程序編寫程序編寫model:title 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題;maxfmax=2*x1+3*x2;TIMEx1+2*x28;A4*x116;B4*x2

36、12;END2.3 敏感性分析敏感性分析運(yùn)行結(jié)果運(yùn)行結(jié)果 Model Title: 生產(chǎn)計(jì)劃問題 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 對(duì)問題對(duì)問題1，安排是生產(chǎn)產(chǎn)品，安排是生產(chǎn)產(chǎn)品4單位，產(chǎn)品單位，產(chǎn)品2單位，最大盈單位，最大盈利為利為14萬元萬元 。2.3

37、 敏感性分析敏感性分析目標(biāo)函數(shù)的系數(shù)變化的敏感性分析目標(biāo)函數(shù)的系數(shù)變化的敏感性分析如果目標(biāo)函數(shù)的系數(shù)發(fā)生變化，將會(huì)影響目標(biāo)函數(shù) f 斜率的變化，但是只要f 的斜率小于等于-1/2（也就是直線l夾在l1與l2之間時(shí)），最優(yōu)解都在(4,2)上取到，最優(yōu)解不變，從而生產(chǎn)計(jì)劃不會(huì)變. 2.3 敏感性分析敏感性分析要使用敏感性分析要使用敏感性分析必須要在這里選擇必須要在這里選擇Prices & Ranges然后然后保存保存退出退出路徑：路徑：LINGOOptionsGeneral Solver(通用求解程序通用求解程序)選項(xiàng)卡選項(xiàng)卡2.3 敏感性分析敏感性分析要調(diào)出敏感性分析的結(jié)果，要調(diào)出敏感性分析的結(jié)

38、果，必須必須先求解先求解后再后再在程序窗在程序窗口下口下點(diǎn)擊點(diǎn)擊LINGORange， 2.3 敏感性分析敏感性分析Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable A

39、llowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 當(dāng)前變量系數(shù)允許增加量允許減少量對(duì)問題對(duì)問題2，產(chǎn)品，產(chǎn)品的單位利潤(rùn)降低到的單位利潤(rùn)降低到1.8萬元，在（萬元，在（1.5，）之間，所以不）之間，所以不改變生產(chǎn)計(jì)劃。如果降低到改變生產(chǎn)計(jì)劃。如果降低到1萬元，不在（萬元，不在（1.5，）內(nèi)，要改變生產(chǎn)計(jì)劃。）內(nèi)，要改變生產(chǎn)計(jì)劃。在程序中將目標(biāo)函數(shù)的系數(shù)在程序中將目標(biāo)函數(shù)的系數(shù)“2”改為改為“1”，可得新的計(jì)

40、劃為，可得新的計(jì)劃為安排是生產(chǎn)產(chǎn)品安排是生產(chǎn)產(chǎn)品2單位，產(chǎn)品單位，產(chǎn)品3單位，最大盈利為單位，最大盈利為11萬元萬元.對(duì)問題對(duì)問題3，要改變生產(chǎn)計(jì)劃，更改程序得新計(jì)劃為生產(chǎn)產(chǎn)品，要改變生產(chǎn)計(jì)劃，更改程序得新計(jì)劃為生產(chǎn)產(chǎn)品2單位，產(chǎn)品單位，產(chǎn)品3單位，最大盈利為單位，最大盈利為19萬元萬元.對(duì)問題對(duì)問題4，因?yàn)閮蓚€(gè)系數(shù)同時(shí)改變了，所以只有更改程序的數(shù)據(jù)，重新運(yùn)，因?yàn)閮蓚€(gè)系數(shù)同時(shí)改變了，所以只有更改程序的數(shù)據(jù)，重新運(yùn)行得：不改變生產(chǎn)計(jì)劃，但是最大利潤(rùn)降低到行得：不改變生產(chǎn)計(jì)劃，但是最大利潤(rùn)降低到8萬元萬元. 2.3 敏感性分析敏感性分析2.3 敏感性分析敏感性分析12121112max232841

41、6. .412,0fxxxxxstxx x0,34224. .12168min3213221321yyyyyyyt syyyg把y1,y2,y3作為三種原料的定價(jià)，定價(jià)的目標(biāo)是在比生產(chǎn)產(chǎn)品獲得更多利潤(rùn)的前提下的最小利潤(rùn). 在最優(yōu)情況下，在最優(yōu)情況下，y的值就是資的值就是資源的源的影子價(jià)格，影子價(jià)格，影子價(jià)格有意影子價(jià)格有意義是有范圍的義是有范圍的。影子價(jià)格經(jīng)濟(jì)含義是：在資源得到最優(yōu)配影子價(jià)格經(jīng)濟(jì)含義是：在資源得到最優(yōu)配置，使總效益最大時(shí)，該資源投入量每增置，使總效益最大時(shí)，該資源投入量每增加一個(gè)單位所帶來總收益的增加量加一個(gè)單位所帶來總收益的增加量 2.3 敏感性分析敏感性分析Ranges i

42、n which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.0

43、0000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 運(yùn)行結(jié)果運(yùn)行結(jié)果 Model Title: 生產(chǎn)計(jì)劃問題 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 2.3 敏感性分析敏感性分析1桶牛奶 3公斤A1 12

44、小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：例例4 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃2.3 敏感性分析敏感性分析x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶

45、生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)2.3 敏感性分析敏感性分析Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000

46、0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元。元。 2.3 敏感性分析敏感性分析 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.00000

47、0 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？ 35 50; x2 + 2*x4 + x5 + 3*x6 20; x3 + x5 + 2*x715;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);end程序編寫程序編寫2.4 整數(shù)規(guī)劃整數(shù)規(guī)劃按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余

48、料根，余料27米米 最優(yōu)解：最優(yōu)解：x2=12, x5=15, 其余為其余為0；最優(yōu)值：最優(yōu)值：27最優(yōu)解：最優(yōu)解：x2=15, x5=5, x7=5, 其余為其余為0；最優(yōu)值：最優(yōu)值：25。按模式按模式2切割切割15根，按模式根，按模式5切割切割5根，按模式根，按模式7切割切割5根，共根，共25根，余料根，余料35米米 當(dāng)余料沒有用處時(shí)，當(dāng)余料沒有用處時(shí)，通常以總根數(shù)最少為目標(biāo)通常以總根數(shù)最少為目標(biāo) 2.4 整數(shù)規(guī)劃整數(shù)規(guī)劃練習(xí)練習(xí)3某服務(wù)部門一周中每天需要不同數(shù)目的雇員，某服務(wù)部門一周中每天需要不同數(shù)目的雇員，周一到周四每天至少需要周一到周四每天至少需要50人，周五至少需要人，周五至少需要

49、80人，人，周六和周日至少需要周六和周日至少需要90人，現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工人，現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作作5天，試確定聘用方案。天，試確定聘用方案。解解 周一至周日分別聘用X(i)（i1,2，7）個(gè)人上班，最少所需人數(shù)為R(i)，總?cè)藬?shù)為Z. 5 , 2 , 121. .min71iiRiXiXZtsXZii課后練習(xí)課后練習(xí)MODEL:SETS:DAYS/MON.SUN/:R,X;ENDSETSDATA:R=50 50 50 50 80 90 90;ENDDATAMIN=Z;N=SIZE(DAYS);!集合的長(zhǎng)度集合的長(zhǎng)度;Z=SUM(DAYS:X);FOR(DAYS(I):Z-X(WRAP(I

50、+1,N)-X(WRAP(I+2,N)R(I);!WRAP()相當(dāng)于求余數(shù)，返回相當(dāng)于求余數(shù)，返回1到到N之間的數(shù)之間的數(shù);FOR(DAYS:GIN(X);END課后練習(xí)課后練習(xí)?,1,2:),(),(),(),(),(),(),(:7, 7654321的的年年利利潤(rùn)潤(rùn)最最大大問問如如何何選選擇擇地地址址使使公公司司元元總總投投資資不不超超過過元元每每年年可可獲獲利利元元投投資資若若選選個(gè)個(gè)漢漢口口漢漢陽陽至至少少個(gè)個(gè)武武昌昌至至多多并并規(guī)規(guī)定定漢漢商商二二十十一一世世紀(jì)紀(jì)行行街街步步武武廣廣司司門門口口亞亞貿(mào)貿(mào)中中商商個(gè)個(gè)地地址址有有擬擬議議中中漢漢陽陽建建立立專專賣賣店店漢漢口口某某公公司

51、司擬擬定定在在在在武武昌昌bcbAAAAAAAAiii例例6 選址問題選址問題2.5 0-1規(guī)劃規(guī)劃 否否則則選選擇擇解解, 0, 1:iiAx 71maxiiixcf 7,.,2 , 110112.765432171ixxxxxxxxbxbtsiiii或或2.5 0-1規(guī)劃規(guī)劃 例例7 面試順序問題面試順序問題有有4名同學(xué)到一家公司參加三個(gè)名同學(xué)到一家公司參加三個(gè)階段的面試，公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，階段的面試，公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到主管部門處復(fù)試，最后到經(jīng)理處參加免試，并且不允然后到主管部門處復(fù)試，最后到經(jīng)理處參加免試，并且不允許插隊(duì)，由于許插隊(duì)，由于4名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段的面試時(shí)間也不同，如表所示，這的面試時(shí)間也不同，如表所示，這4名同學(xué)約定他們?nèi)棵嬖嚸瑢W(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司，假定現(xiàn)在時(shí)間是早上完以后一起離開公司，假定現(xiàn)在時(shí)間是早上8：00，請(qǐng)問他們，請(qǐng)問他們最早何時(shí)能離開公司？最早何時(shí)能離開公司？ 秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201610同學(xué)丁810152.5