第一學(xué)期數(shù)據(jù)建模決策課件chapter1lp

第一講線性規(guī)劃

(LinearProgramming,LP)概述線性規(guī)劃問題的提出最早是1939年由前蘇聯(lián)數(shù)學(xué)家康托洛維奇在研究鐵路運(yùn)輸?shù)慕M織問題、工業(yè)生產(chǎn)的管理問題時(shí)提出來的。1947年，美國(guó)學(xué)者丹西格（G.B.Dantzig）提出了線性規(guī)劃問題的單純形方法。線性規(guī)劃理論最為成熟、應(yīng)用最為廣泛

第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型一、問題提出例1（生產(chǎn)計(jì)劃問題）某企業(yè)利用A、B、C三種資源，在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如下表，問如何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？

產(chǎn)品資源甲乙資源限制ABC120111300kg400kg250kg單位產(chǎn)品利潤(rùn)(元/件)50100決策變量：x1、x2——分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量。目標(biāo)函數(shù)：max

z=50x1+100x2約束條件：x1+x2≤300

2x1+x2≤400x2≤250即有：

max

z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0稱之為上述問題的數(shù)學(xué)模型。例2

靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)m3，在兩個(gè)工廠之間有一條流量為200萬(wàn)m3的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污水分別為2萬(wàn)m3和1.4萬(wàn)m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水的成本分別為1000元/萬(wàn)m3和800元/萬(wàn)m3。現(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠處理工業(yè)污水的費(fèi)用最小.工廠1工廠2200萬(wàn)m3500萬(wàn)m3決策變量：x1、x2——分別代表工廠1和工廠2處理污水的數(shù)量(萬(wàn)m3)。則目標(biāo)函數(shù)：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化簡(jiǎn)有：

minz=1000x1+800x2x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥0稱之為上述問題的數(shù)學(xué)模型。從上述兩個(gè)例子，我們可以總結(jié)出線性規(guī)劃的數(shù)學(xué)模型的一般形式。max(min)z=c1x1+c2x2+…+cnxn——目標(biāo)函數(shù)

a11x1+a12x2+…+a1nxn=(≥,≤)b1

a21x1+a22x2+…+a2nxn=(≥,≤)b2——約束條件

…………………

am1x1+am2x2+…+amnxn=(≥,≤)bm

x1，x2，…，xn≥0模型特點(diǎn)：目標(biāo)函數(shù)(Objectivefunction)與約束條件(Constraint)均為線性的；目標(biāo)函數(shù)實(shí)現(xiàn)極大化或極小化。

第二節(jié)線性規(guī)劃圖解法

(GraphicalSolution)一、基本概念可行解(FeasibleSolution)——任一滿足約束條件的一組決策變量的數(shù)值；可行域(FeasibleRegion)——所有可行解組成的集合，也稱為可行解集；目標(biāo)函數(shù)等值線(Objectivefunctionline)——為于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值；二、圖解法步驟(Procedure)（1）畫出線性規(guī)劃問題的可行域；（2）畫出兩條目標(biāo)函數(shù)等值線；（3）平行移動(dòng)目標(biāo)函數(shù)等值線，使目標(biāo)函數(shù)在可行域范圍內(nèi)達(dá)到最優(yōu)。三、圖解法舉例例1maxZ=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0x2x1z*=27500z1=50x1+100x2=0BOACDz2=14000該問題有唯一最優(yōu)解x1=50；x2=250x1+x2≤3002x1+x2≤400x2≤250例2maxZ=50x1+50x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0x2x1z1=50x1+50x2=0B點(diǎn)和C點(diǎn)所代表的坐標(biāo)同時(shí)為最優(yōu)解，即該問題有無(wú)窮多最優(yōu)解BOACDx1+x2≤3002x1+x2≤400x2≤250maxZ=50x1+100x2z*=27500z2=15000例3maxz=x1+x2x1－x2≥1

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

問題有無(wú)界解

(unbounded)例4

minz=x1+x2x1－x2≥1

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

有唯一最優(yōu)解1－11z=32z=5OAx1－x2≥1－x1+2x2≤0例4maxz=x1+x2

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

問題無(wú)可行解

(nofeasiblesolution)直觀結(jié)論可行域可以是個(gè)凸多邊形，可能無(wú)界，也可能為空；若線性規(guī)劃問題的最優(yōu)解存在，它一定可以在可行域的某一個(gè)頂點(diǎn)上得到；若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則該兩點(diǎn)連線上的所有點(diǎn)都是最優(yōu)解，即LP有無(wú)窮多最優(yōu)解；若可行域非空有界，則一定有最優(yōu)解。四、線性規(guī)劃問題的標(biāo)準(zhǔn)形式(Standardform)規(guī)定如下形式的線性規(guī)劃數(shù)學(xué)模型為L(zhǎng)P標(biāo)準(zhǔn)形式。maxz=c1x1+c2x2+…+cnxn ——目標(biāo)函數(shù)

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2——約束條件

………

am1x1+am2x2+…+amnxn=bm

x1，x2，…，xn≥0特點(diǎn)：Z——max；約束條件為等號(hào)；變量非負(fù)；右端常數(shù)項(xiàng)大等于零。問題：n>

mwhy？上述標(biāo)準(zhǔn)形式的線性規(guī)劃模型還可寫成如下一些形式:(1)

(2)

(3)(5)(4)

五、化非標(biāo)準(zhǔn)形為標(biāo)準(zhǔn)形（1）若minf=cX此時(shí)可令：z=－f，則maxz=－minf=－cX，這樣處理所得最優(yōu)解不變；舉例：

minz=－x1－x22x1+x2≤2

－x1+x2≤1x1、x2≥0maxf=x1+x2z=-1/2f=0f=1/2z=0f=-z=8/3（1/3，4/3）(2)約束條件為“≤”時(shí)，∑aijxj≤bi→∑aijxj+xn+i=bi

xn+i——松弛變量(slackvariable)；(3)約束條件為“≥”時(shí)，∑aijxj≥bi→∑aijxj

－xn+i=bi

xn+i——過剩變量(surplusvariable)；這樣處理所得最優(yōu)解不變；max

z=x1+10x2x1+2x2≤100x1、x2≥0max

z=x1+10x2x1+2x2+x3=100x1、x2≥0（4）若xk為無(wú)限制，則令xk=xk1－xk2，其中xk1、xk2≥0（5）若bi<0，則－bi>0舉例:化下列線性規(guī)劃為標(biāo)準(zhǔn)形

max

z=2x1+2x2－4x3x1+3x2－3x3≥30x1+2x2－4x3≤80x1、x2≥0，x3無(wú)限制max

z=2x1+2x2－4x3’+4x3”x1+3x2－3x3’+3x3”

–x4=30x1+2x2－4x3+4x3”+x5=80x1、x2、x3’、x3”

、x4、x5≥0第三節(jié)線性規(guī)劃的計(jì)算機(jī)求解

(ComputerSolutionforLP)一、用計(jì)算機(jī)求解下列線性規(guī)劃問題maxz=50x1+100x2x1+x2<=3002x1+x2<=400x2<=250x1、x2≥0二、派公司生產(chǎn)計(jì)劃問題的LP模型與計(jì)算機(jī)求解派公司計(jì)劃生產(chǎn)高中價(jià)位的高爾夫袋。生產(chǎn)過程為：1.切割并印染原材料；2.縫合；3.成型；4.檢查和包裝。各過程單位用時(shí)、總用時(shí)及產(chǎn)品單位利潤(rùn)如下表：如何生產(chǎn)使公司利潤(rùn)最大？過程生產(chǎn)耗時(shí)總時(shí)間標(biāo)準(zhǔn)袋高檔袋切割并印染縫合成型檢查和包裝7/101/211/1015/62/31/4630600708135單位產(chǎn)品利潤(rùn)109解：很顯然，若設(shè)x1、x2——分別代表標(biāo)準(zhǔn)袋和高檔袋的生產(chǎn)數(shù)量,則問題的數(shù)學(xué)模型為：

max

z=10x1+9x2

7/10x1+x2<=6301/2x1+5/6x2<=600x1+

2/3x2<=7081/10x1+1/4x2<=135x1、x2≥0三、M&D公司問題問題描述:M&D公司生產(chǎn)兩種產(chǎn)品A和B，根據(jù)現(xiàn)有庫(kù)存水平和下個(gè)月的購(gòu)買潛力分析，M&D管理層確定A和B的總產(chǎn)量至少達(dá)到350加侖。此外公司的一個(gè)主要客戶訂購(gòu)了125加侖的產(chǎn)品A，該產(chǎn)量必須滿足。產(chǎn)品A和產(chǎn)品B的制造時(shí)間分別是2小時(shí)/加侖和1小時(shí)/加侖，下個(gè)月的總工作時(shí)間是600小時(shí)。公司的目標(biāo)是在滿足客戶要求的前提下，盡量降低成本。每加侖A的制造成本是2美元，每加侖B的制造成本是3美元。很顯然，若設(shè)x1、x2——分別代產(chǎn)品A和產(chǎn)品B的生產(chǎn)數(shù)量,則問題的數(shù)學(xué)模型為：

minz=2x1+3x2x1>=125

x1+x2>=

350

2x1+

x2<=600x1、x2≥0第四節(jié)對(duì)偶問題(DualProblem)線性規(guī)劃早期發(fā)展過程中的最為重要的理論成果之一就是線性規(guī)劃的對(duì)偶問題及相關(guān)理論的提出。線性規(guī)劃的對(duì)偶理論解釋資源的影子價(jià)格、線性規(guī)劃問題的敏度分析等的理論基礎(chǔ)。一、對(duì)偶問題的提出例1

（生產(chǎn)計(jì)劃問題）某企業(yè)利用A、B、C三種資源，在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如下表，問如何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？

產(chǎn)品資源甲乙資源限制ABC120111300kg400kg250kg單位產(chǎn)品利潤(rùn)(元/件)50100決策變量：x1、x2——分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量。即有數(shù)學(xué)模型（問題A）：?jiǎn)栴}Amax

z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0稱之為上述問題的數(shù)學(xué)模型。同樣是上述問題，提問：企業(yè)不安排生產(chǎn)，而轉(zhuǎn)讓三種資源，應(yīng)如何給三種資源定價(jià)？決策變量：y1、y2、y3——分別代表A、B、C三種資源的價(jià)格（最低轉(zhuǎn)讓凈收入）。約束條件1：生產(chǎn)一件產(chǎn)品甲所耗資源數(shù)量轉(zhuǎn)讓所得凈收入不能低于一件產(chǎn)品甲所獲利潤(rùn)，即：

1y1+2y2≥50約束條件2：生產(chǎn)一件產(chǎn)品乙所耗資源數(shù)量轉(zhuǎn)讓所得凈收入不能低于一件產(chǎn)品乙所獲利潤(rùn)，即：

1y1+1y2+1y3≥100目標(biāo)函數(shù)為：w=300y1+400y2+250y3即有

w=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0從數(shù)學(xué)和經(jīng)濟(jì)的角度分析，該問題的目標(biāo)函數(shù)只能極小，即該問題的數(shù)學(xué)模型為：?jiǎn)栴}Bminw=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0稱問題B為問題A的對(duì)偶問題，問題A為原問題。問題Amaxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0定義2.1

設(shè)有線性規(guī)劃問題

maxz=CXAX≤bX≥0其對(duì)偶問題定義為

minw=YbYA≥CY≥0且前者稱為原問題，后者稱為對(duì)偶問題。二、對(duì)偶問題的定義具體的數(shù)量對(duì)應(yīng)關(guān)系為原問題maxz=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………

am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0對(duì)偶問題

minw=b1y1+b2y2+…+bmym

a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2…………

a1ny1+a2ny2+…+amnym≥cny1，y2，…，ym≥0根據(jù)對(duì)偶問題的定義不難推出，對(duì)于線性規(guī)劃問題：

minw=Yb；YA≥C；Y≥0其對(duì)偶問題為：

maxz=CX；AX≤b；X≥0即兩線性規(guī)劃問題互為對(duì)偶。事實(shí)上，任一線性規(guī)劃問題都有一個(gè)固定的線性規(guī)劃問題與之對(duì)偶，且二者互為對(duì)偶關(guān)系，線性規(guī)劃的這種性質(zhì)稱為對(duì)稱性。更進(jìn)一步有，對(duì)于線性規(guī)劃問題：

maxz=CX；AX=b，X≥0其對(duì)偶問題為：

minw=Yb；YA≥C，Y無(wú)限制根據(jù)以上分析，線性規(guī)劃原問題與對(duì)偶問題的數(shù)量關(guān)系可用下表描述。原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù)maxzminw目標(biāo)函數(shù)變量n個(gè)≥0≤0無(wú)約束n個(gè)≥≤=約束條件約束條件m個(gè)≤≥=m個(gè)≥0≤0無(wú)約束變量約束條件右端常數(shù)項(xiàng)目標(biāo)函數(shù)變量系數(shù)目標(biāo)函數(shù)變量系數(shù)約束條件右端常數(shù)項(xiàng)例2.1寫出下列線性規(guī)劃問題的對(duì)偶問題

maxz=2x1+2x2－4x3 x1+3x2+3x3≤30 4x1+2x2+4x3≤80 x1、x2，x3≥0解：其對(duì)偶問題為minw=30y1+80y2y1+4y2≥23y1+2y2≥23y1+4y2≥－4y1、y2≥0例2.2寫出下列線性規(guī)劃問題的對(duì)偶問題

minz=2x1+8x2－4x3x1+3x2－3x3≥30

－x1+5x2+4x3=804x1+2x2－4x3≤50x1≤0、x2≥0，x3無(wú)限制解：其對(duì)偶問題為maxw=30y1+80y2+50y3

y1－y2+4y3≥23y1+5y2+2y3≤8

－3y1+4y2－4y3=－4y1≥0，y2無(wú)限制，y3≤0定理2.1(弱對(duì)偶定理)

設(shè)X(0)是原問題maxz=CX，AX≤b，X≥0的可行解

Y(0)是其對(duì)偶問題minw=Yb，YA≥C，Y≥0的可行解則CX（0）≤Y（0）b。原問題任一可行解對(duì)應(yīng)的目標(biāo)函數(shù)值不大于其對(duì)偶問題的任一可行解對(duì)應(yīng)目標(biāo)函數(shù)值???三、對(duì)偶問題基本定理定理2.2(最優(yōu)性定理)

設(shè)X(0)是原問題maxz=CX，AX≤b，X≥0的可行解，

Y（0）是其對(duì)偶問題minw=Yb，YA≥C，Y≥0的可行,若CX（0）=Y（0）b，則X（0）、Y（0）分別是它們的最優(yōu)解。定理2.3(對(duì)偶定理)

若原問題maxz=CX，AX≤b，X≥0有最優(yōu)解，則其對(duì)偶問題minw=Yb，YA≥C，Y≥0一定有最優(yōu)解，且二者的目標(biāo)函數(shù)值相等。定理2.4(互補(bǔ)松弛定理)

原問題maxz=CX，AX≤b，X≥0及其對(duì)偶問題minw=Yb，YA≥C，Y≥0

的可行解X（0）、Y（0）是最優(yōu)解的充要條件是

Y（0）XS=0；YSX（0）=0

其中，XS、YS分別是原問題松弛變量向量和對(duì)偶問題剩余變量向量。（一）資源的影子價(jià)格(ShadowPrice)

如前所述，若X*為線性規(guī)劃maxz=CX，AX≤b，X≥0的最優(yōu)解，則z*=CX*；若Y*為其對(duì)偶問題的最優(yōu)解，則有w*=Y*b。根據(jù)對(duì)偶定理有

z*=w*

即z*=Y*b

因此即由此可以看出，對(duì)偶問題的最優(yōu)解實(shí)際上是右端常數(shù)項(xiàng)的單位變化所引起的目標(biāo)值的變化；四、對(duì)偶問題的經(jīng)濟(jì)意義若原問題描述的是資源有限條件下最優(yōu)生產(chǎn)決策問題，則其對(duì)偶問題的最優(yōu)解yi*(i=1,…，m)表示第i種資源在最優(yōu)生產(chǎn)決策下的邊際值，即若其他條件不變，增加單位第i種資源將會(huì)使目標(biāo)函數(shù)值增加yi*。其經(jīng)濟(jì)意義是：yi*描述了第i種資源在具體生產(chǎn)中的一種估價(jià)，這種估價(jià)不同于該種資源的市場(chǎng)價(jià)格，而是該種資源在給定條件某生產(chǎn)的最優(yōu)生產(chǎn)方案下的一種實(shí)際存在而又看不見的真實(shí)價(jià)值，因此稱之為影子價(jià)格（shadowprice）。同一種資源在不同的生產(chǎn)條件或不同的范圍可能有不同的影子價(jià)格；產(chǎn)品的市場(chǎng)價(jià)格變化，資源的影子價(jià)格也會(huì)發(fā)生變化；資源的數(shù)量結(jié)構(gòu)不同，資源的影子價(jià)格也不同。資源的影子價(jià)格是針對(duì)具體生產(chǎn)或具體企業(yè)而言的與資源的市場(chǎng)價(jià)格比較以決定是否安排生產(chǎn)或轉(zhuǎn)讓資源或提高產(chǎn)品的價(jià)格；革新可以提高資源的影子價(jià)格；可以指導(dǎo)管理部門對(duì)緊缺資源進(jìn)行“擇優(yōu)分配”；幫助預(yù)測(cè)產(chǎn)品的價(jià)格。因此，產(chǎn)品的價(jià)格應(yīng)在“成本”和影子價(jià)格之間；影子價(jià)格的高低可以作為同類企業(yè)經(jīng)濟(jì)效益的評(píng)估標(biāo)準(zhǔn)之一。影子價(jià)格對(duì)于擁有資源的決策者有非常重要的作用對(duì)于目標(biāo)函數(shù)極小化約束條件為大等號(hào)的問題

minz=CX，AX≥b，X≥0，其右端常數(shù)項(xiàng)可理解為需要完成的任務(wù)。因此，該類線性規(guī)劃一般為描述完成一定任務(wù)使耗費(fèi)的資源最小的問題。此時(shí)，其對(duì)偶問題的最優(yōu)解yi*(i=1,…，m)表示第i種任務(wù)的邊際成本，即單位任務(wù)的增加引起的資源耗費(fèi)的增加量。（二）任務(wù)的邊際成本

(MarginalCost)M&D公司生產(chǎn)兩種產(chǎn)品A和B，根據(jù)現(xiàn)有庫(kù)存水平和下個(gè)月的購(gòu)買潛力分析，M&D管理層確定A和B的總產(chǎn)量至少達(dá)到350加侖。此外公司的一個(gè)主要客戶訂購(gòu)了125加侖的產(chǎn)品A，該產(chǎn)量必須滿足。產(chǎn)品A和產(chǎn)品B的制造時(shí)間分別是2小時(shí)/加侖和1小時(shí)/加侖，下個(gè)月的總工作時(shí)間是600小時(shí)。公司的目標(biāo)是在滿足客戶要求的前提下，盡量降低成本。每加侖A的制造成本是2美元，每加侖B的制造成本是3美元。問題的線性規(guī)劃模型為

minz=2x1+3x2x1>=125

x1+x2>=

350

2x1+

x2<=600x1、x2≥0無(wú)論對(duì)偶問題的最優(yōu)解表示的是資源的影子價(jià)格還是任務(wù)的邊際成本，只要為正，則表示右端常數(shù)項(xiàng)增加目標(biāo)函數(shù)值增加，為負(fù)則表示右端常數(shù)項(xiàng)增加目標(biāo)函數(shù)值減少。而對(duì)于極大化的問題，目標(biāo)函數(shù)值增加表明目標(biāo)函數(shù)得到改善，對(duì)于極小化的問題，目標(biāo)函數(shù)減少表明目標(biāo)函數(shù)得到改善。為了二者的統(tǒng)一，定義如下對(duì)偶價(jià)格。（三）對(duì)偶價(jià)格(DualPrice)定義2.2

線性規(guī)劃問題某約束條件的右端常數(shù)項(xiàng)的單位增加量所引起的目標(biāo)函數(shù)的改善量稱為該右端常數(shù)項(xiàng)的對(duì)偶價(jià)格。因此，若對(duì)偶價(jià)格為正，則增加右端常數(shù)項(xiàng)，目標(biāo)函數(shù)值得到改善；若對(duì)偶價(jià)格為負(fù)，則增加右端常數(shù)項(xiàng)，目標(biāo)函數(shù)值將會(huì)“惡化”。（三）對(duì)偶價(jià)格(DualPrice)

第五節(jié)、靈敏度分析

(SensitivityAnalysis)靈敏度分析就是分析aij、bi、cj等因素中的一個(gè)或幾個(gè)的變化給生產(chǎn)決策帶來的影響。靈敏度分析的內(nèi)容是：aij、bi、cj中一個(gè)或幾個(gè)發(fā)生某一具體變化時(shí)，線性規(guī)劃問題的最優(yōu)決策相應(yīng)會(huì)發(fā)生什么樣的變化；aij、bi、cj在什么范圍內(nèi)變化，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變；靈敏度分析一般是在已得到線性規(guī)劃問題最優(yōu)基的基礎(chǔ)上進(jìn)行的。例

（生產(chǎn)計(jì)劃問題）某工廠在計(jì)劃期內(nèi)用資源A、B、C安排生產(chǎn)甲、乙兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下：

maxz=5x1+4x2

x1+3x2<=902x1

+x2<=80

x1

+x2<=45x1、x2，x3≥0

產(chǎn)品資源甲乙資源限制ABC12131190kg80kg45kg單位產(chǎn)品利潤(rùn)(千元/件)54若x1、x2分別表示工廠生產(chǎn)甲、乙產(chǎn)品的數(shù)量，則使工廠獲得最大利潤(rùn)的生產(chǎn)計(jì)劃數(shù)學(xué)模型為：該問題的計(jì)算機(jī)求解結(jié)果如下目標(biāo)函數(shù)最優(yōu)值為：215變量最優(yōu)解檢驗(yàn)數(shù)

x1350

x2100約束松弛/剩余變量對(duì)偶價(jià)格

1250

201

303目標(biāo)函數(shù)系數(shù)范圍（最優(yōu)解不變）變量下限當(dāng)前值上限

x1458

x22.545右端常數(shù)項(xiàng)范圍（對(duì)偶價(jià)格不變）約束下限當(dāng)前值上限

16590

無(wú)上限

2

67.58090

3404550

maxz=5x1+4x2x1+3x2<=902x1

+x2<=80

x1

+x2<=45x1、x2，x3≥0

（一）、派公司的靈敏度分析

1、原問題計(jì)算機(jī)求解派公司計(jì)劃生產(chǎn)高中價(jià)位的高爾夫袋。生產(chǎn)過程為：1.切割并印染原材料；2.縫合；3.成型；4.檢查和包裝。各過程單位用時(shí)、總用時(shí)及產(chǎn)品單位利潤(rùn)如下表：如何生產(chǎn)使公司利潤(rùn)最大？過程生產(chǎn)耗時(shí)總時(shí)間標(biāo)準(zhǔn)袋高檔袋切割并印染縫合成型檢查和包裝7/101/211/1015/62/31/4630600708135單位產(chǎn)品利潤(rùn)109靈敏度分析與解答舉例

解：很顯然，若設(shè)S、D——分別代表標(biāo)準(zhǔn)袋和高檔袋的生產(chǎn)數(shù)量,則問題的數(shù)學(xué)模型為：

maxz=10S+9D7/10S+D

<=6301/2S+5/6D

<=600S

+2/3D

<=7081/10S+1/4D

<=135S、D≥02.對(duì)派公司問題的修改——增加小型袋現(xiàn)管理層希望生產(chǎn)一種小巧的、擊球者可以自己背著的高爾夫袋。設(shè)計(jì)部門計(jì)算后得出小型袋在各過程中所耗時(shí)間為：切割印染0.8h、縫合1h、成型1h、檢驗(yàn)包裝0.25h。單位利潤(rùn)：12.85美元/個(gè)；設(shè)L為小型袋的個(gè)數(shù)，則新的模型為：maxz=10S+9D+12.85L7/10S+D+0.8L

<=6301/2S+5/6D

+L<=600S

+2/3D+L<=7081/10S+1/4D+0.25L<=135S、D、L≥03.對(duì)派公司問題的修改——增加約束條件現(xiàn)管理層無(wú)法接受高檔袋為零的事實(shí)。于是就增加約束條件，即高檔袋至少是標(biāo)準(zhǔn)袋的30%，于是有新的模型為：maxz=10S+9D+12.85L7/10S+D+0.8L

<=6301/2S+5/6D

+L<=600S

+2/3D+L<=7081/10S+1/4D+0.25L<=135-0.3S+D>=0S、D、L≥0靈敏度分析與解答舉例

二、牧草農(nóng)場(chǎng)問題——極小化問題（P69）計(jì)算機(jī)求解與解釋（科學(xué)管理的實(shí)際應(yīng)用P77）三、電子通訊公司問題——等式約束（P73），自己看第六節(jié)線性規(guī)劃的應(yīng)用(ApplicationsofLP)線性規(guī)劃是管理決策制定的最成功的數(shù)量方法之一。它廣泛應(yīng)用于化工、航空、鋼鐵、石油和其他工業(yè)。它研究的問題是多種多樣的——生產(chǎn)計(jì)劃、媒體選擇、金融計(jì)劃、資金預(yù)算、運(yùn)輸、工廠選擇、生產(chǎn)組合、人員調(diào)配等等。例紅旗商場(chǎng)是個(gè)中型的百貨商場(chǎng)，它對(duì)售貨人員的需求經(jīng)過統(tǒng)計(jì)分析如表所示。為了保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應(yīng)該如何安排售貨人員的作息，既滿足了工作需要又使配備的售貨人員的人數(shù)最少？時(shí)間所需售貨員星期日星期一星期二星期三星期四星期五星期六28人15人24人25人19人31人28人一、人力資源分配問題解：設(shè)x1為星期一開始上班的人數(shù)，x2為星期二開始上班的人數(shù)，……，x7星期日開始上班的人數(shù)。我們就可得到如下的數(shù)學(xué)模型：

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；目標(biāo)函數(shù)的最小值為36。媒體被告知的潛在顧客數(shù)（人/次）廣告費(fèi)用（元/次）媒體最高使用次數(shù)（次）每次宣傳的質(zhì)量日間電視夜間電視日?qǐng)?bào)周末新聞雜志電臺(tái)廣播10002000

10001001510254306590406020例

某房地產(chǎn)開發(fā)公司正在建造一個(gè)湖邊小區(qū)，公司準(zhǔn)備投入3萬(wàn)元進(jìn)行廣告媒體宣傳，希望能夠吸引周圍的中高收入家庭前來購(gòu)房。目前有5種媒體可供選擇，相關(guān)信息如表所示。對(duì)于這次活動(dòng)，公司有下列要求：至少進(jìn)行10次電視廣告；至少有5萬(wàn)名潛在顧客被告知；電視廣告投入不超過18000元。如何進(jìn)行媒體組合，才能使廣告質(zhì)量最高？二、媒體選擇解問題中媒體組合實(shí)際上就是要決定每種媒體的使用次數(shù)。設(shè)x1、x2、x3、x4、x5分別表示表中日間電視、夜間電視、日?qǐng)?bào)、周末新聞雜志、電臺(tái)廣播五種媒體的使用次數(shù)。該問題的線性規(guī)劃模型為maxz=65x1+90x2+40x3+60x4+20x51500x1+3000x2+400x3+1000x4+100x5≤30000

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

x3 ≤25

x4≤4

x5≤30

x1，x2，x3，x4，x5≥0這是一個(gè)有5個(gè)變量，9個(gè)約束條件的線性規(guī)劃模型，求解結(jié)果如下：媒體最佳播放次數(shù)（次）廣告費(fèi)用（元）日間電視1015000日?qǐng)?bào)2510000周末新聞雜志22000電臺(tái)廣播303000被告知的顧客數(shù)=61500人產(chǎn)品宣傳質(zhì)量=2370目標(biāo)函數(shù)最優(yōu)值為：2370變量最優(yōu)解檢驗(yàn)數(shù)

x1100

x20－65

x3250

x420

x5300約束松弛/剩余變量對(duì)偶價(jià)格

10

0.06

2115000

30－25

430000

550

6100

7016

820

9014包括：資本預(yù)算、資產(chǎn)分配、財(cái)政計(jì)劃等（一）投資組合問題：從多種投資選擇中選擇具體的投資：股票和債券、基金、保險(xiǎn)等；目標(biāo)：預(yù)期收益極大化、風(fēng)險(xiǎn)最小化約束：投資類型、國(guó)家法律、公司政策、風(fēng)險(xiǎn)或效益限制等三、財(cái)政應(yīng)用案例

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

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

Maxz=0.073Atl+0.103Pac+0.064Mid+0.075Hub+0.045GovAtl+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(二)、金融計(jì)劃案例某公司現(xiàn)有68名員工申請(qǐng)?zhí)崆巴诵?。公司必須在此后?年內(nèi)對(duì)這些員工分期支付一定數(shù)量的現(xiàn)金，如下表所示。 為了完成這項(xiàng)現(xiàn)金支付任務(wù)，公司的財(cái)務(wù)人員必須現(xiàn)在就為此制定一個(gè)投資計(jì)劃。投資計(jì)劃有政府債券投資和銀行儲(chǔ)蓄兩種方式組成。年份（年）12345678合計(jì)現(xiàn)金支付(千元)4302102222312401952252552008注意:三種政府債券的票面價(jià)值均為1000元，債券到期時(shí)按票面價(jià)值進(jìn)行支付，利率的計(jì)算也以票面的價(jià)值為基準(zhǔn)。銀行儲(chǔ)蓄年利率為4%。如何安排投資計(jì)劃，使公司以最小的投資額完成對(duì)退休員工的現(xiàn)金支付任務(wù)？政府債券投資有三種債券類型可供選擇，如下表所示。債券價(jià)格（元）利率（%）到期年限111508.8755210005.50063135011.7507解：1．確定決策變量設(shè)F為完成投資計(jì)劃所需要的總資金額。x1、x2、x3分別表示債券1、2、3的購(gòu)買量；yi(i=1,…，8)表示第i年初銀行儲(chǔ)蓄的投資額。2．確定約束條件這類問題的一個(gè)典型特征就是每年現(xiàn)金支付的一般表達(dá)式為：年初可用資金額–當(dāng)年用于債券和儲(chǔ)蓄的資金額

=當(dāng)年現(xiàn)金支付于是有

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

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

0.08875x1+0.055x2+0.1175x3+1.04y1–y2=210（第2年）同理對(duì)于其它年份有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年）因此事實(shí)上，y8的值應(yīng)為0，若大于0，那么對(duì)應(yīng)的投資計(jì)劃必定不是最優(yōu)的。3.確定目標(biāo)函數(shù)目標(biāo)就是使?jié)M足要求的投資額最小，即Minz=F綜合有如下數(shù)學(xué)模型

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ī)劃模型的求解結(jié)果為目標(biāo)函數(shù)最優(yōu)值為：1728.794變量最優(yōu)解檢驗(yàn)數(shù)

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即得到最佳投資計(jì)劃如下表所示:債券購(gòu)買量投資額(千元)年份儲(chǔ)蓄額(千元)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

約束松弛/剩余變量對(duì)偶價(jià)格

10－1.000

20－0.962

30－0.925

40－0.889

50－0.855

60－0.760

70－0.719

80－0.671結(jié)果分析：前4年的儲(chǔ)蓄額均大于0，可見從第6年起債券的利息和債券到期收入才能夠完全滿足當(dāng)前現(xiàn)金支付需要。每一個(gè)約束條件的對(duì)偶價(jià)格均為負(fù)值，說明減少任何一年的現(xiàn)金支付都將有利于公司總投資額的降低。對(duì)偶價(jià)格的逐年降低也說明了，在前面年份減少現(xiàn)金支付將對(duì)總投資額的減少更為有效。從而暗示了公司可以適當(dāng)減少前面年份的現(xiàn)金支付量，而在后面年份進(jìn)行補(bǔ)足。

(一)制造或購(gòu)買決策案例P98

某公司有Ⅰ，Ⅱ兩種產(chǎn)品，預(yù)計(jì)兩種產(chǎn)品的市場(chǎng)需求量分別為3000件和2000件。兩種產(chǎn)品均由a、b、c三個(gè)部件組成，各部件生產(chǎn)消耗工時(shí)和自制/外購(gòu)成本如下表所示。部件單位部件制造工時(shí)（分鐘）自制成本（元/分鐘）購(gòu)買成本（元/小時(shí)）A1.00.500.60B產(chǎn)品Ⅰ3.03.754.00產(chǎn)品Ⅱ2.53.303.90C產(chǎn)品Ⅰ1.00.600.65產(chǎn)品Ⅱ1.50.750.78四、生產(chǎn)管理應(yīng)用部件單位部件制造工時(shí)（分鐘）自制成本（元/分鐘）購(gòu)買成本（元/小時(shí)）A1.00.500.60B產(chǎn)品Ⅰ3.03.754.00產(chǎn)品Ⅱ2.53.303.90C產(chǎn)品Ⅰ1.00.600.65產(chǎn)品Ⅱ1.50.750.78由于生產(chǎn)能力有限，公司只有200個(gè)正常制造工時(shí)和50個(gè)加班工時(shí)可用于這兩種產(chǎn)品的生產(chǎn)。每個(gè)加班工時(shí)需額外支付9元。如何安排部件自制和外購(gòu)的數(shù)量，從而使總成本（包括生產(chǎn)成本、外購(gòu)成本和加工費(fèi)用）最低？解：1．確定決策變量設(shè)xa、xb1、xb2、xc1、xc2分別表示a部件、用于產(chǎn)品Ⅰ的b部件、用于產(chǎn)品Ⅱ的b部件、用于產(chǎn)品Ⅱ的c部件、用于產(chǎn)品Ⅱ

的c部件的自制量。相應(yīng)地，設(shè)ya、yb1、yb2、yc1、yc2分別為各部件的外購(gòu)量。設(shè)y0為加班工時(shí)數(shù)。

2．確定約束條件a部件的需求量約束xa+ya=5000用于產(chǎn)品Ⅰ的b部件的需求量約束xb1+yb1=3000用于產(chǎn)品Ⅱ的b部件的需求量約束xb2+yb2=2000用于產(chǎn)品Ⅰ的c部件的需求量約束xc1+yc1=3000用于產(chǎn)品Ⅱ的c部件的需求量約束xc2+yc2=2000最大加班工時(shí)數(shù)約束y0≤50最大生產(chǎn)能力約束

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

－60y0≤12000xa、xb1、xb2、xc1、xc2、yb1、yb2、yc1、yc2、y0≥0該線性規(guī)劃模型的求解結(jié)果為目標(biāo)函數(shù)最優(yōu)值為：1728.794變量最優(yōu)解檢驗(yàn)數(shù)

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約束松弛/剩余變量對(duì)偶價(jià)格

10－0.583

20－4.000

30－3.508

40－0.650

50－0.780

6500.000

700.083部件自制量（件）購(gòu)買量（件）a50000b產(chǎn)品Ⅰ6672333產(chǎn)品Ⅱ20000c產(chǎn)品Ⅰ03000產(chǎn)品Ⅱ02000總成本=24，443.33元目標(biāo)函數(shù)系數(shù)范圍變量下限當(dāng)前值上限

xa

無(wú)下限

0.5000.517

ya0.5830.600無(wú)上限

xb13.700

3.7503.850

ybl

3.9004.0004.050

xb2

無(wú)下限

3.3003.692

yb23.5083.900無(wú)上限

xc10.567

0.600無(wú)上限

yc1

無(wú)下限

0.6500.683

xc2

0.655

0.750無(wú)上限

yc2

無(wú)下限

0.7800.875

y0

5.000

9.000無(wú)上限右端常數(shù)項(xiàng)范圍約束下限當(dāng)前值上限

10.0005000

7000

2666.6673000無(wú)上限

30.00020002800

40.0003000

無(wú)上限

5

0.0002000

無(wú)上限

60.00050無(wú)上限

7

10000.00012000

19000(二)生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題是線性規(guī)劃應(yīng)用最為廣泛的領(lǐng)域之一;問題描述:一定時(shí)期內(nèi)，經(jīng)理必須決定生產(chǎn)水平，使公司能夠滿足生產(chǎn)需求，在受到產(chǎn)品生產(chǎn)量、勞動(dòng)力水平以及存儲(chǔ)空間上所有限制的同時(shí)，還要使生產(chǎn)成本最小。線性規(guī)劃解決該類問題的優(yōu)點(diǎn)：可重復(fù)利用已建立好的線性規(guī)劃模型指定不同時(shí)期的生產(chǎn)計(jì)劃。案例P100Bollinger電子公司接到未來三個(gè)月的兩種產(chǎn)品的定單：生產(chǎn)部門分析，生產(chǎn)費(fèi)用有以下方面：（1）生產(chǎn)成本；（2）庫(kù)存儲(chǔ)成本；（3）改變生產(chǎn)力水平所需費(fèi)用。有關(guān)數(shù)據(jù)如下表組件需求生產(chǎn)成本(美元/件)存儲(chǔ)成本(美元/件·月）改變生產(chǎn)力費(fèi)用(美元/件)四月五月六月322A802B1000100030005005000300020100.30.15增加：0.5減少：0.2現(xiàn)要求制定一個(gè)未來3個(gè)月的生產(chǎn)計(jì)劃，使總成本最小。Bollinger公司生產(chǎn)力、勞動(dòng)力能力和庫(kù)存能力月份生產(chǎn)能力(h)勞動(dòng)力能力(h)庫(kù)存能力（面積）四月五月六月400500600300300300100001000010000單位組件對(duì)生產(chǎn)機(jī)器、勞動(dòng)力和存儲(chǔ)的要求組件機(jī)器(h/單位)勞動(dòng)力(h/單位)庫(kù)存(面積/單位)322A802B0.100.080.050.0723決策變量（能描述問題）：

x1i=第i月生產(chǎn)322A的數(shù)量；i=1，2，3(四、五、六月)x2i=第i月生產(chǎn)802B的數(shù)量；i=1，2，3s1i=第i月末322A的存儲(chǔ)量；i=1，2，3s2i=第i月末802B的存儲(chǔ)量；i=1，2，3Ii=第i月生產(chǎn)量增加量；i=1，2，3Di=第i月生產(chǎn)量下降量；i=1，2，3

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

minz=20x11+20x12+20x13+10x21+10x22+10x23

+0.3s11+0.3s12+0.3s13+0.15s21+0.15s22+0.15s23

+0.5I1+0.5I2+0.5I3+0.2D1+0.2D2+0.2D3約束條件（1）需求約束上月期末庫(kù)存+本月生產(chǎn)量–本月期末庫(kù)存=本月需求量第一個(gè)月：設(shè)期初庫(kù)存為：322A：500；802B：200；這樣有：

500+x11-s11=1000→x11-s11=500200+x21-s21=1000→x11-s11=800

第二個(gè)月

s11+x12–s12=3000s21+x22–s22=500第三個(gè)月

s12+x13–s13=5000s22+x23–s23=