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

數(shù)學(xué)規(guī)劃模型第1頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月第四章數(shù)學(xué)規(guī)劃模型

4.1奶制品的生產(chǎn)與銷(xiāo)售4.2

自來(lái)水輸送與貨機(jī)裝運(yùn)4.3

汽車(chē)生產(chǎn)與原油采購(gòu)4.4

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

飲料廠(chǎng)的生產(chǎn)與檢修4.6鋼管和易拉罐下料y第2頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月數(shù)學(xué)規(guī)劃模型

實(shí)際問(wèn)題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件多元函數(shù)條件極值決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)m較大最優(yōu)解在可行域的邊界上取得數(shù)學(xué)規(guī)劃線(xiàn)性規(guī)劃非線(xiàn)性規(guī)劃整數(shù)規(guī)劃重點(diǎn)在模型的建立和結(jié)果的分析第3頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月企業(yè)生產(chǎn)計(jì)劃4.1奶制品的生產(chǎn)與銷(xiāo)售

空間層次工廠(chǎng)級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車(chē)間級(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é)課題第4頁(yè)，課件共29頁(yè)，創(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元可買(mǎi)到1桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?

A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天：第5頁(yè)，課件共29頁(yè)，創(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)

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

加工能力

決策變量

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

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

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

50桶牛奶每天第6頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月模型分析與假設(shè)

比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對(duì)約束條件的“貢獻(xiàn)”與xi取值成正比xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無(wú)關(guān)xi對(duì)約束條件的“貢獻(xiàn)”與xj取值無(wú)關(guān)xi取值連續(xù)A1,A2每公斤的獲利是與各自產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)線(xiàn)性規(guī)劃模型第7頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月模型求解

圖解法

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

Z=0Z=2400Z=3360z=c(常數(shù))~等值線(xiàn)c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線(xiàn)性函數(shù)可行域?yàn)橹本€(xiàn)段圍成的凸多邊形目標(biāo)函數(shù)的等值線(xiàn)為直線(xiàn)最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。第8頁(yè)，課件共29頁(yè)，創(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，利潤(rùn)3360元。第9頁(yè)，課件共29頁(yè)，創(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原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）第10頁(yè)，課件共29頁(yè)，創(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單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格

35元可買(mǎi)到1桶牛奶，要買(mǎi)嗎？35<48,應(yīng)該買(mǎi)！聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？2元！第11頁(yè)，課件共29頁(yè)，創(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)不變！(約束條件不變)第12頁(yè)，課件共29頁(yè)，創(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元可買(mǎi)到1桶牛奶，每天最多買(mǎi)多少？最多買(mǎi)10桶!(目標(biāo)函數(shù)不變)第13頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例2奶制品的生產(chǎn)銷(xiāo)售計(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ì)劃有無(wú)影響？第14頁(yè)，課件共29頁(yè)，創(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)

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

加工能力

決策變量

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

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

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

第15頁(yè)，課件共29頁(yè)，創(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第16頁(yè)，課件共29頁(yè)，創(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é)果解釋每天銷(xiāo)售168千克A2和19.2千克B1，利潤(rùn)3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24千克A1全部加工成B1

除加工能力外均為緊約束第17頁(yè)，課件共29頁(yè)，創(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桶牛奶使利潤(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)）第18頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月結(jié)果解釋B1,B2的獲利有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響

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ù)允許范圍波動(dòng)對(duì)計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為39.6計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化。第19頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月生產(chǎn)中通過(guò)切割、剪裁、沖壓等手段，將原材料加工成所需大小§6鋼管和易拉罐下料原料下料問(wèn)題按照工藝要求，確定下料方案，使所用材料最省，或利潤(rùn)最大第20頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月問(wèn)題1.如何下料最節(jié)省?例1

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

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

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

目標(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ù)第24頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼管下料問(wèn)題1約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比第25頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月鋼管下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過(guò)3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。決策變量

xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量第26頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月滿(mǎn)足需求模式合理：每根余料不超過(guò)3米整數(shù)非線(xiàn)性規(guī)劃模型鋼管下料問(wèn)題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)第27頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：13+10+8=31模式排列順序