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

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

y4.2自來(lái)水輸送與貨機(jī)裝運(yùn)（運(yùn)輸問(wèn)題）4.3汽車生產(chǎn)與原油采購(gòu)(整數(shù)規(guī)劃)第四章數(shù)學(xué)規(guī)劃模型y4.2自來(lái)水輸送與貨機(jī)裝運(yùn)（運(yùn)4.2自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。4.2自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送其他費(fèi)用:450元/千噸

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

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

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

收入：900元/千噸

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

支出引水管理費(fèi)+其他費(fèi)用450160=72,000(元)與送水方案無(wú)關(guān)！

使引水管理費(fèi)最小總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：6供應(yīng)限制約束條件需求限制

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

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

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

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.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(元)模型求解Globaloptimalsolutionf目標(biāo)函數(shù)

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

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

確定送水方案使利潤(rùn)最大需求約束可以不變目標(biāo)函數(shù)總供水量(320)>總需求量(300)每個(gè)水庫(kù)求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”(TransportationProblem)總利潤(rùn)88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”總利潤(rùn)88700（元）A如何裝運(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ī)平衡如何裝運(yùn)，使本次飛行獲利最大？三個(gè)貨艙最大載重(噸),最決策變量

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

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

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

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

貨物供應(yīng)

貨機(jī)裝運(yùn)模型建立10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量約束條件平衡要求貨物供應(yīng)貨機(jī)裝運(yùn)模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue: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：前倉(cāng)10,后倉(cāng)5；

貨物3:中倉(cāng)13,后倉(cāng)3；貨物4:中倉(cāng)3。貨機(jī)裝運(yùn)模型求解最大利潤(rùn)約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)平衡要求運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展Globaloptimalsolutionfou數(shù)學(xué)規(guī)劃模型課件其他費(fèi)用:450元/千噸

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

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

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

收入：900元/千噸

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

支出引水管理費(fèi)+其他費(fèi)用450160=72,000(元)與送水方案無(wú)關(guān)！

使引水管理費(fèi)最小總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：6供應(yīng)限制約束條件需求限制

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

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

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

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.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(元)模型求解Globaloptimalsolutionf目標(biāo)函數(shù)

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

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

確定送水方案使利潤(rùn)最大需求約束可以不變目標(biāo)函數(shù)總供水量(320)>總需求量(300)每個(gè)水庫(kù)求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”(TransportationProblem)總利潤(rùn)88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”總利潤(rùn)88700（元）A如何裝運(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ī)平衡如何裝運(yùn)，使本次飛行獲利最大？三個(gè)貨艙最大載重(噸),最決策變量

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

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

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

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

貨物供應(yīng)

貨機(jī)裝運(yùn)模型建立10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量約束條件平衡要求貨物供應(yīng)貨機(jī)裝運(yùn)模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue: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：前倉(cāng)10,后倉(cāng)5；

貨物3:中倉(cāng)13,后倉(cāng)3；貨物4:中倉(cāng)3。貨機(jī)裝運(yùn)模型求解最大利潤(rùn)約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)平衡要求運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展Globaloptimalsolutionfou4.3汽車生產(chǎn)與原油采購(gòu)整數(shù)規(guī)劃4.3汽車生產(chǎn)與原油采購(gòu)整數(shù)規(guī)劃設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3例1汽車廠生產(chǎn)計(jì)劃模型建立

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

3）

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

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

Globaloptimalsolutionfound.Objectivevalue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237

RowSlackorSurplusDualPrice[ST1]0.0000000.731183[ST2]0.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ì)，通過(guò)比較可能得到更優(yōu)的解?？赡苷也坏阶顑?yōu)！但必須檢驗(yàn)它們是否滿足約束條件?？赡懿皇强尚薪?！模型求解3）模型中增加條件：x1,x2,x3均為IP可用LINDO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)“@gin(x1);”表示“x1為整數(shù)”.

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.0000VariableValueReducedCostX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出IP可用LINDO直接求解整數(shù)規(guī)劃(IntegerProg其中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(mì)=610其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù)，可取1000若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80方法2：引入0-1變量，化為整數(shù)規(guī)劃M為大的正數(shù)，可取10max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<=600;280*x1+250*x2+400*x3<=60000;x1<=1000*y1;x1>=80*y1;x2<=1000*y2;x2>=80*y2;x3<=1000*y3;x3>=80*y3;@gin(x1);@gin(x2);@gin(x3);@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1變量，化為整數(shù)規(guī)劃

Globaloptimalsolutionfound.Objectivevalue:610.0000Extendedsolversteps:0Totalsolveriterations:10VariableValueReducedCostX180.00000-2.000000X2150.0000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。最優(yōu)解同前

max=2*x1+3*x2+4*x3;方法2：引入0-1變量NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAB)，但是其結(jié)果常依賴于初值的選擇。方法3：化為非線性規(guī)劃

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

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

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

80x2=0或

80x3=0或

80NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAmax=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);Globaloptimalsolutionfound.Objectivevalue:610.0000Extendedsolversteps:2Totalsolveriterations:171VariableValueX180.00000X2150.0000X30.000000max=2*x1+3*x2+4*x3;Globalopt應(yīng)如何安排原油的采購(gòu)和加工

？

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

目標(biāo)函數(shù)問(wèn)題分析利潤(rùn)：銷售汽油的收入-購(gòu)買原油A的支出難點(diǎn)：原油A的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜甲(A50%)AB乙(A60%)購(gòu)買xx11x12x21x224.8千元/噸5.6千元/噸原油A的購(gòu)買量,原油A,B生產(chǎn)汽油甲,乙的數(shù)量c(x)~購(gòu)買原油A的支出利潤(rùn)(千元)c(x)如何表述？決策變量目標(biāo)函數(shù)問(wèn)題分析利潤(rùn)：銷售汽油的收入-購(gòu)買原油供應(yīng)

約束條件x

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

汽油含原油A的比例限制約束條件甲(A50%)AB乙(A60%)x11x12x21x22目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；汽油含原油Ax1,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噸

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

x1,x2,x3~以價(jià)格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)解，還能得到更好的解嗎？

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

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

0-1線性規(guī)劃模型，可用LINGO求解y1,y2,y3=0或1Objectivevalue:5000.000VariableValueReducedCostY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000購(gòu)買1000噸原油A，與庫(kù)存的500噸原油A和1000噸原油B一起，生產(chǎn)汽油乙，利潤(rùn)為5,000千元。x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購(gòu)A的噸數(shù)y=0x=0x>0y=1優(yōu)于方法1的結(jié)果y1,y2,y3=1~以價(jià)格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).直接處理處理分段線性函數(shù)c(x)b1b2b3IP模型，LINGO求解，得到的結(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對(duì)于k=1,2,3IP模型，LINGO求解，得到的結(jié)果與方法2相同.處理分段線示性函數(shù)的使用已知mxM,z=0or1,那么若x>0,則z=1若z=0,則x=0xMz若x=0,則z=0若z=1,則x>0xmz條件約束if,then若x1+x2>3,則x3+x46x3+x46z,x1+x2-3Mz若x1+x2=3,則x3+x46x3+x46(1-z),x1+x2-3mz邏輯運(yùn)算or,andx13或x23x13z1,x23z2,z1+z21分段線性目標(biāo)函數(shù)如例2原油采購(gòu)與加工

示性函數(shù)的使用已知mxM,z=0or1,那么數(shù)學(xué)規(guī)劃模型課件第四章數(shù)學(xué)規(guī)劃模型

y4.2自來(lái)水輸送與貨機(jī)裝運(yùn)（運(yùn)輸問(wèn)題）4.3汽車生產(chǎn)與原油采購(gòu)(整數(shù)規(guī)劃)第四章數(shù)學(xué)規(guī)劃模型y4.2自來(lái)水輸送與貨機(jī)裝運(yùn)（運(yùn)4.2自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。4.2自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送其他費(fèi)用:450元/千噸

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

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

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

收入：900元/千噸

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

支出引水管理費(fèi)+其他費(fèi)用450160=72,000(元)與送水方案無(wú)關(guān)！

使引水管理費(fèi)最小總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：6供應(yīng)限制約束條件需求限制

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

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

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

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.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(元)模型求解Globaloptimalsolutionf目標(biāo)函數(shù)

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

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

確定送水方案使利潤(rùn)最大需求約束可以不變目標(biāo)函數(shù)總供水量(320)>總需求量(300)每個(gè)水庫(kù)求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”(TransportationProblem)總利潤(rùn)88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”總利潤(rùn)88700（元）A如何裝運(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ī)平衡如何裝運(yùn)，使本次飛行獲利最大？三個(gè)貨艙最大載重(噸),最決策變量

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

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

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

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

貨物供應(yīng)

貨機(jī)裝運(yùn)模型建立10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量約束條件平衡要求貨物供應(yīng)貨機(jī)裝運(yùn)模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue: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：前倉(cāng)10,后倉(cāng)5；

貨物3:中倉(cāng)13,后倉(cāng)3；貨物4:中倉(cāng)3。貨機(jī)裝運(yùn)模型求解最大利潤(rùn)約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)平衡要求運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展Globaloptimalsolutionfou數(shù)學(xué)規(guī)劃模型課件其他費(fèi)用:450元/千噸

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

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

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

收入：900元/千噸

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

支出引水管理費(fèi)+其他費(fèi)用450160=72,000(元)與送水方案無(wú)關(guān)！

使引水管理費(fèi)最小總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：6供應(yīng)限制約束條件需求限制

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

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

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

Globaloptimalsolutionfound.Objectivevalue:24400.00Totalsolveriterations:8VariableValueReducedCostX110.00000030.00000X1250.000000.000000X130.00000050.00000X140.00000020.00000X210.00000010.00000X2250.000000.000000X230.00000020.00000

X2410.000000.000000

X3140.000000.000000X320.00000010.00000

X3310.000000.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(元)模型求解Globaloptimalsolutionf目標(biāo)函數(shù)

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

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

確定送水方案使利潤(rùn)最大需求約束可以不變目標(biāo)函數(shù)總供水量(320)>總需求量(300)每個(gè)水庫(kù)求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”(TransportationProblem)總利潤(rùn)88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030

Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000

X2130.000000.000000X2240.000000.000000

X230.00000010.00000X2450.000000.000000

X3150.000000.000000X320.00000020.00000

X3330.000000.000000求解這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”總利潤(rùn)88700（元）A如何裝運(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ī)平衡如何裝運(yùn)，使本次飛行獲利最大？三個(gè)貨艙最大載重(噸),最決策變量

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

j=1,2,3(分別代表前、中、后倉(cāng))模型假設(shè)每種貨物可以分割到任意小；貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；模型建立決策變量xij--第i種貨物裝入第j個(gè)貨艙的重量(噸）貨艙容積

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

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

貨物供應(yīng)

貨機(jī)裝運(yùn)模型建立10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量約束條件平衡要求貨物供應(yīng)貨機(jī)裝運(yùn)模型建立10；6800

Globaloptimalsolutionfound.Objectivevalue: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：前倉(cāng)10,后倉(cāng)5；

貨物3:中倉(cāng)13,后倉(cāng)3；貨物4:中倉(cāng)3。貨機(jī)裝運(yùn)模型求解最大利潤(rùn)約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)平衡要求運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展Globaloptimalsolutionfou4.3汽車生產(chǎn)與原油采購(gòu)整數(shù)規(guī)劃4.3汽車生產(chǎn)與原油采購(gòu)整數(shù)規(guī)劃設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3例1汽車廠生產(chǎn)計(jì)劃模型建立

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

3）

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

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

Globaloptimalsolutionfound.Objectivevalue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237

RowSlackorSurplusDualPrice[ST1]0.0000000.731183[ST2]0.0000000.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)