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

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

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

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

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

Z=3x1+2x2Min目標(biāo)函數(shù)12x1+3x2≥42x1+3x2≥23x1+15x2≥5x1+x2=1x1,x2≥0約束條件S.t.典例2----配料問題Z=3x1+2x2Mi典例3----食譜問題[例3]問在滿足營養(yǎng)的條件下,如何安排食譜最有利?解:設(shè)每人每周食用大米、白菜、雞蛋、豬肉的數(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ù)學(xué)模型食譜問題的拓展問在滿足營養(yǎng)的條件下,如何安排食譜最有利?NewBedfordSteel煉焦煤供應(yīng)問題

AshleyBedfordConsolDunbyEarlamFlorenceGastonHopt供應(yīng)量(千噸/年）300600510655575680450490工會(huì)（U）/非工會(huì)（N）

U

U

N

U

N

U

N

N卡車（T）/

鐵路（R）

R

T

R

T

T

T

R

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

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

G=450千噸，H=0千噸；最小成本=73,267.50千美元；平均供應(yīng)成本=73,267.50/1,225=59.81美元/噸NBS的煉焦煤供應(yīng)問題的線性最優(yōu)化模型求解，得：二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式一般形式目標(biāo)函數(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簡寫形式目標(biāo)函數(shù)：Max（Min）z=

約束條件：s.t.

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

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

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

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

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0或即:同時(shí)滿足如下四個(gè)條件:目標(biāo)函數(shù)求極大約束條件全為等式約束條件右端常數(shù)項(xiàng)全為非負(fù)變量取值全為非負(fù)第二節(jié)線性規(guī)劃問題的標(biāo)準(zhǔn)形式一、標(biāo)準(zhǔn)形式或即:同時(shí)§2.1線性規(guī)劃問題與標(biāo)準(zhǔn)形式為了今后討論的方便，我們稱以下兩種形式的線性規(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ī)劃問題與標(biāo)準(zhǔn)形式為了§2.1線性規(guī)劃問題與標(biāo)準(zhǔn)形式而稱以下的形式為標(biāo)準(zhǔn)形式（StandardForm）： maxz＝CTX s.t. AX＝b

X≥0

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

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

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

設(shè)約束條件為

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

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

當(dāng)約束條件為2約束條件不是等式的問題

設(shè)約束條件為

2約束條件不是等式的問題時(shí)，類似地令則同樣有xn+i≥0，新的約束條件成為為了使約束由不等式成為等式而引進(jìn)的變量xn+i稱為“松弛變量”。如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對各個(gè)約束引進(jìn)不同的松弛變量。

2約束條件不是等式的問題時(shí)，類似地令為3變量無符號(hào)限制的問題

在標(biāo)準(zhǔn)形式中，每一個(gè)變量都有非負(fù)約束。當(dāng)一個(gè)變量xj沒有非負(fù)約束時(shí)，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

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

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

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

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

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

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

x1+x2=6 -x1+2x2=8的交點(diǎn)求得

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

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

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

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

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

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

(a)凸集

(b)凸集

(c)凸集

(d)非凸集

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

(f)非凸集

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

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

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

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

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

3、可行域?yàn)榭占蚨鴽]有可行解。以上幾種情況的圖示如下：(a)可行域有界(b)可行域有界(c)可行域無界

唯一最優(yōu)解

唯一最優(yōu)解

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

3、可行域?yàn)榭占?，因而沒有§2.2線性規(guī)劃問題的幾何解釋

(d)可行域無界

(e)可行域無界(f)可行域?yàn)榭占?/p>

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

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

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

AX=b

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

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

2單純形表

3初始基礎(chǔ)可行解

4退化和循環(huán)

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

設(shè)標(biāo)準(zhǔn)的線性規(guī)劃問題為

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

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

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

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

BXB+NXN=b即

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

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

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

就是對應(yīng)于基B的基礎(chǔ)解。如果B是一個(gè)可行基，則有

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

當(dāng)前的目標(biāo)函數(shù)值為

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

令

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

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

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

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

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

則(1.6.2)可以表示為

當(dāng)進(jìn)基變量xk的值由0增加到某一正值，其余非基變量均保持為0時(shí)，上式成為

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

即

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

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

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

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

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

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

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

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

X0并設(shè)B是A的一個(gè)可行基，并記A=[B，N]，相應(yīng)地將目標(biāo)函數(shù)系數(shù)向量C以及變量X表示為2單純形表單純形算法的實(shí)質(zhì)是將非基變量視為一組參數(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為了將第一行中的目標(biāo)函數(shù)z用非基變量XN表出，在矩陣的后m行左乘CBT后加到第一行上，消去基變量在目標(biāo)函數(shù)中的系數(shù)，得到2單純形表稱以上矩陣為線性規(guī)劃問題的系數(shù)矩陣（并不是單純形2單純形表zXBXNRHS10TCBTB-1bCBTB-1N-CNT0IB-1NB-1b以上矩陣的第一行與(1.6.3)完全等價(jià)，后m行與(1.6.2)完全等價(jià)。這一矩陣稱為與基B對應(yīng)的單純形表。單純形表可以由系數(shù)矩陣經(jīng)過一系列行變換得到，這些行變換使得系數(shù)矩陣中的基矩陣變?yōu)閱挝痪仃嘔，而將基變量在目標(biāo)函數(shù)中的系數(shù)全消為零。

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

k；4、以yr

k為主元進(jìn)行行變換（稱為以yrk為主元的旋轉(zhuǎn)運(yùn)算），使得單純形表中yr

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

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

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

初始基礎(chǔ)可行解

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

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

(2.15)

3初始基礎(chǔ)可行解

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

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

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

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

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

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

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

Z=3x1+2x2Min目標(biāo)函數(shù)12x1+3x2≥42x1+3x2≥23x1+15x2≥5x1+x2=1x1,x2≥0約束條件S.t.典例2----配料問題Z=3x1+2x2Mi典例3----食譜問題[例3]問在滿足營養(yǎng)的條件下,如何安排食譜最有利?解:設(shè)每人每周食用大米、白菜、雞蛋、豬肉的數(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ù)學(xué)模型食譜問題的拓展問在滿足營養(yǎng)的條件下,如何安排食譜最有利?NewBedfordSteel煉焦煤供應(yīng)問題

AshleyBedfordConsolDunbyEarlamFlorenceGastonHopt供應(yīng)量(千噸/年）300600510655575680450490工會(huì)（U）/非工會(huì)（N）

U

U

N

U

N

U

N

N卡車（T）/

鐵路（R）

R

T

R

T

T

T

R

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

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

G=450千噸，H=0千噸；最小成本=73,267.50千美元；平均供應(yīng)成本=73,267.50/1,225=59.81美元/噸NBS的煉焦煤供應(yīng)問題的線性最優(yōu)化模型求解，得：二、線性規(guī)劃數(shù)學(xué)模型的幾種表達(dá)形式一般形式目標(biāo)函數(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簡寫形式目標(biāo)函數(shù)：Max（Min）z=

約束條件：s.t.

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

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

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

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

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0或即:同時(shí)滿足如下四個(gè)條件:目標(biāo)函數(shù)求極大約束條件全為等式約束條件右端常數(shù)項(xiàng)全為非負(fù)變量取值全為非負(fù)第二節(jié)線性規(guī)劃問題的標(biāo)準(zhǔn)形式一、標(biāo)準(zhǔn)形式或即:同時(shí)§2.1線性規(guī)劃問題與標(biāo)準(zhǔn)形式為了今后討論的方便，我們稱以下兩種形式的線性規(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ī)劃問題與標(biāo)準(zhǔn)形式為了§2.1線性規(guī)劃問題與標(biāo)準(zhǔn)形式而稱以下的形式為標(biāo)準(zhǔn)形式（StandardForm）： maxz＝CTX s.t. AX＝b

X≥0

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

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

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

設(shè)約束條件為

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

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

當(dāng)約束條件為2約束條件不是等式的問題

設(shè)約束條件為

2約束條件不是等式的問題時(shí)，類似地令則同樣有xn+i≥0，新的約束條件成為為了使約束由不等式成為等式而引進(jìn)的變量xn+i稱為“松弛變量”。如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對各個(gè)約束引進(jìn)不同的松弛變量。

2約束條件不是等式的問題時(shí)，類似地令為3變量無符號(hào)限制的問題

在標(biāo)準(zhǔn)形式中，每一個(gè)變量都有非負(fù)約束。當(dāng)一個(gè)變量xj沒有非負(fù)約束時(shí)，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

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

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

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

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

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

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

x1+x2=6 -x1+2x2=8的交點(diǎn)求得

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

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

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

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

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

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

(a)凸集

(b)凸集

(c)凸集

(d)非凸集

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

(f)非凸集

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

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

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

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

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

3、可行域?yàn)榭占蚨鴽]有可行解。以上幾種情況的圖示如下：(a)可行域有界(b)可行域有界(c)可行域無界

唯一最優(yōu)解

唯一最優(yōu)解

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

3、可行域?yàn)榭占?，因而沒有§2.2線性規(guī)劃問題的幾何解釋

(d)可行域無界

(e)可行域無界(f)可行域?yàn)榭占?/p>

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

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

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

AX=b

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

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

2單純形表

3初始基礎(chǔ)可行解

4退化和循環(huán)

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

設(shè)標(biāo)準(zhǔn)的線性規(guī)劃問題為

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

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

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

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

BXB+NXN=b即

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

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

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

就是對應(yīng)于基B的基礎(chǔ)解。如果B是一個(gè)可行基，則有

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

當(dāng)前的目標(biāo)函數(shù)值為

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

令

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

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

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

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

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

則(1.6.2)可以表示為

當(dāng)進(jìn)基變量xk的值由0增加到某一正值，其余非基變量均保持為0時(shí)，上式成為

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

即

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

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