1、線性規劃與LINGO編程剖析線性規劃與LINGO編程(1)2.1 什么是數學規劃什么是數學規劃2.2 連續性線性規劃連續性線性規劃2.3 敏感性分析敏感性分析2.4 整數線性規劃整數線性規劃2.5 0-1規劃規劃內容說明內容說明 數學規劃俗稱最優化,首先是一種理念,其次才是一種方法,它所追求的是一種“至善”之道,一種追求卓越的精神.2.1 什么是數學規劃 小明同學，燒一壺水要8分鐘，灌開水要1分鐘，取牛奶和報紙要5分鐘，整理書包要6分鐘，為了盡快做完這些事，怎樣安排才能使時間最少？最少需要幾分鐘？ 十個人各提一只水桶，同時到水龍頭前打水。設水龍頭注滿第一個人的桶需要1分鐘，注滿第二個人的桶需要

2、2分鐘，依此類推，注滿第幾個人的桶就需要幾分鐘，如果只有一只水龍頭，適當安排這10個人的順序，就可以使每個人所費的時間總和盡可能小，問這個總費時至少是幾分鐘？ 2.1 什么是數學規劃 數學規劃(最優化)作為一門學科孕育于20世紀的30年代,誕生于第二次世界大戰彌漫的硝煙中。 數學規劃指在一系列客觀或主觀限制條件下，尋求合理分配有限資源使所關注的某個或多個指標達到最大（或最?。┑臄祵W理論和方法，是運籌學里一個十分重要的分支。 2.1 什么是數學規劃最優化問題的數學模型的一般形式為： （1）（2）三個要素：決策變量decision bariable，目標函數objective function，約

3、束條件constraints。 2.1 什么是數學規劃 約束條件（2）所確定的x的范圍稱為可行域feasible region，滿足（2）的解x稱為可行解feasible solution，同時滿足（1）（2）的解x稱為最優解Optimal solution，整個可行域上的最優解稱為全局最優解global optimal solution，可行域中某個領域上的最優解稱為局部最優解local optimal solution。最優解所對應的目標函數值稱為最優值optimum。 2.1 什么是數學規劃（一）按有無約束條件（2）可分為：1.無約束優化unconstrained optimizatio

4、n。2.約束優化constrained optimization。大部分實際問題都是約束優化問題。 優化模型的分類2.1 什么是數學規劃（二）按決策變量取值是否連續可分為：1.數學規劃或連續優化?？衫^續劃分為線性規劃(LP)Linear programming和非線性規劃(NLP) Nonlinear programming。在非線性規劃中有一種規劃叫做二次規劃(QP)Quadratic programming，目標為二次函數，約束為線性函數。2.離散優化或組合優化。包含：整數規劃(IP)Integer programming，整數規劃中又包含很重要的一類規劃：0-1（整數）規劃Zero-on

5、e programming，這類規劃問題的決策變量只取0或者1。2.1 什么是數學規劃（三）按目標的多少可分為：1.單目標規劃。2.多目標規劃。（四）按模型中參數和變量是否具有不確定性可分為：1.確定性規劃。2.不確定性規劃。（五）按問題求解的特性可分為：1.目標規劃。2.動態規劃。3.多層規劃。4.網絡優化。5.等等。2.1 什么是數學規劃 LINGO軟件和MATLAB軟件。 對于LINGO軟件，線性優化求解程序通常使用單純形法simplex method，單純形法雖然在實際應用中是最好最有效的方法，但對某些問題具有指數階的復雜性，為了能解大規模問題，也提供了內點算法interior poi

6、nt method備選（LINGO中一般稱為障礙法，即barrier），非線性優化求解程序采用的是順序線性規劃法，也可用順序二次規劃法，廣義既約梯度法，另外可以使用多初始點（LINGO中稱multistart）找多個局部最優解增加找全局最優解的可能，還具有全局求解程序分解原問題成一系列的凸規劃。求解優化問題常用的軟件2.1 什么是數學規劃線性規劃的一般形式： 2.2 連續性線性規劃 一般線性規劃問題都可以通過引入非負的松弛變量slack variable與非負的剩余變量surplus v-ariable的方法化為標準形式（約束全是等約束）。 線性規劃問題的可行域feasible region是

7、一個凸集convex set（任意兩點的連線上的點都在區域內部，可以看作是沒有凹坑的凸多面體），所以最優解Optimal solution/point在凸多面體的某個頂點上達到 求解方法：單純形算法simplex method。 2.2 連續性線性規劃1.比例性：每個決策變量對目標函數以及右端項的貢獻與該決策變量的取值成正比。2.可加性：每個決策變量對目標函數以及右端項的貢獻與其他決策變量的取值無關。3.連續性：每個決策變量的取值都是連續的。 連續線性規劃問題的性質 要解決的問題的目標可以用數值指標反映 對于要實現的目標有多種方案可選擇 有影響決策的若干約束條件2.2 連續性線性規劃例1 運輸

8、問題2.2 連續性線性規劃解 設A1,A2調運到三個糧站的大米分別為x1，x2， x3， x4， x5， x6噸。題設量可總到下表：2.2 連續性線性規劃結合存量限制和需量限制得數學模型：2.2 連續性線性規劃程序編寫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提示：課件中的程序請先粘貼在記事本中再轉帖于lingo軟件中2.2 連續性線性規劃運行結果 Global optimal solution found. Total solver iterations: 0

9、 Variable Value Reduced Cost Row Slack or Surplus Dual Price2.2 連續性線性規劃84庫存量x23x22x21A2542需要量x13x12x11A1B3B2B1糧庫糧站距離及運量12122430824變量更換為：2.2 連續性線性規劃模型:2.2 連續性線性規劃程序編寫MODEL:TITLE 調運大米的運輸問題程序3;!定義集合段;SETS:LIANGKU/1.2/:A;!定義糧庫的集合;LIANGZHAN/1.3/:B;!定義糧站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定義運量和距離;ENDSETSD

10、ATA:!糧庫到糧站的距離;C= 12 24 8 30 12 24;2.2 連續性線性規劃!糧庫的限量;A=4 8 ;!糧站的限量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!糧庫上限的約束;FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 2.2 連續性線性規劃程序的調試1.直接點擊運行，如果出錯會彈出錯誤提示，根據提示做相應的修改；2.可以用“！”把約束變成說明語句，而把這條語句屏蔽掉，縮小尋找出錯的范圍；3.可以邊寫程序邊運行，保證每行書寫都是正確的程序；2.2 連續性線性規劃例2 階段生產問題 某公司

11、生產某產品,最大生產能力為10000單位,每單位存儲費2元,預定的銷售量與單位成本如下:月份單位成本(元) 銷售量1234 70 6000 72 7000 80 12000 76 6000求一生產計劃,使 1)滿足需求; 2)不超過生產能力;3)成本(生產成本與存儲費之和)最低.2.2 連續性線性規劃 解 假定1月初無庫存,4月底買完,當月生產的不庫存,庫存量無限制.2.2 連續性線性規劃model:title 生產計劃程序1;Sets:yuefen/1.4/:c,x,e,d;endsetsdata:c=70 71 80 76;d=6000 7000 1202X 6000;e=2 2 2 2

12、;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);end 2.2 連續性線性規劃2.2 連續性線性規劃Model:Title 生產計劃程序2;Sets:yuefen/1.4/:c,x,e,d,s;endsetsdata:c=70 71 8

13、0 76;d=6000 7000 1202X 6000;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 連續性線性規劃月份單位成本(元) 銷售量1234 70 6000 72 7000 80 12000 76 60002.2 連續性線性規劃76827676-80-7472-747270生產月10000100001000010000產量60004120007000600

14、0銷量4321321需求月費用cij2.2 連續性線性規劃建立模型如下：2.2 連續性線性規劃model:title 生產計劃程序3;sets:yuefen/1.4/:a,d,xx;!定義上三角矩陣;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70 72 74 76 71 73 75 80 82 76;d=6000 7000 1202X 6000;a=10000 10000 10000 10000;enddatamin=sum(link:c*x);for(yuefen(i):sum(yuefen(j)|j#ge#i:x(i,j)

15、d(j););!得到每個月的生產量;for(yuefen(i):xx=sum(yuefen(j)|j#ge#i:x(i,j);End2.2 連續性線性規劃Model Title: :生產計劃程序1 Variable Value Reduced Cost 2.2 連續性線性規劃 設有兩個工廠A、B，產量都是10萬個，工廠有三個倉庫x，y，z，產品都先送到倉庫?，F有四個顧客分別為甲，乙，丙，丁，需求量分別為3，5，4，5萬個。工廠到倉庫、倉庫到顧客的運費單價（元/個）見下表所示。試求總運費最少的運輸方案以及總運費。 AB甲乙丙丁x43571020y2196715z5220674課后訓練model:

16、title 轉運問題;sets: Plant /A, B/: produce; Warhouse /x, y, z/; Customer /1.4/: require; LinkI ( Plant, Warhouse): cI, xI; LinkII ( Warhouse, Customer): cII, 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課后練習OBJ min =

17、sum( LinkI: cI * xI) + sum( LinkII: cII * xII);! The supply constraints;for( Plant(i): SUP sum( Warhouse(j): xI(i,j) = produce(i);! 運進倉庫的量等于運出的量;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

18、(k);課后練習連續投資10萬元A：從第1年 到第4年每年初要投資，次年末回收本利B：，最大投資4萬元C：，最大投資3萬元D：。求：5年末總資本最大。練習2 連續投資課后練習第1年第2年第3年第4年第5年Ax1Ax1Ax1Ax1ABx3BCx2CDx1Dx1Dx1Dx1Dx1D練習2解答變量設置課后練習模型建立 課后練習程序編寫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

19、*x2a+1.06*x3d;x5d=1.15*x3a+1.06*x4d;x3b=40000;x2c=30000;課后練習運行結果Global optimal solution found. Total solver iterations: 2 Model Title: 投資問題 Variable Value Reduced Cost課后練習 例3 生產計劃問題某工廠計劃安排生產，兩種產品，已知每種單位產品的利潤，生產單位產品所需設備臺時及A,B兩種原材料的消耗，現有原材料和設備臺時的定額如表所示，問：）怎么安排生產使得工廠獲利最大？）產品的單位利潤降低到萬元，要不要改變生產計劃，如果降低到1萬

20、元呢？）產品的單位利潤增大到5萬元，要不要改變生產計劃？）如果產品，的單位利潤同時降低了1萬元，要不要改變生產計劃？ 產品產品最大資源量設備128臺時原材料A4016kg原材料B0412kg單位產品利潤232.3 敏感性分析2.3 敏感性分析程序編寫model:title 生產計劃問題;maxfmax=2*x1+3*x2;TIMEx1+2*x28;A4*x116;B4*x212;END2.3 敏感性分析運行結果 Model Title: 生產計劃問題 Variable Value Reduced Cost Row Slack or Surplus Dual Price 對問題1，安排是生產產品

21、4單位，產品2單位，最大盈利為14萬元 。2.3 敏感性分析目標函數的系數變化的敏感性分析如果目標函數的系數發生變化，將會影響目標函數 f 斜率的變化，但是只要f 的斜率小于等于-1/2（也就是直線l夾在l1與l2之間時），最優解都在(4,2)上取到，最優解不變，從而生產計劃不會變. 2.3 敏感性分析要使用敏感性分析必須要在這里選擇Prices & Ranges然后保存退出路徑：LINGOOptionsGeneral Solver(通用求解程序)選項卡2.3 敏感性分析要調出敏感性分析的結果，必須先求解后再在程序窗口下點擊LINGORange， 2.3 敏感性分析Ranges in

22、which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 當前變量系數允許增加量允許減少量對問題2，產品的單位利潤降低到萬元，在（，）之間，所以不改變生產計劃。如果降低到1萬元，不在（，）內，要改變生產計劃。在程序中將目標函數的系數“2”改為“1”，可得

23、新的計劃為安排是生產產品2單位，產品3單位，最大盈利為11萬元.對問題3，要改變生產計劃，更改程序得新計劃為生產產品2單位，產品3單位，最大盈利為19萬元.對問題4，因為兩個系數同時改變了，所以只有更改程序的數據，重新運行得：不改變生產計劃，但是最大利潤降低到8萬元. 2.3 敏感性分析2.3 敏感性分析把y1,y2,y3作為三種原料的定價，定價的目標是在比生產產品獲得更多利潤的前提下的最小利潤. 在最優情況下，y的值就是資源的影子價格，影子價格有意義是有范圍的。影子價格經濟含義是：在資源得到最優配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量 2.3 敏感性分析Range

24、s in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 運行結果 Model Title: 生產計劃問題 Variable Value Reduced Cost Row Slack or Surplus Dual Price MAXF 14.

25、00000 A 0.000000 B 0.000000 TIME 4.000000 2.3 敏感性分析1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 時間480小時 至多加工100公斤A1 制訂生產計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/公斤，應否改變生產計劃？ 每天：例4 加工奶制品的生產計劃2.3 敏感性分析x1桶牛奶生產A1 x2桶牛奶生產A2 獲利 243x1 獲利 164 x2 原料供應 勞動時間 加工能力 決策變量 目標函數

26、 每天獲利約束條件非負約束 線性規劃模型(LP)2.3 敏感性分析Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 220桶牛奶生產A1, 30桶生產A2，利潤3360元。 2.3 敏感性分析 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3) 0.000000 4) 40.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);