第二章線性規(guī)劃的基本性質(zhì)對于最優(yōu)化或整個運籌學(xué)來說，線性規(guī)劃是最早形成、最為完善的一個分支。同時，它又是數(shù)學(xué)規(guī)劃通、農(nóng)業(yè)種植和軍事運籌等許多方面?！?

s.t.(x1,x2)T

Sx1x2的線性約束，我們可采用圖解法求其最優(yōu)解。算法1.1.1：圖解法 minzx1s.t.x1x2-x12x2x1,x2x1+1.1.1ODEF是其可行域，O(0,0)，D(6,0)，E(4/3,14/3)，F(xiàn)(0,4)，紅線是目標函數(shù)的等x*(43,143)Tz*463。最優(yōu)解是可行域的極點。 1．若將目標函數(shù)改為x1x2，會發(fā)生什么情況？（無窮多個最優(yōu)解，但其中有極點若去掉第一個約束，會發(fā)生什么情況？（不存在最優(yōu)解，最優(yōu)值為若將第二個約束改為x1+2x28，會發(fā)生什么情況？（不存在可行解可行域非空，但不存在最優(yōu)解，最優(yōu)值為。這時，可行域一 S種情況之一。若猜想正確，那么對于存在最優(yōu)解的含極點線性規(guī)劃問題，我們只需在其可行域的所有極點中尋找使目標函數(shù)值最小的點，而不需要在整個可行域中尋找。這樣，則大大減小了最優(yōu)解的搜索區(qū)域。。minzcTs.t.Axx

AaijRmn，向量bb1b2bm)TRm，c(c1c2cn)TRn，x(x1x2xn)TRnpj)AjxjA的系數(shù)列向量，則aj0(j1,n。集合SxRn|Axb,x0}為(LP)Axb稱為(LP)x0是非負約束。 考慮例minzx1s.t.x1x2

maxzx1s.t.3x1x2-x12x2x2-

x4、無可行解分別對應(yīng)于其標準形式有最優(yōu)解、、無可行解。因此，以下我們只需研究具有標準形 在有限個極點，設(shè)為x1,,xk，當(dāng)S 時存在有限個極向，設(shè)為d1,,dl。xS當(dāng)且僅當(dāng)xxdj，其中0,i1,,k,1,0,j1,,

i j

cTxicTxijcTd

j1j1,l，有cTdj0。則由kcTx icTxi,x令cTxpmincTxi cTxicTxicTxpicTxp,x

2：存在q，使cTdq0q0q，則由 ijcTxcTxicTdjij j 設(shè)(LP)的可行域S非空，（1）(LP)S的所有極向d1,dl，有cTdj0,j1,l2.1.11.2.1 n顯然，S的基的個數(shù)是有限的，最多有Cmn AxbBxBNxNbxBB1NxNB1bxBB1bB1Nx

x0 x0B N 定義2.2.2 是S(或(LP))關(guān)于B的基本可行解，這時B稱為S(或(LP))的可行基。n 由S的基的個數(shù)的有限性知，S的基本可行解的個數(shù)也是有限的，最多有Cm個n 為求S關(guān)于基B的基本解，只需在方程Axb中，令關(guān)于B的所有非基變量為零，即求聯(lián)AxxN方程xN

定義2.2.3設(shè)(2.2.2)是S關(guān)于B的基本可行解。若B1b0，則稱(2.2.2)是非的基本可行解，B為非的可行基，否則稱(2.2.2)為的基本可行解，B為的可行基。若S的所有基本可行解都是非退 minzx1s.t.x1x2 則

0 6 A ，b，c 1 8 0 0BaaI

Ax x1x2 Ax 若取B(a1,a2)，則求聯(lián)立方程xx0，得關(guān)于B的基本解x(4/3,14/3,0,0)，是 Ax Ba1a3，則求聯(lián)立方程xx0Bx8,0,14,0) 例2.2.2考慮線性規(guī)劃問題則

maxz3x1s.t.x1x2-x1+2x262x1x28x1,x20minz3x1s.t.x1x2 -x12x2 x4 2x1x2 x5=8x1,x2,x3,x4,x50

A 0，b6，c0 1 8 0 0若取B(a,a,a)，則求聯(lián)立方程Axb，得關(guān)于B的基本解x0(2,4,0,0,0)T， xx 本可行解，B是的可行基2.2.1x0Sx0Sx0中正分量所對應(yīng)的系數(shù)列向量線性 ,,aRm線性無關(guān)， 此km。于是，由r(A)=m知，存在A的列向量 ,, Rm，使ai,ai,,ai線性無關(guān)，因 Bai1ai2,aikS2.2.2x0SB的基本可行解。注2.2.3在定理2.2.1的充分性證明中，若k<m，則x0是的基本可行解，并且它可能是關(guān)于多個 設(shè)x0S，則x0是S的基本可行解的充要條件是x0是S的極點*證明x0Sx00

Ax0 jx0j

j1,,jk1,,

a1a2ak線性相關(guān)，因此存在不全為零的實數(shù)1,,kkj令

ja

y(1,,k,0,,0)TRn，x1x0y，x2x0 其中0y0x1x2x01x1x2。我們只需證明存在02x1,x2這樣由極點的定義知x0不是S的極點，與條件 對任意的，由(2.2.6)并利用(2.2.3)和(2.2.5)得，

Ax2b。再由(2.2.4)

Ax1Ax0 jajj，x1x0 j1,,，

x2x0jj j1,, jk1,,

jk1,,j因此當(dāng)0x1x20x1x2S，即(2.2.7)a1,a2,,ak線性相 。下面證明(2.2.8)x0Sx1x1x1x1TSx2x2x2x2TS x1x2(0,1)x0x11x2x1x2S

x0x1(1)x2，j1,2,, Ax1b，Ax2 x10，x20，j1,2,, jk1,n時，由(2.2.9)并利用(2.2.4)、(2.2.11)及(0,1) x1x20，jk1,, 再由(2.2.10)知x1abx

jj

jj

k (x1x2)a j x