規(guī)劃問題及其數(shù)學(xué)模型二

(一)線性規(guī)劃問題最優(yōu)化模型

線性規(guī)劃問題的提出線性規(guī)劃問題的基本概念線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的解法綜合實(shí)例

內(nèi)容提要1.問題的提出引例1:生產(chǎn)計(jì)劃問題問：如何安排生產(chǎn)，使得利潤最大？第1步–設(shè)I的產(chǎn)量為x1，II的產(chǎn)量為x2，第2步確立目標(biāo)：第3步表示約束條件：數(shù)學(xué)模型

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

MaxZ=2x1+3x2

約束條件

線性規(guī)劃2.1什么是線性規(guī)劃？在工業(yè)、農(nóng)業(yè)、國防、建筑、交通運(yùn)輸、科研、商業(yè)等各種活動(dòng)中，常常要求對資源進(jìn)行統(tǒng)一分配、全面規(guī)劃和合理調(diào)度，以便從各種可能安排方案中找出最優(yōu)的計(jì)劃或設(shè)計(jì)，用以指導(dǎo)生產(chǎn)。在這類問題中，一方面有期望達(dá)到最優(yōu)要求的目標(biāo)（例如希望產(chǎn)值最高或消耗最少），另一方面又要受到一定條件的限制（例如人力、物力、財(cái)力的限制），如何安排才能使成效最高，消耗既定資源取得的收益最大，或達(dá)到既定收益所消耗的資源最少。這可以借助線性規(guī)劃（LinearProgramming，LP）來解決。2.2線性規(guī)劃研究的內(nèi)容在現(xiàn)有的資源條件下，如何充分利用資源，使任務(wù)或目標(biāo)完成得最好（求極大化問題）。在給定目標(biāo)下，如何以最少的資源消耗，實(shí)現(xiàn)這個(gè)目標(biāo)（求極小化問題）。2.3確立線性規(guī)劃模型的步驟第1步-確定決策變量問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。設(shè)I的產(chǎn)量為x1，II的產(chǎn)量為x2，第2步--定義目標(biāo)函數(shù)

MaxZ=2x1+3x2決策變量系數(shù)第3步--表示約束條件

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

MaxZ=2x1+3x2

約束條件

可行域最優(yōu)解2.5線性規(guī)劃基本概念

某單位有一批資金用于四個(gè)工程項(xiàng)目的投資，用于各工程項(xiàng)目時(shí)所得之凈收益（投入資金的百分比）如下表所示。由于某種原因，決定用于項(xiàng)目A的投資不大于其它各項(xiàng)投資之和；而用于項(xiàng)目B和C的投資不小于項(xiàng)目D的投資。試確定使該單位收益最大的投資分配方案。工程項(xiàng)目ABCD收益（％）1510812

2.6例2投資問題第一步：確定變量

x1、

x2、

x3、

x4分別表示用于項(xiàng)目A、B、C、D的投資百分?jǐn)?shù)。第三步：確定目標(biāo)函數(shù)maxz=0.15x1+0.1x2+0.08x3+0.12x4第二步：確定約束條件

x1－

x2－

x3－

x4

≤

0

x2＋

x3－

x4

≥

0

x1＋x2＋x3＋x4＝1

xj≥

0，j＝1,2,…,4數(shù)學(xué)模型maxz=0.15x1+0.1x2+0.08x3+0.12x4

x1－x2－x3－x4≤0

x2＋x3－x4≥0

x1＋x2＋x3＋x4＝1

xj≥0，j＝1，2,…,42.7例3資源分配問題

某廠生產(chǎn)甲乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需用資源A3噸，資源B4m3；制成一噸產(chǎn)品乙需用資源A2噸，資源B6m3，資源c7個(gè)單位。若一噸產(chǎn)品甲和乙的經(jīng)濟(jì)價(jià)值分別為7萬元和5萬元，三種資源的限制量分別為90噸、200m3和210個(gè)單位，試決定應(yīng)生產(chǎn)這兩種產(chǎn)品各多少噸才能使創(chuàng)造的總經(jīng)濟(jì)價(jià)值最高?第一步：確定決策變量

x1：生產(chǎn)產(chǎn)品甲的數(shù)量（噸）

x2：生產(chǎn)產(chǎn)品乙的數(shù)量（噸）第二步：確定目標(biāo)函數(shù)

以Z表示生產(chǎn)甲和乙兩種產(chǎn)品各為x1和x2（噸）時(shí)產(chǎn)生的經(jīng)濟(jì)價(jià)值，總經(jīng)濟(jì)價(jià)值最高的目標(biāo)可表示為：maxz＝7x1十5x2

第三步：確定約束條件約束條件為三種資源的限制用量

資源A限制：3x1十2x2

≤90資源B限制；4x1十6x2

≤200資源C限制：7x2

≤210

此外，產(chǎn)量x1和x2不能為負(fù)，只能取正值非負(fù)條件：x1

≥0，x2

≥0經(jīng)上述分析，可將該問題數(shù)學(xué)模型表示為：

maxz＝7x1十5x23x1十2x2

≤904x1十6x2

≤2007x2

≤210

x1

≥0，x2

≥03.如何使用matlab求解線性規(guī)劃MatLab中線性規(guī)劃的標(biāo)準(zhǔn)型：基本函數(shù)形式為：

[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)

fval返回目標(biāo)函數(shù)的值，lb和lb分別為x的下界和上界例：求優(yōu)化問題Matlab實(shí)現(xiàn)為：>>f=[-542];>>a=[6-11;124];>>b=[810];>>lb=[-100];>>ub=[32inf];>>[x,fval]=linprog(f,a,b,[],[],lb,ub);>>[x,fval,exitflag]=linprog(f,a,b,[],[],lb,ub);>>[x,fval,exitflag]=linprog();exitflag返回一整數(shù)值，代表優(yōu)化算法結(jié)束的原因，對應(yīng)關(guān)系如下：1：優(yōu)化成功，函數(shù)最終收斂到優(yōu)化解點(diǎn)上；0：迭代次數(shù)超過了options.Maxlter值。注：

[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub,options)-2：沒有找到合適解；-3：問題無界；-4：在算法求解的過程中遇到了NAN數(shù)；-5：問題不可實(shí)現(xiàn)；-7：搜索方向變得過小，進(jìn)一步求解過程無法進(jìn)行。例：求解下面的線性規(guī)劃問題Matlab實(shí)現(xiàn)為：>>f=[-2-35];>>a=[-25-1;131];>>b=[-1012];>>lb=[000];>>aeq=[111];>>beq=7;>>[x,fval,exitflag]=linprog(f,a,b,aeq,beq,lb,[]);4如何使用lingo軟件求解線性規(guī)劃例：在主窗口中輸入：min=2*x1+3*x2;x1+x2>=350;x1>=100;2*x1+x2<=600;Globaloptimalsolutionfound.

Objectivevalue:800.0000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCost

X1250.00000.000000

X2100.00000.000000RowSlackorSurplusDualPrice1800.0000-1.00000020.000000-4.0000003150.00000.00000040.0000001.000000點(diǎn)擊Lingo軟件使用的注意事項(xiàng)（1）LINGO中不區(qū)分大小寫字母，變量（和行名）可以使用不超過32個(gè)字符表示，且必須以字母開頭。（2）LINGO中的語句的順序是不重要的，因?yàn)長INGO總是根據(jù)“MAX=”或“MIN=”語句尋找目標(biāo)函數(shù)，而其它語句都是約束條件（當(dāng)然注釋語句和TITLE除外）。（3）LINGO模型是由一系列語句組成，每個(gè)語句以分號“;”結(jié)束。（4）LINGO中以感嘆號“!”開始的是說明語句（說明語句也需要以分號“;”結(jié)束）。（5）LINGO中解優(yōu)化模型時(shí)假定所有變量非負(fù)（除非用限定變量函數(shù)@free或@bin）。@bnd(L,x,U)

限制L≤x≤U

@bnd(L,x,U)

限制L≤x≤U

(1)@bnd(L,x,U):限制L≤x≤U(2)@free(x)

取消對變量x的默認(rèn)下界為0的限制，即x可以取任意實(shí)數(shù).

min=-5*x1+4*x2+2*x3;6*x1-x2+x3<=8;x1+2*x2+4*x3<=10;@bnd(-1,x1,3);@bnd(0,x2,2);min=-5*x1+4*x2+2*x3;6*x1-x2+x3<=8;x1+2*x2+4*x3<=10;@free(x1);x1>=-1;x1<=3;x2<=2;作業(yè)1:使用lingo軟件求解:(1)例2(

投資問題)。(2)提示：@free(x1);@free(x2);@bnd(6,x3,1);某企業(yè)生產(chǎn)兩種產(chǎn)品，分別使用4種原料制成，4種原材料目前庫存量分別為300，400，500和500噸，兩種產(chǎn)品所需各種原材料數(shù)量見表。又知兩種產(chǎn)品的單位利潤分別為2800和3200元/噸，如何計(jì)劃兩種產(chǎn)品的產(chǎn)量，使利潤達(dá)到最大。(求解時(shí)請使用Matlab軟件)

兩種產(chǎn)品所需的原材料數(shù)量原材料產(chǎn)品 1 2 3 4

1 1.4 1.3 1.4 1.4

2 1.6 1.7 1.5 1.7

庫存300400500500作業(yè)2：產(chǎn)品計(jì)劃問題（二）線性規(guī)劃的綜合實(shí)例例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ì)劃？每天：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ù)約束

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

50桶牛奶每天模型求解

max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[A1]3*x1<100;Globaloptimalsolutionfound.

Objectivevalue:3360.000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCost

X120.000000.000000

X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000A140.000000.00000020桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?

A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000

TIME0.0000002.000000

A140.000000.000000原料無剩余時(shí)間無剩余加工能力剩余40三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice1b3360.0001.000000MILK0.00000048.00000TIME0.0000002.000000A140.000000.000000最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤增長48影子價(jià)格結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice1b3360.0001.000000MILK0.00000048.00000TIME0.0000002.000000A140.000000.000000最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤增長48時(shí)間增加1單位,利潤增長2加工能力增長不影響利潤影子價(jià)格

35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？2元！

A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？

A1的獲利增加到40元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？歸結(jié)為求解：最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍LINGOOptionsGeneralSolverDualComputations在下拉框中選中“Price&Ranges”,保存。重新運(yùn)行,然后選擇“LINGO|Range”菜單，得到如下輸出。Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000A1100.0000INFINITY40.00000Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowable

VariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000A1100.0000INFINITY40.00000最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)(約束條件不變)

A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?Globaloptimalsolutionfound.Objectivevalue:3360.000Infeasibilities:0.000000Totalsolveriterations:VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000A140.000000.000000由影子價(jià)格知道：每增加一桶牛奶利潤增長48元，但是增加到一定程度后利潤就不再增長。也即影子價(jià)格的作用是有限制的。問題：影子價(jià)格有意義時(shí)約束右端的允許變化范圍如何確定？結(jié)果解釋

影子價(jià)格有意義時(shí)約束右端的允許變化范圍Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease

MILK50.0000010.000006.666667TIME480.000053.3333380.00000A1100.0000INFINITY40.00000原料最多增加10時(shí)間最多增加53

35元可買到1桶牛奶，每天最多買多少？最多買10桶!例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%的波動(dòng)，對計(jì)劃有無影響？

若公司已經(jīng)簽訂了每天銷售10kgA1的合同必須滿足，該合同對公司的利潤有什么影響？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ù)

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

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

模型求解

max=24*x1+16*x2+44*x3+32*x4-3*x5-3*x6;[milk]4*x1+3*x2+4*x5+3*x6<=600;[time]4*x1+2*x2+6*x5+4*x6<=480;[A1]x1+x5<=100;x3=0.8*x5;x4=0.75*x6;Globaloptimalsolutionfound.

Objectivevalue:3460.800Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCost

X10.0000001.680000

X2168.00000.000000

X319.200000.000000

X40.0000000.000000

X524.000000.000000

X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000A176.000000.00000050.00000044.0000060.00000032.00000結(jié)果解釋每天銷售168千克A2和19.2千克B1，利潤3460.8（元）除A1限制外均為緊約束30元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？RowSlackorSurplusDualPrice13460.8001.000000MILK

0.0000003.160000TIME0.0000003.260000A176.000000.00000050.00000044.0000060.00000032.00000增加1千克A1使利潤增長3.16×12=37.92增加1小時(shí)時(shí)間使利潤增長3.26投資150元增加5桶牛奶，可賺回189.6元。投資150元增加50小時(shí)，可賺回163元?！探Y(jié)果解釋B1,B2的獲利有10%的波動(dòng)，對計(jì)劃有無影響歸結(jié)為求解：最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍max=24*x1+16*x2+44*x3+32*x4-3*x5-3*x6;[milk]4*x1+3*x2+4*x5+3*x6<=600;[time]4*x1+2*x2+6*x5+4*x6<=480;[A1]x1+x5<=100;x3=0.8*x5;x4=0.75*x6;Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX124.000001.680000INFINITYX216.000008.1500002.100000

X344.0000019.750003.166667X432.000002.026667INFINITYX5-3.00000015.800002.533333X6-3.0000001.520000INFINITYRighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK600.0000120.0000280.0000TIME480.0000253.333380.00000A1100.0000INFINITY76.0000050.0INFINITY19.2000060.0INFINITY0.0B1獲利下降10%，超出X3系數(shù)允許范圍B1,B2的獲利有10%的波動(dòng)，對計(jì)劃有無影響B(tài)2獲利上升10%，超出X4系數(shù)允許范圍波動(dòng)對計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為39.6計(jì)算，會發(fā)現(xiàn)結(jié)果有很大變化。

若公司已經(jīng)簽訂了每天銷售10kgA1的合同必須滿足，該合同對公司的利潤有什么影響？Globaloptimalsolutionfound.Objectivevalue:3460.800Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.00000