第2章線性基本性質(zhì)

第二章線性規(guī)劃的基本性質(zhì)對(duì)于或整個(gè)運(yùn)籌學(xué)來說，線性規(guī)劃是最早形成、最為完善的一個(gè)分支。同時(shí)，它又是數(shù)學(xué)規(guī)§1

s.t.(x1,x2)T

Sx1x2的線性約束，我們可采用圖解法求其最優(yōu)解。算法1.1.1：圖解法 minzx1s.t.x1x2-x12x2x1,x2x1+O1.1.1ODEF是其可行域，O(0,0)，D(6,0)，E(4/3,14/3)，F(xiàn)(0,4)，紅線是目標(biāo)函數(shù)的x*(4/3,143)Tz*463。最優(yōu)解是可行域的極點(diǎn)。1.1.11．若將目標(biāo)函數(shù)改為x1x2，會(huì)發(fā)生什么情況？（無窮多個(gè)最優(yōu)解，但其中有極點(diǎn)minzcT其中矩 A(aij)

，向量

xb(b1,b2,,bm)T ，c(c1,c2,,cn)T

，jxx1x2xn)TRn是(LP)的決策變量。在(LP)Ar(A)=mA不含零向量列。則a0(j1,nSxRn|Axb,x0}為(LP)Axb稱為(LP)的主約束，x0是非負(fù)約束。j minzx1s.t.x1x2 maxzx1s.t.3x1x2-x12x2x2-s.t.3x13x1x2x39x1x12x2x410 存在有限個(gè)極點(diǎn)，設(shè)為x1,,xk，當(dāng)S無界時(shí)存在有限個(gè)極向，設(shè)為d1,dlx xxdj，其中0,i1,k10,j1,l

i j

cTxicTxijcTdj j1

1j1,l，有cTdj0。則由kcTxicTxi,x令cTxpmincTxi

cTxicTxicTxpicTxp,x cTxicTxijcTdj j （1）(LP)S的所有極向d1,dl，有cTdj0,j1,l根據(jù)定理2.1.1知和注1.2.1得知如下結(jié)論。 (LP)S的極點(diǎn)是一個(gè)幾何概念，有直觀性強(qiáng)的優(yōu)點(diǎn)，但是卻不便于計(jì)算。為此，我們需要研究它的代數(shù)含意。事實(shí)上，S的極點(diǎn)就是所謂的基本可行解。2.2.1ARmn，r(A)=mAmS的基，n顯然，S的基的個(gè)數(shù)是有限的，最多有Cmn AxbBxBNxNbxBB1NxNB1bxBB1bB1Nx

x0 B1bx0B N 02.2.2BS(2.2.2)S(或(LP))BB1b0S(或(LP))BBS(或(LP))n n 為求S關(guān)于基B的基本解，只需在方程Axb中，令關(guān)于B的所有非基變量為零，即AxxN聯(lián)立方程xN

2.2.3設(shè)(2.2.2)SBB1b0，則稱(2.2.2)是非退化的基本可行解，B為非退化的可行基，否則稱(2.2.2)為退化的基本可行解，BS的所有基本可行解都 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, Ax 若取B(a1,a3)，則求聯(lián)立方程xx0，得關(guān)于B的基本解x(8,0,14, 例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 0BaaaAxbBx02,4,0,0,0)T xx 2.2.1x0Sx0S的基本可行解的充要條件是，x0中正分量所對(duì)應(yīng)的系數(shù)列向量線 ,,aRm線性無關(guān) 因此km。于是，由r(A)=m知，存在A的列向量 ,,aRm，使ai,ai,,ai線性無關(guān)，因 Baa,aS2.2.2x0S 注2.2.3 設(shè)x0S，則x0是S的基本可行解的充要條件是x0是S的極點(diǎn)*證明x0Sx00

Ax0 jx0j

j1,,jk1,,

a1a2ak線性相關(guān)，因此存在不全為零的實(shí)數(shù)1,,kkjaj kj令y(1,,k,0,,0)TRn，x1x0y，x2x0 其中0y0x1x2x01x1x2。我們只需證明存在02對(duì)任意的，由(2.2.6)并利用(2.2.3)和(2.2.5)得，

Ax1Ax0jajjx1x0 j1,, x2x0 j1,, jk1,, jk1,,因此當(dāng)0x1x20x1x2S，即(2.2.7)a1,a2,,ak線性相 x1x2(0,1)x0x11x2

x1x2S

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

jjj

x1ab

j

xxj

j

(x1x2)a x1x2和(2.2.12)x1x2,j1,k不全為零，因此由(