第三講數(shù)學(xué)規(guī)劃模型

第三講數(shù)學(xué)規(guī)劃模型第一頁，共三十三頁，2022年，8月28日優(yōu)化模型的簡單分類

線性規(guī)劃(LP)目標(biāo)和約束均為線性函數(shù)

非線性規(guī)劃(NLP)目標(biāo)或約束中存在非線性函數(shù)

二次規(guī)劃(QP)目標(biāo)為二次函數(shù)、約束為線性

整數(shù)規(guī)劃(IP)決策變量(全部或部分)為整數(shù)整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP)一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學(xué)規(guī)劃第二頁，共三十三頁，2022年，8月28日例1加工奶制品的生產(chǎn)計劃獲利24元/公斤1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利16元/公斤50桶牛奶時間480小時甲設(shè)備至多加工100公斤A1

制訂生產(chǎn)計劃，使每天獲利最大每天：線性規(guī)劃模型第三頁，共三十三頁，2022年，8月28日1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動時間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時間480小時至多加工100公斤A1

50桶牛奶每天第四頁，共三十三頁，2022年，8月28日模型求解

軟件實現(xiàn)

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元.第五頁，共三十三頁，2022年，8月28日如何裝運，使本次飛行獲利最大？

三個貨艙最大載重(t),最大容積(m3)

例2貨機裝運

重量（t）體積(m3/t）利潤（元/t）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個貨艙中實際載重必須與其最大載重成比例.

前倉：10；6800中倉：16；8700后倉：8；5300飛機平衡第六頁，共三十三頁，2022年，8月28日WET=(10,16,8),VOL=(6800,8700,5300);w=(18,15,23,12),v=(480,650,580,390),p=(3100,3800,3500,2850).已知參數(shù)i=1,2,3,4（貨物）j=1,2,3(分別代表前、中、后倉)貨艙j的重量限制WETj體積限制VOLj第i種貨物的重量wi，單位重量的體積vi，利潤pi貨機裝運第七頁，共三十三頁，2022年，8月28日決策變量

xij--第i種貨物裝入第j個貨艙的重量(t）i=1,2,3,4,

j=1,2,3(分別代表前、中、后倉)模型假設(shè)每種貨物可以分割到任意?。回洐C裝運每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；所給出的數(shù)據(jù)都是精確的，沒有誤差.

模型建立第八頁，共三十三頁，2022年，8月28日貨艙容積

目標(biāo)函數(shù)(利潤)約束條件貨機裝運模型建立貨艙重量

10；680016；87008；5300xij--第i種貨物裝入第j個貨艙的重量第九頁，共三十三頁，2022年，8月28日約束條件平衡要求

貨物供應(yīng)

貨機裝運模型建立10；680016；87008；5300xij--第i種貨物裝入第j個貨艙的重量j,k=1,2,3;j≠k

第十頁，共三十三頁，2022年，8月28日!定義集合及變量;sets:cang/1..3/:WET,VOL;wu/1..4/:w,v,p;link(wu,cang):x;endsets!對已知變量賦值;data:WET=10,16,8;VOL=6800,8700,5300;w=18,15,23,12;v=480,650,580,390;p=3100,3800,3500,2850;enddatamax=@sum(wu(i):p(i)*@sum(cang(j):x(i,j)));@for(wu(i):@sum(cang(j):x(i,j))<w(i));@for(cang(j):@sum(wu(i):x(i,j))<WET(j));@for(cang(j):@sum(wu(i):v(i)*x(i,j))<VOL(j));@for(cang(j):

@for(cang(k)|k#GT#j: !#GT#是大于等于的含義; @sum(wu(i):x(i,j)/WET(j))=@sum(wu(i):x(i,k)/WET(k))););END貨機裝運LINGO程序第十一頁，共三十三頁，2022年，8月28日

Globaloptimalsolutionfound.Objectivevalue:121515.8Totalsolveriterations:12VariableValueReducedCostX(1,1)0.000000400.0000X(1,2)0.00000057.89474X(1,3)0.000000400.0000X(2,1)7.0000000.000000X(2,2)0.000000239.4737X(2,3)8.0000000.000000X(3,1)3.0000000.000000X(3,2)12.947370.000000X(3,3)0.0000000.000000X(4,1)0.000000650.0000X(4,2)3.0526320.000000X(4,3)0.000000650.0000貨物2：前倉7,后倉8；

貨物3:前倉3,中倉13；貨物4:中倉3.貨機裝運模型求解最大利潤約121516元第十二頁，共三十三頁，2022年，8月28日如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變？例1汽車廠生產(chǎn)計劃汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量.小型中型大型現(xiàn)有量鋼材（t）1.535600勞動時間（h）28025040060000利潤（萬元）234制訂月生產(chǎn)計劃，使工廠的利潤最大.4.3

汽車生產(chǎn)與原油采購第十三頁，共三十三頁，2022年，8月28日IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000IP結(jié)果輸出設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3第十四頁，共三十三頁，2022年，8月28日其中3個子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個LP子模型汽車廠生產(chǎn)計劃若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z=610第十五頁，共三十三頁，2022年，8月28日LINGO中對0-1變量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù),本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

第十六頁，共三十三頁，2022年，8月28日max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;x1*(x1-80)>0;x2*(x2-80)>0;x3*(x3-80)>0;@gin(x1);@gin(x2);@gin(x3);方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡記NLP）

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前.一般地，整數(shù)規(guī)劃和非線性規(guī)劃的求解比線性規(guī)劃困難得多，特別是問題規(guī)模較大或者要求得到全局最優(yōu)解時.

第十七頁，共三十三頁，2022年，8月28日汽車廠生產(chǎn)計劃決策變量為整數(shù),建立整數(shù)規(guī)劃模型.求解整數(shù)規(guī)劃和非線性規(guī)劃比線性規(guī)劃困難得多(即便用數(shù)學(xué)軟件).當(dāng)整數(shù)變量取值很大時,可作為連續(xù)變量處理,問題簡化為線性規(guī)劃.

對于類似于“x=0或

80”這樣的條件，通常引入0-1變量處理，盡量不用非線性規(guī)劃（特別是引入的整數(shù)變量個數(shù)較少時）.第十八頁，共三十三頁，2022年，8月28日應(yīng)如何安排原油的采購和加工

？

例2原油采購與加工市場上可買到不超過1500t的原油A：購買量不超過500t時的單價為10000元/t；購買量超過500t但不超過1000t時，超過500t的部分8000元/t；購買量超過1000t時，超過1000t的部分6000元/t.售價4800元/t售價5600元/t庫存500t庫存1000t汽油甲(A50%)原油A原油B汽油乙(A60%)第十九頁，共三十三頁，2022年，8月28日決策變量

目標(biāo)函數(shù)問題分析利潤：銷售汽油的收入購買原油A的支出.難點：原油A的購價與購買量的關(guān)系較復(fù)雜.甲(A50%)AB乙(A60%)購買xx11x12x21x224.8千元/t5.6千元/t原油A的購買量,原油A,B生產(chǎn)汽油甲,乙的數(shù)量c(x)~購買原油A的支出利潤(千元)c(x)如何表述？第二十頁，共三十三頁，2022年，8月28日原油供應(yīng)

約束條件x

500t單價為10千元/t；500tx1000t，超過500t的8千元/t；1000tx1500t，超過1000t的6千元/t.目標(biāo)函數(shù)購買xABx11x12x21x22庫存500t庫存1000t第二十一頁，共三十三頁，2022年，8月28日目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；對于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解；想辦法將模型化簡，用現(xiàn)成的軟件求解.

汽油含原油A的比例限制約束條件甲(A50%)AB乙(A60%)x11x12x21x22第二十二頁，共三十三頁，2022年，8月28日x1,x2,x3~以價格10,8,6(千元/t)采購A的噸數(shù)目標(biāo)函數(shù)

只有當(dāng)以10千元/t的價格購買x1=500(t)時，才能以8千元/t的價格購買x2方法1

非線性規(guī)劃模型，可以用LINGO求解模型求解x=x1+x2+x3,c(x)=10x1+8x2+6x3

500t

x1000t，超過500t的8千元/t增加約束x=x1+x2+x3,c(x)=10x1+8x2+6x3

類似地有第二十三頁，共三十三頁，2022年，8月28日方法1：LINGO求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12<x+500;x21+x22<1000;x11-x21>0;2*x12-3*x22>0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1<500;x2<500;x3<500;end

Localoptimalsolutionfound.Objectivevalue:4800.000Totalsolveriterations:14VariableValueReducedCostX11500.00000.000000X21500.00000.000000X120.0000000.2666667X220.0000000.000000X10.0000000.4000000X20.0000000.000000X30.0000000.000000X0.0000000.000000LINGO得到的是局部最優(yōu)解,還能得到更好的解嗎？

用庫存的500t原油A、500t原油B生產(chǎn)汽油甲，不購買新的原油A，利潤為4800千元.

第二十四頁，共三十三頁，2022年，8月28日方法1：LINGO求解計算全局最優(yōu)解：選LINGO|Options菜單；在彈出的選項卡中選擇“GeneralSolver”；然后找到選項“UseGlobalSolver”將其選中；應(yīng)用或保存；重新求解。

Globaloptimalsolutionfound.Objectivevalue:5000.000Extendedsolversteps:1Totalsolveriterations:43VariableValueReducedCost

X110.0000000.000000X210.0000000.900000X121500.0000.000000X221000.0000.000000X1500.00000.000000X2500.00000.000000X30.0000000.000000X1000.0000.000000

還有其他建模和求解方法嗎？

購買1000t原油A，與庫存的500t原油A和1000t原油B一起，共生產(chǎn)2500t汽油乙，利潤為5000千元

.

第二十五頁，共三十三頁，2022年，8月28日y1,y2,y3=1~以價格10,8,6(千元/t)采購A增加約束方法2

0-1線性規(guī)劃模型,可用LINGO求解.y1,y2,y3=0或1購買1000t原油A，與庫存的500t原油A和1000t原油B一起，生產(chǎn)汽油乙，利潤為5000千元.x1,x2,x3~以價格10,8,6(千元/t)采購A的噸數(shù)y=0x=0x>0y=1與方法1（全局最優(yōu)解）的結(jié)果相同引入0-1變量模型求解第二十六頁，共三十三頁，2022年，8月28日b1b2

b3

b4方法3

b1

xb2，x=z1b1+z2b2，z1+z2=1，z1,z20,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000O50010001500b2

xb3，x=z2b2+z3b3，z2+z3=1，z2,z3

0,c(x)=z2c(b2)+z3c(b3).b3

xb4，x=z3b3+z4b4，z3+z4=1，z3,z4

0,c(x)=z3c(b3)+z4c(b4).直接處理分段線性函數(shù)c(x)第二十七頁，共三十三頁，2022年，8月28日IP模型，LINGO求解，得到的結(jié)果與方法2相同.bkxbk+1yk=1,否則,yk=0方法3

bkxbk+1,x=zkbk+zk+1bk+1zk+zk+1=1，zk,zk+10,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x1200090005000O50010001500b1b2

b3

b4對于k=1,2,3第二十八頁，共三十三頁，2022年，8月28日

方法3:直接處理分段線性函數(shù)，方法更具一般性.

分段函數(shù)無法直接用非