數學規(guī)劃建模

數學規(guī)劃建模第一頁，共一百一十五頁，編輯于2023年，星期三內容提要什么是數學規(guī)劃連續(xù)性線性規(guī)劃整數線性規(guī)劃非線性規(guī)劃多目標規(guī)劃目標規(guī)劃第二頁，共一百一十五頁，編輯于2023年，星期三最優(yōu)化問題的數學模型的一般形式為：（1）（2）三個要素：決策變量decisionvariable，目標函數objectivefunction，約束條件constraints。什么是數學規(guī)劃？第三頁，共一百一十五頁，編輯于2023年，星期三（2）所確定的x的范圍稱為可行域feasibleregion，滿足（2）的解x稱為可行解feasiblesolution，同時滿足（1）（2）的解x稱為最優(yōu)解Optimalsolution，整個可行域上的最優(yōu)解稱為全局最優(yōu)解globaloptimalsolution，可行域中某個領域上的最優(yōu)解稱為局部最優(yōu)解localoptimalsolution。最優(yōu)解所對應的目標函數值稱為最優(yōu)值optimum。什么是數學規(guī)劃？第四頁，共一百一十五頁，編輯于2023年，星期三（一）按有無約束條件（2）可分為：1.無約束優(yōu)化unconstrainedoptimization。2.約束優(yōu)化constrainedoptimization。大部分實際問題都是約束優(yōu)化問題。優(yōu)化模型的分類什么是數學規(guī)劃？第五頁，共一百一十五頁，編輯于2023年，星期三（二）按決策變量取值是否連續(xù)可分為：1.數學規(guī)劃或連續(xù)優(yōu)化?？衫^續(xù)劃分為線性規(guī)劃(LP)Linearprogramming和非線性規(guī)劃(NLP)Nonlinearprogramming。在非線性規(guī)劃中有一種規(guī)劃叫做二次規(guī)劃(QP)Quadraticprogramming，目標為二次函數，約束為線性函數。2.離散優(yōu)化或組合優(yōu)化。包含：整數規(guī)劃(IP)Integerprogramming，整數規(guī)劃中又包含很重要的一類規(guī)劃：0-1（整數）規(guī)劃Zero-oneprogramming，這類規(guī)劃問題的決策變量只取0或者1。什么是數學規(guī)劃？第六頁，共一百一十五頁，編輯于2023年，星期三（三）按目標的多少可分為：1.單目標規(guī)劃。2.多目標規(guī)劃。（四）按模型中參數和變量是否具有不確定性可分為：1.確定性規(guī)劃。2.不確定性規(guī)劃。（五）按問題求解的特性可分為：1.目標規(guī)劃。2.動態(tài)規(guī)劃。3.多層規(guī)劃。4.網絡優(yōu)化。5.……等等。什么是數學規(guī)劃？第七頁，共一百一十五頁，編輯于2023年，星期三LINGO軟件和MATLAB軟件。

求解優(yōu)化問題常用的軟件什么是數學規(guī)劃？第八頁，共一百一十五頁，編輯于2023年，星期三線性規(guī)劃的一般形式：連續(xù)性線性規(guī)劃第九頁，共一百一十五頁，編輯于2023年，星期三一般線性規(guī)劃問題都可以通過引入非負的松弛變量slackvariable與非負的剩余變量surplusvariable的方法化為標準形式（約束全是等約束）。線性規(guī)劃問題的可行域feasibleregion是一個凸集convexset（任意兩點的連線上的點都在區(qū)域內部，可以看作是沒有凹坑的凸多面體），所以最優(yōu)解Optimalsolution/point在凸多面體的某個頂點上達到求解方法：單純形算法simplexmethod。連續(xù)性線性規(guī)劃第十頁，共一百一十五頁，編輯于2023年，星期三連續(xù)性線性規(guī)劃

例1運輸問題第十一頁，共一百一十五頁，編輯于2023年，星期三解設A1,A2調運到三個糧站的大米分別為x1，x2，

x3，

x4，

x5，

x6噸。題設量可總到下表：連續(xù)性線性規(guī)劃

第十二頁，共一百一十五頁，編輯于2023年，星期三結合存量限制和需量限制得數學模型：連續(xù)性線性規(guī)劃

第十三頁，共一百一十五頁，編輯于2023年，星期三程序編寫1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6;x1+x2+x3<4;x4+x5+x6<8;x1+x4>2;x2+x5>4;x3+x6>5;end提示：課件中的程序請先粘貼在記事本中再轉帖于lingo軟件中連續(xù)性線性規(guī)劃

第十四頁，共一百一十五頁，編輯于2023年，星期三運行結果

Globaloptimalsolutionfound.Objectivevalue:160.0000Totalsolveriterations:0VariableValueReducedCostX12.0000000.000000X20.00000028.00000X32.0000000.000000X40.0000002.000000X54.0000000.000000X63.0000000.000000RowSlackorSurplusDualPrice1160.0000-1.00000020.00000016.0000031.0000000.00000040.000000-28.0000050.000000-12.0000060.000000-24.00000連續(xù)性線性規(guī)劃

第十五頁，共一百一十五頁，編輯于2023年，星期三模型修改為連續(xù)性線性規(guī)劃

第十六頁，共一百一十五頁，編輯于2023年，星期三程序編寫2MODEL:TITLE調運大米的運輸問題程序2;!定義集合段;SETS:HANG/1..5/:B;!定義矩陣的行;LIE/1..6/:C,X;!定義矩陣的列以及變量;XISHU(HANG,LIE):A;!定義約束的系數矩陣;ENDSETSDATA:A=111000!系數矩陣賦值;000111-100-1000-100-1000-100-1;連續(xù)性線性規(guī)劃

第十七頁，共一百一十五頁，編輯于2023年，星期三C=12248301224;!目標函數的系數;B=48-2-4-5;!約束的右端項;ENDDATA!標準形式的目標函數的矩陣形式;MIN=@SUM(LIE:C*X);@FOR(HANG(I):

@SUM(LIE(J):A(I,J)*X(J))<B(I));END連續(xù)性線性規(guī)劃

第十八頁，共一百一十五頁，編輯于2023年，星期三84庫存量x23x22x21A2542需要量x13x12x11A1B3B2B1糧庫糧站距離及運量12122430824變量更換為：連續(xù)性線性規(guī)劃

第十九頁，共一百一十五頁，編輯于2023年，星期三模型:連續(xù)性線性規(guī)劃

第二十頁，共一百一十五頁，編輯于2023年，星期三程序編寫3MODEL:TITLE調運大米的運輸問題程序3;!定義集合段;SETS:LIANGKU/1..2/:A;!定義糧庫的集合;LIANGZHAN/1..3/:B;!定義糧站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定義運量和距離;ENDSETSDATA:!糧庫到糧站的距離;C=12248301224;連續(xù)性線性規(guī)劃

第二十一頁，共一百一十五頁，編輯于2023年，星期三!糧庫的限量;A=48;!糧站的限量;B=245;ENDDATA[OBJ]MIN=@SUM(YULIANG:C*X);!糧庫上限的約束;@FOR(LIANGKU(I):[LK]

@SUM(LIANGZHAN(J):X(I,J))<A(I));!糧站下限的約束;@FOR(LIANGZHAN(J):[LZ]

@SUM(LIANGKU(I):X(I,J))>B(J));END

連續(xù)性線性規(guī)劃

第二十二頁，共一百一十五頁，編輯于2023年，星期三程序的調試1.直接點擊運行，如果出錯會彈出錯誤提示，根據提示做相應的修改；2.可以用“！”把約束變成說明語句，而把這條語句屏蔽掉，縮小尋找出錯的范圍；3.可以邊寫程序邊運行，保證每行書寫都是正確的程序；連續(xù)性線性規(guī)劃

第二十三頁，共一百一十五頁，編輯于2023年，星期三例2階段生產問題(P31)某公司生產某產品,最大生產能力為10000單位,每單位存儲費2元,預定的銷售量與單位成本如下:月份單位成本(元)銷售量12347060007270008012000766000求一生產計劃,使1)滿足需求;2)不超過生產能力;3)成本(生產成本與存儲費之和)最低.連續(xù)性線性規(guī)劃

第二十四頁，共一百一十五頁，編輯于2023年，星期三

解假定1月初無庫存,4月底買完,當月生產的不庫存,庫存量無限制.連續(xù)性線性規(guī)劃

第二十五頁，共一百一十五頁，編輯于2023年，星期三model:title生產計劃程序1;Sets:yuefen/1..4/:c,x,e,d;endsetsdata:c=70718076;d=60007000120006000;e=2222;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:x<a);end

連續(xù)性線性規(guī)劃

第二十六頁，共一百一十五頁，編輯于2023年，星期三連續(xù)性線性規(guī)劃

第二十七頁，共一百一十五頁，編輯于2023年，星期三Model:Title生產計劃程序2;Sets:yuefen/1..4/:c,x,e,d,s;endsetsdata:c=70718076;d=60007000120006000;e=2222;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:x<a);End連續(xù)性線性規(guī)劃

第二十八頁，共一百一十五頁，編輯于2023年，星期三月份單位成本(元)銷售量12347060007270008012000766000連續(xù)性線性規(guī)劃

第二十九頁，共一百一十五頁，編輯于2023年，星期三76827676---80--7472-747270生產月10000100001000010000產量600041200070006000銷量4321321需求月費用cij連續(xù)性線性規(guī)劃

第三十頁，共一百一十五頁，編輯于2023年，星期三連續(xù)性線性規(guī)劃

建立模型如下：第三十一頁，共一百一十五頁，編輯于2023年，星期三model:title生產計劃程序3;sets:yuefen/1..4/:a,d,xx;!定義上三角矩陣;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70727476717375808276;d=60007000120006000;a=10000100001000010000;enddatamin=@sum(link:c*x);@for(yuefen(i):@sum(yuefen(j)|j#ge#i:x(i,j))<a(i););@for(yuefen(j):@sum(yuefen(i)|j#ge#i:x(i,j))>d(j););!得到每個月的生產量;@for(yuefen(i):xx=@sum(yuefen(j)|j#ge#i:x(i,j)));End連續(xù)性線性規(guī)劃

第三十二頁，共一百一十五頁，編輯于2023年，星期三ModelTitle::生產計劃程序1VariableValueReducedCostA10000.000.000000C(1)70.000000.000000C(2)71.000000.000000C(3)80.000000.000000C(4)76.000000.000000X(1)10000.000.000000X(2)10000.000.000000X(3)5000.0000.000000X(4)6000.0000.000000E(1)2.0000000.000000E(2)2.0000000.000000E(3)2.0000000.000000E(4)2.0000000.000000D(1)6000.0000.000000D(2)7000.0000.000000D(3)12000.000.000000D(4)6000.0000.000000

連續(xù)性線性規(guī)劃

第三十三頁，共一百一十五頁，編輯于2023年，星期三連續(xù)投資10萬元A：從第1年到第4年每年初要投資，次年末回收本利1.15B：第3年初投資，到第5年末回收1.25，最大投資4萬元C：第2年初投資，到第5年末回收1.40，最大投資3萬元D：每年初投資，每年末回收1.11。求：5年末總資本最大。練習一下吧

連續(xù)投資第三十四頁，共一百一十五頁，編輯于2023年，星期三

例3生產計劃問題某工廠計劃安排生產Ⅰ，Ⅱ兩種產品，已知每種單位產品的利潤，生產單位產品所需設備臺時及A,B兩種原材料的消耗，現(xiàn)有原材料和設備臺時的定額如表所示，問：１）怎么安排生產使得工廠獲利最大？２）產品Ⅰ的單位利潤降低到1.8萬元，要不要改變生產計劃，如果降低到1萬元呢？３）產品Ⅱ的單位利潤增大到5萬元，要不要改變生產計劃？４）如果產品Ⅰ，Ⅱ的單位利潤同時降低了1萬元，要不要改變生產計劃？產品Ⅰ產品Ⅱ最大資源量設備128臺時原材料A4016kg原材料B0412kg單位產品利潤23敏感性分析1

第三十五頁，共一百一十五頁，編輯于2023年，星期三敏感性分析1

第三十六頁，共一百一十五頁，編輯于2023年，星期三程序編寫model:title生產計劃問題;[maxf]max=2*x1+3*x2;[TIME]x1+2*x2<8;[A]4*x1<16;[B]4*x2<12;END敏感性分析1

第三十七頁，共一百一十五頁，編輯于2023年，星期三運行結果ModelTitle:生產計劃問題VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

對問題1，安排是生產產品Ⅰ4單位，產品Ⅱ2單位，最大盈利為14萬元。敏感性分析1

第三十八頁，共一百一十五頁，編輯于2023年，星期三目標函數的系數變化的敏感性分析如果目標函數的系數發(fā)生變化，將會影響目標函數f斜率的變化，但是只要f的斜率小于等于-1/2（也就是直線l夾在l1與l2之間時），最優(yōu)解都在(4,2)上取到，最優(yōu)解不變，從而生產計劃不會變.

敏感性分析1

第三十九頁，共一百一十五頁，編輯于2023年，星期三要使用敏感性分析必須要在這里選擇Prices&Ranges然后保存退出路徑：LINGO︱Options︱GeneralSolver(通用求解程序)選項卡敏感性分析1

第四十頁，共一百一十五頁，編輯于2023年，星期三要調出敏感性分析的結果，必須先求解后再在程序窗口下點擊LINGO｜Range，敏感性分析1

第四十一頁，共一百一十五頁，編輯于2023年，星期三Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRanges

CurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

當前變量系數允許增加量允許減少量對問題2，產品Ⅰ的單位利潤降低到1.8萬元，在（1.5，∞）之間，所以不改變生產計劃。如果降低到1萬元，不在（1.5，∞）內，要改變生產計劃。在程序中將目標函數的系數“2”改為“1”，可得新的計劃為安排是生產產品Ⅰ2單位，產品Ⅱ3單位，最大盈利為11萬元.對問題3，要改變生產計劃，更改程序得新計劃為生產產品Ⅰ2單位，產品Ⅱ3單位，最大盈利為19萬元.對問題4，因為兩個系數同時改變了，所以只有更改程序的數據，重新運行得：不改變生產計劃，但是最大利潤降低到8萬元.

敏感性分析1

第四十二頁，共一百一十五頁，編輯于2023年，星期三敏感性分析2

第四十三頁，共一百一十五頁，編輯于2023年，星期三把y1,y2,y3作為三種原料的定價，定價的目標是在比生產產品獲得更多利潤的前提下的最小利潤.在最優(yōu)情況下，y的值就是資源的影子價格，影子價格有意義是有范圍的。影子價格經濟含義是：在資源得到最優(yōu)配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量．敏感性分析2

第四十四頁，共一百一十五頁，編輯于2023年，星期三Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000

RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

運行結果ModelTitle:生產計劃問題VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

敏感性分析2

第四十五頁，共一百一十五頁，編輯于2023年，星期三1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

制訂生產計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/公斤，應否改變生產計劃？每天：例4加工奶制品的生產計劃敏感性分析第四十六頁，共一百一十五頁，編輯于2023年，星期三x1桶牛奶生產A1

x2桶牛奶生產A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數

每天獲利約束條件非負約束

線性規(guī)劃模型(LP)敏感性分析1

第四十七頁，共一百一十五頁，編輯于2023年，星期三Max=72*x1+64*x2;x1+x2<50;12*x1+8*x2<480;3*x1<100;

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生產A1,30桶生產A2，利潤3360元。敏感性分析第四十八頁，共一百一十五頁，編輯于2023年，星期三OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.00000035元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？2元！敏感性分析第四十九頁，共一百一十五頁，編輯于2023年，星期三RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE

250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000A1獲利增加到30元/千克，應否改變生產計劃？不變！35元可買到1桶牛奶，每天最多買多少？最多買10桶！敏感性分析第五十頁，共一百一十五頁，編輯于2023年，星期三問題：如何下料最節(jié)省?原料鋼管:每根19米4米50根6米20根8米15根客戶需求例5下料問題(P71)整數線性規(guī)劃第五十一頁，共一百一十五頁，編輯于2023年，星期三按照客戶需要在一根原料鋼管上安排切割的一種組合。

余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根整數線性規(guī)劃第五十二頁，共一百一十五頁，編輯于2023年，星期三model:title搜索合理的下料方式;sets:ren:;!用一根原料可下各需求長度的最多根數定義元素個數，最多為4，這里要定義5(0—4有5個數);long(ren,ren,ren):;!有三種需求長度，定義三維數組;endsetsdata:ren=1..5;!為了美觀輸出一些題頭;@text('d:renxinglong.txt')=@write(1*'','下料方式',7*'','余料長度',@newline(1));@text('d:renxinglong.txt')=@write(12*'-',4*'',8*'-',@newline(1));!搜索所有滿足過濾條件的i,j,k;@text('d:renxinglong.txt')=@writefor(long(i,j,k)|(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0#and#(19-8*(i-1)-6*(j-1)-4*(k-1))#lt#a

!一種下料方式下料長度和不超過總長度,合理模式的余料小于最短需求;

!輸出下料方式到文本文件renxinglong.txt，我們需要的數是0--4;

:i-1,4*'',j-1,4*'',k-1,8*'',19-8*(i-1)-6*(j-1)-4*(k-1),@newline(2));!輸出計算段計數過的下料方式總數;@text('d:renxinglong.txt')=@write('下料方式總數為：',2*'',n,'種');Enddata整數線性規(guī)劃第五十三頁，共一百一十五頁，編輯于2023年，星期三calc:a=@smin(8,6,4);b=@floor(19/a)+1;n=0;@for(long(i,j,k)|(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0#and#(19-8*(i-1)-6*(j-1)-4*(k-1))#lt#a:n=n+1);!下料方式計數;endcalcend整數線性規(guī)劃第五十四頁，共一百一十五頁，編輯于2023年，星期三為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。磕Ｊ?/p>

4米鋼管根數6米鋼管根數8米鋼管根數余料(米)14003231013201341203511116030170023xi~按第i種模式切割的原料鋼管根數(i=1,2,…7)決策變量

整數線性規(guī)劃第五十五頁，共一百一十五頁，編輯于2023年，星期三2.所用原料鋼管總根數最少1.原料鋼管剩余總余量最小目標函數：（兩種標準）整數線性規(guī)劃第五十六頁，共一百一十五頁，編輯于2023年，星期三模式4米根數6米根數8米根數余料14003231013201341203511116030170023需求502015約束整數約束：xi為整數整數線性規(guī)劃第五十七頁，共一百一十五頁，編輯于2023年，星期三model:Title

鋼管下料;

Min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5>50; x2+2*x4+x5+3*x6>20; x3+x5+2*x7>15;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);end程序編寫整數線性規(guī)劃第五十八頁，共一百一十五頁，編輯于2023年，星期三按模式2切割12根,按模式5切割15根，余料27米

最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米當余料沒有用處時，通常以總根數最少為目標整數線性規(guī)劃第五十九頁，共一百一十五頁，編輯于2023年，星期三練習3某服務部門一周中每天需要不同數目的雇員，周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人，現(xiàn)規(guī)定應聘者需連續(xù)工作5天，試確定聘用方案。練習一下吧

第六十頁，共一百一十五頁，編輯于2023年，星期三例6選址問題0-1規(guī)劃第六十一頁，共一百一十五頁，編輯于2023年，星期三0-1規(guī)劃

第六十二頁，共一百一十五頁，編輯于2023年，星期三某班準備從5名游泳員中選擇４人組成接力隊，參加學校的4×100m混合泳接力比賽，5名隊員4種泳姿的百米平均成績如表，問如何選拔隊員。隊員甲乙丙丁戊蝶泳1’06’’857’’21’18’’1’10’’1’07’’4仰泳1’15’’61’06’’1’14’’21’14’’21’11’’蛙泳1’27’’1’06’’41’09’’61’09’’61’23’’8自由泳58’’653’’59’’457’’21’02’’4練習一下吧

第六十三頁，共一百一十五頁，編輯于2023年，星期三客戶增加需求：由于采用不同切割模式太多，會增加生產和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)?。?米10根例8續(xù)例5下料問題(P87)非線性規(guī)劃第六十四頁，共一百一十五頁，編輯于2023年，星期三對大規(guī)模問題，用模型的約束條件界定合理模式現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，由搜索算法確定有16種合理切割模式。決策變量

xi~按第i種模式切割的原料鋼管根數(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產4米、5米、6米和8米長的鋼管的數量非線性規(guī)劃

第六十五頁，共一百一十五頁，編輯于2023年，星期三滿足需求目標函數（總根數）約束條件xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數模式合理：每根余料不超過3米整數約束：非線性規(guī)劃

第六十六頁，共一百一十五頁，編輯于2023年，星期三增加約束，縮小可行域，便于求解原料鋼管總根數下界：

需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長19米非線性規(guī)劃

第六十七頁，共一百一十五頁，編輯于2023年，星期三特殊生產計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數上界：31模式排列順序可任定

上下界非線性規(guī)劃

第六十八頁，共一百一十五頁，編輯于2023年，星期三model:Title

鋼管下料-最小化鋼管根數的LINGO模型;SETS:NEEDS/1..4/:LENGTH,NUM; CUTS/1..3/:X; PATTERNS(NEEDS,CUTS):R;ENDSETSDATA: LENGTH=4568; NUM=50102015; CAPACITY=19;ENDDATA非線性規(guī)劃

第六十九頁，共一百一十五頁，編輯于2023年，星期三min=@SUM(CUTS(I):X(I)); @FOR(NEEDS(I):@SUM(CUTS(J):X(J)*R(I,J))>NUM(I));!滿足需求約束;@FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))<CAPACITY);!合理切割模式約束;@FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))>CAPACITY-@MIN(NEEDS(I):LENGTH(I)));!合理切割模式約束;@SUM(CUTS(I):X(I))>26;@SUM(CUTS(I):X(I))<31;!人為增加約束;@FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1)); !人為增加約束;@FOR(CUTS(J):@GIN(X(J)));@FOR(PATTERNS(I,J):@GIN(R(I,J)));end非線性規(guī)劃

第七十頁，共一百一十五頁，編輯于2023年，星期三結果模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數為28根。用去原料鋼管總根數為28根。

非線性規(guī)劃

第七十一頁，共一百一十五頁，編輯于2023年，星期三

練習料場的建立與運輸

建筑工地的位置(用平面坐標a,b表示，距離單位：公里)及水泥日用量d(噸)下表給出。有兩個臨時料場位于P(5,1),Q(2,7),日儲量各有20噸。從A,B兩料場分別向各工地運送多少噸水泥，使總的噸公里數最小。兩個新的料場應建在何處，節(jié)省的噸公里數有多大？１２３４５６a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611練習一下吧

第七十二頁，共一百一十五頁，編輯于2023年，星期三線性規(guī)劃致力于某個目標函數的最優(yōu)解，這個最優(yōu)解若是超過了實際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價。線性規(guī)劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產還得繼續(xù)進行，這將給人們進一步應用線性規(guī)劃方法帶來困難。多目標規(guī)劃第七十三頁，共一百一十五頁，編輯于2023年，星期三例9重新考慮例6選址問題。(增加投資最少)多目標規(guī)劃

第七十四頁，共一百一十五頁，編輯于2023年，星期三多目標決策問題有許多共同的特點，其中最顯著的是：目標的不可公度性，和目標間的矛盾性。因此不能簡單的把多個目標歸并為單個目標，并使用單目標決策問題的方法去求解多目標問題。多目標問題的數學模型多目標規(guī)劃

第七十五頁，共一百一十五頁，編輯于2023年，星期三記可行域為D.MinxMinyxyABCD多目標規(guī)劃

第七十六頁，共一百一十五頁，編輯于2023年，星期三多目標決策的本質問題是：如何根據決策者的主觀價值判斷，對有效解的好壞做出比較？由于可行域中的一個點，對應目標函數是一個向量，所以問題實際是：如何比較兩個向量的大小？ABABBC多目標規(guī)劃

第七十七頁，共一百一十五頁，編輯于2023年，星期三多目標規(guī)劃

第七十八頁，共一百一十五頁，編輯于2023年，星期三

多目標規(guī)劃的常用解法

思想：轉化為單目標問題（1）線性加權法：

權數評價函數單目標:多目標規(guī)劃

第七十九頁，共一百一十五頁，編輯于2023年，星期三（2）變權加權法：

（3）指數加權法：

多目標規(guī)劃

第八十頁，共一百一十五頁，編輯于2023年，星期三（4）極小極大（min-max）法

多目標規(guī)劃

第八十一頁，共一百一十五頁，編輯于2023年，星期三（5）理想點法

先求解單目標的最優(yōu)值確定理想點：在找距離理想點最近的點作為最優(yōu)解：多目標規(guī)劃

第八十二頁，共一百一十五頁，編輯于2023年，星期三（6）加權偏差函數法

多目標規(guī)劃

第八十三頁，共一百一十五頁，編輯于2023年，星期三（7）費效比函數：多目標規(guī)劃

第八十四頁，共一百一十五頁，編輯于2023年，星期三（8）功效系數函數：對不同的性質的目標函數統(tǒng)一量綱，再構造效用函數：比如構造功效系數函數：然后求解規(guī)劃問題：還可以對功效系數函數進行加權構造效用函數，如多目標規(guī)劃

第八十五頁，共一百一十五頁，編輯于2023年，星期三（9）參考目標法

約束法：在多個目標中選定一個主要目標，而對其他目標設定一個期望值，在要求結果不比期望值壞的情況下，求主要目標的最優(yōu)值。分層序列法：把多個目標按照重要程度進行排序，先求第一個目標的最有解，在達到此目標的條件下求第二個目標的最優(yōu)解，依次類推寬容分層序列法：給前面的最優(yōu)值設置一定的寬容值，和最優(yōu)值相差寬容值之內的都是可以接受的。多目標規(guī)劃

第八十六頁，共一百一十五頁，編輯于2023年，星期三（10）逼近理想解法正負理想解：計算距離，不妨取為歐式距離：計算測度：求最大測度：多目標規(guī)劃

第八十七頁，共一百一十五頁，編輯于2023年，星期三例10投資問題某企業(yè)擬用1000萬元投資于A、B兩個項目的技術改造.設、分別表示分配給A、B項目的投資（萬元）.據估計，投資項目A、B的年收益分別為投資的60%和70%；但投資風險損失，與總投資和單項投資均有關系：

據市場調查顯示，A項目的投資前景好于B項目，因此希望A項目的投資額不小B項目.試問應該如何在A、B兩個項目之間分配投資，才能既使年利潤最大，又使風險損失為最小？多目標規(guī)劃

第八十八頁，共一百一十五頁，編輯于2023年，星期三

解該問題是一個非線性多目標規(guī)劃問題，將它用數學語言描述出來，就是：求、，使：

而且滿足：

多目標規(guī)劃

第八十九頁，共一百一十五頁，編輯于2023年，星期三對于上述多目標規(guī)劃問題，處理成單目標如下：多目標規(guī)劃

第九十頁，共一百一十五頁，編輯于2023年，星期三練習72007全國大學生數學建模競賽B題乘公交，看奧運

第29屆奧運會明年8月將在北京舉行，大部分人將會乘坐公共交通工具到現(xiàn)場觀看奧運比賽，這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。請你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數學模型與算法。并根據附錄數據，利用你們的模型與算法，求出以下6對起始站→終到站之間的最佳路線(1)、S3359→S1828(2)、S1557→S0481。。。2、同時考慮公汽與地鐵線路，解決以上問題。練習：請給出模型的目標練習一下吧

第九十一頁，共一百一十五頁，編輯于2023年，星期三線性規(guī)劃與目標規(guī)劃線性規(guī)劃通?？紤]一個目標函數(問題簡單)目標規(guī)劃考慮多個目標函數(問題復雜)線性規(guī)劃目標規(guī)劃發(fā)展演變目標規(guī)劃第九十二頁，共一百一十五頁，編輯于2023年，星期三某企業(yè)生產甲、乙兩種產品，需要用到A,B,C三種設備，關于產品的盈利與使用設備的工時及限制如下表所示。

例11生產安排問題問該企業(yè)應如何安排生產，使得在計劃期內總利潤最大？目標規(guī)劃

第九十三頁，共一百一十五頁，編輯于2023年，星期三該例11是一個線性規(guī)劃問題，直接考慮它的線性規(guī)劃模型設甲、乙產品的產量分別為x1,x2,建立線性規(guī)劃模型：用Lingo軟件求解,得到最優(yōu)解目標規(guī)劃

第九十四頁，共一百一十五頁，編輯于2023年，星期三在上例11中，企業(yè)的經營目標不僅要考慮利潤，還需要考慮多個方面，因此增加下列因素(目標)：力求使利潤指標不低于1500元考慮到市場需求,甲、乙兩種產品的產量比應盡量保持1:2設備A為貴重設備，嚴格禁止超時使用設備C可以適當加班，但要控制；設備B既要求充分利用，又盡可能不加班，在重要性上，設備B是設備C的3倍從上述問題可以看出，僅用線性規(guī)劃方法是不夠的，需要借助于目標規(guī)劃的方法進行建模求解目標規(guī)劃

第九十五頁，共一百一十五頁，編輯于2023年，星期三線性規(guī)劃建模局限性線性規(guī)劃要求所有求解的問題必須滿足全部的約束，而實際問題中并非所有約束都需要嚴格的滿足；線性規(guī)劃只能處理單目標的優(yōu)化問題，而對一些次目標只能轉化為約束處理。但在實際問題中，目標和約束好似可以相互轉化的，處理時不一定要嚴格區(qū)分；線性規(guī)劃在處理問題時，將各個約束(也可看作目標)的地位看成同等重要，而在實際問題中，各個目標的重要性即有層次上的差別，也有在同一層次上不同權重的差別線性規(guī)劃尋求最優(yōu)解，而許多實際問題只需要找到滿意解就可以了。目標規(guī)劃

第九十六頁，共一百一十五頁，編輯于2023年，星期三目標規(guī)劃的數學模型為了克服線性規(guī)劃的局限性,目標規(guī)劃采用如下手段：1.設置偏差變量;2.統(tǒng)一處理目標與約束;3.目標的優(yōu)先級與權系數。目標規(guī)劃的基本概念目標規(guī)劃

第九十七頁，共一百一十五頁，編輯于2023年，星期三1.設置偏差變量用偏差變量(Deviationalvariables)來表示實際值與目標值之間的差異，令----超出目標的差值，稱為正偏差變量----未達到目標的差值，稱為負偏差變量其中與至少有一個為0約定如下：當實際值超過目標值時，有當實際值未達到目標值時，有當實際值與目標值一致時，有目標規(guī)劃

第九十八頁，共一百一十五頁，編輯于2023年，星期三2.統(tǒng)一處理目標與約束在目標規(guī)劃中，約束可分兩類，一類是對資源有嚴格限制的，稱為剛性約束(HardConstraint)；例如在用目標規(guī)劃求解例11中設備A禁止超時使用，則有剛性約束另一類是可以不嚴格限制的，連同原線性規(guī)劃的目標,構成柔性約束(SoftConstraint).例如在求解例11中，我們希望利潤不低于1500元，則目標可表示為目標規(guī)劃

第九十九頁，共一百一十五頁，編輯于2023年，星期三求解例11中甲、乙兩種產品的產量盡量保持1:2的比例，則目標可表示為設備C可以適當加班，但要控制，則目標可表示為設備B既要求充分利用，又盡可能不加班，則目標可表示為從上面的分析可以看到：如果希望不等式保持大于等于，則極小化負偏差；如果希望不等式保持小于等于，則極小化正偏差；如果希望保持等式，則同時極小化正、負偏差．目標規(guī)劃

第一百頁，共一百一十五頁，編輯于2023年，星期三3.目標的優(yōu)先級與權系數在目標規(guī)劃模型中，目標的優(yōu)先分為兩個層次，第一個層次是目標分成不同的優(yōu)先級，在計算目標規(guī)劃時，必須先優(yōu)化高優(yōu)先級的目標，然后再優(yōu)化低優(yōu)先級的目標。通常以P1,P2,...表示不同的因子,并規(guī)定Pk>>Pk+1，第二個層次是目標處于同一優(yōu)先級，但兩個目標的權重不一樣，因此兩目標同時優(yōu)化，用權系數的大小來表示目標重要性的差別。目標規(guī)劃

第一百零一頁，共一百一十五頁，編輯于2023年，星期三解在例11中設備A是剛性約束，其于是柔性約束．首先，最重要的指標是企業(yè)的利潤，將它的優(yōu)先級列為第一級；其次，甲、乙兩種產品的產量保持1:2的比例，列為第二級；再次，設備B和C的工作時間要有所控制，列為第三級，設備B的重要性是設備C的三倍，因此它們的權重不一樣。由此可以得到相應的目標規(guī)劃模型。用目標規(guī)劃方法求解例11目標規(guī)劃

第一百零二頁，共一百一十五頁，編輯于2023年，星期三目標規(guī)劃的一般模型目標規(guī)劃

第一百