數學規劃模型第一頁，共二十六頁，編輯于2023年，星期三數學規劃模型

實際問題中的優化模型x~決策變量f(x)~目標函數gi(x)0~約束條件多元函數條件極值n和m較大最優解在邊界上取得數學規劃線性規劃非線性規劃整數規劃本課程重點：模型的建立和結果的分析不等式約束無法用微分法求解第二頁，共二十六頁，編輯于2023年，星期三優化模型的簡單分類

線性規劃(LP)目標和約束均為線性函數

非線性規劃(NLP)目標或約束中存在非線性函數

二次規劃(QP)目標為二次函數、約束為線性

整數規劃(IP)決策變量(全部或部分)為整數整數線性規劃(ILP)，整數非線性規劃(INLP)純整數規劃(PIP),混合整數規劃(MIP)一般整數規劃，0-1（整數）規劃連續優化離散優化數學規劃第三頁，共二十六頁，編輯于2023年，星期三優化模型的簡單分類和求解難度

優化線性規劃非線性規劃二次規劃連續優化整數規劃問題求解的難度增加

第四頁，共二十六頁，編輯于2023年，星期三企業生產計劃4.1奶制品的生產與銷售

空間層次工廠級：根據外部需求和內部設備、人力、原料等條件，以最大利潤為目標制訂產品生產計劃；車間級：根據生產計劃、工藝流程、資源約束及費用參數等，以最小成本為目標制訂生產批量計劃。時間層次若短時間內外部需求和內部資源等不隨時間變化，可制訂單階段生產計劃，否則應制訂多階段生產計劃。本節課題第五頁，共二十六頁，編輯于2023年，星期三例1加工奶制品的生產計劃1桶牛奶3公斤A1

12小時8小時4公斤A2

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

制訂生產計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/公斤，應否改變生產計劃？每天：第六頁，共二十六頁，編輯于2023年，星期三1桶牛奶3公斤A1

12小時8小時4公斤A2

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

x2桶牛奶生產A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數

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

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

50桶牛奶每天第七頁，共二十六頁，編輯于2023年，星期三模型分析與假設

比例性可加性連續性xi對目標函數的“貢獻”與xi取值成正比xi對約束條件的“貢獻”與xi取值成正比xi對目標函數的“貢獻”與xj取值無關xi對約束條件的“貢獻”與xj取值無關xi取值連續A1,A2每公斤的獲利是與各自產量無關的常數每桶牛奶加工出A1,A2的數量和時間是與各自產量無關的常數A1,A2每公斤的獲利是與相互產量無關的常數每桶牛奶加工出A1,A2的數量和時間是與相互產量無關的常數加工A1,A2的牛奶桶數是實數線性規劃模型第八頁，共二十六頁，編輯于2023年，星期三模型求解

圖解法

x1x20ABCDl1l2l3l4l5約束條件目標函數

Z=0Z=2400Z=3600z=c(常數)~等值線c在B(20,30)點得到最優解目標函數和約束條件是線性函數可行域為直線段圍成的凸多邊形目標函數的等值線為直線最優解一定在凸多邊形的某個頂點取得。第九頁，共二十六頁，編輯于2023年，星期三模型求解

軟件實現

LINGO10.0[obj]max=72*x1+64*x2;[st1]x1+x2<50;[st2]12*x1+8*x2<480;[st3]3*x1<100;

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ3360.0001.000000ST10.00000048.00000ST20.0000002.000000ST340.000000.00000020桶牛奶生產A1,30桶生產A2，利潤3360元。迭代2次第十頁，共二十六頁，編輯于2023年，星期三運行狀態窗口Variables（變量數量）：變量總數（Total）、非線性變量數（Nonlinear）、整數變量數（Integer）。Constraints（約束數量）：約束總數（Total）、非線性約束個數(Nonlinear)。Nonzeros（非零系數數量）：總數（Total）、非線性項系數個數(Nonlinear)。GeneratorMemoryUsed(K)(內存使用量)ElapsedRuntime(hh:mm:ss)（求解花費的時間）第十一頁，共二十六頁，編輯于2023年，星期三運行狀態窗口求解器(求解程序)狀態框當前模型的類型:LP，QP，ILP，IQP，PILP，PIQP，NLP，INLP，PINLP（以I開頭表示IP，以PI開頭表示PIP）當前解的狀態:"GlobalOptimum","LocalOptimum","Feasible","Infeasible“(不可行),"Unbounded“(無界),"Interrupted“(中斷),"Undetermined“(未確定)解的目標函數值當前約束不滿足的總量(不是不滿足的約束的個數):實數（即使該值=0，當前解也可能不可行，因為這個量中沒有考慮用上下界命令形式給出的約束）目前為止的迭代次數第十二頁，共二十六頁，編輯于2023年，星期三運行狀態窗口擴展的求解器(求解程序)狀態框使用的特殊求解程序:B-and-B(分枝定界算法)Global(全局最優求解程序)Multistart(用多個初始點求解的程序)目前為止找到的可行解的最佳目標函數值目標函數值的界特殊求解程序當前運行步數：分枝數(對B-and-B程序)；子問題數(對Global程序)；初始點數(對Multistart程序)有效步數第十三頁，共二十六頁，編輯于2023年，星期三注：凡是可以從一個約束直接解出變量取值時，這個變量就不認為是決策變量而是固定變量，不列入統計中；只含有固定變量的約束也不列入約束統計中。運行狀態窗口第十四頁，共二十六頁，編輯于2023年，星期三結果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ3360.0001.000000ST10.00000048.00000

ST20.0000002.000000

ST340.000000.000000原料無剩余時間無剩余加工能力剩余40[obj]max=72*x1+64*x2;[st1]x1+x2<50;[st2]12*x1+8*x2<480;[st3]3*x1<100;三種資源“資源”剩余為零的約束為緊約束（有效約束）第十五頁，共二十六頁，編輯于2023年，星期三Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ

3360.0001.000000ST10.00000048.00000ST20.0000002.000000ST340.000000.000000結果解釋

最優解下“資源”增加1單位時“效益”的增量原料增加1單位,利潤增長48時間增加1單位,利潤增長2加工能力增長不影響利潤影子價格35元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？2元！第十六頁，共二十六頁，編輯于2023年，星期三第十七頁，共二十六頁，編輯于2023年，星期三

Rangesinwhichthebasisisunchanged:

ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseST150.0000010.000006.666667ST2480.000053.3333380.00000ST3100.0000INFINITY40.00000最優解不變時目標函數系數允許變化范圍x1系數范圍(64,96)

x2系數范圍(48,72)A1獲利增加到30元/千克，應否改變生產計劃x1系數由243=72增加為303=90，在允許范圍內不變！(約束條件不變)第十八頁，共二十六頁，編輯于2023年，星期三結果解釋

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseST150.0000010.000006.666667ST2480.000053.3333380.00000ST3100.0000INFINITY40.00000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標函數不變)加工能力可任意增加原料最多減少10時間最多減少53加工能力最多減少40第十九頁，共二十六頁，編輯于2023年，星期三例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%的波動，對計劃有無影響？第二十頁，共二十六頁，編輯于2023年，星期三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附加約束

第二十一頁，共二十六頁，編輯于2023年，星期三模型求解

軟件實現

LINGO10.0[obj]max=24*x1+16*x2+44*x3+32*x4-3*x5-3*x6;[st1]4*x1+3*x2+4*x5+3*x6<=600;[st2]4*x1+2*x2+6*x5+4*x6<=480;[st3]x1+x5<=100;[st4]x3=0.8*x5;[st5]x4=0.75*x6;第二十二頁，共二十六頁，編輯于2023年，星期三LINGO10.0模型求解

軟件實現

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000

X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000ST376.000000.000000ST40.00000044.00000ST50.00000032.00000“ReducedCost”列出最優單純形表中判別數所在行的變量的系數，表示當變量有微小變動時,目標函數的變化率。其中基變量的reducedcost值應為0，對于非基變量Xj,相應的reducedcost值表示當某個變量Xj增加一個單位時目標函數減少的量(max型問題)。本例中：變量X1對應的reducedcost值為1.68，表示當非基變量X1的值從0變為1時（此時假定其他非基變量保持不變,但為了滿足約束條件，基變量顯然會發生變化），最優的目標函數值=3460.8–1.68=3459.12。(基本不用它)第二十三頁，共二十六頁，編輯于2023年，星期三

Globaloptimalsolutionfound.

Objectivevalue:3460.800Totalsolveriterations:2

VariableValueReducedCost

X10.0000001.680000

X2168.00000.000000

X319.200000.000000

X40.0000000.000000

X524.000000.000000

X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000ST376.000000.000000ST40.00000044.00000ST50.00000032.00000結果解釋每天銷售168千克A2和19.2千克B1，利潤3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24千克A1全部加工成B1

除加工能力外均為緊約束第二十四頁，共二十六頁，編輯于2023年，星期三結果解釋

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000

X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000