企業(yè)管理MBA運籌學2第二 五章 線性規(guī)劃課件

第二三四五章線性規(guī)劃§2.1線性規(guī)劃問題與標準形式§2.2線性規(guī)劃問題的幾何解釋§2.3單純型法方法第二三四五章線性規(guī)劃問題的提出（1）【例】派公司是一個生產(chǎn)高爾夫器材的小型公司，公司決定生產(chǎn)中高價位的高爾夫袋。產(chǎn)品的生產(chǎn)過程有四個程序：切割并印染原材料、縫合、成型、檢查和包裝，不同價位高爾夫袋生產(chǎn)程序的耗時信息如下表，表中還列出了派公司在本輪生產(chǎn)過程中每個部門的最大生產(chǎn)時間。問題的提出（1）【例】派公司是一個生產(chǎn)高爾夫器材的小型公司，問題的提出（2）會計部門的數(shù)據(jù)表明，生產(chǎn)一個標準袋的利潤是10美元，生產(chǎn)一個高級袋的利潤是9美元。如何安排兩種產(chǎn)品的生產(chǎn)才能使公司獲得最大利潤？耗時/標準袋耗時/高檔袋最大生產(chǎn)時間切割印染0.71630縫合0.55/6600成型12/3708檢查包裝0.10.25135問題的提出（2）會計部門的數(shù)據(jù)表明，生產(chǎn)一個標準袋的利潤是1問題的提出（3）設x1、x2分別為兩種高爾夫袋的生產(chǎn)量，則該計劃問題可用如下數(shù)學模型表示為：問題的提出（3）設x1、x2分別為兩種高爾夫袋的生產(chǎn)量，則該§2.1線性規(guī)劃問題與標準形式

典例1-----生產(chǎn)計劃問題例2.某工廠在計劃期內(nèi)要生產(chǎn)產(chǎn)品I和產(chǎn)品II這兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種設備計劃期的有效臺時，如下表：問如何安排生產(chǎn)最有利？解∶設產(chǎn)品I和產(chǎn)品II的產(chǎn)量分別為x1和x2件,利潤為Z,則:

Z=x1+2x2Max目標函數(shù)2x1+2x2≤80x1+2x2≤4x1,x2≥0約束條件S.t.非負條件§2.1線性規(guī)劃問題與標準形式

典例1-----[企業(yè)管理]MBA運籌學2第二五章線性規(guī)劃課件above,above,[企業(yè)管理]MBA運籌學2第二五章線性規(guī)劃課件[企業(yè)管理]MBA運籌學2第二五章線性規(guī)劃課件典例2----配料問題

Z=3x1+2x2Min目標函數(shù)12x1+3x2≥42x1+3x2≥23x1+15x2≥5x1+x2=1x1,x2≥0約束條件S.t.典例2----配料問題Z=3x1+2x2Mi典例3----食譜問題[例3]問在滿足營養(yǎng)的條件下,如何安排食譜最有利?解:設每人每周食用大米、白菜、雞蛋、豬肉的數(shù)量分別為x1、x2、

x3、

x4Z=C1x1+C2x2+C3x3+C4x4Mina11x1+a12x2+a13x3+a14x4b1=a21x1+a22x2+a23x3+a24x4=

b2a31x1+a32x2+a33x3+a34x4=

b3x1,x2,x3,

x4≥0典例3----食譜問題[例3]問在滿足營養(yǎng)的條件下,如何安排食譜問題的拓展問在滿足營養(yǎng)的條件下,如何安排食譜最有利?Z=C1x1+C2x2+C3x3+C4x4+...+CnxnMina11x1+a12x2+a13x3+a14x4+…..+a1nxn=

b1a21x1+a22x2+a23x3+a24x4+…..+a2nxn=

b2a31x1+a32x2+a33x3+a34x4+…..+a3nxn=

b3am1x1+am2x2+am3x3+am4x4+…..+amnxn=

bmx1,x2,x3,...

xn≥0∶數(shù)學模型食譜問題的拓展問在滿足營養(yǎng)的條件下,如何安排食譜最有利?NewBedfordSteel煉焦煤供應問題

AshleyBedfordConsolDunbyEarlamFlorenceGastonHopt供應量(千噸/年）300600510655575680450490工會（U）/非工會（N）

U

U

N

U

N

U

N

N卡車（T）/

鐵路（R）

R

T

R

T

T

T

R

R可燃率（%）1516182021222325價格(＄/噸）49.5050.0061.0063.5066.5071.0072.5080.00NewBedfordSteel(NBS)是一家小型的煉鋼企業(yè)。煉焦煤(cokingcoal)是NBS公司煉鋼時所必需的一種原材料，每年的需求量是100至150萬噸?，F(xiàn)在到了該公司計劃明年生產(chǎn)的時候了，他們收到了來自八家供應商的報價。NewBedfordSteel煉焦煤供應問題NewBedfordSteel煉焦煤供應問題根據(jù)對未來的形勢估計和生產(chǎn)現(xiàn)狀的考察，NBS計劃明年要定購1,225千噸的煉焦煤。這些煉焦煤的平均可燃率至少要達到19%。為了不影響勞工關系，NBS決定至少50%的煉焦煤要來自于工會煤礦。另外，每年由火車運輸?shù)臒捊姑毫恐炼嗖怀^650千噸，而由卡車運輸?shù)臒捊姑毫恐炼嗖怀^720千噸。現(xiàn)在要解決以下問題：為了使煉焦煤的成本最小，應該從各個供應商處定購多少噸煉焦煤？NBS的總供應成本是多少？NBS的平均供應成本是多少？NewBedfordSteel煉焦煤供應問題根NBS供應問題的數(shù)學表達變量：A= 從Ashley 處定購的煉焦煤量（千噸）B= 從Bedford 處定購的煉焦煤量（千噸）C= 從Consol 處定購的煉焦煤量（千噸）D= 從Dunby 處定購的煉焦煤量（千噸）E= 從Earlam 處定購的煉焦煤量（千噸）F= 從Florence 處定購的煉焦煤量（千噸）G= 從Gaston 處定購的煉焦煤量（千噸）H= 從Hopt 處定購的煉焦煤量（千噸）NBS供應問題的數(shù)學表達變量：供應成本成：49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H供應約束：A+B+C+D+E+F+G+H=1,225工會煤礦的約束：A+B–C+D–E+F–G–H≥0卡車運輸量約束：B+D+E+F≤720火車運輸量約束：A+C+G+H≤650平均可燃率約束：可改寫成：–4A–3B–C+D+2E+3F+4G+6H≥0各煤礦的煉焦煤供應量約束：A≤300，B≤600，C≤510，D≤655，E≤575，F(xiàn)≤680，G≤450，H≤490非負約束：A≥0，B≥0，C≥0，D≥0，E≥0，F(xiàn)≥0，G≥0，H≥0供應成本成：NBS的煉焦煤供應問題的線性最優(yōu)化模型MINIMIZECOST=49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80HSUBJECTTO：SUPPLY： A+B+C+D+E+F+G+H=1,225UNION： A+B–C+D–E+F–G–H≥0TRUCK： B+D+E+F≤720RAIL：A+C+G+H≤650VOL：–4A–3B–C+D+2E+3F+4G+6H≥0ACAP： A≤300BCAP： B≤600CCAP： C≤510DCAP： D≤655ECAP： E≤575FCAP： F≤680GCAP： G≤450HCAP： H≤490NONNEGATIVITYCONDITIONS：A≥0,B≥0,C≥0,D≥0,E≥0,F≥0,G≥0,H≥0NBS的煉焦煤供應問題的線性最優(yōu)化模型MINIMIZECNBS的煉焦煤供應問題的線性最優(yōu)化模型求解，得：A=55千噸，B=600千噸，C=0千噸，

D=20千噸，E=100千噸，F(xiàn)=0千噸，

G=450千噸，H=0千噸；最小成本=73,267.50千美元；平均供應成本=73,267.50/1,225=59.81美元/噸NBS的煉焦煤供應問題的線性最優(yōu)化模型求解，得：二、線性規(guī)劃數(shù)學模型的幾種表達形式一般形式目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0簡寫形式目標函數(shù)：Max（Min）z=

約束條件：s.t.

≤（=,≥）bi,i=1,2,…..m

xj≥0,j=1,2,….n二、線性規(guī)劃數(shù)學模型的幾種表達形式一般形式簡寫形式向量形式C=(c1,c2,…,cn)

價值向量,二、線性規(guī)劃數(shù)學模型的幾種表達形式限定向量變量xj對應的系數(shù)列向量向量形式二、線性規(guī)劃數(shù)學模型的幾種表達形式限定向量變量xj對二、線性規(guī)劃數(shù)學模型的幾種表達形式矩陣形式約束條件系數(shù)矩陣二、線性規(guī)劃數(shù)學模型的幾種表達形式矩陣形式約束條件系數(shù)矩陣第二節(jié)線性規(guī)劃問題的標準形式一、標準形式目標函數(shù)：Maxz=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0或即:同時滿足如下四個條件:目標函數(shù)求極大約束條件全為等式約束條件右端常數(shù)項全為非負變量取值全為非負第二節(jié)線性規(guī)劃問題的標準形式一、標準形式或即:同時§2.1線性規(guī)劃問題與標準形式為了今后討論的方便，我們稱以下兩種形式的線性規(guī)劃問題為線性規(guī)劃的規(guī)范形式（CanonicalForm）： min z＝CTX s.t. AX≥b

X≥0 max z＝CTX s.t. AX≤b

X≥0

§2.1線性規(guī)劃問題與標準形式為了§2.1線性規(guī)劃問題與標準形式而稱以下的形式為標準形式（StandardForm）： maxz＝CTX s.t. AX＝b

X≥0

對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下的變換，將其轉化為標準形式。1極小化目標函數(shù)的問題2約束條件不是等式的問題3變量無符號限制的問題§2.1線性規(guī)劃問題與標準形式而1極小化目標函數(shù)的問題

設目標函數(shù)為令z’＝－z，則以上極大化問題和極小化問題有相同的最優(yōu)解，即但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數(shù)值卻相差一個符號，即min z＝－maxz’1極小化目標函數(shù)的問題

設目標函數(shù)為令z’＝－z，則以上極2約束條件不是等式的問題

設約束條件為

(i=1,2……,m)可以引進一個新的變量xn+i，使它等于約束右邊與左邊之差

顯然xn+I也具有非負約束，即xn+i≥0，這時新的約束條件成為

當約束條件為2約束條件不是等式的問題

設約束條件為

2約束條件不是等式的問題時，類似地令則同樣有xn+i≥0，新的約束條件成為為了使約束由不等式成為等式而引進的變量xn+i稱為“松弛變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量。

2約束條件不是等式的問題時，類似地令為3變量無符號限制的問題

在標準形式中，每一個變量都有非負約束。當一個變量xj沒有非負約束時，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個非負變量之差來表示一個無符號限制的變量，當xj的符號取決于xj’和xj”的大小。3變量無符號限制的問題在標準形式中，每一個變量都§2.2線性規(guī)劃問題的幾何解釋

對于只有兩個變量的線性規(guī)劃問題，可以在二維直角坐標平面上表示線性規(guī)劃問題。Maxz=x1+3x2s.tx1+x2≤6-x1+2x2≤8x1,x2≥0例1.4.1的線性規(guī)劃問題的可行域如圖1.4.1中陰影部分所示?！?.2線性規(guī)劃問題的幾何解釋

對于只有兩個變量的線性規(guī)劃§2.2線性規(guī)劃問題的幾何解釋

§2.2線性規(guī)劃問題的幾何解釋

§2.2線性規(guī)劃問題的幾何解釋

在以上問題中，目標函數(shù)等值線在平行移動過程中與可行域的最后一個交點是B點，這就是線性規(guī)劃問題的最優(yōu)解，這個最優(yōu)解可以由兩直線

x1+x2=6 -x1+2x2=8的交點求得

最優(yōu)解的目標函數(shù)值為

§2.2線性規(guī)劃問題的幾何解釋

在以上問題中，目標函數(shù)等值§2.2線性規(guī)劃問題的幾何解釋

定義1.4.3設S是n維空間中的一個點集。若對任意n維向量X1S，X2S，且X1X2，以及任意實數(shù)（01），有

X=X1+(1-)X2S則稱S為n維空間中的一個凸集。點X稱為點X1和X2的凸組合。以上定義有明顯的幾何意義，它表示凸集S中的任意兩個不相同的點連線上的點（包括這兩個端點），都位于凸集S之中。圖1.4.2表示二維平面中一些凸集和非凸集的例子?！?.2線性規(guī)劃問題的幾何解釋

定義1.4.3設S是n維§2.2線性規(guī)劃問題的幾何解釋

(a)凸集

(b)凸集

(c)凸集

(d)非凸集

(e)非凸集 (d)非凸集

(f)非凸集

§2.2線性規(guī)劃問題的幾何解釋

(a)凸集 (§2.2線性規(guī)劃問題的幾何解釋

定義1.4.4設S為一凸集，且XS，X1S，X2S。對于01，若

X=X1+(1-)X2則必定有X=X1=X2，則稱X為S的一個極點。運用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質：1、若線性規(guī)劃的可行域非空，則可行域必定為一凸集。2、若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少位于一個極點上。這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個可行解中搜索的問題轉化為在其可行域的有限個極點上搜索的問題。最后，來討論線性規(guī)劃的可行域和最優(yōu)解的幾種可能的情況。1、可行域為封閉的有界區(qū)域2、可行域為非封閉的無界區(qū)域§2.2線性規(guī)劃問題的幾何解釋

定義1.4.4設S為一凸§2.2線性規(guī)劃問題的幾何解釋

3、可行域為空集，因而沒有可行解。以上幾種情況的圖示如下：(a)可行域有界(b)可行域有界(c)可行域無界

唯一最優(yōu)解

唯一最優(yōu)解

唯一最優(yōu)解§2.2線性規(guī)劃問題的幾何解釋

3、可行域為空集，因而沒有§2.2線性規(guī)劃問題的幾何解釋

(d)可行域無界

(e)可行域無界(f)可行域為空集

多個最優(yōu)解 目標函數(shù)無界 無可行解圖1.4.3線性規(guī)劃可行域和最優(yōu)解的幾種情況§2.2線性規(guī)劃問題的幾何解釋

(d)可行域無界§2.3單純形法方法

設線性規(guī)劃的約束條件為

AX=b

X≥0其中A為m×n的矩陣，n>m，秩A=m，b為m×1向量。定義2.6線性規(guī)劃的基(Basis)設B是A矩陣中的一個非奇異的m×m子矩陣，則稱B為線性規(guī)劃的一個基(矩陣).定義2.7設B是線性規(guī)劃的一個基（矩陣），線性規(guī)劃的解:稱為線性規(guī)劃與基B對應的基礎解。若其中B-1b0，則稱以上的基礎解為一基礎可行解，相應的基B稱為可行基。定理2.1線性規(guī)劃的基礎可行解就是可行域的極點。

§2.3單純形法方法設線性規(guī)劃的約束條件為§2.3單純形法方法1單純形原理的矩陣描述

2單純形表

3初始基礎可行解

4退化和循環(huán)

§2.3單純形法方法1單純形原理的矩陣描述1單純形原理的矩陣描述

設標準的線性規(guī)劃問題為

max z= CTX s.t. AX=b (1.6.1) X0并設

A=[a1，a2，…，an]其中aj(j=1，2，…，n)是A矩陣的第j個列向量。

B=[a1，a2，…，am]是A的一個基。1單純形原理的矩陣描述

設標準的線性規(guī)劃問題為1單純形原理的矩陣描述這樣，矩陣A可以分塊記為A=[B，N]，相應地，向量X和C可以記為并設R為非基變量的下標集合。利用以上的記號，（1.6.1）中的等式約束AX=b可以寫成

BXB+NXN=b即

XB=B-1b-B-1NXN (1.6.2)這就是在約束條件中，基變量用非基變量表出的形式。1單純形原理的矩陣描述這樣，矩陣A可以分塊記為A=[B，N1單純形原理的矩陣描述對于一個確定的基B，目標函數(shù)z可以寫成

將(1.6.2)式代入以上目標函數(shù)表達式，得到目標函數(shù)z用非基變量表出的形式

1單純形原理的矩陣描述對于一個確定的基B，目標函數(shù)z可以寫1單純形原理的矩陣描述(1.6.2)和(1.6.3)式表示，非基變量的任何一組確定的值，基變量和目標函數(shù)都有一組確定的值與之對應。特別，當XN=0時，相應的解

就是對應于基B的基礎解。如果B是一個可行基，則有

1單純形原理的矩陣描述(1.6.2)和(1.6.3)式表示1單純形原理的矩陣描述下面我們來詳細說明如何實現(xiàn)以上步驟。步驟1、獲得初始基礎可行解的一般化的方法將在下一節(jié)中敘述。在這里，我們假定已經(jīng)獲得了一個初始的可行基B，基B對應的基礎解為

當前的目標函數(shù)值為

1單純形原理的矩陣描述下面我們來詳細說明如何實現(xiàn)以上步驟。1單純形原理的矩陣描述步驟2、確定進基的非基變量xk由(1.6.1)可知，當前目標函數(shù)值用非基變量用非基變量表出的形式是

令

1單純形原理的矩陣描述步驟2、確定進基的非基變量xk 令1單純形原理的矩陣描述則

如果對于所有jR，有zj-cj0，則任何非基變量xj的值由0開始增加都不會使z減少，因此當前基B已是最優(yōu)基，相應的基礎可行解

如果有kR，使zk-ck>0，則非基變量xk的增加將會使目標函數(shù)值減少。為了使目標函數(shù)值下降得快一些，一般選取滿足1單純形原理的矩陣描述則 如果對于所有jR，有zj-1單純形原理的矩陣描述

的非基變量xk為進基變量。由于除xk以外的非基變量的值均保持為0不變，這時目標函數(shù)可以表示為

步驟3、確定基變量中離基的變量xBr在(1.6.2)中，令1單純形原理的矩陣描述 的非基變量xk為進基變量。由于除1單純形原理的矩陣描述

則(1.6.2)可以表示為

當進基變量xk的值由0增加到某一正值，其余非基變量均保持為0時，上式成為

1單純形原理的矩陣描述 則(1.6.2)可以表示為 當1單純形原理的矩陣描述

即

1單純形原理的矩陣描述 即 1單純形原理的矩陣描述在(1.6.6)中，有以下幾種情形：（1）如果向量Yk中所有的分量yik0，則xk的增加將不會使任何xBi(i=1，2，...，m)減少，這時xk可無限增加，同時所有的基變量仍保持非負。同時由于xk在目標函數(shù)中的系數(shù)zk-ck>0，由(1.6.5)可知當xk增加時目標函數(shù)將無限減少，即目標函數(shù)無界。（2）如果向量Yk中至少有一個分量yik>0，則xk由0開始增加將會使相應的基變量xBi的值由當前的值bi開始減少。當xk增加到

1單純形原理的矩陣描述在(1.6.6)中，有以下幾種情形：1單純形原理的矩陣描述相應的基變量xBr=0，而其余的基變量xBi0（i=1，2，...，m，ir），這時基變量xBr離基，它在基B中相應的列向量aBr將換出基矩陣，進基變量xk在A矩陣中相應的列向量ak將取代基矩陣B中aBr的位置，得到新的可行基

B’=[aB1，aB2，…，aBr-1，ak，aBr+1，…，aBm]新的基B’相應的基變量的值為

1單純形原理的矩陣描述相應的基變量xBr=0，而其余的基變1單純形原理的矩陣描述B’相應的非基變量的值為

XN=0B’對應的目標函數(shù)值為步驟4、由新的基B’重新確定非基變量集合R’，并重新計算(1.6.4)以判定B’是否為最優(yōu)基。若不是，計算(1.6.4)~(1.6.8)以實現(xiàn)進一步的基變換。

1單純形原理的矩陣描述B’相應的非基變量的值為步驟4、由新2單純形表

單純形算法的實質是將非基變量視為一組參數(shù)，并將目標函數(shù)和基變量都表示成為由非基變量表示的形式。即（1.6.2）和（1.6.3）兩式。這樣就可以討論當非基變量變化時，目標函數(shù)和基變量隨之變化的情況。我們可以用一個矩陣來表示單純形法迭代中所需要的全部信息，這就是所謂的單純形表。設線性規(guī)劃問題為

maxz=CTX s.t. AX=b (1.7.1)

X0并設B是A的一個可行基，并記A=[B，N]，相應地將目標函數(shù)系數(shù)向量C以及變量X表示為2單純形表單純形算法的實質是將非基變量視為一組參數(shù)，并將2單純形表

則(1.7.1)可表為即2單純形表 則(1.7.1)可表為即2單純形表

將(1.7.3)的系數(shù)寫成矩陣形式，有zXBXNRHS10-CBT-CNT0BNb2單純形表 將(1.7.3)的系數(shù)寫成矩陣形式，有zXB2單純形表稱以上矩陣為線性規(guī)劃問題的系數(shù)矩陣（并不是單純形表）。為了將約束中的基變量用非基變量表出，用B-1左乘以上系數(shù)矩陣的后m行，得到zXBXNRHS1-CBT0-CNT0IB-1NB-1b為了將第一行中的目標函數(shù)z用非基變量XN表出，在矩陣的后m行左乘CBT后加到第一行上，消去基變量在目標函數(shù)中的系數(shù)，得到2單純形表稱以上矩陣為線性規(guī)劃問題的系數(shù)矩陣（并不是單純形2單純形表zXBXNRHS10TCBTB-1bCBTB-1N-CNT0IB-1NB-1b以上矩陣的第一行與(1.6.3)完全等價，后m行與(1.6.2)完全等價。這一矩陣稱為與基B對應的單純形表。單純形表可以由系數(shù)矩陣經(jīng)過一系列行變換得到，這些行變換使得系數(shù)矩陣中的基矩陣變?yōu)閱挝痪仃嘔，而將基變量在目標函數(shù)中的系數(shù)全消為零。

2單純形表zXBXNRHS10TCBTB-1bCBTB-12單純形表利用上一節(jié)中的記號，可以將表1.7.3的單純形表用分量的形式表示如表1.7.4。

zx1..xr..xmxk…xjRHS10…0…0…y1k…y1j…b10001…0…00…1…00…0…1…y1k…y1j……yr

k…yrj……ym

k…ym

j…b1BrBm可以看出，單純形表中直接包含了單純形迭代所需要的一切信息。

2單純形表利用上一節(jié)中的記號，可以將表1.7.3的單純形表2單純形表用單純形表求解線性規(guī)劃問題的步驟可以歸納如下：1、寫出線性規(guī)劃問題的系數(shù)矩陣表；2、找到一個可行基B，對系數(shù)矩陣進行變換，使得：（1）基矩陣成為單位矩陣；（2）基變量在目標函數(shù)中的系數(shù)為零。從而得到以B為基的單純形表。3、根據(jù)單純形表，確定進基變量xk和離基變量xr，并根據(jù)列指標k和行指標r確定主元yr

k；4、以yr

k為主元進行行變換（稱為以yrk為主元的旋轉運算），使得單純形表中yr

k所在的列中其他元素為0，yr

k本身為1；重復步驟3、4，直至獲得最優(yōu)解或確定目標函數(shù)無界。

2單純形表用單純形表求解線性規(guī)劃問題的步驟可以歸納如下：3

初始基礎可行解

設線性規(guī)劃問題為

minz=CTX s.t. AX=b X≥0 (2.14) 第一階段：引進人工變量Xa=(xn+1，xn+2，…，xn+m)T，構造輔助問題

(2.15)

3初始基礎可行解

設線性規(guī)劃問題為3

初始基礎可行解求解輔助問題。若輔助問題的最優(yōu)基B全部在A中，即Xa全部是非基變量（minz’=0），則B為(2.14)的一個可行基。轉第二階段。若輔助問題的最優(yōu)目標函數(shù)值minz’>0，則至少有一個人工變量留在第一階段問題最優(yōu)解的基變量中，這時(2.14)無可行解。第二階段：以第一階段(2.15)的最優(yōu)基B作為(1.8.4)的初始可行基，求解(2.14)，得到(2.14)的最優(yōu)基和最優(yōu)解。3初始基礎可行解求解輔助問題。若輔助問題的最優(yōu)基B全部在A4退化和循環(huán)如何防止出現(xiàn)循環(huán)作了大量研究。1952年Charnes提出了“攝動法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”。這些方法都比較復雜，同時也降低了疊代的速度。

1976年，Bland提出了一個避免循環(huán)的新方法，其原則十分簡單。僅在選擇進基變量和離基變量時作了以下規(guī)定：1、在選擇進基變量時，在所有zj-cj>0的非基變量中選取下標最小的進基；2、當有多個變量同時可作為離基變量時，選擇下標最小的那個變量離基。這樣就可以避免出現(xiàn)循環(huán)。當然，用Bland的方法，由于選取進基變量時不再考慮zj-cj絕對值的大小，將會導致收斂速度的降低。

4退化和循環(huán)如何防止出現(xiàn)循環(huán)作了大量研究。1952年Cha第二三四五章線性規(guī)劃§2.1線性規(guī)劃問題與標準形式§2.2線性規(guī)劃問題的幾何解釋§2.3單純型法方法第二三四五章線性規(guī)劃問題的提出（1）【例】派公司是一個生產(chǎn)高爾夫器材的小型公司，公司決定生產(chǎn)中高價位的高爾夫袋。產(chǎn)品的生產(chǎn)過程有四個程序：切割并印染原材料、縫合、成型、檢查和包裝，不同價位高爾夫袋生產(chǎn)程序的耗時信息如下表，表中還列出了派公司在本輪生產(chǎn)過程中每個部門的最大生產(chǎn)時間。問題的提出（1）【例】派公司是一個生產(chǎn)高爾夫器材的小型公司，問題的提出（2）會計部門的數(shù)據(jù)表明，生產(chǎn)一個標準袋的利潤是10美元，生產(chǎn)一個高級袋的利潤是9美元。如何安排兩種產(chǎn)品的生產(chǎn)才能使公司獲得最大利潤？耗時/標準袋耗時/高檔袋最大生產(chǎn)時間切割印染0.71630縫合0.55/6600成型12/3708檢查包裝0.10.25135問題的提出（2）會計部門的數(shù)據(jù)表明，生產(chǎn)一個標準袋的利潤是1問題的提出（3）設x1、x2分別為兩種高爾夫袋的生產(chǎn)量，則該計劃問題可用如下數(shù)學模型表示為：問題的提出（3）設x1、x2分別為兩種高爾夫袋的生產(chǎn)量，則該§2.1線性規(guī)劃問題與標準形式

典例1-----生產(chǎn)計劃問題例2.某工廠在計劃期內(nèi)要生產(chǎn)產(chǎn)品I和產(chǎn)品II這兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種設備計劃期的有效臺時，如下表：問如何安排生產(chǎn)最有利？解∶設產(chǎn)品I和產(chǎn)品II的產(chǎn)量分別為x1和x2件,利潤為Z,則:

Z=x1+2x2Max目標函數(shù)2x1+2x2≤80x1+2x2≤4x1,x2≥0約束條件S.t.非負條件§2.1線性規(guī)劃問題與標準形式

典例1-----[企業(yè)管理]MBA運籌學2第二五章線性規(guī)劃課件above,above,[企業(yè)管理]MBA運籌學2第二五章線性規(guī)劃課件[企業(yè)管理]MBA運籌學2第二五章線性規(guī)劃課件典例2----配料問題

Z=3x1+2x2Min目標函數(shù)12x1+3x2≥42x1+3x2≥23x1+15x2≥5x1+x2=1x1,x2≥0約束條件S.t.典例2----配料問題Z=3x1+2x2Mi典例3----食譜問題[例3]問在滿足營養(yǎng)的條件下,如何安排食譜最有利?解:設每人每周食用大米、白菜、雞蛋、豬肉的數(shù)量分別為x1、x2、

x3、

x4Z=C1x1+C2x2+C3x3+C4x4Mina11x1+a12x2+a13x3+a14x4b1=a21x1+a22x2+a23x3+a24x4=

b2a31x1+a32x2+a33x3+a34x4=

b3x1,x2,x3,

x4≥0典例3----食譜問題[例3]問在滿足營養(yǎng)的條件下,如何安排食譜問題的拓展問在滿足營養(yǎng)的條件下,如何安排食譜最有利?Z=C1x1+C2x2+C3x3+C4x4+...+CnxnMina11x1+a12x2+a13x3+a14x4+…..+a1nxn=

b1a21x1+a22x2+a23x3+a24x4+…..+a2nxn=

b2a31x1+a32x2+a33x3+a34x4+…..+a3nxn=

b3am1x1+am2x2+am3x3+am4x4+…..+amnxn=

bmx1,x2,x3,...

xn≥0∶數(shù)學模型食譜問題的拓展問在滿足營養(yǎng)的條件下,如何安排食譜最有利?NewBedfordSteel煉焦煤供應問題

AshleyBedfordConsolDunbyEarlamFlorenceGastonHopt供應量(千噸/年）300600510655575680450490工會（U）/非工會（N）

U

U

N

U

N

U

N

N卡車（T）/

鐵路（R）

R

T

R

T

T

T

R

R可燃率（%）1516182021222325價格(＄/噸）49.5050.0061.0063.5066.5071.0072.5080.00NewBedfordSteel(NBS)是一家小型的煉鋼企業(yè)。煉焦煤(cokingcoal)是NBS公司煉鋼時所必需的一種原材料，每年的需求量是100至150萬噸。現(xiàn)在到了該公司計劃明年生產(chǎn)的時候了，他們收到了來自八家供應商的報價。NewBedfordSteel煉焦煤供應問題NewBedfordSteel煉焦煤供應問題根據(jù)對未來的形勢估計和生產(chǎn)現(xiàn)狀的考察，NBS計劃明年要定購1,225千噸的煉焦煤。這些煉焦煤的平均可燃率至少要達到19%。為了不影響勞工關系，NBS決定至少50%的煉焦煤要來自于工會煤礦。另外，每年由火車運輸?shù)臒捊姑毫恐炼嗖怀^650千噸，而由卡車運輸?shù)臒捊姑毫恐炼嗖怀^720千噸?，F(xiàn)在要解決以下問題：為了使煉焦煤的成本最小，應該從各個供應商處定購多少噸煉焦煤？NBS的總供應成本是多少？NBS的平均供應成本是多少？NewBedfordSteel煉焦煤供應問題根NBS供應問題的數(shù)學表達變量：A= 從Ashley 處定購的煉焦煤量（千噸）B= 從Bedford 處定購的煉焦煤量（千噸）C= 從Consol 處定購的煉焦煤量（千噸）D= 從Dunby 處定購的煉焦煤量（千噸）E= 從Earlam 處定購的煉焦煤量（千噸）F= 從Florence 處定購的煉焦煤量（千噸）G= 從Gaston 處定購的煉焦煤量（千噸）H= 從Hopt 處定購的煉焦煤量（千噸）NBS供應問題的數(shù)學表達變量：供應成本成：49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H供應約束：A+B+C+D+E+F+G+H=1,225工會煤礦的約束：A+B–C+D–E+F–G–H≥0卡車運輸量約束：B+D+E+F≤720火車運輸量約束：A+C+G+H≤650平均可燃率約束：可改寫成：–4A–3B–C+D+2E+3F+4G+6H≥0各煤礦的煉焦煤供應量約束：A≤300，B≤600，C≤510，D≤655，E≤575，F(xiàn)≤680，G≤450，H≤490非負約束：A≥0，B≥0，C≥0，D≥0，E≥0，F(xiàn)≥0，G≥0，H≥0供應成本成：NBS的煉焦煤供應問題的線性最優(yōu)化模型MINIMIZECOST=49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80HSUBJECTTO：SUPPLY： A+B+C+D+E+F+G+H=1,225UNION： A+B–C+D–E+F–G–H≥0TRUCK： B+D+E+F≤720RAIL：A+C+G+H≤650VOL：–4A–3B–C+D+2E+3F+4G+6H≥0ACAP： A≤300BCAP： B≤600CCAP： C≤510DCAP： D≤655ECAP： E≤575FCAP： F≤680GCAP： G≤450HCAP： H≤490NONNEGATIVITYCONDITIONS：A≥0,B≥0,C≥0,D≥0,E≥0,F≥0,G≥0,H≥0NBS的煉焦煤供應問題的線性最優(yōu)化模型MINIMIZECNBS的煉焦煤供應問題的線性最優(yōu)化模型求解，得：A=55千噸，B=600千噸，C=0千噸，

D=20千噸，E=100千噸，F(xiàn)=0千噸，

G=450千噸，H=0千噸；最小成本=73,267.50千美元；平均供應成本=73,267.50/1,225=59.81美元/噸NBS的煉焦煤供應問題的線性最優(yōu)化模型求解，得：二、線性規(guī)劃數(shù)學模型的幾種表達形式一般形式目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0簡寫形式目標函數(shù)：Max（Min）z=

約束條件：s.t.

≤（=,≥）bi,i=1,2,…..m

xj≥0,j=1,2,….n二、線性規(guī)劃數(shù)學模型的幾種表達形式一般形式簡寫形式向量形式C=(c1,c2,…,cn)

價值向量,二、線性規(guī)劃數(shù)學模型的幾種表達形式限定向量變量xj對應的系數(shù)列向量向量形式二、線性規(guī)劃數(shù)學模型的幾種表達形式限定向量變量xj對二、線性規(guī)劃數(shù)學模型的幾種表達形式矩陣形式約束條件系數(shù)矩陣二、線性規(guī)劃數(shù)學模型的幾種表達形式矩陣形式約束條件系數(shù)矩陣第二節(jié)線性規(guī)劃問題的標準形式一、標準形式目標函數(shù)：Maxz=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0或即:同時滿足如下四個條件:目標函數(shù)求極大約束條件全為等式約束條件右端常數(shù)項全為非負變量取值全為非負第二節(jié)線性規(guī)劃問題的標準形式一、標準形式或即:同時§2.1線性規(guī)劃問題與標準形式為了今后討論的方便，我們稱以下兩種形式的線性規(guī)劃問題為線性規(guī)劃的規(guī)范形式（CanonicalForm）： min z＝CTX s.t. AX≥b

X≥0 max z＝CTX s.t. AX≤b

X≥0

§2.1線性規(guī)劃問題與標準形式為了§2.1線性規(guī)劃問題與標準形式而稱以下的形式為標準形式（StandardForm）： maxz＝CTX s.t. AX＝b

X≥0

對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下的變換，將其轉化為標準形式。1極小化目標函數(shù)的問題2約束條件不是等式的問題3變量無符號限制的問題§2.1線性規(guī)劃問題與標準形式而1極小化目標函數(shù)的問題

設目標函數(shù)為令z’＝－z，則以上極大化問題和極小化問題有相同的最優(yōu)解，即但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數(shù)值卻相差一個符號，即min z＝－maxz’1極小化目標函數(shù)的問題

設目標函數(shù)為令z’＝－z，則以上極2約束條件不是等式的問題

設約束條件為

(i=1,2……,m)可以引進一個新的變量xn+i，使它等于約束右邊與左邊之差

顯然xn+I也具有非負約束，即xn+i≥0，這時新的約束條件成為

當約束條件為2約束條件不是等式的問題

設約束條件為

2約束條件不是等式的問題時，類似地令則同樣有xn+i≥0，新的約束條件成為為了使約束由不等式成為等式而引進的變量xn+i稱為“松弛變量”。如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的松弛變量。

2約束條件不是等式的問題時，類似地令為3變量無符號限制的問題

在標準形式中，每一個變量都有非負約束。當一個變量xj沒有非負約束時，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個非負變量之差來表示一個無符號限制的變量，當xj的符號取決于xj’和xj”的大小。3變量無符號限制的問題在標準形式中，每一個變量都§2.2線性規(guī)劃問題的幾何解釋

對于只有兩個變量的線性規(guī)劃問題，可以在二維直角坐標平面上表示線性規(guī)劃問題。Maxz=x1+3x2s.tx1+x2≤6-x1+2x2≤8x1,x2≥0例1.4.1的線性規(guī)劃問題的可行域如圖1.4.1中陰影部分所示?！?.2線性規(guī)劃問題的幾何解釋

對于只有兩個變量的線性規(guī)劃§2.2線性規(guī)劃問題的幾何解釋

§2.2線性規(guī)劃問題的幾何解釋

§2.2線性規(guī)劃問題的幾何解釋

在以上問題中，目標函數(shù)等值線在平行移動過程中與可行域的最后一個交點是B點，這就是線性規(guī)劃問題的最優(yōu)解，這個最優(yōu)解可以由兩直線

x1+x2=6 -x1+2x2=8的交點求得

最優(yōu)解的目標函數(shù)值為

§2.2線性規(guī)劃問題的幾何解釋

在以上問題中，目標函數(shù)等值§2.2線性規(guī)劃問題的幾何解釋

定義1.4.3設S是n維空間中的一個點集。若對任意n維向量X1S，X2S，且X1X2，以及任意實數(shù)（01），有

X=X1+(1-)X2S則稱S為n維空間中的一個凸集。點X稱為點X1和X2的凸組合。以上定義有明顯的幾何意義，它表示凸集S中的任意兩個不相同的點連線上的點（包括這兩個端點），都位于凸集S之中。圖1.4.2表示二維平面中一些凸集和非凸集的例子?！?.2線性規(guī)劃問題的幾何解釋

定義1.4.3設S是n維§2.2線性規(guī)劃問題的幾何解釋

(a)凸集

(b)凸集

(c)凸集

(d)非凸集

(e)非凸集 (d)非凸集

(f)非凸集

§2.2線性規(guī)劃問題的幾何解釋

(a)凸集 (§2.2線性規(guī)劃問題的幾何解釋

定義1.4.4設S為一凸集，且XS，X1S，X2S。對于01，若

X=X1+(1-)X2則必定有X=X1=X2，則稱X為S的一個極點。運用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質：1、若線性規(guī)劃的可行域非空，則可行域必定為一凸集。2、若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少位于一個極點上。這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個可行解中搜索的問題轉化為在其可行域的有限個極點上搜索的問題。最后，來討論線性規(guī)劃的可行域和最優(yōu)解的幾種可能的情況。1、可行域為封閉的有界區(qū)域2、可行域為非封閉的無界區(qū)域§2.2線性規(guī)劃問題的幾何解釋

定義1.4.4設S為一凸§2.2線性規(guī)劃問題的幾何解釋

3、可行域為空集，因而沒有可行解。以上幾種情況的圖示如下：(a)可行域有界(b)可行域有界(c)可行域無界

唯一最優(yōu)解

唯一最優(yōu)解

唯一最優(yōu)解§2.2線性規(guī)劃問題的幾何解釋

3、可行域為空集，因而沒有§2.2線性規(guī)劃問題的幾何解釋

(d)可行域無界

(e)可行域無界(f)可行域為空集

多個最優(yōu)解 目標函數(shù)無界 無可行解圖1.4.3線性規(guī)劃可行域和最優(yōu)解的幾種情況§2.2線性規(guī)劃問題的幾何解釋

(d)可行域無界§2.3單純形法方法

設線性規(guī)劃的約束條件為

AX=b

X≥0其中A為m×n的矩陣，n>m，秩A=m，b為m×1向量。定義2.6線性規(guī)劃的基(Basis)設B是A矩陣中的一個非奇異的m×m子矩陣，則稱B為線性規(guī)劃的一個基(矩陣).定義2.7設B是線性規(guī)劃的一個基（矩陣），線性規(guī)劃的解:稱為線性規(guī)劃與基B對應的基礎解。若其中B-1b0，則稱以上的基礎解為一基礎可行解，相應的基B稱為可行基。定理2.1線性規(guī)劃的基礎可行解就是可行域的極點。

§2.3單純形法方法設線性規(guī)劃的約束條件為§2.3單純形法方法1單純形原理的矩陣描述

2單純形表

3初始基礎可行解

4退化和循環(huán)

§2.3單純形法方法1單純形原理的矩陣描述1單純形原理的矩陣描述

設標準的線性規(guī)劃問題為

max z= CTX s.t. AX=b (1.6.1) X0并設

A=[a1，a2，…，an]其中aj(j=1，2，…，n)是A矩陣的第j個列向量。

B=[a1，a2，…，am]是A的一個基。1單純形原理的矩陣描述

設標準的線性規(guī)劃問題為1單純形原理的矩陣描述這樣，矩陣A可以分塊記為A=[B，N]，相應地，向量X和C可以記為并設R為非基變量的下標集合。利用以上的記號，（1.6.1）中的等式約束AX=b可以寫成

BXB+NXN=b即

XB=B-1b-B-1NXN (1.6.2)這就是在約束條件中，基變量用非基變量表出的形式。1單純形原理的矩陣描述這樣，矩陣A可以分塊記為A=[B，N1單純形原理的矩陣描述對于一個確定的基B，目標函數(shù)z可以寫成

將(1.6.2)式代入以上目標函數(shù)表達式，得到目標函數(shù)z用非基變量表出的形式

1單純形原理的矩陣描述對于一個確定的基B，目標函數(shù)z可以寫1單純形原理的矩陣描述(1.6.2)和(1.6.3)式表示，非基變量的任何一組確定的值，基變量和目標函數(shù)都有一組確定的值與之對應。特別，當XN=0時，相應的解

就是對應于基B的基礎解。如果B是一個可行基，則有

1單純形原理的矩陣描述(1.6.2)和(1.6.3)式表示1單純形原理的矩陣描述下面我們來詳細說明如何實現(xiàn)以上步驟。步驟1、獲得初始基礎可行解的一般化的方法將在下一節(jié)中敘述。在這里，我們假定已經(jīng)獲得了一個初始的可行基B，基B對應的基礎解為

當前的目標函數(shù)值為

1單純形原理的矩陣描述下面我們來詳細說明如何實現(xiàn)以上步驟。1單純形原理的矩陣描述步驟2、確定進基的非基變量xk由(1.6.1)可知，當前目標函數(shù)值用非基變量用非基變量表出的形式是

令

1單純形原理的矩陣描述步驟2、確定進基的非基變量xk 令1單純形原理的矩陣描述則

如果對于所有jR，有zj-cj0，則任何非基變量xj的值由0開始增加都不會使z減少，因此當前基B已是最優(yōu)基，相應的基礎可行解

如果有kR，使zk-ck>0，則非基變量xk的增加將會使目標函數(shù)值減少。為了使目標函數(shù)值下降得快一些，一般選取滿足1單純形原理的矩陣描述則 如果對于所有jR，有zj-1單純形原理的矩陣描述

的非基變量xk為進基變量。由于除xk以外的非基變量的值均保持為0不變，這時目標函數(shù)可以表示為

步驟3、確定基變量中離基的變量xBr在(1.6.2)中，令1單純形原理的矩陣描述 的非基變量xk為進基變量。由于除1單純形原理的矩陣描述

則(1.6.2)可以表示為

當進基變量xk的值由0增加到某一正值，其余非基變量均保持為0時，上式成為

1單純形原理的矩陣描述 則(1.6.2)可以表示為 當1單純形原理的矩陣描述

即

1單純形原理的矩陣描述 即 1單純形原理的矩陣描述在(1.6.6)中，有以下幾種情形：（1）如果向量Yk中所有的分量yik0，則xk的增加將不會使任何xBi(i=1，2，...，m)減少，這時xk可無限增加，同時所有的基變量仍保持非負。同時由于xk在目標函數(shù)中的系數(shù)zk-ck>0，由(1.6.5)可知當xk增加時目標函數(shù)將無限減少，即目標函數(shù)無界。（2）如果向量Yk中至少有一個分量yik>0，則xk由0開始增加將會使相應的基變量xBi的值由當前的值bi開始減少。當xk增加到

1單純形原理的矩陣描述在(1.6.6)中，有以下幾種情形：1單純形原理的矩陣描述相應的基變量xBr=0，而其余的基變量xBi0（i=1，2，...，m，ir），這時基變量xBr離基，它在基B中相應的列向量aBr將換出基矩陣，進基變量xk在A矩陣中相應的列向量ak將取代基矩陣B中aBr的位置，得到新的可行基