數(shù)學(xué)模型：第四章 數(shù)學(xué)規(guī)劃模型

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

4.1奶制品的生產(chǎn)與銷售4.2自來水輸送與貨機(jī)裝運(yùn)4.3汽車生產(chǎn)與原油采購(gòu)4.4接力隊(duì)選拔和選課策略數(shù)學(xué)規(guī)劃模型

實(shí)際問題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件多元函數(shù)條件極值決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)m較大最優(yōu)解在可行域的邊界上取得數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃重點(diǎn)在模型的建立和結(jié)果的分析鏈接:/s/1o7IkogM密碼:kfxuLingo軟件下載及相關(guān)資料企業(yè)生產(chǎn)計(jì)劃4.1奶制品的生產(chǎn)與銷售

空間層次工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車間級(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é)課題例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ì)劃？每天：?jiǎn)栴}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桶牛奶每天基本模型模型分析與假設(shè)

比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對(duì)約束條件的“貢獻(xiàn)”與xi取值成正比xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān)xi對(duì)約束條件的“貢獻(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ī)劃模型模型求解

圖解法

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)取得。模型求解

軟件實(shí)現(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，利潤(rùn)3360元。結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無剩余時(shí)間無剩余加工能力剩余40結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量影子價(jià)格35元可買到1桶牛奶，要買嗎?35<48,應(yīng)該買！

聘用臨時(shí)工人付出的工資最多每小時(shí)幾元?2元！原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000

最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍敏感性分析

(“LINGO|Ranges”)

x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)

A1獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃?x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加5335元可買到1桶牛奶,每天最多買多少?最多買10桶!(目標(biāo)函數(shù)不變)充分條件!例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ì)劃，使每天凈利潤(rùn)最大30元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶,480小時(shí)至多100公斤A1

B1，B2的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無影響？

每天銷售10公斤A1的合同必須滿足，對(duì)利潤(rùn)有什么影響？1桶牛奶3kgA1

12小時(shí)8小時(shí)4kgA2

或獲利24元/kg

獲利16元/kg

0.8kgB12小時(shí),3元1kg獲利44元/kg

0.75kgB22小時(shí),3元1kg獲利32元/kg

出售x1kgA1,

x2kgA2，

x3kgB1,x4kgB2原料供應(yīng)

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

加工能力

決策變量

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

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

x5kgA1加工B1，x6kgA2加工B2附加約束

基本模型模型求解

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

LINGO

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000Globaloptimalsolutionfound.Objectivevalue:3460.800

Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000

MILK0.0000003.160000

TIME0.0000003.260000

CPCT76.000000.000000

50.00000044.00000

60.00000032.00000結(jié)果解釋每天銷售168kgA2和19.2kgB1，利潤(rùn)3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24kgA1全部加工成B1

除加工能力外均為緊約束結(jié)果解釋Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000

MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000增加1桶牛奶使利潤(rùn)增長(zhǎng)3.16×12=37.92增加1小時(shí)時(shí)間使利潤(rùn)增長(zhǎng)3.2630元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？投資150元增加5桶牛奶,可賺回189.6元。(大于增加時(shí)間的利潤(rùn)增長(zhǎng))結(jié)果解釋B1,B2的獲利有10%的波動(dòng)，對(duì)計(jì)劃有無影響Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX124.0000001.680000INFINITYX216.0000008.1500002.100000

X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY

……

……敏感性分析

B1獲利下降10%，超出X3系數(shù)允許范圍B2獲利上升10%，超出X4系數(shù)允許范圍波動(dòng)對(duì)計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為39.6計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化。Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000結(jié)果解釋x1從0開始增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值將減少1.68ReducedCost有意義也是有條件的(LINGO沒有給出)每天銷售10公斤A1的合同必須滿足，對(duì)利潤(rùn)有什么影響？公司利潤(rùn)減少1.68×10=16.8（元）最優(yōu)利潤(rùn)為3460.8–16.8=3444

奶制品的生產(chǎn)與銷售

由于產(chǎn)品利潤(rùn)、加工時(shí)間等均為常數(shù)，可建立線性規(guī)劃模型.

線性規(guī)劃模型的三要素：決策變量、目標(biāo)函數(shù)、約束條件.

用LINGO求解，輸出豐富，利用影子價(jià)格和靈敏性分析可對(duì)結(jié)果做進(jìn)一步研究.

建模時(shí)盡可能利用原始的數(shù)據(jù)信息，把盡量多的計(jì)算留給計(jì)算機(jī)去做（分析例2的建模）.4.2

自來水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大?運(yùn)輸問題各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少?其他費(fèi)用:450元/千噸

應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？

若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)例1

自來水輸送收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫(kù)供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計(jì)）總供水量：160確定送水方案使利潤(rùn)最大問題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40<總需求量：120+180=300總收入900160=144,000(元)收入：900元/千噸

其他費(fèi)用:450元/千噸

支出引水管理費(fèi)其他支出450160=72,000(元)使引水管理費(fèi)最小供應(yīng)限制約束條件需求限制

線性規(guī)劃模型(LP)目標(biāo)函數(shù)

水庫(kù)i向j區(qū)的日供水量為xij（x34=0）決策變量

模型建立確定3個(gè)水庫(kù)向4個(gè)小區(qū)的供水量模型求解

部分結(jié)果：ObjectiveValue:24400.00VariableValueReducedCostX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利潤(rùn)=總收入-其它費(fèi)用-引水管理費(fèi)=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理費(fèi)24400(元)目標(biāo)函數(shù)

總供水量(320)>總需求量(300)每個(gè)水庫(kù)最大供水量都提高一倍利潤(rùn)=收入(900)–其它費(fèi)用(450)

–引水管理費(fèi)利潤(rùn)(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/供應(yīng)限制B,C類似處理問題討論

確定送水方案使利潤(rùn)最大需求約束可以不變求解部分結(jié)果：ObjectiveValue:88700.00VariableValueReducedCost

X110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X3150.0000000.000000X320.00000020.000000X3330.0000000.000000運(yùn)輸問題總利潤(rùn)88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030供應(yīng)點(diǎn)需求點(diǎn)物資供需平衡或不平衡如何裝運(yùn)，使本次飛行獲利最大？

三個(gè)貨艙最大載重(噸),最大容積(米3)

例2貨機(jī)裝運(yùn)

重量（噸）空間(米3/噸）利潤(rùn)（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大載重成比例.

前倉(cāng)：10；6800中倉(cāng)：16；8700后倉(cāng)：8；5300飛機(jī)平衡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(分別代表前、中、后倉(cāng))貨艙j的重量限制WETj體積限制VOLj第i種貨物的重量wi，體積vi，利潤(rùn)pi貨機(jī)裝運(yùn)決策變量

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

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

模型建立貨艙容積

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

10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量約束條件平衡要求

貨物供應(yīng)

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

!定義集合及變量;sets:cang/1..3/:WET,VOL;wu/1..4/:w,v,p;link(wu,cang):x;endsets!對(duì)已知變量賦值;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貨機(jī)裝運(yùn)LINGO程序

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：前倉(cāng)7,后倉(cāng)8；

貨物3:前倉(cāng)3,中倉(cāng)13；貨物4:中倉(cāng)3。貨機(jī)裝運(yùn)模型求解最大利潤(rùn)約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)裝載平衡要求運(yùn)輸問題運(yùn)輸問題的擴(kuò)展

如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例1汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量.

小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動(dòng)時(shí)間（小時(shí)）28025040060000利潤(rùn)（萬(wàn)元）234

制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大.4.3

汽車生產(chǎn)與原油采購(gòu)設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)模型求解

3）模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大.2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過比較可能得到更優(yōu)的解.

但必須檢驗(yàn)它們是否滿足約束條件.為什么？IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=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.000000模型求解

IP結(jié)果輸出其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型汽車廠生產(chǎn)計(jì)劃

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

80

x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610LINGO中對(duì)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)計(jì)劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

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，簡(jiǎn)記NLP）

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

80x2=0或

80x3=0或

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

汽車廠生產(chǎn)計(jì)劃

決策變量為整數(shù),建立整數(shù)規(guī)劃模型.

求解整數(shù)規(guī)劃和非線性規(guī)劃比線性規(guī)劃困難得多(即便用數(shù)學(xué)軟件).

當(dāng)整數(shù)變量取值很大時(shí),可作為連續(xù)變量處理,問題簡(jiǎn)化為線性規(guī)劃.

對(duì)于類似于“x=0或

80”這樣的條件，通常引入0-1變量處理，盡量不用非線性規(guī)劃（特別是引入的整數(shù)變量個(gè)數(shù)較少時(shí)）.應(yīng)如何安排原油的采購(gòu)和加工

？

例2原油采購(gòu)與加工市場(chǎng)上可買到不超過1500噸的原油A：購(gòu)買量不超過500噸時(shí)的單價(jià)為10000元/噸；購(gòu)買量超過500噸但不超過1000噸時(shí)，超過500噸的部分8000元/噸；購(gòu)買量超過1000噸時(shí)，超過1000噸的部分6000元/噸.售價(jià)4800元/噸售價(jià)5600元/噸庫(kù)存500噸庫(kù)存1000噸汽油甲(A

50%)原油A原油B汽油乙(A

60%)決策變量

目標(biāo)函數(shù)問題分析

利潤(rùn)：銷售汽油的收入

購(gòu)買原油A的支出.

難點(diǎn)：原油A的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜.甲(A

50%)AB乙(A

60%)購(gòu)買x

x11x12x21x224.8千元/噸5.6千元/噸原油A的購(gòu)買量,原油A,B生產(chǎn)汽油甲,乙的數(shù)量c(x)~購(gòu)買原油A的支出利潤(rùn)(千元)c(x)如何表述？原油供應(yīng)

約束條件x

500噸單價(jià)為10千元/噸；

500噸

x

1000噸，超過500噸的8千元/噸；1000噸

x

1500噸，超過1000噸的6千元/噸.目標(biāo)函數(shù)購(gòu)買x

ABx11x12x21x22庫(kù)存500噸庫(kù)存1000噸

目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；對(duì)于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解；想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解.

汽油含原油A的比例限制約束條件甲(A

50%)AB乙(A

60%)x11x12x21x22x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購(gòu)A的噸數(shù)目標(biāo)函數(shù)

只有當(dāng)以10千元/噸的價(jià)格購(gòu)買x1=500(噸)時(shí)，才能以8千元/噸的價(jià)格購(gòu)買x2方法1

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

500噸

x

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

類似地有方法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)解,還能得到更好的解嗎？

用庫(kù)存的500噸原油A、500噸原油B生產(chǎn)汽油甲，不購(gòu)買新的原油A，利潤(rùn)為4800千元。

方法1：LINGO求解計(jì)算全局最優(yōu)解：選LINGO|Options菜單；在彈出的選項(xiàng)卡中選擇“GeneralSolver”；然后找到選項(xiàng)“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

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

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

。

y1,y2,y3=1~以價(jià)格10,8,6(千元/噸)采購(gòu)A增加約束方法2

0-1線性規(guī)劃模型,可用LINGO求解.y1,y2,y3=0或1購(gòu)買1000噸原油A，與庫(kù)存的500噸原油A和1000噸原油B一起，生產(chǎn)汽油乙，利潤(rùn)為5000千元。x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購(gòu)A的噸數(shù)y=0x=0x>0

y=1與方法1（全局最優(yōu)解）的結(jié)果相同引入0-1變量b1b2

b3

b4方法3

b1

x

b2，x=z1b1+z2b2，z1+z2=1，z1,z2

0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2

x

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

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

x

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

0,c(x)=z3c(b3)+z4c(b4).

直接處理處理分段線性函數(shù)c(x)IP模型，LINGO求解，得到的結(jié)果與方法2相同.bk

x

bk+1

yk=1,否則,yk=0方法3

bk

x

bk+1,x=zkbk+zk+1bk+1zk+zk+1=1，zk,zk+1

0,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x1200090005000050010001500b1b2

b3

b4對(duì)于k=1,2,3

方法3:

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

分段函數(shù)無法直接用非線性規(guī)劃方法或軟件求解.原油采購(gòu)與加工

方法1:

增加約束化為非線性規(guī)劃,可以用LINGO求解,但可能得到的是局部最優(yōu)解.

方法2:

引入0-1變量,化為線性規(guī)劃模型,可用LINGO求解.分派問題4.4

接力隊(duì)選拔和選課策略

若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長(zhǎng)不同,完成每項(xiàng)任務(wù)取得的效益或需要的資源不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少?

若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個(gè)策略之間有相互制約關(guān)系，如何在滿足一定條件下作出抉擇，使得收益最大或成本最小?討論:丁的蛙泳成績(jī)退步到1’15”2；戊的自由泳成績(jī)進(jìn)步到57”5,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成4

100米混合泳接力隊(duì)?例1混合泳接力隊(duì)的選拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績(jī)窮舉法：組成接力隊(duì)的方案共有5!=120種.目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i

第j種泳姿的百米成績(jī)約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人模型求解

MODEL:sets:person/1..5/;position/1..4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;enddata輸入LINGO求解

min=@sum(link:c*x);@for(person(i):@sum(position(j):x(i,j))<=1;);@for(position(i):@sum(person(j):x(j,i))=1;);@for(link:@bin(x));END

模型求解

最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績(jī)?yōu)?53.2(秒)=4’13”2輸入LINGO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43

=69.6

75.2(秒)，戊自由泳c54=62.4

57.5(秒),方案是否調(diào)整？

敏感性分析？新方案:乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP一般沒有與LP相類似的理論，LINGO輸出的敏感性分析結(jié)果通常是沒有意義的.最優(yōu)解：x21=x32=x43=x51=1,成績(jī)?yōu)?’17”7c43,c54

的新數(shù)據(jù)重新輸入模型，用LINGO求解

原分配方案:甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.討論混合泳接力隊(duì)的選拔指派(Assignment)問題：有若干項(xiàng)任務(wù),

每項(xiàng)任務(wù)必有且只能有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)，不同人員承擔(dān)不同任務(wù)的效益(或成本)不同，怎樣分派各項(xiàng)任務(wù)使總效益最大(或總成本最小)?

人員數(shù)量與任務(wù)數(shù)量相等

人員數(shù)量大于任務(wù)數(shù)量(本例)

人員數(shù)量小于任務(wù)數(shù)量

?建立0-1規(guī)劃模型是常用方法為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？

例2選課策略要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課課號(hào)課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)

2線性代數(shù)4數(shù)學(xué)

3最優(yōu)化方法4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)6計(jì)算機(jī)模擬3計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)編程7計(jì)算機(jī)編程2計(jì)算機(jī)

8預(yù)測(cè)理論2運(yùn)籌學(xué)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線性代數(shù)選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？

0-1規(guī)劃模型

決策變量

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

xi=1~選修課號(hào)i的課程（xi=0~不選）

選修課程總數(shù)最少約束條件最少2門數(shù)學(xué)課，3門運(yùn)籌學(xué)課，2門計(jì)算機(jī)課.課號(hào)課名所屬類別1微積分?jǐn)?shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運(yùn)籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計(jì)算機(jī)5應(yīng)用統(tǒng)計(jì)數(shù)學(xué)；運(yùn)籌學(xué)6計(jì)算機(jī)模擬計(jì)算機(jī)；運(yùn)籌學(xué)7計(jì)算機(jī)編程計(jì)算機(jī)8預(yù)測(cè)理論運(yùn)籌學(xué)9數(shù)學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)；計(jì)算機(jī)