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

數(shù)學(xué)規(guī)劃模型第一頁，共二十六頁，編輯于2023年，星期三數(shù)學(xué)規(guī)劃模型

實(shí)際問題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件多元函數(shù)條件極值n和m較大最優(yōu)解在邊界上取得數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃本課程重點(diǎn)：模型的建立和結(jié)果的分析不等式約束無法用微分法求解第二頁，共二十六頁，編輯于2023年，星期三優(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ī)劃(PIP),混合整數(shù)規(guī)劃(MIP)一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學(xué)規(guī)劃第三頁，共二十六頁，編輯于2023年，星期三優(yōu)化模型的簡單分類和求解難度

優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃問題求解的難度增加

第四頁，共二十六頁，編輯于2023年，星期三企業(yè)生產(chǎn)計(jì)劃4.1奶制品的生產(chǎn)與銷售

空間層次工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車間級：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。時(shí)間層次若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可制訂單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。本節(jié)課題第五頁，共二十六頁，編輯于2023年，星期三例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

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

制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天：第六頁，共二十六頁，編輯于2023年，星期三1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

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

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

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

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

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

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

50桶牛奶每天第七頁，共二十六頁，編輯于2023年，星期三模型分析與假設(shè)

比例性可加性連續(xù)性xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對約束條件的“貢獻(xiàn)”與xi取值成正比xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān)xi對約束條件的“貢獻(xiàn)”與xj取值無關(guān)xi取值連續(xù)A1,A2每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與相互產(chǎn)量無關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)線性規(guī)劃模型第八頁，共二十六頁，編輯于2023年，星期三模型求解

圖解法

x1x20ABCDl1l2l3l4l5約束條件目標(biāo)函數(shù)

Z=0Z=2400Z=3600z=c(常數(shù))~等值線c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。第九頁，共二十六頁，編輯于2023年，星期三模型求解

軟件實(shí)現(xiàn)

LINGO10.0[obj]max=72*x1+64*x2;[st1]x1+x2<50;[st2]12*x1+8*x2<480;[st3]3*x1<100;

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ3360.0001.000000ST10.00000048.00000ST20.0000002.000000ST340.000000.00000020桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。迭代2次第十頁，共二十六頁，編輯于2023年，星期三運(yùn)行狀態(tài)窗口Variables（變量數(shù)量）：變量總數(shù)（Total）、非線性變量數(shù)（Nonlinear）、整數(shù)變量數(shù)（Integer）。Constraints（約束數(shù)量）：約束總數(shù)（Total）、非線性約束個(gè)數(shù)(Nonlinear)。Nonzeros（非零系數(shù)數(shù)量）：總數(shù)（Total）、非線性項(xiàng)系數(shù)個(gè)數(shù)(Nonlinear)。GeneratorMemoryUsed(K)(內(nèi)存使用量)ElapsedRuntime(hh:mm:ss)（求解花費(fèi)的時(shí)間）第十一頁，共二十六頁，編輯于2023年，星期三運(yùn)行狀態(tài)窗口求解器(求解程序)狀態(tài)框當(dāng)前模型的類型:LP，QP，ILP，IQP，PILP，PIQP，NLP，INLP，PINLP（以I開頭表示IP，以PI開頭表示PIP）當(dāng)前解的狀態(tài):"GlobalOptimum","LocalOptimum","Feasible","Infeasible“(不可行),"Unbounded“(無界),"Interrupted“(中斷),"Undetermined“(未確定)解的目標(biāo)函數(shù)值當(dāng)前約束不滿足的總量(不是不滿足的約束的個(gè)數(shù)):實(shí)數(shù)（即使該值=0，當(dāng)前解也可能不可行，因?yàn)檫@個(gè)量中沒有考慮用上下界命令形式給出的約束）目前為止的迭代次數(shù)第十二頁，共二十六頁，編輯于2023年，星期三運(yùn)行狀態(tài)窗口擴(kuò)展的求解器(求解程序)狀態(tài)框使用的特殊求解程序:B-and-B(分枝定界算法)Global(全局最優(yōu)求解程序)Multistart(用多個(gè)初始點(diǎn)求解的程序)目前為止找到的可行解的最佳目標(biāo)函數(shù)值目標(biāo)函數(shù)值的界特殊求解程序當(dāng)前運(yùn)行步數(shù)：分枝數(shù)(對B-and-B程序)；子問題數(shù)(對Global程序)；初始點(diǎn)數(shù)(對Multistart程序)有效步數(shù)第十三頁，共二十六頁，編輯于2023年，星期三注：凡是可以從一個(gè)約束直接解出變量取值時(shí)，這個(gè)變量就不認(rèn)為是決策變量而是固定變量，不列入統(tǒng)計(jì)中；只含有固定變量的約束也不列入約束統(tǒng)計(jì)中。運(yùn)行狀態(tài)窗口第十四頁，共二十六頁，編輯于2023年，星期三結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ3360.0001.000000ST10.00000048.00000

ST20.0000002.000000

ST340.000000.000000原料無剩余時(shí)間無剩余加工能力剩余40[obj]max=72*x1+64*x2;[st1]x1+x2<50;[st2]12*x1+8*x2<480;[st3]3*x1<100;三種資源“資源”剩余為零的約束為緊約束（有效約束）第十五頁，共二十六頁，編輯于2023年，星期三Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ

3360.0001.000000ST10.00000048.00000ST20.0000002.000000ST340.000000.000000結(jié)果解釋

最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤增長48時(shí)間增加1單位,利潤增長2加工能力增長不影響利潤影子價(jià)格35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？2元！第十六頁，共二十六頁，編輯于2023年，星期三第十七頁，共二十六頁，編輯于2023年，星期三

Rangesinwhichthebasisisunchanged:

ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseST150.0000010.000006.666667ST2480.000053.3333380.00000ST3100.0000INFINITY40.00000最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)第十八頁，共二十六頁，編輯于2023年，星期三結(jié)果解釋

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseST150.0000010.000006.666667ST2480.000053.3333380.00000ST3100.0000INFINITY40.00000影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標(biāo)函數(shù)不變)加工能力可任意增加原料最多減少10時(shí)間最多減少53加工能力最多減少40第十九頁，共二十六頁，編輯于2023年，星期三例2奶制品的生產(chǎn)銷售計(jì)劃

在例1基礎(chǔ)上深加工1桶牛奶3千克A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤0.8千克B12小時(shí),3元1千克獲利44元/千克0.75千克B22小時(shí),3元1千克獲利32元/千克制訂生產(chǎn)計(jì)劃，使每天凈利潤最大30元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶,480小時(shí)至多100公斤A1

B1，B2的獲利經(jīng)常有10%的波動(dòng)，對計(jì)劃有無影響？第二十頁，共二十六頁，編輯于2023年，星期三1桶牛奶

3千克A1

12小時(shí)8小時(shí)4千克A2

或獲利24元/千克獲利16元/kg

0.8千克

B12小時(shí),3元1千克獲利44元/千克0.75千克B22小時(shí),3元1千克獲利32元/千克出售x1千克A1,

x2千克A2，

X3千克B1,x4千克B2原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

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

利潤約束條件非負(fù)約束

x5千克A1加工B1，x6千克A2加工B2附加約束

第二十一頁，共二十六頁，編輯于2023年，星期三模型求解

軟件實(shí)現(xiàn)

LINGO10.0[obj]max=24*x1+16*x2+44*x3+32*x4-3*x5-3*x6;[st1]4*x1+3*x2+4*x5+3*x6<=600;[st2]4*x1+2*x2+6*x5+4*x6<=480;[st3]x1+x5<=100;[st4]x3=0.8*x5;[st5]x4=0.75*x6;第二十二頁，共二十六頁，編輯于2023年，星期三LINGO10.0模型求解

軟件實(shí)現(xiàn)

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000

X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000ST376.000000.000000ST40.00000044.00000ST50.00000032.00000“ReducedCost”列出最優(yōu)單純形表中判別數(shù)所在行的變量的系數(shù)，表示當(dāng)變量有微小變動(dòng)時(shí),目標(biāo)函數(shù)的變化率。其中基變量的reducedcost值應(yīng)為0，對于非基變量Xj,相應(yīng)的reducedcost值表示當(dāng)某個(gè)變量Xj增加一個(gè)單位時(shí)目標(biāo)函數(shù)減少的量(max型問題)。本例中：變量X1對應(yīng)的reducedcost值為1.68，表示當(dāng)非基變量X1的值從0變?yōu)?時(shí)（此時(shí)假定其他非基變量保持不變,但為了滿足約束條件，基變量顯然會發(fā)生變化），最優(yōu)的目標(biāo)函數(shù)值=3460.8–1.68=3459.12。(基本不用它)第二十三頁，共二十六頁，編輯于2023年，星期三

Globaloptimalsolutionfound.

Objectivevalue:3460.800Totalsolveriterations:2

VariableValueReducedCost

X10.0000001.680000

X2168.00000.000000

X319.200000.000000

X40.0000000.000000

X524.000000.000000

X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000ST376.000000.000000ST40.00000044.00000ST50.00000032.00000結(jié)果解釋每天銷售168千克A2和19.2千克B1，利潤3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24千克A1全部加工成B1

除加工能力外均為緊約束第二十四頁，共二十六頁，編輯于2023年，星期三結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000

X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000