【正文】 集。 定理二 線性規(guī)劃問題的基本可行解 X 對應線性規(guī)劃 問題可行域（凸集）的頂點。 定理三 若線性規(guī)劃問題有最優(yōu)解，一定存在一個基 可行解是最優(yōu)解。 從上述三個定理可以看出，要求線性規(guī)劃問題的最優(yōu)解，只要比較可行域（凸集）各個頂點對應的目標函數(shù)值即可，最大的就是我們所要求的最優(yōu)解。 定理 1： 若 LP模型存在可行解，則可行域為凸集。 證明： 設 max z=CX st. AX=b X?0 并設其可行域為 C，若 X X2為其可行解， 且 X1≠X2 ， 則 X1?C， X2 ?C， 即 AX1=b， AX2=b， X1?0， X2?0， 又 X為 X X2連線上一點，即 X=?X1+(1?)X2， (0?1)， AX=?AX1+ (1?)AX2 = ?b+ (1?)b =b , (0?1)，且 X ?0， ∴ X ?C， ∴ C為凸集。 三個基本定理： 引理： 線性規(guī)劃問題的可行解 X=(x1, x2,,xn)T 為基本可行解的充要條件是 X的正分量所對應的系數(shù)列向量線性獨立。 證： （ 1）必要性： X基本可行解 ?X的正分量所對應的系數(shù)列向量線性獨立 可設 X=(x1,x2,,xk,0,0,,0)T，若 X為基本可行解， 顯然，由基本可行解 定義可知 x1, x2,,xk所對應 的系數(shù)列向量 P1,P2,,Pk應該線性獨立。 （ 2）充分性： X的正分量所對應的系數(shù)列向量線性獨立 ? X為基本可行解 若 A的秩為 m，則 X的正分量的個數(shù) k?m； 當 k=m時，則 x1,x2,,xk的系數(shù)列向量 P1,P2,,Pk恰好構成基， ∴ X為基本可行解。 當 km時，則必定可再找出 mk個列向量與 P1,P2,,Pk一起構成基， ∴ X為基本可行解。 證：等價于 X非基本可行解 ?X非凸集頂點 （ 1）必要性 ： X非基本可行解 ? X非凸集頂點 不失一般性，設 X=(x1,x2,,xm,0,0,,0)T，為非基本可行解， ∵ X為可行解， ∴ ?pjxj=b， j=1 n 即 ? pjxj=b (1) j=1 m 又 X是非基本可行解， ∴ P1,P2,,Pm線性相關，即有 ?1P1+?2P2++?mPm=0， 其中 ?1， ?2， ， ?m不全為 0，兩端同乘 ?≠ 0，得 ??1P1+??2P2++??mPm=0， （ 2） 定理 2： 線性規(guī)劃模型的基本可行解對應其可行域的頂點。 由 (1)+(2)得 (x1+ ??1)P1+ (x2+ ??2)P2++ (xm+ ??m)Pm=b 由 (1)(2)得 (x1 ??1)P1+ (x2 ??2)P2++ (xm ??m)Pm=b 令 X1=(x1+ ??1， x2+ ??2， ， xm+ ??m， 0， ， 0)T X2=(x1 ??1， x2 ??2， ， xm ??m ， 0， ， 0)T 取 ?充分小 ,使得 xj? ??j?0， 則 X X2均為可行解， 但 X=+()X2， ∴ X是 X X2連線上的點， ∴ X非凸集頂點。 （ 2）充分性： X非凸集頂點 ? X非基本可行解 設 X=(x1,x2,,xr,0,0,,0)T為 非凸集頂點，則必存在 Y、 Z兩點，使得 X=?Y+(1?)Z， (0?1)，且 Y、 Z為可行解 或者 xj=?yj+(1?)zj (0?1)，（ j=1,2,,n)， yj?0， zj?0 ∵ ?0, 1?0 ，當 xj=0， 必有 yj=zj=0 ∴ ? pjyj = j=1 n ? pjyj=b (1) j=1 r ? pjzj = j=1 n ? pjzj=b (2) j=1 r ? (yjzj)pj=0 j=1 r ,(1)(2),得 即 (y1 z1)P1+ (y2 z2)P2++ (yr zr)Pr=0 ∵ Y、 Z為不同兩點， ∴ yjzj不全為 0， ∴ P1,P2,,Pr線性相關， ∴ X非基本可行解。 z1=CX1=CX0C?=zmaxC? ， z2=CX2=CX0+C? =zmax+C? ∵ z0 = zmax ? z1 ， z0 = zmax ? z2 ， ∴ z1 = z2 = z0 ，即 X1 、 X2也為最優(yōu)解， 若 X X2仍不是頂點，可如此遞推，直至找出一個頂點為最優(yōu)解。 從而，必然會找到一個 基本可行解 為最優(yōu)解。 定理 3： 若線性規(guī)劃模型有最優(yōu)解，則一定存在一個基本可行解為最優(yōu)解 。 證： 設 X0=(x10, x20,,xn0)T 是線性規(guī)劃模型的一個最優(yōu)解， z0=zmax=CX0 若 X0非基本可行解，即非頂點，只要取 ?充分小， 則必能找出 X1= X0??0 ， X2 = X0 +??0 ，即 X1 、 X2為可行解， 單純形法的計算步驟： 初始基本可行解 新的基本可行解 最優(yōu)否？ STOP Y N 二、確定初始基可行解 線性規(guī)劃問題的最優(yōu)解一定會在基可行解中取得，我們先找到一個初始基可行解。然后設法轉換到另一個基可行解，直到找到最優(yōu)解為止。 設給定線性規(guī)劃問題： ??????????????），（），（njxmibxaxczjinjjijnjjj??1 01 m a x11因此約束方程組的系數(shù)矩陣為： ??????????????100010001212222111211??????????????mnmmnnaaaaaaaaa由于該矩陣含有一個單位子矩陣，因此，用這個單位陣做基，就可以求出一個基可行解： ? ? TmbbX ,0,0 1 ???其標準形為： ??????????????????），（），（njxmibxxaxxczjisinjjijmisinjjj??1 01 0m a x111三、從初始基可行解轉換為 另一個基可行解 對初始可行解的系數(shù)矩陣進行初等行變換，構造出一個新的單位矩陣，其各列所對應的變量即為一組新的基變量，求出其數(shù)值，就是一個新的基可行解。 從一個基本可行解向另一個基本可行解轉換 不失一般性，設基本可行解 X0=(x10, x20,,xm0,0,,0)T ， 前 m個分量為正值，秩為 m，其系數(shù)矩陣為 P1 P2 …… P m Pm+1 …… P j…… P n b 1 0 …… 0 a 1,m+1 a1j a 1n b1 0 1 …… 0 a 2,m+1 a2j a 2n b2 0 0 …… 1 a m,m+1 amj a mn bm …… …… …… …… …… …… …… ∴ ? pjxj0 = j=1 n ? pixi0=b (1) i=1 m 又 P1 P2 …… P m為一個基，任意一個非基向量 Pj可以以該組向量線性組合表示，即 Pj = a1j P1 + a2j P2 ++ amj Pm ，即 Pj =? aij pi ， 移項，兩端同乘 ?0 ，有 ?(Pj? aij pi )=0 (2) i=1 m i=1 m (1)+(2)： ?(xi 0 ?aij)Pi + ? Pj =b， 取 ?充分小，使所有 xi 0 ?aij ?0，從而 i=1 m X1 = (x1 0 ?a1j ,x2 0 ?a2j ,,xm 0 ?amj ,0,,?,183