運籌學(xué)課件第1章線性規(guī)劃與單純形法-第2節(jié)-在線瀏覽
2024-12-03 13:00本頁面
【正文】 k個點 。 ? 使 X=μ1X(1)+μ2X(2)+…+μkX(k) ? 則稱 X為 X(1)， X(2)， … ， X(k)的凸組合 。 ? 圖中 0， Q1,2,3,4都是頂點。 設(shè) 是 D內(nèi)的任意兩點； X(1)≠X (2)。 由此可見 X ∈ D ， D 是凸集。 引理 1 線性規(guī)劃問題的可行解 X=(x1,x2,… ， xn)T為基可行解的充要條件是 X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。 (2) 充分性若向量 P 1 ， P 2 ，?， P k 線性獨立， 則必有 k ≤ m ；當 k=m 時，它們恰構(gòu)成一個基，從而 X=(x 1 ,x 2 , ? ,x k ,0 ? 0) 為相應(yīng)的基可行解。 定理 2 線性規(guī)劃問題的基可行解 X對應(yīng)于可行 D的頂點。 故 ???mjjj bxP1現(xiàn)在分兩步來討論 ， 分別用反證法 。 這樣得到 (x1μα 1)P1+(x2μα 2)P2+…+(xmμα m)Pm=b (x1+μα 1)P1+(x2+μα 2)P2+…+(xm+μα m)Pm=b 現(xiàn)取 X(1)=［ (x1μα 1),(x2μα 2),…,(xmμα m),0,…， 0］ X(2)=［ (x1+μα 1),(x2+μα 2),…,(xm+μα m),0,…， 0］ 由 X(1),X(2)可以得到 X=（ 1/2） X(1)+（ 1/2） X(2)， 即 X是 X(1)， X(2)連線的中點 另一方面，當 μ 充分小時，可保證 ? xi177。 ? 這證明了 X 不是可行域 D 的頂點。 當 j＞ m時 ， 有 xj=xj(1)=xj(2)=0， 由于X(1)， X(2)是可行域的兩點 。 即 X不是基可行解 。 ? 本引理證明從略 ， 用以下例子說明這引理 。因 X′ 是 X(1)、 X(3)連線上一點，故可用 X(1)、 X(3)線性組合表示為 ? X′= α X(1)+(1α )X(3) 0＜ α ＜ 1 ? 又因 X是 X′ 與 X(2)連線上的一個點 ， 故 ? X=λ X′+(1 λ )X(2) 0＜ λ ＜ 1 ? 將 X′ 的表達式代入上式得到 ? X=λ ［ α X(1)+(1α )X(3)］ +(
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1