規(guī)劃模型《數學模型》(第三版)電子課件

第四章數學規(guī)劃模型

4.1奶制品的生產與銷售4.2自來水輸送與貨機裝運4.3

汽車生產與原油采購4.5飲料廠的生產與檢修4.6鋼管和易拉罐下料y第四章數學規(guī)劃模型4.1奶制品的生產與銷售y數學規(guī)劃模型

實際問題中的優(yōu)化模型x~決策變量f(x)~目標函數gi(x)0~約束條件多元函數條件極值決策變量個數n和約束條件個數m較大最優(yōu)解在可行域的邊界上取得數學規(guī)劃線性規(guī)劃非線性規(guī)劃整數規(guī)劃重點在模型的建立和結果的分析數學規(guī)劃模型實際問題中x~決策變量f(x)~目標函數gi(企業(yè)生產計劃4.1奶制品的生產與銷售

空間層次工廠級：根據外部需求和內部設備、人力、原料等條件，以最大利潤為目標制訂產品生產計劃；車間級：根據生產計劃、工藝流程、資源約束及費用參數等，以最小成本為目標制訂生產批量計劃。時間層次若短時間內外部需求和內部資源等不隨時間變化，可制訂單階段生產計劃，否則應制訂多階段生產計劃。本節(jié)課題企業(yè)生產計劃4.1奶制品的生產與銷售空間層次工廠級：根例1加工奶制品的生產計劃1桶牛奶3公斤A1

12小時8小時4公斤A2

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

制訂生產計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/公斤，應否改變生產計劃？每天：例1加工奶制品的生產計劃1桶牛奶3公斤A112小1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產A1

x2桶牛奶生產A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數

每天獲利約束條件非負約束

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

50桶牛奶每天1桶牛奶3公斤A112小時8小時4公斤A2或獲利2模型分析與假設

比例性可加性連續(xù)性xi對目標函數的“貢獻”與xi取值成正比xi對約束條件的“貢獻”與xi取值成正比xi對目標函數的“貢獻”與xj取值無關xi對約束條件的“貢獻”與xj取值無關xi取值連續(xù)A1,A2每公斤的獲利是與各自產量無關的常數每桶牛奶加工出A1,A2的數量和時間是與各自產量無關的常數A1,A2每公斤的獲利是與相互產量無關的常數每桶牛奶加工出A1,A2的數量和時間是與相互產量無關的常數加工A1,A2的牛奶桶數是實數線性規(guī)劃模型模型分析與假設比例性可加性連續(xù)性xi對目標函數的“貢模型求解

圖解法

x1x20ABCDl1l2l3l4l5約束條件目標函數

Z=0Z=2400Z=3600z=c(常數)~等值線c在B(20,30)點得到最優(yōu)解目標函數和約束條件是線性函數可行域為直線段圍成的凸多邊形目標函數的等值線為直線最優(yōu)解一定在凸多邊形的某個頂點取得。模型求解圖解法x1x20ABCDl1l2l3l4l5約束模型求解

軟件實現

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桶牛奶生產A1,30桶生產A2，利潤3360元。模型求解軟件實現LINDO6.1max72x1+6結果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料無剩余時間無剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）結果解釋OBJECTIVEFUNCTIONVA結果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時“效益”的增量原料增加1單位,利潤增長48時間增加1單位,利潤增長2加工能力增長不影響利潤影子價格35元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？2元！結果解釋OBJECTIVEFUNCTIORANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

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

Yesx1系數范圍(64,96)

x2系數范圍(48,72)A1獲利增加到30元/千克，應否改變生產計劃x1系數由243=72增加為303=90，在允許范圍內不變！(約束條件不變)RANGESINWHICHTHEBASISISU結果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標函數不變)結果解釋RANGESINWHICHTHEBASIS例2奶制品的生產銷售計劃

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

12小時8小時4公斤A2

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

B1，B2的獲利經常有10%的波動，對計劃有無影響？例2奶制品的生產銷售計劃在例1基礎上深加工1桶牛奶1桶牛奶

3千克A1

12小時8小時4千克A2

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

0.8千克

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

x2千克A2，

X3千克B1,x4千克B2原料供應

勞動時間

加工能力

決策變量

目標函數

利潤約束條件非負約束

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

1桶牛奶3千克A112小時8小時4千克A2或模型求解

軟件實現

LINDO6.1OBJECTIVEFUNCTIONVALUE1)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模型求解軟件實現LINDO6.1OBJ

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結果解釋每天銷售168千克A2和19.2千克B1，利潤3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24千克A1全部加工成B1

除加工能力外均為緊約束OBJECTIVEFUNCTIONVA結果解釋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小時時間使利潤增長3.2630元可增加1桶牛奶，3元可增加1小時時間，應否投資？現投資150元，可賺回多少？投資150元增加5桶牛奶，可賺回189.6元。（大于增加時間的利潤增長）結果解釋OBJECTIVEFUNCTIO結果解釋B1,B2的獲利有10%的波動，對計劃有無影響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系數允許范圍B2獲利上升10%，超出X4系數允許范圍波動對計劃有影響生產計劃應重新制訂：如將x3的系數改為39.6計算，會發(fā)現結果有很大變化。結果解釋B1,B2的獲利有10%的波動，對計劃有無影響4.2自來水輸送與貨機裝運生產、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大；運輸問題各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數量最少。4.2自來水輸送與貨機裝運生產、生活物資從若干供應點運送其他費用:450元/千噸

應如何分配水庫供水量，公司才能獲利最多？

若水庫供水量都提高一倍，公司利潤可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費例1自來水輸送收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計）其他費用:450元/千噸應如何分配水庫供水量，公司才能獲總供水量：160確定送水方案使利潤最大問題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40<總需求量：120+180=300總收入900160=144,000(元)收入：900元/千噸

其他費用:450元/千噸

支出引水管理費其他支出450160=72,000(元)使引水管理費最小總供水量：160確定送水方案使利潤最大問題分析A：50B：6供應限制約束條件需求限制

線性規(guī)劃模型(LP)目標函數

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

模型建立確定3個水庫向4個小區(qū)的供水量供應限制約束條件需求限制線性規(guī)劃模型(LP)目標函數水庫模型求解

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利潤=總收入-其它費用-引水管理費=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理費24400(元)模型求解OBJECTIVEFUNCTIONVALUE利目標函數

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

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

確定送水方案使利潤最大需求約束可以不變目標函數總供水量(320)>總需求量(300)每個水庫求解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這類問題一般稱為“運輸問題”(TransportationProblem)總利潤88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030求解OBJECTIVEFUNCTIONVALUE這類問如何裝運，使本次飛行獲利最大？

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

例2貨機裝運

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

前倉：10；6800中倉：16；8700后倉：8；5300飛機平衡如何裝運，使本次飛行獲利最大？三個貨艙最大載重(噸),最決策變量

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

j=1,2,3(分別代表前、中、后倉)模型假設每種貨物可以分割到任意?。回洐C裝運每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；模型建立決策變量xij--第i種貨物裝入第j個貨艙的重量(噸）貨艙容積

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

10；680016；87008；5300xij--第i種貨物裝入第j個貨艙的重量貨艙容積目標函數(利潤)約束條件貨機裝運模型建立貨艙重量約束條件平衡要求

貨物供應

貨機裝運模型建立10；680016；87008；5300xij--第i種貨物裝入第j個貨艙的重量約束條件平衡要求貨物供應貨機裝運模型建立10；6800OBJECTIVEFUNCTIONVALUE1)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。貨機裝運模型求解最大利潤約121516元貨物~供應點貨艙~需求點平衡要求運輸問題運輸問題的擴展OBJECTIVEFUNCTIONVALUE貨物2：如果生產某一類型汽車，則至少要生產80輛，那么最優(yōu)的生產計劃應作何改變？例1汽車廠生產計劃汽車廠生產三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現有量。小型中型大型現有量鋼材（噸）1.535600勞動時間（小時）28025040060000利潤（萬元）234制訂月生產計劃，使工廠的利潤最大。4.3

汽車生產與原油采購如果生產某一類型汽車，則至少要生產80輛，那么最優(yōu)的生設每月生產小、中、大型汽車的數量分別為x1,x2,x3汽車廠生產計劃模型建立

小型中型大型現有量鋼材1.535600時間28025040060000利潤234線性規(guī)劃模型(LP)設每月生產小、中、大型汽車的數量分別為x1,x2,x3汽模型求解

3）

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

均為整數，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226結果為小數，怎么辦？1）舍去小數：取x1=64，x2=167，算出目標函數值z=629，與LP最優(yōu)值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數值z，通過比較可能得到更優(yōu)的解。但必須檢驗它們是否滿足約束條件。為什么？模型求解3）模型中增加條件：x1,x2,x3均為IP可用LINDO直接求解整數規(guī)劃(IntegerProgramming,簡記IP)“gin3”表示“前3個變量為整數”，等價于：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結果輸出IP可用LINDO直接求解整數規(guī)劃(IntegerProg其中3個子模型應去掉，然后逐一求解，比較目標函數值，再加上整數約束，得最優(yōu)解：方法1：分解為8個LP子模型汽車廠生產計劃若生產某類汽車，則至少生產80輛，求生產計劃。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z=610其中3個子模型應去掉，然后逐一求解，比較目標函數值，再加上整LINDO中對0-1變量的限定：inty1inty2inty3方法2：引入0-1變量，化為整數規(guī)劃

M為大的正數，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOST

X180.000000-2.000000

X2150.000000-3.000000

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

80x2=0或

80x3=0或

80最優(yōu)解同前

LINDO中對0-1變量的限定：方法2：引入0-1變量，化為NLP雖然可用現成的數學軟件求解(如LINGO,MATLAB)，但是其結果常依賴于初值的選擇。方法3：化為非線性規(guī)劃

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

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

若生產某類汽車，則至少生產80輛，求生產計劃。x1=0或

80x2=0或

80x3=0或

80NLP雖然可用現成的數學軟件求解(如LINGO,MATLA應如何安排原油的采購和加工

？

例2原油采購與加工市場上可買到不超過1500噸的原油A：購買量不超過500噸時的單價為10000元/噸；購買量超過500噸但不超過1000噸時，超過500噸的部分8000元/噸；購買量超過1000噸時，超過1000噸的部分6000元/噸。售價4800元/噸售價5600元/噸庫存500噸庫存1000噸汽油甲(A50%)原油A原油B汽油乙(A60%)應如何安排原油的采購和加工？例2原油采購與加工決策變量

目標函數問題分析利潤：銷售汽油的收入-購買原油A的支出難點：原油A的購價與購買量的關系較復雜甲(A50%)AB乙(A60%)購買xx11x12x21x224.8千元/噸5.6千元/噸原油A的購買量,原油A,B生產汽油甲,乙的數量c(x)~購買原油A的支出利潤(千元)c(x)如何表述？決策變量目標函數問題分析利潤：銷售汽油的收入-購買原油供應

約束條件x

500噸單價為10千元/噸；500噸x1000噸，超過500噸的8千元/噸；1000噸x1500噸，超過1000噸的6千元/噸。目標函數購買xABx11x12x21x22庫存500噸庫存1000噸原油供應約束條件x500噸單價為10千元/噸；目標函目標函數中c(x)不是線性函數，是非線性規(guī)劃；對于用分段函數定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解；想辦法將模型化簡，用現成的軟件求解。

汽油含原油A的比例限制約束條件甲(A50%)AB乙(A60%)x11x12x21x22目標函數中c(x)不是線性函數，是非線性規(guī)劃；汽油含原油Ax1,x2,x3~以價格10,8,6(千元/噸)采購A的噸數目標函數

只有當以10千元/噸的價格購買x1=500(噸)時，才能以8千元/噸的價格購買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

x1,x2,x3~以價格10,8,6(千元/噸方法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生產汽油甲，不購買新的原油A，利潤為4,800千元。

方法1：LINGO求解Model:Objectivevaly1,y2,y3=1~以價格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一起，生產汽油乙，利潤為5,000千元。x1,x2,x3~以價格10,8,6(千元/噸)采購A的噸數y=0x=0x>0y=1優(yōu)于方法1的結果y1,y2,y3=1~以價格10,8,6(千元/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).直接處理處理分段線性函數c(x)b1b2b3IP模型，LINDO求解，得到的結果與方法2相同.處理分段線性函數，方法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,3IP模型，LINDO求解，得到的結果與方法2相同.處理分段線4.5飲料廠的生產與檢修單階段生產計劃多階段生產計劃生產批量問題企業(yè)生產計劃考慮與產量無關的固定費用給優(yōu)化模型求解帶來新的困難外部需求和內部資源隨時間變化4.5飲料廠的生產與檢修單階段生產計劃多階段生產計劃生安排生產計劃,滿足每周的需求,使4周總費用最小。存貯費:每周每千箱飲料0.2千元。例1飲料廠的生產與檢修計劃在4周內安排一次設備檢修，占用當周15千箱生產能力，能使檢修后每周增產5千箱，檢修應排在哪一周?

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

某種飲料4周的需求量、生產能力和成本安排生產計劃,滿足每周的需求,使4周總費用最小。存貯問題分析除第4周外每周的生產能力超過每周的需求；生產成本逐周上升；前幾周應多生產一些。周次需求能力11530225403354542520合計100135成本5.05.15.45.5

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

問題分析除第4周外每周的生產能力超過每周的需求；周次需求能目標函數約束條件產量、庫存與需求平衡決策變量

能力限制非負限制模型建立x1~x4：第1~4周的生產量y1~y3：第1~3周末庫存量周次需求能力11530225403354542520成本5.05.15.45.5存貯費:0.2(千元/周?千箱)目標函數約束條件產量、庫存與需求平衡決策變量能力限制非模型求解

4周生產計劃的總費用為528(千元)最優(yōu)解：x1~x4：15，40，25，20；

y1~y3：

0，15，5.周次需求能力11530225403354542520成本5.05.15.45.5產量15402520庫存01550LINDO求解模型求解4周生產計劃的總費用為528(千元)最優(yōu)解：檢修計劃0-1變量wt：wt=1~檢修安排在第t周(t=1,2,3,4）在4周內安排一次設備檢修，占用當周15千箱生產能力，能使檢修后每周增產5千箱，檢修應排在哪一周?

檢修安排在任一周均可周次需求能力11530225403354542520成本5.05.15.45.5約束條件能力限制產量、庫存與需求平衡條件不變檢修計劃0-1變量wt：wt=1~檢修安排在第t周(t=增加約束條件：檢修1次檢修計劃目標函數不變0-1變量wt：wt=1~檢修安排在第t周(t=1,2,3,4）LINDO求解總費用由528千元降為527千元檢修所導致的生產能力提高的作用,需要更長的時間才能得到充分體現。最優(yōu)解：w1=1,w2,w3,

w4=0;x1~x4：15,45,15,25；

y1~y3：0,20,0.增加約束條件：檢修1次檢修計劃目標函數不變0-1變量wt：例2飲料的生產批量問題安排生產計劃,滿足每周的需求,使4周總費用最小。存貯費:每周每千箱飲料0.2千元。飲料廠使用同一條生產線輪流生產多種飲料。若某周開工生產某種飲料,需支出生產準備費8千元。

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

例2飲料的生產批量問題安排生產計劃,滿足每周的需生產批量問題的一般提法ct~時段t生產費用(元/件)；ht~時段t(末)庫存費(元/件)；st~時段t生產準備費(元)；dt~時段t市場需求(件)；Mt~時段t生產能力(件)。假設初始庫存為0制訂生產計劃,滿足需求,并使T個時段的總費用最小。決策變量

xt~時段t生產量；yt~時段t(末)庫存量；wt=1~時段t開工生產(wt=0~不開工)。目標約束生產批量問題的一般提法ct~時段t生產費用(元/件)；假混合0-1規(guī)劃模型

最優(yōu)解：x1~x4：15，40，45，0；總費用：554.0(千元)生產批量問題的一般提法將所給參數代入模型，用LINDO求解混合0-1規(guī)劃模型最優(yōu)解：x1~x4：15，40，45，生產中通過切割、剪裁、沖壓等手段，將原材料加工成所需大小§6鋼管和易拉罐下料原料下料問題按照工藝要求，確定下料方案，使所用材料最省，或利潤最大生產中通過切割、剪裁、沖壓等手段，將原材料加工成所需大小§6問題1.如何下料最節(jié)省?例1鋼管下料問題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標準是什么？由于采用不同切割模式太多，會增加生產和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)省？5米10根問題1.如何下料最節(jié)省?例1鋼管下料問題2.按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料按照客戶需要在一根原料鋼管上安排切割的一種組合。切割模式余為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？合理切割模式2.所用原料鋼管總根數最少模式

4米鋼管根數6米鋼管根數8米鋼管根數余料(米)14003231013201341203511116030170023鋼管下料問題1兩種標準1.原料鋼管剩余總余量最小為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼xi~按第i種模式切割的原料鋼管根數(i=1,2,…7)約束滿足需求決策變量

目標1（總余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根數6米根數8米根數余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27。整數約束：xi為整數xi~按第i種模式切割的原料鋼管根數(i=1,2,…7)當余料沒有用處時，通常以總根數最少為目標目標2（總根數）鋼管下料問題1約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標1的結果“共切割27根，余料27米”相比當余料沒有用處時，通常以總根數最少為目標目標2（總根數）鋼鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種?，F有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復雜。決策變量

xi~按第i種模式切割的原料鋼管根數(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產4米、5米、6米和8米長的鋼管的數量鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式增加滿足需求模式合理：每根余料不超過3米整數非線性規(guī)劃模型鋼管下料問題2目標函數（總根數）約束條件整數約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數滿足需求模式合理：每根余料不超過3米整數非線性規(guī)劃模型鋼管下增加約束，縮小可行域，便于求解原料鋼管總根數下界：

特殊生產計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數上界：13+10+8=31模式排列順序可任定

鋼管下料問題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長19米增加約束，縮小可行域，便于求解原料鋼管總根數下界：特殊生產LINGO求解整數非線性規(guī)劃模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數為28根。LINGO求解整數非線性規(guī)劃模型Localoptimal板材規(guī)格2：長方形，3228cm，2萬張。例2易拉罐下料每周工作40小時，每只易拉罐利潤0.10元，原料余料損失0.001元/cm2（不能裝配的罐身、蓋、底也是余料）模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒上蓋下底罐身罐身高10cm，上蓋、下底直徑均5cm。

板材規(guī)格1：正方形，邊長24cm，5萬張。如何安排每周生產？

板材規(guī)格2：例2易拉罐下料每周工作40小時，每只易拉罐利潤

罐身個數底、蓋個數余料損失（cm2）沖壓時間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53模式1:正方形邊長24cm問題分析計算各種模式下的余料損失上、下底直徑d=5cm，罐身高h=10cm。模式1余料損失242-10d2/4-dh=222.6cm2

罐身個數底、蓋余料損失沖壓時間（秒）模式1110222.6問題分析目標:易拉罐利潤扣除原料余料損失后的凈利潤最大

約束：每周工作時間不超過40小時；原料數量：規(guī)格1（模式1~3）5萬張，規(guī)格2（模式4）2萬張；罐身和底、蓋的配套組裝。注意：不能裝配的罐身、上下底也是余料決策變量

xi~按照第i種模式的生產張數(i=1,2,3,4)；y1~一周生產的易拉罐個數；y2~不配套的罐身個數；y3~不配套的底、蓋個數。模型建立問題分析目標:易拉罐利潤扣除原料余料損失后的凈利潤最大約目標

約束條件

時間約束原料約束產量余料時間x1222.61.5x2183.32x3261.81x4169.53模型建立y1~易拉罐個數；y2~不配套的罐身；y3~不配套的底、蓋。每只易拉罐利潤0.10元，余料損失0.001元/cm2罐身面積dh=157.1cm2

底蓋面積d2/4=19.6cm2(40小時)目標約束條件時間約束原料約束產量余料時間x1222.約束條件

配套約束y1~易拉罐個數；y2~不配套的罐身；y3~不配套的底、蓋。罐身底、蓋1102401645產量x1x2x3x4雖然xi和y1，y2，y3應是整數，但是因生產量很大，可以把它們看成實數，從而用線性規(guī)劃模型處理。約束條件配套約束y1~易拉罐個數；y2~不配套的將所有決策變量擴大10000倍（xi~萬張，yi~萬件）

LINDO發(fā)出警告信息：“數據之間的數量級差別太大，建議進行預處理，縮小數據之間的差別”模式2生產40125張，模式3生產3750張，模式4生產20000張，共產易拉罐160250個(罐身和底、蓋無剩余)，凈利潤為4298元

模型求解OBJECTIVEFUNCTIONVALUE1)0.4298337VARIABLEVALUEREDUCEDCOSTY116.0250000.000000X10.0000000.000050X24.0125000.000000X30.3750000.000000X42.0000000.000000Y2