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

求解優化問題常用的軟件什么是數學規劃？第8頁，共115頁，2023年，2月20日，星期六線性規劃的一般形式：連續性線性規劃第9頁，共115頁，2023年，2月20日，星期六一般線性規劃問題都可以通過引入非負的松弛變量slackvariable與非負的剩余變量surplusvariable的方法化為標準形式（約束全是等約束）。線性規劃問題的可行域feasibleregion是一個凸集convexset（任意兩點的連線上的點都在區域內部，可以看作是沒有凹坑的凸多面體），所以最優解Optimalsolution/point在凸多面體的某個頂點上達到求解方法：單純形算法simplexmethod。連續性線性規劃第10頁，共115頁，2023年，2月20日，星期六連續性線性規劃

例1運輸問題第11頁，共115頁，2023年，2月20日，星期六解設A1,A2調運到三個糧站的大米分別為x1，x2，

x3，

x4，

x5，

x6噸。題設量可總到下表：連續性線性規劃

第12頁，共115頁，2023年，2月20日，星期六結合存量限制和需量限制得數學模型：連續性線性規劃

第13頁，共115頁，2023年，2月20日，星期六程序編寫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軟件中連續性線性規劃

第14頁，共115頁，2023年，2月20日，星期六運行結果

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連續性線性規劃

第15頁，共115頁，2023年，2月20日，星期六模型修改為連續性線性規劃

第16頁，共115頁，2023年，2月20日，星期六程序編寫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;連續性線性規劃

第17頁，共115頁，2023年，2月20日，星期六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連續性線性規劃

第18頁，共115頁，2023年，2月20日，星期六84庫存量x23x22x21A2542需要量x13x12x11A1B3B2B1糧庫糧站距離及運量12122430824變量更換為：連續性線性規劃

第19頁，共115頁，2023年，2月20日，星期六模型:連續性線性規劃

第20頁，共115頁，2023年，2月20日，星期六程序編寫3MODEL:TITLE調運大米的運輸問題程序3;!定義集合段;SETS:LIANGKU/1..2/:A;!定義糧庫的集合;LIANGZHAN/1..3/:B;!定義糧站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定義運量和距離;ENDSETSDATA:!糧庫到糧站的距離;C=12248301224;連續性線性規劃

第21頁，共115頁，2023年，2月20日，星期六!糧庫的限量;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

連續性線性規劃

第22頁，共115頁，2023年，2月20日，星期六程序的調試1.直接點擊運行，如果出錯會彈出錯誤提示，根據提示做相應的修改；2.可以用“！”把約束變成說明語句，而把這條語句屏蔽掉，縮小尋找出錯的范圍；3.可以邊寫程序邊運行，保證每行書寫都是正確的程序；連續性線性規劃

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

第24頁，共115頁，2023年，2月20日，星期六

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

第25頁，共115頁，2023年，2月20日，星期六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

連續性線性規劃

第26頁，共115頁，2023年，2月20日，星期六連續性線性規劃

第27頁，共115頁，2023年，2月20日，星期六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連續性線性規劃

第28頁，共115頁，2023年，2月20日，星期六月份單位成本(元)銷售量12347060007270008012000766000連續性線性規劃

第29頁，共115頁，2023年，2月20日，星期六76827676---80--7472-747270生產月10000100001000010000產量600041200070006000銷量4321321需求月費用cij連續性線性規劃

第30頁，共115頁，2023年，2月20日，星期六連續性線性規劃

建立模型如下：第31頁，共115頁，2023年，2月20日，星期六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連續性線性規劃

第32頁，共115頁，2023年，2月20日，星期六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

連續性線性規劃

第33頁，共115頁，2023年，2月20日，星期六連續投資10萬元A：從第1年到第4年每年初要投資，次年末回收本利1.15B：第3年初投資，到第5年末回收1.25，最大投資4萬元C：第2年初投資，到第5年末回收1.40，最大投資3萬元D：每年初投資，每年末回收1.11。求：5年末總資本最大。練習一下吧

連續投資第34頁，共115頁，2023年，2月20日，星期六

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

第35頁，共115頁，2023年，2月20日，星期六敏感性分析1

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

第37頁，共115頁，2023年，2月20日，星期六運行結果ModelTitle:生產計劃問題VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

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

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

敏感性分析1

第39頁，共115頁，2023年，2月20日，星期六要使用敏感性分析必須要在這里選擇Prices&Ranges然后保存退出路徑：LINGO︱Options︱GeneralSolver(通用求解程序)選項卡敏感性分析1

第40頁，共115頁，2023年，2月20日，星期六要調出敏感性分析的結果，必須先求解后再在程序窗口下點擊LINGO｜Range，敏感性分析1

第41頁，共115頁，2023年，2月20日，星期六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

第42頁，共115頁，2023年，2月20日，星期六敏感性分析2

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

第44頁，共115頁，2023年，2月20日，星期六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

第45頁，共115頁，2023年，2月20日，星期六1桶牛奶3公斤A1

12小時8小時4公斤A2

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

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

x2桶牛奶生產A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數

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

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

第47頁，共115頁，2023年，2月20日，星期六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元。敏感性分析第48頁，共115頁，2023年，2月20日，星期六OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.00000035元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？2元！敏感性分析第49頁，共115頁，2023年，2月20日，星期六RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE

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

余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根整數線性規劃第52頁，共115頁，2023年，2月20日，星期六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整數線性規劃第53頁，共115頁，2023年，2月20日，星期六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整數線性規劃第54頁，共115頁，2023年，2月20日，星期六為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節省？模式

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

整數線性規劃第55頁，共115頁，2023年，2月20日，星期六2.所用原料鋼管總根數最少1.原料鋼管剩余總余量最小目標函數：（兩種標準）整數線性規劃第56頁，共115頁，2023年，2月20日，星期六模式4米根數6米根數8米根數余料14003231013201341203511116030170023需求502015約束整數約束：xi為整數整數線性規劃第57頁，共115頁，2023年，2月20日，星期六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程序編寫整數線性規劃第58頁，共115頁，2023年，2月20日，星期六按模式2切割12根,按模式5切割15根，余料27米

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

第60頁，共115頁，2023年，2月20日，星期六例6選址問題0-1規劃第61頁，共115頁，2023年，2月20日，星期六0-1規劃

第62頁，共115頁，2023年，2月20日，星期六某班準備從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練習一下吧

第63頁，共115頁，2023年，2月20日，星期六客戶增加需求：由于采用不同切割模式太多，會增加生產和管理成本，規定切割模式不能超過3種。如何下料最節省？5米10根例8續例5下料問題(P87)非線性規劃第64頁，共115頁，2023年，2月20日，星期六對大規模問題，用模型的約束條件界定合理模式現有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米長的鋼管的數量非線性規劃

第65頁，共115頁，2023年，2月20日，星期六滿足需求目標函數（總根數）約束條件xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數模式合理：每根余料不超過3米整數約束：非線性規劃

第66頁，共115頁，2023年，2月20日，星期六增加約束，縮小可行域，便于求解原料鋼管總根數下界：

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

第67頁，共115頁，2023年，2月20日，星期六特殊生產計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數上界：31模式排列順序可任定

上下界非線性規劃

第68頁，共115頁，2023年，2月20日，星期六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非線性規劃

第69頁，共115頁，2023年，2月20日，星期六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非線性規劃

第70頁，共115頁，2023年，2月20日，星期六結果模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數為28根。用去原料鋼管總根數為28根。

非線性規劃

第71頁，共115頁，2023年，2月20日，星期六

練習料場的建立與運輸

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

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

第74頁，共115頁，2023年，2月20日，星期六多目標決策問題有許多共同的特點，其中最顯著的是：目標的不可公度性，和目標間的矛盾性。因此不能簡單的把多個目標歸并為單個目標，并使用單目標決策問題的方法去求解多目標問題。多目標問題的數學模型多目標規劃

第75頁，共115頁，2023年，2月20日，星期六記可行域為D.MinxMinyxyABCD多目標規劃

第76頁，共115頁，2023年，2月20日，星期六多目標決策的本質問題是：如何根據決策者的主觀價值判斷，對有效解的好壞做出比較？由于可行域中的一個點，對應目標函數是一個向量，所以問題實際是：如何比較兩個向量的大小？ABABBC多目標規劃

第77頁，共115頁，2023年，2月20日，星期六多目標規劃

第78頁，共115頁，2023年，2月20日，星期六

多目標規劃的常用解法

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

權數評價函數單目標:多目標規劃

第79頁，共115頁，2023年，2月20日，星期六（2）變權加權法：

（3）指數加權法：

多目標規劃

第80頁，共115頁，2023年，2月20日，星期六（4）極小極大（min-max）法

多目標規劃

第81頁，共115頁，2023年，2月20日，星期六（5）理想點法

先求解單目標的最優值確定理想點：在找距離理想點最近的點作為最優解：多目標規劃

第82頁，共115頁，2023年，2月20日，星期六（6）加權偏差函數法

多目標規劃

第83頁，共115頁，2023年，2月20日，星期六（7）費效比函數：多目標規劃

第84頁，共115頁，2023年，2月20日，星期六（8）功效系數函數：對不同的性質的目標函數統一量綱，再構造效用函數：比如構造功效系數函數：然后求解規劃問題：還可以對功效系數函數進行加權構造效用函數，如多目標規劃

第85頁，共115頁，2023年，2月20日，星期六（9）參考目標法

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

第86頁，共115頁，2023年，2月20日，星期六（10）逼近理想解法正負理想解：計算距離，不妨取為歐式距離：計算測度：求最大測度：多目標規劃

第87頁，共115頁，2023年，2月20日，星期六例10投資問題某企業擬用1000萬元投資于A、B兩個項目的技術改造.設、分別表示分配給A、B項目的投資（萬元）.據估計，投資項目A、B的年收益分別為投資的60%和70%；但投資風險損失，與總投資和單項投資均有關系：

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

第88頁，共115頁，2023年，2月20日，星期六

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

而且滿足：

多目標規劃

第89頁，共115頁，2023年，2月20日，星期六對于上述多目標規劃問題，處理成單目標如下：多目標規劃

第90頁，共115頁，2023年，2月20日，星期六練習72007全國大學生數學建模競賽B題乘公交，看奧運

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

第91頁，共115頁，2023年，2月20日，星期六線性規劃與目標規劃線性規劃通常考慮一個目標函數(問題簡單)目標規劃考慮多個目標函數(問題復雜)線性規劃目標規劃發展演變目標規劃第92頁，共115頁，2023年，2月20日，星期六某企業生產甲、乙兩種產品，需要用到A,B,C三種設備，關于產品的盈利與使用設備的工時及限制如下表所示。

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

第93頁，共115頁，2023年，2月20日，星期六該例11是一個線性規劃問題，直接考慮它的線性規劃模型設甲、乙產品的產量分別為x1,x2,建立線性規劃模型：用Lingo軟件求解,得到最優解目標規劃

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

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

第96頁，共115頁，2023年，2月20日，星期六目標規劃的數學模型為了克服線性規劃的局限性,目標規劃采用如下手段：1.設置偏差變量;2.統一處理目標與約束;3.目標的優先級與權系數。目標規劃的基本概念目標規劃

第97頁，共115頁，2023年，2月20日，星期六1.設置偏差變量用偏差變量(Deviationalvariables)來表示實際值與目標值之間的差異，令----超出目標的差值，稱為正偏差變量----未達到目標的差值，稱為負偏差變量其中與至少有一個為0約定如下：當實際值超過目標值時，有當實際值未達到目標值時，有當實際值與目標值一致時，有目標規劃

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

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

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

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

第102頁，共115頁，2023年，2月20日，星期六目標規劃的一般模型目標規