建模培訓(xùn)-數(shù)學(xué)規(guī)劃

二、線性規(guī)劃模型

線性規(guī)劃模型是所有規(guī)劃模型中最基本、最例1.（食譜問題）設(shè)有n種食物，各含m種營養(yǎng)素，第j種食物中第i種營養(yǎng)素的含量為aij,n種食物價格分別為c1,c2,…,cn，請確定食譜中n種食物的數(shù)量x1,x2,…,xn，要求在食譜中m種營養(yǎng)素簡單的一種.

2.1線性規(guī)劃模型的基本形式

的含量分別不低于b1,b2,…,bm的情況下，使得總的費(fèi)用最低.

首先根據(jù)食物數(shù)量及價格可寫出食譜費(fèi)用為其次食譜中第i種營養(yǎng)素的含量為因此上述問題可表述為：解線性規(guī)劃中的特殊形式----運(yùn)輸問題例2.

設(shè)要從甲地調(diào)出物資2000噸，從乙地調(diào)出物資1100噸，分別供給A地1700噸、B地1100噸、C假定運(yùn)費(fèi)與運(yùn)量成正比.在這種情況下，采用不地200噸、D地100噸.已知每噸運(yùn)費(fèi)如表1.1所示.同的調(diào)撥計劃，運(yùn)費(fèi)就可能不一樣.現(xiàn)在問：怎樣才能找出一個運(yùn)費(fèi)最省的調(diào)撥計劃？1572521甲15375151乙DCBA表1.1銷地運(yùn)費(fèi)產(chǎn)地乙甲DCBA解一般的運(yùn)輸問題可以表述如下：數(shù)學(xué)模型：

若其中各產(chǎn)地的總產(chǎn)量等于各銷地的總銷量，即

類似與將一般的線性規(guī)劃問題轉(zhuǎn)化為其標(biāo)準(zhǔn)否則，稱為不平衡的運(yùn)輸問題，包括：，則稱該問題為平衡的運(yùn)輸問題.總產(chǎn)量>總銷量和總產(chǎn)量<總銷量.形式，我們總可以通過引入假想的銷地或產(chǎn)地，將不平衡的運(yùn)輸問題轉(zhuǎn)化為平衡的運(yùn)輸問題.從而，我們的重點(diǎn)就是解決平衡運(yùn)輸問題的求解.

以1988年美國大學(xué)生數(shù)學(xué)建模競賽B題為例，說明整數(shù)線性規(guī)劃模型的建立及用LINGO軟件包如何求解整數(shù)線性規(guī)劃模型。例3.有七種規(guī)格的包裝箱要裝到兩節(jié)鐵路平板車上去。包裝箱的寬和高是一樣的，但厚度（t，以cm計）及重量（w，以kg計）是不同的.表1給出了每種包裝箱的厚度、重量以及數(shù)量。每節(jié)平板車有10.2m長的地方可用來裝包裝箱（像面包片那樣），載重為40t.由于當(dāng)?shù)刎涍\(yùn)的限制，對于C5,C6,C7類包裝箱的總數(shù)有一個特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm.試把包裝箱裝到平板車上，使得浪費(fèi)的空間最小.種類C1C2C3C4C5C6C7t/cm48.753.061.372.048.752.064.0w/kg200030001000500400020001000n/件8796648

為在第節(jié)車上裝載第件包裝箱的解令

下面我們建立該問題的整數(shù)線性規(guī)劃模型。1)約束條件兩節(jié)車的裝箱數(shù)不能超過需要裝的件數(shù)，即：每節(jié)車可裝的長度不能超過車能提供的長度：每節(jié)車可裝的重量不超過車能夠承受的重量：對于C5,C6,C7類包裝箱的總數(shù)的特別限制：2)目標(biāo)函數(shù)浪費(fèi)的空間最小，即包裝箱的總厚度最大：3)整數(shù)線性規(guī)劃模型由上一步中的求解結(jié)果可以看出，4)模型求解運(yùn)用LINGO軟件求解得到：5)最優(yōu)解的分析說明的裝車方案，此時裝箱的總長度為1019.7cm，兩節(jié)車共裝箱的總長度為2039.4cm.即為最優(yōu)

但是，上述求解結(jié)果只是其中一種最優(yōu)的裝車方案，即此答案并不唯一.背包問題例4.有n個物品，編號為1,2,…,n，第i件物品重ai千克，價值為ci

元，現(xiàn)有一個載重量不超過大，應(yīng)如何裝載這些物品？a千克的背包，為了使裝入背包的物品總價值最用變量xi

表示物品i是否裝包，i=1,2,…,n，并令：解可得到背包問題的規(guī)劃模型為：指派問題例5.有n項(xiàng)任務(wù)，由n個人來完成，每個人只能做一件，第i個人完成第j項(xiàng)任務(wù)要cij小時，如何合理安排時間才能使總用時最小？引入狀態(tài)變量xij

，并令：解則總用時表達(dá)式為：可得到指派問題的規(guī)劃模型為：

上面介紹的指派問題稱為指派問題的標(biāo)準(zhǔn)形式，還有許多其它的諸如人數(shù)與任務(wù)數(shù)不等、及但一般可以通過一些轉(zhuǎn)化，將其變?yōu)闃?biāo)準(zhǔn)形式.某人可以完成多個任務(wù)，某人不可以完成任務(wù)，某任務(wù)必須由某人完成等特殊要求的指派問題.

對于標(biāo)準(zhǔn)形式的指派問題，我們可以利用匈牙利算法實(shí)現(xiàn)求解.它將指派問題中的系數(shù)構(gòu)成一個矩陣，利用矩陣上簡單的行和列變換，結(jié)合解的判定條件，實(shí)現(xiàn)求解（見相關(guān)文獻(xiàn)）.六.非線性規(guī)劃模型

前面介紹了線性規(guī)劃問題，即目標(biāo)函數(shù)和約束條件都是線性函數(shù)的規(guī)劃問題，但在實(shí)際問題建模過程中，還常常會遇到另一類更一般的規(guī)劃問題，即目標(biāo)函數(shù)和約束條件中至少有一個是非線性函數(shù)的規(guī)劃問題，即非線性規(guī)劃問題.2023/11/2623

主程序?yàn)?f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作圖語句

[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin(x)';[xmax,ymax]=fminbnd(f1,0,8)2023/11/2624例2對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？解先編寫M文件fminbndtest.m如下:functionf=myfun(x)f=-(3-2*x).^2*x;主程序調(diào)用fminbnd:[x,fval]=fminbnd('fminbndtest',0,1.5);xmax=xfmax=-fval運(yùn)算結(jié)果為:xmax=0.5000,fmax=2.0000.即剪掉的正方形的邊長為0.5米時水槽的容積最大,最大容積為2立方米.2023/11/2625例3minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)1、編寫M-文件fun1.m:functionf=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2、輸入M文件myprg3.m如下:x0=[-1,1];x=fminunc('fun1',x0);y=fun1(x)

3、運(yùn)行結(jié)果:x=0.5000-1.0000y=1.3029e-102023/11/26262.畫出Rosenbrock函數(shù)的等高線圖,輸入命令：

contour(x,y,z,20)holdonplot(-1.2,2,'o');text(-1.2,2,'startpoint')plot(1,1,'o')text(1,1,'solution')2023/11/26274.

用fminunc函數(shù)(1)建立M-文件fun1.m

functionf=fun1(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2(2)求解主程序oldoptions=optimset('fminunc')options=optimset(oldoptions,'LargeScale','off')

options11=optimset(options,'HessUpdate','dfp')[x11,fval11,exitflag11,output11]=fminunc('fun1',[-1.22],options11)非線性規(guī)劃建模實(shí)例(一)：供應(yīng)與選址

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米）及水泥日用量d(噸)由下表給出。目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20噸。假設(shè)從料場到工地之間均有直線道路相連。（1）試制定每天的供應(yīng)計劃，即從A，B兩料場分別向各工地運(yùn)送多少噸水泥，使總的噸千米數(shù)最小。（2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20噸，問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？（一）、建立模型

記工地的位置為(ai，bi)，水泥日用量為di，i=1,…,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；從料場j向工地i的運(yùn)送量為Xij。當(dāng)用臨時料場時決策變量為：Xij，當(dāng)不用臨時料場時決策變量為：Xij，xj，yj。（二）使用臨時料場的情形

使用兩個臨時料場A(5,1)，B(2,7).求從料場j向工地i的運(yùn)送量為Xij，在各工地用量必須滿足和各料場運(yùn)送量不超過日儲量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問題.線性規(guī)劃模型為：設(shè)X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

編寫程序gying1.m2023/11/2631計算結(jié)果為：x=[3.00005.00000.00007.00000.00001.00000.00000.00004.00000.00006.000010.0000]’fval=136.22752023/11/2632（三）改建兩個新料場的情形

改建兩個新料場,要同時確定料場的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下使總噸千米數(shù)最小.這是非線性規(guī)劃問題。非線性規(guī)劃模型為：2023/11/2633設(shè)X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

x1=X13,y1=X14,x2=X15,y2=X16

（1）先編寫M文件liaoch.m定義目標(biāo)函數(shù)。(2)取初值為線性規(guī)劃的計算結(jié)果及臨時料場的坐標(biāo):x0=[35070100406105127]';編寫主程序gying2.m.2023/11/2634(3)計算結(jié)果為：x=[3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867]’fval=105.4626exitflag=12023/11/2635(4)若修改主程序gying2.m,取初值為上面的計算結(jié)果:x0=[3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867]’得結(jié)果為:x=[3.00005.00000.30947.00000.01080.6798003.690605.989210.32025.53694.91945.82917.2852]’fval=103.4760exitflag=1總的噸千米數(shù)比上面結(jié)果略優(yōu).(5)若再取剛得出的結(jié)果為初值,卻計算不出最優(yōu)解.2023/11/2636(6)若取初值為:x0=[35471000005115.63484.86877.24797.7499]',則計算結(jié)果為:x=[3.00005.00004.00007.00001.0000000005.000011.00005.69594.92857.25007.7500]’fval=89.8835exitflag=1總的噸千米數(shù)89.8835比上面結(jié)果更好.通過此例可看出fmincon函數(shù)在選取初值上的重要性.2023/11/2637A城和B城之間準(zhǔn)備建一條高速公路，B城位于A城正南20公里和正東30公里交匯處，它們之間有東西走向連綿起伏的山脈。公路造價與地形特點(diǎn)有關(guān)，下圖給出了整個地區(qū)的大致地貌情況，顯示可分為三條沿東西方向的地形帶。你的任務(wù)是建立一個數(shù)學(xué)模型，在給定三種地形上每公里的建造費(fèi)用的情況下，確定最便宜的路線。圖中直線AB顯然是路徑最短的，但不一定最便宜。而路徑ARSB過山地的路段最短，但是否是最好的路徑呢？你怎樣使你的模型適合于下面兩個限制條件的情況呢？1.當(dāng)?shù)缆忿D(zhuǎn)彎是，角度至少為1400。2.道路必須通過一個已知地點(diǎn)（如P）。2023/11/26382023/11/2639問題分析

在建設(shè)高速公路時，總是希望建造費(fèi)用最小。如果要建造的起點(diǎn)、終點(diǎn)在同一地貌中，那么最佳路線則是兩點(diǎn)間連接的線段，這樣費(fèi)用則最省。因此本問題是一個典型的最優(yōu)化問題，以建造費(fèi)用最小為目標(biāo)，需要做出的決策則是確定在各個地貌交界處的匯合點(diǎn)。2023/11/2640變量說明

xi：在第i個匯合點(diǎn)上的橫坐標(biāo)（以左下角為直角坐標(biāo)原點(diǎn)），i＝1，2，…，4；

x5＝30（指目的地B點(diǎn)的橫坐標(biāo)）

li

：第i段南北方向的長度（i＝1，…，5）

Si：在第i段上地所建公路的長度（i＝1，2，…，5）。由問題分析可知，2023/11/2641C1：平原每公里的造價（單位：萬元/公里）C2：高地每公里的造價（單位：萬元/公里）C3：高山每公里的造價（單位：萬元/公里）

2023/11/2642模型假設(shè)1、假設(shè)在相同地貌中修改高速公路，建造費(fèi)用與公路長度成正比；2、假設(shè)在相同地貌中修改高速為直線。在理論上，可以使得建造費(fèi)用最少，當(dāng)然實(shí)際中一般達(dá)不到。2023/11/2643模型建立

在A城與B城之間建造一條高速公路的問題可以轉(zhuǎn)化為下面的非線性規(guī)劃模型。優(yōu)化目標(biāo)是在A城與B城之間建造高速公路的費(fèi)用。2023/11/2644模型求解

這里采用Matlab編程求解。模型求解時，分別取Ci如下。平原每公里的造價C1＝400萬元/公里；高地每公里的造價C2＝800萬元/公里；高山每公里的造價C3＝1200萬元/公里。

（注意：實(shí)際建模時必須查找資料來確定參數(shù)或者題目給定有數(shù)據(jù)）

2023/11/2645模型結(jié)果及分析

通過求解可知，為了使得建造費(fèi)用最小。建造地點(diǎn)的選擇宜采取下列結(jié)果。

建造總費(fèi)用為2.2584億元?？傞L度為38.9350公里。

2023/11/2646求解模型的主程序文件model_p97

functionx=model_p97clearallglobalCLC=[4008001200];L=[44444];x=fmincon('objfun_97',[1,1,1,1],[],[],[],[],zeros(1,4),ones(1,4)*30,'mycon_p97');optans=objfun_97(x)C=ones(3,1);len=objfun_97(x)

2023/11/2647模型中描述目標(biāo)函數(shù)的Matlab程序objfun_97.m

functionobj=objfun_97(x)globalCLobj=C(1)*sqrt(L(1)^2+x(1)^2)+C(2)*sqrt(L(2)^2+(x(2)-x(1))^2)+...C(3)*sqrt(L(3)^2+(x(3)-x(2))^2)+C(2)*sqrt(L(4)^2+(x(4)-x(3))^2)+...C(1)*sqrt(L(5)^2+(30-x(4))^2);

2023/11/2648描述約束條件的Matlab函數(shù)mycon_p97.m

function[c,ceq]=mycon_p97(x)c(1)=x(1)-x(2);c(2)=x(2)-x(3);c(3)=x(3)-x(4);c(4)=x(4)-30;ceq=[];2023/11/2649主程序運(yùn)行結(jié)果model_p97optans

=2.2584e+004len

=

38.9350ans

=

12.173114.332315.667717.8269

2023/11/26532用Lingo求解二次規(guī)劃（QP）模型例2.1某廠生產(chǎn)的一種產(chǎn)品有甲、乙兩個牌號，討論在產(chǎn)銷平衡的情況下如何確定各自的產(chǎn)量，使總的利潤最大。所謂產(chǎn)銷平衡指工廠的產(chǎn)量等于市場上的銷量，沒有賣不出去的產(chǎn)品的情況。顯然，銷售總利潤既取決于兩種牌號產(chǎn)品的銷量和（單件）價格，也依賴于產(chǎn)量和（單件）成本，按照市場經(jīng)濟(jì)規(guī)律，甲的價格p1固然會隨其銷量x1的增長而降低，同時乙的銷量x2的增長也會使甲的價格有稍微的下降，可以簡單地假設(shè)價格與銷量成線性關(guān)系，即p1=b1－a11x1－a12x2，b1,a11,a12>0，a11>a12；類似地，乙的價格p2遵循同樣的規(guī)律，即有p2=b2－a21x1－a22x2，b2,a21,a22>0，a22>a21.例如，假定實(shí)際中b1=100，a11=1，a12=0.1，b2=280；a21=0.2，a22=2。此外，假設(shè)工廠的生產(chǎn)能力有限，兩種牌號產(chǎn)品的產(chǎn)量之和不可能超過100件，且甲的產(chǎn)量不可能超過乙的產(chǎn)量的兩倍，甲乙的單件生產(chǎn)成本分別是q1=2和q2=3(假定為常數(shù))。求甲、乙兩個牌號的產(chǎn)量x1，x2使總利潤最大。2023/11/2654優(yōu)化模型

決策變量：決策變量就是甲、乙兩個牌號的產(chǎn)量（也是銷量）x1，x2目標(biāo)函數(shù)：顯然，目標(biāo)函數(shù)就是總利潤z(x1，x2)，即

z(x1，x2)＝（p1－q1）x1＋（p2－q2）x2

＝（100－x1－0.1x2－２）x1＋（280－0.2x1－ 2x2－3）x2

＝98x1＋277x2－x12－0.3x1x2－2x22約束條件：題中假設(shè)工廠的生產(chǎn)能力有限，兩種產(chǎn)品的產(chǎn)量之和不可能超過100件，且產(chǎn)品甲的產(chǎn)量不可能超過乙的產(chǎn)量的兩倍。寫成數(shù)學(xué)表達(dá)式，就是x1＋x2≤100,x1≤2x22023/11/2655綜上所述maxｚ＝98x1＋277x2－x12－0.3 x1x2－2x22

（1.1）

s．t．

x1＋x2≤100（1.2）

x1≤2x2（1.3）

x1，x2≥０（1.4）2023/11/2656

例3.1一奶制品加工廠用牛奶生產(chǎn)A1，A2兩種奶制品，1桶牛奶可以在甲車間用12h加工成3kgA1，或者在乙車間用8h加工成4kgA2。根據(jù)市場需求，生產(chǎn)出的A1，A2全部能售出，且每千克A1獲利24元，每千克A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間為480h，并且甲車間的設(shè)備每天至多能加工100kgA1，乙車間的設(shè)備的加工能力可以認(rèn)為沒有上限限制（即加工能力足夠大）。試為該廠制定一個生產(chǎn)計劃，使每天獲利最大，并進(jìn)一步討論以下3個附加問題： （1）若用35元可以買到1桶牛奶，是否作這項(xiàng)投資？若投資，每天最多購買多少桶牛奶？ （2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？ （3）由于市場需求變化，每千克A1的獲利增加到30元，是否應(yīng)該改變生產(chǎn)計劃？2023/11/2657優(yōu)化模型

決策變量： 設(shè)每天用x1桶牛奶生產(chǎn)A1，用x2桶牛奶生產(chǎn)A2

目標(biāo)函數(shù)： 設(shè)每天獲利為z（元），x1桶牛奶生產(chǎn)3x1(kg)A1，獲利24×3x1，x2桶牛奶生產(chǎn)4x2(kg)A2，獲利16×4x1，故z=72x1+64x2.

約束條件：

原料供應(yīng)：生產(chǎn)A1，A2的原料（牛奶）總量不得超過每 天的供應(yīng)，即x1+x2≤50（桶）；

勞動時間：生產(chǎn)A1，A2的總加工時間不得超過每天正式 工人總的勞動時間，即12x1+8x2≤480（h）；

設(shè)備能力：A1的產(chǎn)量不得超過甲車間設(shè)備每天的加工 能力，即3x1≤100；

非負(fù)約束：x1，x2均不能為負(fù)值。2023/11/2658綜上所述Maxz=72x1+64x2；s.t.x1+x2≤50，

12x1+8x2≤480，

3x1≤100，

x1，x2≥0線性規(guī)劃模型（LP）2023/11/2659模型分析與假設(shè)

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

圖解法

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

Z=0Z=2400Z=3600z=c(常數(shù))~等值線c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個頂點(diǎn)取得。2023/11/2661Lingo優(yōu)化模型這是一個（連續(xù)）線性規(guī)劃（LP）問題2023/11/2662“LINGO|Solve”求解結(jié)果報告（1）若用35元可以買到1桶牛奶，是否作這項(xiàng)投資？若投資，每天最多購買多少桶牛奶？（2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？（3）由于市場需求變化，每千克A1的獲利增加到30元，是否應(yīng)該改變生產(chǎn)計劃？“LINGO|Range”敏感性分析2023/11/2663結(jié)論應(yīng)該批準(zhǔn)用35元買1桶牛奶的投資，但每天最多購買10桶牛奶。可以用低于2元/h的工資聘用臨時工人以增加勞動時間，但最多增加53.3333h。若每千克A1的獲利增加到30元，則x1系數(shù)變?yōu)?0×3=90，在允許的范圍內(nèi)，所以不應(yīng)改變生產(chǎn)計劃，但最優(yōu)值變?yōu)?0×20+64×30=3720。2023/11/2664

例4.1SAIL