運籌學錢頌迪

第2章線性規(guī)劃及

單純形法本章主要內容線性規(guī)劃問題及其數學模型圖解法單純性法的計算步驟應用舉例2.1線性規(guī)劃問題及其數學模型2.1.1問題的提出例1：某工廠計劃制造Ⅰ、Ⅱ兩種產品，占用一種設備和兩種原材料A、B，通過分析與抽象，各數據見下表。項目ⅠⅡ現有可用資源設備

被占用1h/每件被占用2h/每件8h原材料A被占用4kg/每件被占用0h/每件16kg原材料B被占用0kg/每件被占用4kg/每件12kg單件利潤（元）23問：兩種產品各制造多少件，能使利潤最大？例1中設該公司應該制造Ⅰ類家電X1件設該公司應該制造Ⅱ類家電X2件這樣，其利潤為根據這個目標函數，我們只要把盡量做大，利潤就一定會高。但這可行嗎？不可行！我們還有許多制約條件：對設備:對原材料A:對原材料B：還有，每個家電要么生產，要么不生產非負條件X1，X2稱為決策變量Z稱為目標函數例2：某奶牛生產商，他的目標是用最低的成本飼養(yǎng)奶牛，但必須保證奶牛有足夠的營養(yǎng)。具體數據見下表。

飼料A飼料B每噸價格（元）100200每噸飼料的營養(yǎng)單位數每期需要的最低營養(yǎng)單位數蛋白質1140鈣3160碳水化合物1660設兩種飼料的購買量為X1和X2（決策變量）例

靠近某河流有兩個化工廠，流經第一化工廠的河流流量為每天500萬m3，在兩個工廠之間有一條流量為200萬m3的支流。兩化工廠每天排放某種有害物質的工業(yè)污水分別為2萬m3和1.4萬m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水的成本分別為1000元/萬m3和800元/萬m3?，F在要問在滿足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠處理工業(yè)污水的費用最小.工廠1工廠2200萬m3500萬m3其它例子決策變量：x1、x2——分別代表工廠1和工廠2處理污水的數量(萬m3)。則目標函數：minz=1000x1+800x2約束條件：第一段河流（工廠1——工廠2之間）：

(2－x1)/500≤0.2%第二段河流：[0.8(2－x1)+(1.4－x2)]/700≤0.2%此外有：

x1≤2；x2≤1.4化簡有：

minz=1000x1+800x2x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥0數學模型的一般表達式設有n個決策變量xj

(j=1,2,…,n)。目標函數中的系數cj

（價值系數）;設有m個約束條件，該條件中各變量的系數aij稱為技術系數或工藝系數，i=1,2,…,m;約束條件等式（或不等式）右側為bi.這樣，線性規(guī)劃問題數學模型的一般表達式簡寫式2.1.2圖解法(GraphicalSolution)一、基本概念目標函數等值線(Objectivefunctionline)——為于同一直線上的點，具有相同的目標函數值；二、圖解法步驟(Procedure)（1）畫出線性規(guī)劃問題的可行域；（2）畫出兩條目標函數等值線；（3）平行移動目標函數等值線，使目標函數在可行域范圍內達到最優(yōu)。三、圖解法只能適用于模型中僅含兩個變量的問題再看書上的例1x2x1z2=6該問題有唯一最優(yōu)解x1=4；x2=2最優(yōu)目標函數值為144x2≤12例1maxZ=2x1+3x2x1+2x2≤84x1≤164x2≤12x1、x2≥0z*=134x1≤16x1+2x2≤8其他情況B點和C點所代表的坐標同時為最優(yōu)解，即該問題有無窮多最優(yōu)解例1maxZ=2x1+4x2x1+2x2≤84x1≤164x2≤12x1、x2≥0原問題：maxZ=2x1+3x2x2x14x2≤12z*=134x1≤16x1+2x2≤8BC例

maxz=x1+x2x1－x2≥1

－x1+2x2≤0x1、x2≥0

問題有無界解

(unbounded)1－11z=32z=5OAx1－x2≥1－x1+2x2≤0還有一種情況是無可行解。從圖形來說，約束方程形成的可行域沒有交集。由圖解法得到的啟示解的情況有：唯一最優(yōu)解；無窮最優(yōu)解；無界解；也有無解（可行區(qū)矛盾或者不存在）可行域若存在，則它是個凸多邊形，為凸集若線性規(guī)劃問題的最優(yōu)解存在，它一定可以在可行域的某一個頂點上得到若在兩個頂點上同時得到最優(yōu)解，則該兩點連線上的所有點都是最優(yōu)解，即LP有無窮多最優(yōu)解若可行域非空有界，則一定有最優(yōu)解解題思路：先找出凸集的任一頂點，計算頂點處的目標函數值；依次比較，目標函數值最大的即為最優(yōu)解2.1.3線性規(guī)劃問題的標準形式標準形式目標函數為尋求最大約束條件除決策變量約束為非負約束外（Xi≥0

），其余為等式約束，且b≥0如果不滿足這些條件或者要求，均可“改造”成標準形式。改造方式如下：1、如果目標函數為minZ，則將右邊乘以（-1）如果bi<0（即不滿足b為非負條件）,則將該式兩邊同乘（-1）2、如果約束條件為不等式1）當約束條件為“≤”時，如2x1+2x2≤12，增加一個非負變量x3，使得2x1+2x2+x3=12松弛變量(slackvariable)2）當約束條件為“≥”時，如10x1+12x2≥18，增加一個非負變量x4，使得10x1+12x2-x4=18過剩變量(surplusvariable)新增加的決策變量，在目標函數中的系數為零3、如果xj無約束，即它的取值可能為正，可能為負，還可能為零，則令Xj=xj′-xj′′其中xj′≥0，xj′′≥0這樣，原來的一個變量變成了二個變量4、如果xj≤0,令xj′=-xj其中xj′≥0例子將下例線性規(guī)劃問題化為標準形式問題目標函數追求最小，而不是最大x3取值無約束第一個約束方程為“≤”，第二個約束方程為“≥”第三個約束方程為等式令Z’=-Z,使min→max;X3=x’3-x’’3,其中x’3≥0，x’’3≥0，滿足了X3無約束的條件，也使新的變量x’3

、x’’3都為非負對約束條件一加變量x4;對約束條件二減變量x5這樣，該問題的標準形式為課后作業(yè)：55頁2.1(1);2.2題的（1）,第二題只做第一問2.1.4線性規(guī)劃問題解的概念對于標準形式的線性規(guī)劃：

maxz=cX

（a）

AX=bX≥0（b）線性規(guī)劃問題就是求解X，要保證X滿足約束條件，有使目標函數取得最大可行解(feasiblesolution)——滿足約束條件（b）的點X=（x1，x2，…，xn）T稱為該LP的一個可行解；可行域(FeasibleRegion)——所有可行解組成的集合，也稱為可行解集；最優(yōu)解(optimalsolution)——使目標函數值達到最大的可行解3．基、基變量、非基變量

(base,basicvariable,nonbasicvariable)設約束方程的系數矩陣A中，有m個線性無關的列向量，且設

B=（P1，P2，…，Pm）線性無關，則稱B為該LP的一個基；相應的

P1，P2，…，Pm——為基向量；與之對應的變量

x1，x2，…，xm——基變量，記為：XB=（x1，x2，…，xm）T

；其余的向量為非基向量，記為：N=（Pm+1，Pm+2，…，Pn）；其余的變量為非基變量

，記為：XN=（xm+1，xm+2，…，xn）T；4．基本解(基解basicsolution)、基可行解、可行基將AX=b改寫

（B，N）（XB，XN）T=b有：

BXB=b－NXN令

XN=0得到

BXB=b——線性方程組。由于B中各列向量線性無關，因此解此方程組有唯一解即：XB=（x10，x20，…，xm0）T于是得到AX=b的一個確定的解：

X0=（XB，XN）T=（x10，x20，…，xm0，0，0，…，0）T稱X0為該線性規(guī)劃對應與基B的一個基本解。所有X滿足非負條件的基解就是基可行解對應基可行解的基叫可行基2.2線性規(guī)劃問題的集合意義2.2.1凸集的定義定義凸集——設K是n維歐氏空間的一個點集，若任意兩點X(1)∈K，X(2)∈K的連線上所有的點X=αX（1）+（1－α）X（2）∈K，（0≤α≤1），則稱K為凸集。2.2.2幾個定理定理1

若線性規(guī)劃存在可行域，則其可行域R=｛X|AX=b，X≥0｝是凸集。定理2

線性規(guī)劃問題的可行解X=（x1，x2，…，xn）T為基可行解的充要條件是：X的非零分量所對應的系數列向量是線性無關的。定理3

如果線性規(guī)劃有可行解，則一定有基可行解。定理4

線性規(guī)劃問題的基可行解對應于可行域的頂點。定理5

若線性規(guī)劃問題的可行域非空有界，則線性規(guī)劃問題的最優(yōu)解一定可以在其可行域的某個頂點上得到以上定理的理論證明（略）2.3單純形法2.3.1舉例根據圖解法以及前面的定理，解題思路：先找出凸集的任一頂點，計算頂點處的目標函數值；依次比較，目標函數值最大的即為最優(yōu)解。但單純形法是不是就是簡單的比較呢？我們說不是，否則不需要專門講述了。來看簡單比較的做法：在A中任選m個線性無關的列向量都可以組成一個基，對應著一個基本解。對于一個LP最多有多少呢？從n個中選m個進行組合，即：Cnm=n！/[（n－m）！m！]舉例：找出下列LP所有的基及其對應的基本解、基可行解、最優(yōu)解

maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1、x2≥0解：化為標準型

maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1++x4=164x2+x5=12x1、x2，x3，x4

，x5≥0

P1P2P4P3P5答案如下表根據排列組合公式，有Cnm=n!/[(n-m)!m!]=5!/(2!3!)=10。但P1、P3、P4和P2、P3、P5兩個向量組合不能作為基。

基 基本解可行否目標值B1=(P1，P2，P3)B2=(P1，P2，P4)B3=(P1，P2，P5)B4=(P1，P3，P5)B5=(P1，P4，P5)B6=(P2，P3，P4)B7=(P2，P4，P5)B8=(P3，P4，P5)X1=(4，3，-2，0，0)TX2=(2，3，0，8，0)TX3=(4，2，0，0，4)TX4=(4，0，4，0，12)TX5=(8，0，0，-16，12)TX6=(0，3，2，16，0)TX7=(0，4，0，16，-4)TX8=(0，0，8，16，12)T×√√√×√×

√171314*8169120以上是窮舉法，不是單純形法。單純形法的基本思想：在有限的基可行解中尋找最優(yōu)解。即，從初始基可行解出發(fā)，轉換到另一個基可行解，使目標值增大，直到達到最優(yōu)解，或判斷出無最優(yōu)解為止。通常，初始基選擇單位矩陣（后面會詳細講）求解過程：從引例可以總結出求解過程：（1）找出初始基及其基可行解；（2）判斷是否為最優(yōu)解，是停止，否則轉下一步；（3）轉換可行基，并求出相應的基可行解，使目標函數值有所改進，轉（2）。

舉例：用單純形法的基本思路解前面例子的線性規(guī)劃問題

Maxz=2x1

+3x2

s.t.x1

+2x2

+x3

=84x1

+x4=164x2

+x5

=12

x1,x2,x3,x4,x5

≥0第一次迭代：（1）取初始可行基B8=(p3,p4,p5)，那么x3，x4，x5為基變量，x1，x2為非基變量。將基變量和目標函數用非基變量表示：

z=2x1+3x2

x3=8-x1

-2x2

x4=16-4x1

x5=12-4x2當非基變量x1，x2=0時，相應的基變量和目標函數值為x3=8，x4=16，x5=12，z=0，得到當前的基本可行解：x=(0,0,8,16,12)T，z=0。這個解對應于圖解法中的坐標原點。

（2）選擇進基變量。在目標函數z

=2x1

+3x2中，非基變量x1，x2的系數都是正數，因此x1，x2進基都可以使目標函數z增大，但x2的系數為3，絕對值比x1的系數2大，因此把x2作為進基變量可以使目標函數z增加更快。選擇x2為進基變量，使x2的值從0開始增加，另一個非基變量x1保持零值不變。

（3）確定出基變量。在約束條件

x3=8-x1

-2x2

x4=16–4x1

x5=12-4x2中，由于進基變量x2在3個約束條件中的系數都是負數，當x2的值從0開始增加時，基變量x3、x4、x5的值分別從當前的值8、16和12開始減少，當x2增加到3時（此時x1=0

），x5首先下降為0成為非基變量。這時，新的基變量為x3、x4、x2，新的非基變量為x1、x5，當前的基本可行解和目標函數值為：x=(0，3，2，16，0)T，z=9。這個解對應于圖中的縱坐標上可行域的最高點。

第二次迭代：（1）當前的可行基為B6=(p2,p3,

p4)，那么x2，x3，x4為基變量，x1，x5為非基變量。將基變量和目標函數用非基變量表示（由原方程導出）：

z=9+2x1

–(3/4)x5

x2=3–(1/4)x5x3=2-x1

+(1/2)x5

x4=16-4x1

（2）選擇進基變量。在目標函數z=9+2x1

–(3/4)x5

中，非基變量x1的系數是正數，因此x1進基可以使目標函數z增大，于是選擇x1進基，使x1的值從0開始增加,另一個非基變量x5保持零值不變。

(3)確定出基變量。在約束條件（注意x5不變）

x2=3–(1/4)x5x3=2-x1

+(1/2)x5

x4=16-4x1中，由于進基變量x1在兩個約束條件中的系數都是負數，當x1的值從0開始增加時，基變量x3、x4的值分別從當前的值2、16開始減少，當x1增加到2時，x3首先下降為0成為非基變量。這時，新的基變量為x1、x2、x4，新的非基變量為x3、x5，當前的基本可行解和目標函數值為：x=(2，3，0，8，0)T，z=13。這個解對應于圖中的B點。

第三次迭代：（1）當前的可行基為B2=(p1,p2,p4)，那么x1，x2，x4為基變量，x3，x5為非基變量。將基變量和目標函數用非基變量表示：

z=13–2x3+(1/4)

x5x1=2-x3

+(1/2)x5

x2=3–(1/4)x5x4=8+4x3

-2x5

（2）選擇進基變量。在目標函數z=13-2x3

+(1/4)x5

中，非基變量x5的系數是正數，因此x5進基可以使目標函數z增大，于是選擇x5進基，使x5的值從0開始增加,另一個非基變量x3保持零值不變。

(3)確定出基變量。在約束條件（注意x5不變）x1=2-x3+(1/2)x5

x2=3–(1/4)x5x4=8+4x3-2x5中，由于進基變量x5在兩個約束條件中的系數都是負數，當x5的值從0開始增加時，基變量x2、x4的值分別從當前的值3、8開始減少，當x5增加到4時，x4首先下降為0成為非基變量。這時，新的基變量為x1、x2、x5，新的非基變量為x3、x4，當前的基本可行解和目標函數值為：x=(4，2，0，0，4)T，z=14。這個解對應于圖中的C點。

第四次迭代：（1）當前的可行基為B3=(p1,p2,p5)，那么x1，x2，x5為基變量，x3，x4為非基變量。將基變量和目標函數用非基變量表示：

z=14–（3/2)x3–(1/8)

x4x1=4–(1/4)x4x2=2–(1/2)x3+(1/8)x4

x5=4+2x3

–(1/2)x4

（2）在目標函數

z=14–(3/2)x3–（1/8）x4

中，非基變量x3、x4的系數均不是正數，因此進基都不可能使目標函數z增大，于是得到最優(yōu)解，

x*=(4，2，0，0，4)T最優(yōu)目標值為z*=14。這個解對應于圖解法中的C點。我們也稱相應的基

B3=(p1,p2,p5)為最優(yōu)基。計算結束。

3.3.2初始基可行解的確定通常選單位矩陣的那個基作為初始基根據此，可以容易算出它的可行解。通常此時的解不是最優(yōu)解（1）x1=b’1-（a’1m+1xm+1+a’1m+2xm+2+…+a’1nxn）x2=b’2-（a’2m+1xm+1+a’2m+2xm+2+…+a’2nxn）(2-1).`..

xm=b’m-（a’mm+1xm+1+a’mm+2xm+2+…+a’mnxn）把它們代入目標函數，得

z=z’+m+1xm+1+m+2xm+2+…+nxn

(2-2)其中

j=cj-（c1a’1j+c2a’2j+…+cm

a’mj）

我們把由非基變量表示的目標函數形式稱為基B相應的目標函數典式。3.3.3最優(yōu)性檢驗和解的判斷

檢驗數法(evaluationindex)檢驗數——用非基變量表示目標函數后，非基變量在目標函數中的系數，用σj

表示經過前面的理論推導說明，檢驗數為：最優(yōu)性檢驗(optimalitytesting)判別定理1：設X為線性規(guī)劃的一個基可行解，且對于一切j∈J（J為非基變量的下標集）有σj≤0，則X為線性規(guī)劃的最優(yōu)解；判別定理2：設X為線性規(guī)劃的一個基可行解，且對于一切j∈J（J為非基變量的下標集）有σj≤0，同時有某個非基變量的檢驗數σk=0（k∈J），則該線性規(guī)劃有無窮多最優(yōu)解；判別定理3：設X為線性規(guī)劃的一個基可行解，若有σk>0（k∈J），且Pk≤0，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。若對于一切j∈J有σj≤0，則已得到線性規(guī)劃的最優(yōu)解，可停止計算，否則轉下一步；若有σk>0（k∈J），且Pk≤0，則該線性規(guī)劃問題具有無界解（無最優(yōu)解），停止計算，否則轉下一步1、換入變量的確定

若j>0，那么相應的非基變量xj，它的值從當前值0開始增加時，目標函數值隨之增加。這個選定的非基變量xj稱為“進基變量”，選j>0

中的最大值max(j

>0)=k的那個變量作為換入的基變量。如果任何一個非基變量的值增加都不能使目標函數值增加，即所有j

非正，則當前的基本可行解就是最優(yōu)解，計算結束；3.3.4基變換2、換出變量的確定

根據前面的例子，我們可以認為滿足：=minb’i/a’ij

a’ij>0=b’r

/a’rj這個基變量xr稱為“出基變量”。當進基變量的值增加到

時，出基變量xr的值降為0時，可行解就移動到了相鄰的基本可行解（極點）。如果進基變量的值增加時，所有基變量的值都不減少，即所有a’ij

非正，則表示可行域是不封閉的，且目標函數值隨進基變量的增加可以無限增加，此時，不存在有限最優(yōu)解，計算結束；2.3.5迭代計算將進基變量作為新的基變量，出基變量作為新的非基變量，確定新的基、新的基本可行解和新的目標函數值。在新的基變量、非基變量的基礎上重復以上計算。線性規(guī)劃采用的是線性代數中的矩陣求解法，迭代就是對系數矩陣用高斯消元法進行運算。具體見課堂講授2.4單純形法的計算步驟2.4.1單純形表；結合表格課堂講授各元素的含義，以及檢驗數的計算2.4.2計算步驟（1）找出初始可行基，建立初始單純形表（2）進行最優(yōu)性檢驗（3）從一個基可行解轉換到相鄰的目標函數值更大的基可行解，列出新的單純形表（4）重復第（2）、（3）步，直到得到最優(yōu)解為止。單純形法解題舉例用單純形法的表格法求解

max

z=2x1+3x2x1+2x2≤84x1≤164x2≤12x1、x2≥0解：化為標準型

max

z=2x1+3x2+0x3+0x4+0x5x1+2x2

+x3=84x1

+x4=164x2

+x5=12x1、x2，x3，x4

，x5≥0找初始可行基：B1=（P3，P4，P5）從表中有：X（1）=（0，0，8，16，12）T為對應于基B1的基可行解，顯然不是最優(yōu)解；根據max｛σj|σj>0｝=σ2，確定x2為換入變量；

按θ規(guī)則確定換出變量，即：θ=min｛bi/aik|aik>0｝=12/4，對應的x5為換出變量；列初始單純形表以[4]為主元素進行迭代，得新的單純形表：從表中有：X（2）=（0，3，2，16，0）T為對應于基B2的基可行解，顯然不是最優(yōu)解；根據max｛σj|σj>0｝=σ1，確定x1為換入變量；

按θ規(guī)則確定換出變量，即：θ=min｛bi/aik|aik>0｝=2/1，對應的x3為換出變量；從表中有：X（3）=（2，3，0，8，0）T為對應于基B3的基可行解，也不是最優(yōu)解；根據max｛σj|σj>0｝=σ1，確定x4為換入變量；按θ規(guī)則確定換出變量，即：θ=min｛bi/aik|aik>0｝=8/2，對應的x4為換出變量；以[1]為主元素進行迭代，得新的單純形表：表中σj≤0，j=1，…，5，因此得最優(yōu)解：X*=（4，2，0，0，4）T，Z*=14以[2]為主元素進行迭代，得新的單純形表：例2：用單純形法求解

max

z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0標準形式為max

z=50x1+100x2x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1、x2、x3、x4、x5≥0課后作業(yè)（第二次）56頁，2.4中，只求出2.1（1）的最優(yōu)解即可。要求用表格法單純形法的計算機求解所用軟件ManagementScientist演示線性規(guī)劃的應用(ApplicationsofLP)(下頁)例紅旗商場是個中型的百貨商場，它對售貨人員的需求經過統計分析如表所示。為了保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應該如何安排售貨人員的作息，既滿足了工作需要又使配備的售貨人員的人數最少？時間所需售貨員星期日星期一星期二星期三星期四星期五星期六28人15人24人25人19人31人28人一、人力資源分配問題線性規(guī)劃的應用解：設x1為星期一開始上班的人數，x2為星期二開始上班的人數，……，x7星期日開始上班的人數。我們就可得到如下的數學模型：

minx1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x7≥28x4+x5+x6+x7+x1≥15x5+x6+x7+x1+x2≥24x6+x7+x1+x2+x3≥25x7+x1+x2+x3+x4≥19x1+x2+x3+x4+x5≥31x2+x3+x4+x5+x6≥28x1、x2、x3、x4、x5、x6、x7≥0該問題的最優(yōu)解為：x1=8，x2=0，x3=12，x4=0，x5=11，x6=5，x7=0；目標函數的最小值為36。媒體被告知的潛在顧客數（人/次）廣告費用（元/次）媒體最高使用次數（次）每次宣傳的質量日間電視夜間電視日報周末新聞雜志電臺廣播10002000150025003001500300040010001001510254306590406020例

某房地產開發(fā)公司正在建造一個湖邊小區(qū)，公司準備投入3萬元進行廣告媒體宣傳，希望能夠吸引周圍的中高收入家庭前來購房。目前有5種媒體可供選擇，相關信息如表所示。對于這次活動，公司有下列要求：至少進行10次電視廣告；至少有5萬名潛在顧客被告知；電視廣告投入不超過18000元。如何進行媒體組合，才能使廣告質量最高？二、媒體選擇解

問題中媒體組合實際上就是要決定每種媒體的使用次數。設x1、x2、x3、x4、x5分別表示表中日間電視、夜間電視、日報、周末新聞雜志、電臺廣播五種媒體的使用次數。該問題的線性規(guī)劃模型為

maxz=65x1+90x2+40x3+60x4+20x51500x1+3000x2+400x3+1000x4+100x5≤30000

1000x1+2000x2+1500x3+2500x4+300x5≥50000x1+x2≥101500x1+3000x2≤18000x1≤15x2≤10

x3 ≤25

x4≤4

x5≤30

x1，x2，x3，x4，x5≥0這是一個有5個變量，9個約束條件的線性規(guī)劃模型，求解結果如下：媒體最佳播放次數（次）廣告費用（元）日間電視1015000日報2510000周末新聞雜志22000電臺廣播303000被告知的顧客數=61500人產品宣傳質量=2370目標函數最優(yōu)值為：2370變量最優(yōu)解檢驗數

x1100

x20－65

x3250

x420

x5300約束松弛/剩余變量對偶價格

10

0.06

2115000

30－25

430000

550

6100

7016

820

9014包括：資本預算、資產分配、財政計劃等（一）投資組合問題：從多種投資選擇中選擇具體的投資：股票和債券、基金、保險等；目標：預期收益極大化、風險最小化約束：投資類型、國家法律、公司政策、風險或效益限制等三、財政應用案例

Welte公司擁有100000美元，財務專家確定了如下5個投資機會，并預計了它們的年收益：1.在石油或鋼鐵行業(yè)投資不能超過50000每元；2.對政府債券的投資至少相當于對鋼鐵行業(yè)投資的25%；3.對太平洋石油的投資不能多于整個石油行業(yè)投資的60%求預期收益最大的投資方案。投資預期收益率（%）大西洋石油太平洋石油中西部鋼鐵Huber鋼鐵政府債券7.310.36.47.54.5設：Atl=大西洋石油投資；Pac=太平洋石油投資；

Mid=中西部鋼鐵投資；Hub=Huber鋼鐵投資；Gov=政府債券投資則問題的數學模型為：

Maxz=0.073Atl+0.103Pac+0.064Mid+0.075Hub+0.045Gov

Atl+Pac+Mid+Hub+Gov=100000總投資

Atl+Pac≤50000石油投資限制

Mid+Hub≤50000鋼鐵投資限制

-0.25Mid–0.25Hub+Gov≥0政府債券比例

-0.6Atl+0.4Pac≤0太平洋石油限制

Atl,Pac,Mid,Hub,Gov≥0(二)、金融計劃案例

某公司現有68名員工申請?zhí)崆巴诵?。公司必須在此后?年內對這些員工分期支付一定數量的現金，如下表所示。 為了完成這項現金支付任務，公司的財務人員必須現在就為此制定一個投資計劃。投資計劃有政府債券投資和銀行儲蓄兩種方式組成。年份（年）12345678合計現金支付(千元)4302102222312401952252552008注意:三種政府債券的票面價值均為1000元，債券到期時按票面價值進行支付，利率的計算也以票面的價值為基準。銀行儲蓄年利率為4%。如何安排投資計劃，使公司以最小的投資額完成對退休員工的現金支付任務？政府債券投資有三種債券類型可供選擇，如下表所示。債券價格（元）利率（%）到期年限111508.8755210005.50063135011.7507解：1．確定決策變量設F為完成投資計劃所需要的總資金額。x1、x2、x3分別表示債券1、2、3的購買量；yi

(i=1,…，8)表示第i年初銀行儲蓄的投資額。2．確定約束條件這類問題的一個典型特征就是每年現金支付的一般表達式為：年初可用資金額–當年用于債券和儲蓄的資金額

=當年現金支付于是有

F–1.15x1–1x2–1.35x3–y1=430

（第1年）對于第二年，用于三種債券投資的第一年利息加上第一年儲蓄利息為年初可用資金，第二年用于儲蓄的資金為y2，因此有

0.08875x1+0.055x2+0.1175x3+1.04y1–y2=210（第2年）同理對于其它年份有0.08875x1+0.055x2+0.1175x3+1.04y2–y3=222（第3年）0.08875x1+0.055x2+0.1175x3+1.04y3–y4=231（第4年）0.08875x1+0.055x2+0.1175x3+1.04y4–y5=240（第5年）1.08875x1+0.055x2+0.1175x3+1.04y5–y6=195（第6年）

1.055x2+0.1175x3+1.04y6–y7=225（第7年）

1.1175x3+1.04y7–y8=255（第8年）因此事實上，y8的值應為0，若大于0，那么對應的投資計劃必定不是最優(yōu)的。3.確定目標函數目標就是使?jié)M足要求的投資額最小，即Minz=F綜合有如下數學模型

Minz=FF–1.15x1–1x2–1.35x3–y1=4300.08875x1+0.055x2+0.1175x3+1.04y1–y2=2100.08875x1+0.055x2+0.1175x3+1.04y2–y3=2220.08875x1+0.055x2+0.1175x3+1.04y3–y4=2310.08875x1+0.055x2+0.1175x3+1.04y4–y5=2401.08875x1+0.055x2+0.1175x3+1.04y5–y6=1951.055x2+0.1175x3+1.04y6–y7=225

1.1175x3+1.04y7–y8=255x1，x2，x3≥0，yi≥0，i=1，…，8該線性規(guī)劃模型的求解結果為目標函數最優(yōu)值為：1728.794變量最優(yōu)解檢驗數

F1728.794

0

x1144.9880

x2187.8560

x3228.1880

y1636.1480

y2501.6060

y3349.6820

y4182.6810

y500.064

y600.0126

y700.0213

y800.671即得到最佳投資計劃如下表所示:債券購買量投資額(千元)年份儲蓄額(千元)1144.9881.150×144.988=166.7361636.1482187.8561.000×187.856=187.8562501.6063228.1881.350×228.188=308.0543349.682總投資額F=1728794元4182.681

5～80約束松弛/剩余變量對偶價格

10－1.000

20－0.962

30－0.925

40－0.889

50－0.855

60－0.760

70－0.719

80－0.671結果分析：前4年的儲蓄額均大于0，可見從第6年起債券的利息和債券到期收入才能夠完全滿足當前現金支付需要。每一個約束條件的對偶價格均為負值，說明減少任何一年的現金支付都將有利于公司總投資額的降低。對偶價格的逐年降低也說明了，在前面年份減少現金支付將對總投資額的減少更為有效。從而暗示了公司可以適當減少前面年份的現金支付量，而在后面年份進行補足。**LP在制造業(yè)中的應用(Applications)線性規(guī)劃在制造業(yè)也有廣泛的應用——最優(yōu)產品組合、資源最優(yōu)分配、最優(yōu)生產計劃、自制和外購決策、勞動力最優(yōu)分配問題等等。例Hartman公司的管理層正嘗試決定接下來的計劃期間兩種產品中的每一種產品的生產數量。下表的信息包括了可用的勞動力、勞動力的利用以及產品的獲利能力。部門單位產品耗時(h/件)可利用的勞動時間(h)產品1產品2ABC1.000.300.200.350.200.501003650單位產品利潤($)30.0015.00一、最優(yōu)產品組合為Hartman公司建立一個LP模型,以決定產品1和產品2的最優(yōu)生產數量假設某些部門安排了加班，你建議哪個部門安排加班，你愿意為每個部門每小時支付多少加班費；若A、B、C各可安排加班10、6、8小時，且加班費分別為18美元/h、22.5美元/h和12美元/h。再建立一個LP模型，用于決定加班后的最優(yōu)生產量，并回答有關加班時間、利潤增加量等問題解(1)

設P1,P2分別為產品1、2的產量，則問題的數學模型為：max

z=30P1+15P2P1+0.35P2≤1000.3P1+0.2P2≤36

02P1+0.5P2≤50P1、P2≥0計算機求解結果目標函數最優(yōu)值為：3236.84變量最優(yōu)解檢驗數

P181.580

P252.630約束松弛/剩余變量對偶價格

1015.79

2047.37

37.370解(2)

可在A部門和B部門，最多愿意支付的加班費分別為15.79美元/h和43.37美元/h;解(3)社三部門的加班時間分別為YA、YB和YC，則max

z=30P1+15P2–18YA–22.5YB–12YCP1+0.35P2≤100+YA0.3P1+0.2P2≤36+YB

0.2P1+0.5P2≤50+YCYA<=10YB<=6YC<=8P1、P2,YA,YB,YC≥0LPOPTIMUMFOUNDATSTEP4OBJECTIVEFUNCTIONVALUE:3341.337VARIABLEVALUEREDUCEDCOSTP187.2093050.000000P265.1162800.000000YA10.0000000.000000YB3.1860470.000000YC0.0000006.505814ROWSLACKORSURPLUSDUALPRICES2)0.00000022.1511633)0.00000022.5000004)0.0000005.4941865)0.0000004.1511636)2.8139530.0000007)8.0000000.000000某公司有Ⅰ，Ⅱ兩種產品，預計兩種產品的市場需求量分別為3000件和2000件。兩種產品均由a、b、c三個部件組成，各部件生產消耗工時和自制/外購成本如下表所示。部件單位部件制造工時（分鐘）自制成本（元/件）購買成本（元/件）A1.00.500.60B產品Ⅰ3.03.754.00產品Ⅱ2.53.303.90C產品Ⅰ1.00.600.65產品Ⅱ1.50.750.78二、自制或購買決策部件單位部件制造工時（分鐘）自制成本（元/件）購買成本（元/件）A1.00.500.60B產品Ⅰ3.03.754.00產品Ⅱ2.53.303.90C產品Ⅰ1.00.600.65產品Ⅱ1.50.750.78由于生產能力有限，公司只有200個正常制造工時和50個加班工時可用于這兩種產品的生產。每個加班工時需額外支付9元。如何安排部件自制和外購的數量，從而使總成本（包括生產成本、外購成本和加工費用）最低？解：1．確定決策變量設xa、xb1、xb2、xc1、xc2分別表示a部件、用于產品Ⅰ的b部件、用于產品Ⅱ的b部件、用于產品Ⅱ的c部件、用于產品Ⅱ

的c部件的自制量。相應地，設ya、yb1、yb2、yc1、yc2分別為各部件的外購量。設y0為加班工時數。

2．確定約束條件a部件的需求量約束

xa+ya=5000用于產品Ⅰ的b部件的需求量約束

xb1+yb1=3000用于產品Ⅱ的b部件的需求量約束

xb2+yb2=2000用于產品Ⅰ的c部件的需求量約束

xc1+yc1=3000用于產品Ⅱ的c部件的需求量約束

xc2+yc2=2000最大加班工時數約束

y0≤50最大生產能力約束

xa+3xb1+2.5xb2+xc1+1.5xc2≤200×60+60y03．確定目標函數目標是使總成本最小，即Minz=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+3.9yb2+0.6xc1+0.65yc1+0.75xc2+0.78yc2+9y0因此，該問題的數學模型為Minz=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+3.9yb2+0.6xc1+0.65yc1+0.75xc2+0.78yc2+9y0

xa+ya=5000xb1+yb1=3000xb2+yb2=2000xc1+yc1=3000xc2+yc2=2000y0≤50

xa+3xb1+2.5xb2+xc1+1.5xc2

－60y0≤12000

xa、xb1、xb2、xc1、xc2、yb1、yb2、yc1、yc2、y0≥0該線性規(guī)劃模型的求解結果為目標函數最優(yōu)值為：1728.794變量最優(yōu)解檢驗數

xa5000

0.000

ya

00.017

xb1

667

0.000

ybl

23330.000

xb2

2000

0.000

yb2

0

0.392

xc1

0

0.033

yc1

3000

0.000

xc2

0

0.095

yc2

2000

0.000

y0

0

4.000約束松弛/剩余變量對偶價格

10－0.583

20－4.000

30－3.508

40－0.650

50－0.780

6500.000

700.083部件自制量（件）購買量（件）a50000b產品Ⅰ6672333產品Ⅱ20000c產品Ⅰ03000產品Ⅱ02000總成本=24，443.33元目標函數系數范圍變量下限當前值上限

xa

無下限

0.5000.517

ya0.5830.600無上限

xb13.700

3.7503.850

ybl

3.9004.0004.050

xb2

無下限

3.3003.692

yb23.5083.900無上限

xc10.567

0.600無上限

yc1