數(shù)模 數(shù)學(xué)規(guī)劃模型_第1頁
數(shù)模 數(shù)學(xué)規(guī)劃模型_第2頁
數(shù)模 數(shù)學(xué)規(guī)劃模型_第3頁
數(shù)模 數(shù)學(xué)規(guī)劃模型_第4頁
數(shù)模 數(shù)學(xué)規(guī)劃模型_第5頁
已閱讀5頁,還剩80頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

數(shù)模數(shù)學(xué)規(guī)劃模型第1頁,課件共85頁,創(chuàng)作于2023年2月數(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é)果的分析第2頁,課件共85頁,創(chuàng)作于2023年2月企業(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é)課題第3頁,課件共85頁,創(chuàng)作于2023年2月例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ì)劃?每天:第4頁,課件共85頁,創(chuàng)作于2023年2月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)

勞動時(shí)間

加工能力

決策變量

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

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

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

50桶牛奶每天第5頁,課件共85頁,創(chuàng)作于2023年2月模型分析與假設(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ī)劃模型第6頁,課件共85頁,創(chuàng)作于2023年2月模型求解

圖解法

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)取得。第7頁,課件共85頁,創(chuàng)作于2023年2月模型求解

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

LINDO6.1max72x1+64x2st2)x1+x2<503)12x1+8x2<4804)3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2,利潤3360元。第8頁,課件共85頁,創(chuàng)作于2023年2月結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料無剩余時(shí)間無剩余加工能力剩余40max72x1+64x2st2)x1+x2<503)12x1+8x2<4804)3x1<100end三種資源“資源”剩余為零的約束為緊約束(有效約束)第9頁,課件共85頁,創(chuàng)作于2023年2月結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤增長48時(shí)間增加1單位,利潤增長2加工能力增長不影響利潤影子價(jià)格

35元可買到1桶牛奶,要買嗎?35<48,應(yīng)該買!聘用臨時(shí)工人付出的工資最多每小時(shí)幾元?2元!第10頁,課件共85頁,創(chuàng)作于2023年2月RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

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

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

A1獲利增加到30元/千克,應(yīng)否改變生產(chǎn)計(jì)劃x1系數(shù)由243=72增加為303=90,在允許范圍內(nèi)不變!(約束條件不變)第11頁,課件共85頁,創(chuàng)作于2023年2月結(jié)果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加53

35元可買到1桶牛奶,每天最多買多少?最多買10桶!(目標(biāo)函數(shù)不變)第12頁,課件共85頁,創(chuàng)作于2023年2月例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%的波動,對計(jì)劃有無影響?第13頁,課件共85頁,創(chuàng)作于2023年2月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)

勞動時(shí)間

加工能力

決策變量

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

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

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

第14頁,課件共85頁,創(chuàng)作于2023年2月模型求解

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

LINDO6.1

OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No第15頁,課件共85頁,創(chuàng)作于2023年2月

OBJECTIVEFUNCTIONVALUE1)3460.800

VARIABLEVALUEREDUCEDCOST

X10.0000001.680000

X2168.0000000.000000

X319.2000010.000000

X40.0000000.000000

X524.0000000.000000

X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2結(jié)果解釋每天銷售168千克A2和19.2千克B1,利潤3460.8(元)8桶牛奶加工成A1,42桶牛奶加工成A2,將得到的24千克A1全部加工成B1

除加工能力外均為緊約束第16頁,課件共85頁,創(chuàng)作于2023年2月結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000增加1桶牛奶使利潤增長3.16×12=37.92增加1小時(shí)時(shí)間使利潤增長3.2630元可增加1桶牛奶,3元可增加1小時(shí)時(shí)間,應(yīng)否投資?現(xiàn)投資150元,可賺回多少?投資150元增加5桶牛奶,可賺回189.6元。(大于增加時(shí)間的利潤增長)第17頁,課件共85頁,創(chuàng)作于2023年2月結(jié)果解釋B1,B2的獲利有10%的波動,對計(jì)劃有無影響

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000

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

…………DORANGE(SENSITIVITY)ANALYSIS?YesB1獲利下降10%,超出X3系數(shù)允許范圍B2獲利上升10%,超出X4系數(shù)允許范圍波動對計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂:如將x3的系數(shù)改為39.6計(jì)算,會發(fā)現(xiàn)結(jié)果有很大變化。第18頁,課件共85頁,創(chuàng)作于2023年2月4.2

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

應(yīng)如何分配水庫供水量,公司才能獲利最多?

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

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

支出A:50B:60C:50甲:30;50乙:70;70丙:10;20?。?0;40水庫供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)(以天計(jì))第20頁,課件共85頁,創(chuàng)作于2023年2月總供水量:160確定送水方案使利潤最大問題分析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)最小第21頁,課件共85頁,創(chuàng)作于2023年2月供應(yīng)限制約束條件需求限制

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

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

模型建立確定3個(gè)水庫向4個(gè)小區(qū)的供水量第22頁,課件共85頁,創(chuàng)作于2023年2月模型求解

OBJECTIVEFUNCTIONVALUE1)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利潤=總收入-其它費(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(元)第23頁,課件共85頁,創(chuàng)作于2023年2月目標(biāo)函數(shù)

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

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

確定送水方案使利潤最大需求約束可以不變第24頁,課件共85頁,創(chuàng)作于2023年2月求解

OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X31

50.0000000.000000X320.00000020.000000X33

30.0000000.000000這類問題一般稱為“運(yùn)輸問題”(TransportationProblem)總利潤88700(元)

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030第25頁,課件共85頁,創(chuàng)作于2023年2月如何裝運(yùn),使本次飛行獲利最大?

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

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

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

前倉:10;6800中倉:16;8700后倉:8;5300飛機(jī)平衡第26頁,課件共85頁,創(chuàng)作于2023年2月決策變量

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

j=1,2,3(分別代表前、中、后倉)模型假設(shè)每種貨物可以分割到任意??;貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布;多種貨物可以混裝,并保證不留空隙;模型建立第27頁,課件共85頁,創(chuàng)作于2023年2月貨艙容積

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

10;680016;87008;5300xij--第i種貨物裝入第j個(gè)貨艙的重量第28頁,課件共85頁,創(chuàng)作于2023年2月約束條件平衡要求

貨物供應(yīng)

貨機(jī)裝運(yùn)模型建立10;680016;87008;5300xij--第i種貨物裝入第j個(gè)貨艙的重量第29頁,課件共85頁,創(chuàng)作于2023年2月

OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000

X32

12.9473690.000000X33

3.0000000.000000X410.000000650.000000

X423.0526320.000000X430.000000650.000000貨物2:前倉10,后倉5;

貨物3:中倉13,后倉3;貨物4:中倉3。貨機(jī)裝運(yùn)模型求解最大利潤約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)平衡要求運(yùn)輸問題運(yùn)輸問題的擴(kuò)展第30頁,課件共85頁,創(chuàng)作于2023年2月如果生產(chǎn)某一類型汽車,則至少要生產(chǎn)80輛,那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變?例1汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)三種類型的汽車,已知各類型每輛車對鋼材、勞動時(shí)間的需求,利潤及工廠每月的現(xiàn)有量。小型中型大型現(xiàn)有量鋼材(噸)1.535600勞動時(shí)間(小時(shí))28025040060000利潤(萬元)234制訂月生產(chǎn)計(jì)劃,使工廠的利潤最大。4.3

汽車生產(chǎn)與原油采購第31頁,課件共85頁,創(chuàng)作于2023年2月設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤234線性規(guī)劃模型(LP)第32頁,課件共85頁,創(chuàng)作于2023年2月模型求解

3)

模型中增加條件:x1,x2,x3

均為整數(shù),重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226結(jié)果為小數(shù),怎么辦?1)舍去小數(shù):取x1=64,x2=167,算出目標(biāo)函數(shù)值z=629,與LP最優(yōu)值632.2581相差不大。2)試探:如取x1=65,x2=167;x1=64,x2=168等,計(jì)算函數(shù)值z,通過比較可能得到更優(yōu)的解。但必須檢驗(yàn)它們是否滿足約束條件。為什么?第33頁,課件共85頁,創(chuàng)作于2023年2月IP可用LINDO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡記IP)“gin3”表示“前3個(gè)變量為整數(shù)”,等價(jià)于:ginx1ginx2ginx3IP的最優(yōu)解x1=64,x2=168,x3=0,最優(yōu)值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出第34頁,課件共85頁,創(chuàng)作于2023年2月其中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或80x1=80,x2=150,x3=0,最優(yōu)值z=610第35頁,課件共85頁,創(chuàng)作于2023年2月LINDO中對0-1變量的限定:inty1inty2inty3方法2:引入0-1變量,化為整數(shù)規(guī)劃

M為大的正數(shù),可取1000OBJECTIVEFUNCTIONVALUE1)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)解同前

第36頁,課件共85頁,創(chuàng)作于2023年2月NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAB),但是其結(jié)果常依賴于初值的選擇。方法3:化為非線性規(guī)劃

非線性規(guī)劃(Non-LinearProgramming,簡記NLP)

實(shí)踐表明,本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí),才能得到正確的結(jié)果。

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

80x2=0或

80x3=0或

80第37頁,課件共85頁,創(chuàng)作于2023年2月應(yīng)如何安排原油的采購和加工

?

例2原油采購與加工市場上可買到不超過1500噸的原油A:購買量不超過500噸時(shí)的單價(jià)為10000元/噸;購買量超過500噸但不超過1000噸時(shí),超過500噸的部分8000元/噸;購買量超過1000噸時(shí),超過1000噸的部分6000元/噸。售價(jià)4800元/噸售價(jià)5600元/噸庫存500噸庫存1000噸汽油甲(A50%)原油A原油B汽油乙(A60%)第38頁,課件共85頁,創(chuàng)作于2023年2月決策變量

目標(biāo)函數(shù)問題分析利潤:銷售汽油的收入-購買原油A的支出難點(diǎn):原油A的購價(jià)與購買量的關(guān)系較復(fù)雜甲(A50%)AB乙(A60%)購買xx11x12x21x224.8千元/噸5.6千元/噸原油A的購買量,原油A,B生產(chǎn)汽油甲,乙的數(shù)量c(x)~購買原油A的支出利潤(千元)c(x)如何表述?第39頁,課件共85頁,創(chuàng)作于2023年2月原油供應(yīng)

約束條件

x

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

500噸x1000噸,超過500噸的8千元/噸;1000噸x1500噸,超過1000噸的6千元/噸。目標(biāo)函數(shù)購買xABx11x12x21x22庫存500噸庫存1000噸第40頁,課件共85頁,創(chuàng)作于2023年2月目標(biāo)函數(shù)中c(x)不是線性函數(shù),是非線性規(guī)劃;對于用分段函數(shù)定義的c(x),一般的非線性規(guī)劃軟件也難以輸入和求解;想辦法將模型化簡,用現(xiàn)成的軟件求解。

汽油含原油A的比例限制約束條件甲(A50%)AB乙(A60%)x11x12x21x22第41頁,課件共85頁,創(chuàng)作于2023年2月x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購A的噸數(shù)目標(biāo)函數(shù)

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

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

500噸

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

第42頁,課件共85頁,創(chuàng)作于2023年2月方法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;x>0;x11>0;x12>0;x21>0;x22>0;x1>0;x2>0;x3>0;endObjectivevalue:4800.000VariableValueReducedCostX11500.00000.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00LINGO得到的是局部最優(yōu)解,還能得到更好的解嗎?

用庫存的500噸原油A、500噸原油B生產(chǎn)汽油甲,不購買新的原油A,利潤為4,800千元。

第43頁,課件共85頁,創(chuàng)作于2023年2月y1,y2,y3=1~以價(jià)格10,8,6(千元/噸)采購A增加約束方法2

0-1線性規(guī)劃模型,可用LINDO求解y1,y2,y3=0或1OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLEVALUEREDUCEDCOSTY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000購買1000噸原油A,與庫存的500噸原油A和1000噸原油B一起,生產(chǎn)汽油乙,利潤為5,000千元。x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購A的噸數(shù)y=0x=0x>0y=1優(yōu)于方法1的結(jié)果第44頁,課件共85頁,創(chuàng)作于2023年2月b1b2

b3

b4方法3

b1

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

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)第45頁,課件共85頁,創(chuàng)作于2023年2月IP模型,LINDO求解,得到的結(jié)果與方法2相同.處理分段線性函數(shù),方法3更具一般性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)x1200090005000050010001500b1b2

b3

b4對于k=1,2,3第46頁,課件共85頁,創(chuàng)作于2023年2月分派問題4.4

接力隊(duì)選拔和選課策略若干項(xiàng)任務(wù)分給一些候選人來完成,每人的專長不同,完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同,如何分派任務(wù)使獲得的總效益最大,或付出的總資源最少。若干種策略供選擇,不同的策略得到的收益或付出的成本不同,各個(gè)策略之間有相互制約關(guān)系,如何在滿足一定條件下作出決擇,使得收益最大或成本最小。第47頁,課件共85頁,創(chuàng)作于2023年2月丁的蛙泳成績退步到1’15”2;戊的自由泳成績進(jìn)步到57”5,組成接力隊(duì)的方案是否應(yīng)該調(diào)整?如何選拔隊(duì)員組成4100米混合泳接力隊(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名候選人的百米成績窮舉法:組成接力隊(duì)的方案共有5!=120種。第48頁,課件共85頁,創(chuàng)作于2023年2月目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽,記xij=1,否則記xij=0

0-1規(guī)劃模型

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

第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人第49頁,課件共85頁,創(chuàng)作于2023年2月模型求解

最優(yōu)解:x14=x21=x32=x43=1,其它變量為0;成績?yōu)?53.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14<=1

……x41+x42+x43+x44<=1x11+x21+x31+x41+x51=1

……x14+x24+x34+x44+x54=1ENDINT20

輸入LINDO求解

甲乙丙丁戊蝶泳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甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.第50頁,課件共85頁,創(chuàng)作于2023年2月丁蛙泳c43

=69.675.2,戊自由泳c54=62.4

57.5,方案是否調(diào)整?敏感性分析?乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論,LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。最優(yōu)解:x21=x32=x43=x51=1,成績?yōu)?’17”7c43,c54

的新數(shù)據(jù)重新輸入模型,用LINDO求解指派(Assignment)問題:每項(xiàng)任務(wù)有且只有一人承擔(dān),每人只能承擔(dān)一項(xiàng),效益不同,怎樣分派使總效益最大.討論甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案第51頁,課件共85頁,創(chuàng)作于2023年2月為了選修課程門數(shù)最少,應(yīng)學(xué)習(xí)哪些課程?

例2選課策略要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課課號課名學(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ù)測理論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í)哪些課程?

第52頁,課件共85頁,創(chuàng)作于2023年2月0-1規(guī)劃模型

決策變量

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

xi=1~選修課號i的課程(xi=0~不選)

選修課程總數(shù)最少約束條件最少2門數(shù)學(xué)課,3門運(yùn)籌學(xué)課,2門計(jì)算機(jī)課。

課號課名所屬類別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ù)測理論運(yùn)籌學(xué)9數(shù)學(xué)實(shí)驗(yàn)運(yùn)籌學(xué);計(jì)算機(jī)第53頁,課件共85頁,創(chuàng)作于2023年2月先修課程要求最優(yōu)解:

x1=x2=x3=x6=x7=x9=1,其它為0;6門課程,總學(xué)分210-1規(guī)劃模型

約束條件x3=1必有x1=x2=1模型求解(LINDO)課號課名先修課要求1微積分

2線性代數(shù)

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

8預(yù)測理論應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)微積分;線性代數(shù)第54頁,課件共85頁,創(chuàng)作于2023年2月學(xué)分最多多目標(biāo)優(yōu)化的處理方法:化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo))規(guī)劃

討論:選修課程最少,學(xué)分盡量多,應(yīng)學(xué)習(xí)哪些課程?課程最少以學(xué)分最多為目標(biāo),不管課程多少。以課程最少為目標(biāo),不管學(xué)分多少。最優(yōu)解如上,6門課程,總學(xué)分21。最優(yōu)解顯然是選修所有9門課程。第55頁,課件共85頁,創(chuàng)作于2023年2月多目標(biāo)規(guī)劃

在課程最少的前提下以學(xué)分最多為目標(biāo)。最優(yōu)解:

x1=x2=x3=x5=x7=x9=1,其它為0;總學(xué)分由21增至22。注意:最優(yōu)解不唯一!課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計(jì)46計(jì)算機(jī)模擬37計(jì)算機(jī)編程28預(yù)測理論29數(shù)學(xué)實(shí)驗(yàn)3LINDO無法告訴優(yōu)化問題的解是否唯一??蓪9=1易為x6=1增加約束,以學(xué)分最多為目標(biāo)求解。第56頁,課件共85頁,創(chuàng)作于2023年2月多目標(biāo)規(guī)劃

對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo),如三七開。最優(yōu)解:

x1=x2=x3=x4=x5=x6=x7=x9=1,其它為0;總學(xué)分28。課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計(jì)46計(jì)算機(jī)模擬37計(jì)算機(jī)編程28預(yù)測理論29數(shù)學(xué)實(shí)驗(yàn)3第57頁,課件共85頁,創(chuàng)作于2023年2月討論與思考最優(yōu)解與1=0,2=1的結(jié)果相同——學(xué)分最多多目標(biāo)規(guī)劃

最優(yōu)解與1=1,2=0的結(jié)果相同——課程最少第58頁,課件共85頁,創(chuàng)作于2023年2月4.5

飲料廠的生產(chǎn)與檢修單階段生產(chǎn)計(jì)劃多階段生產(chǎn)計(jì)劃生產(chǎn)批量問題企業(yè)生產(chǎn)計(jì)劃考慮與產(chǎn)量無關(guān)的固定費(fèi)用給優(yōu)化模型求解帶來新的困難外部需求和內(nèi)部資源隨時(shí)間變化第59頁,課件共85頁,創(chuàng)作于2023年2月安排生產(chǎn)計(jì)劃,滿足每周的需求,使4周總費(fèi)用最小。存貯費(fèi):每周每千箱飲料0.2千元。例1

飲料廠的生產(chǎn)與檢修計(jì)劃在4周內(nèi)安排一次設(shè)備檢修,占用當(dāng)周15千箱生產(chǎn)能力,能使檢修后每周增產(chǎn)5千箱,檢修應(yīng)排在哪一周?

周次需求量(千箱)生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計(jì)100135

某種飲料4周的需求量、生產(chǎn)能力和成本第60頁,課件共85頁,創(chuàng)作于2023年2月問題分析除第4周外每周的生產(chǎn)能力超過每周的需求;生產(chǎn)成本逐周上升;前幾周應(yīng)多生產(chǎn)一些。周次需求能力11530225403354542520合計(jì)100135成本5.05.15.45.5

飲料廠在第1周開始時(shí)沒有庫存;從費(fèi)用最小考慮,第4周末不能有庫存;周末有庫存時(shí)需支出一周的存貯費(fèi);每周末的庫存量等于下周初的庫存量。模型假設(shè)

第61頁,課件共85頁,創(chuàng)作于2023年2月目標(biāo)函數(shù)約束條件產(chǎn)量、庫存與需求平衡決策變量

能力限制非負(fù)限制模型建立x1~x4:第1~4周的生產(chǎn)量y1~y3:第1~3周末庫存量周次需求能力11530225403354542520成本5.05.15.45.5存貯費(fèi):0.2(千元/周?千箱)第62頁,課件共85頁,創(chuàng)作于2023年2月模型求解

4周生產(chǎn)計(jì)劃的總費(fèi)用為528(千元)最優(yōu)解:x1~x4:15,40,25,20;

y1~y3:

0,15,5.周次需求能力11530225403354542520成本5.05.15.45.5產(chǎn)量15402520庫存01550LINDO求解第63頁,課件共85頁,創(chuàng)作于2023年2月檢修計(jì)劃0-1變量wt

:wt=1~檢修安排在第t周(t=1,2,3,4)在4周內(nèi)安排一次設(shè)備檢修,占用當(dāng)周15千箱生產(chǎn)能力,能使檢修后每周增產(chǎn)5千箱,檢修應(yīng)排在哪一周?

檢修安排在任一周均可周次需求能力11530225403354542520成本5.05.15.45.5約束條件能力限制產(chǎn)量、庫存與需求平衡條件不變第64頁,課件共85頁,創(chuàng)作于2023年2月增加約束條件:檢修1次檢修計(jì)劃目標(biāo)函數(shù)不變0-1變量wt

:wt=1~檢修安排在第t周(t=1,2,3,4)LINDO求解總費(fèi)用由528千元降為527千元檢修所導(dǎo)致的生產(chǎn)能力提高的作用,需要更長的時(shí)間才能得到充分體現(xiàn)。最優(yōu)解:w1=1,w2,w3,

w4=0;x1~x4:15,45,15,25;

y1~y3:0,20,0.第65頁,課件共85頁,創(chuàng)作于2023年2月例2飲料的生產(chǎn)批量問題安排生產(chǎn)計(jì)劃,滿足每周的需求,使4周總費(fèi)用最小。存貯費(fèi):每周每千箱飲料0.2千元。飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種飲料。若某周開工生產(chǎn)某種飲料,需支出生產(chǎn)準(zhǔn)備費(fèi)8千元。

某種飲料4周的需求量、生產(chǎn)能力和成本周次需求量(千箱)生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計(jì)100135

第66頁,課件共85頁,創(chuàng)作于2023年2月生產(chǎn)批量問題的一般提法ct~時(shí)段t生產(chǎn)費(fèi)用(元/件);ht~時(shí)段t(末)庫存費(fèi)(元/件);st~時(shí)段t生產(chǎn)準(zhǔn)備費(fèi)(元);dt~時(shí)段t市場需求(件);Mt~時(shí)段t生產(chǎn)能力(件)。假設(shè)初始庫存為0制訂生產(chǎn)計(jì)劃,滿足需求,并使T個(gè)時(shí)段的總費(fèi)用最小。決策變量

xt~時(shí)段t生產(chǎn)量;yt~時(shí)段t(末)庫存量;wt=1~時(shí)段t開工生產(chǎn)(wt=0~不開工)。目標(biāo)約束第67頁,課件共85頁,創(chuàng)作于2023年2月混合0-1規(guī)劃模型

最優(yōu)解:x1~x4:15,40,45,0;總費(fèi)用:554.0(千元)生產(chǎn)批量問題的一般提法將所給參數(shù)代入模型,用LINDO求解第68頁,課件共85頁,創(chuàng)作于2023年2月生產(chǎn)中通過切割、剪裁、沖壓等手段,將原材料加工成所需大小§6鋼管和易拉罐下料原料下料問題按照工藝要求,確定下料方案,使所用材料最省,或利潤最大第69頁,課件共85頁,創(chuàng)作于2023年2月問題1.如何下料最節(jié)省?例1

鋼管下料問題2.客戶增加需求:原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么?由于采用不同切割模式太多,會增加生產(chǎn)和管理成本,規(guī)定切割模式不能超過3種。如何下料最節(jié)?。?米10根第70頁,課件共85頁,創(chuàng)作于2023年2月按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料第71頁,課件共85頁,創(chuàng)作于2023年2月為滿足客戶需要,按照哪些種合理模式,每種模式切割多少根原料鋼管,最為節(jié)省?合理切割模式2.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小第72頁,課件共85頁,創(chuàng)作于2023年2月xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標(biāo)1(總余量)按模式2切割12根,按模式5切割15根,余料27米

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解:x2=12,x5=15,

其余為0;最優(yōu)值:27。整數(shù)約束:xi為整數(shù)第73頁,課件共85頁,創(chuàng)作于2023年2月當(dāng)余料沒有用處時(shí),通常以總根數(shù)最少為目標(biāo)目標(biāo)2(總根數(shù))鋼管下料問題1約束條件不變最優(yōu)解:x2=15,x5=5,x7=5,其余為0;最優(yōu)值:25。xi為整數(shù)按模式2切割15根,按模式5切割5根,按模式7

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論