【正文】 67 復習舉例 有兩個變量的線性規(guī)劃問題 ?????????????0,1m ax2121211xxxxaxxxz （ 1 ） 證明本題當且僅當1?a 時為可行。 64 解的判斷 唯一最優(yōu)解的判斷： 最優(yōu)表中所有非基變量的檢驗數(shù)小于零 ,則線 規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷 :最優(yōu)表中存在非基變量的檢驗數(shù)為零 ,則線則性規(guī)劃具有多重最優(yōu)解。 54 線性規(guī)劃求解的兩階段法 兩階段法的基本思路是： 第一階段 ，首先不考慮原問題是否存在基可行解 ， 先求解一個目標函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù) ( 一般取 1) ，在保持原問題約束條件不變的情況下求這個目標函數(shù)極小化時的解。如果在最終單純形表中還存在非零的人工變量，這表示無可行解。求出初始解： ??????????????01bBXXNB （ 2 ） 計算非基變量NX的檢驗數(shù)N? ， NBCC BNN 1???? ，若0?N?已得到最優(yōu)解，停止計算，若還存在Njj ?? ,0? ，轉入下一步。 34 唯一最優(yōu)解的判斷： 最優(yōu)表中所有非基變量的檢驗數(shù) 非零 ,則線規(guī)劃具有唯一最優(yōu)解 。目標函數(shù)中含有基變量 x4,由第二個約束得到 x4=6+x1－ x2，并代入目標函數(shù)消去 x4得 1 2 1 2 1 22 2 ( 6 ) 6Z x x x x x x? ? ? ? ? ? ? ?＝26 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 1↑ 0 0 0 x2 x4 x5 1 2 4 1 0 0 1 1 2 0 1 0 0 0 1 5 1 11 λj 2 0 1 0 0 表中 λj≥0,j=1,2,… ,5所以最優(yōu)解為 X=(0,5,0,1,11,)最優(yōu)值 Z=2x1－ 2x2－ x4=－ 2 5－ 1=－ 11 極小值問題 ,注意判斷標準 ,選進基變量時 ,應選 λj0的變量 xj進基。 檢驗數(shù) 目標函數(shù)用非基變量表達時的變量系數(shù) 16 進基列 出基行 bi /ai2， ai20 θi 表 14 (1) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 σ j 3 4 0 0 (2) x3 x2 σ j (3) x1 x2 σ j 基變量 1 10 0 0 1/3 0 1/3 10 5/3 1 1/3 40 5/3 0 4/3 30 1 0 3/5 1/5 18 0 1 1/5 2/5 4 0 0 1 1 將 3化為 1 乘以1/3后得到 30 18 17 最優(yōu)解 X=(18， 4， 0， 0)T，最優(yōu)值 Z=70 O 20 30 10 40 (3,4) X(3)=(18,4) 最優(yōu)解 X=(18,4) 最優(yōu)值 Z=70 402 21 ?? xx 21 ?? xx??????????????0,30340243m a x432142132121xxxxxxxxxxxxZX(1)=(0,0) 20 10 x2 x1 30 0,0402212121??????xxxxxxX(2)=(0,10) 18 單純形表 c j c 1 c 2 … c m c m +1 … c m + k … c n c B X B x 1 x 2 … x m x m +1 … x m + k … x n b θ i c 1 c 2 ? c m x 1 x 2 ? x m 1 0 ? 0 0 1 ? 0 … … … … 0 0 ? 1 a 1 , m +1 a 2 , m +1 ? a m , m +1 … … … a 1 , m + k a 2 , m + k ? a m , m + k … … ?… a 1n a 2n ? a mn b 1 b 2 ? b m θ 1 θ 2 ? θ m ????miijijj acc1? 0 0 … 0 σm +1 … σ m + k … σ n ???miii bcz1 單純形法全過程的計算 ， 可以用列表的方法計算更為簡潔 ， 這種表格稱為單純形表 。 10 (1)可行解區(qū)域要畫正確 (2)目標函數(shù)增加的方向不能畫錯 (3)目標函數(shù)的直線怎樣平行移動 11 線性規(guī)劃單純形解法的原理 ? 單純形方法的基本思想 從可行域中的一個基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如不是，尋找下一個基可行解，并且同時努力使目標函數(shù)得到改進，如此迭代下去，直到找到最優(yōu)解或判定問題無解為止。1 線性規(guī)劃的圖解法與單純形解法 ? 線性規(guī)劃問題的圖解法 ? 線性規(guī)劃單純形解法的原理 ? 線性規(guī)劃單純形解法的計算步驟 ? 單純形法計算的矩陣描述 ? 線性規(guī)劃單純形求解的大 M法 ? 線性規(guī)劃單純形求解的兩階段法 ? 線性規(guī)劃單純形求解可能的循環(huán)現(xiàn)象 2 線性規(guī)劃問題的圖解法 ? 圖解法，就是用作圖的方法求解線性規(guī)劃問題。 ? 單純形算法必須解決三個方面的問題： 1. 如何確定初始的基可行解？ 2. 如何進行解的最優(yōu)性判別？ 3. 如何尋找改進的基可行解？ 12 確定初始的基可行解 ? 標準型的線性規(guī)劃問題 ??????????0m a x1XbxPCXznjjj???????????????100000100001),( 21????? mPPP系數(shù)矩陣中存在一個單位陣 以單位陣為一初始可行基。 19 單純形算法的計算步驟 ① 將線性規(guī)劃問題化成標準型。 表 27 21m a x xxZ ???????????????0,42123212121xxxxxx【 例 】 求解線性規(guī)劃 【 解 】 化為標準型 21m a x xxZ ????????????????4,1,042123421321?jxxxxxxxj28 初始單純形表為 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 ?j － 1 1 0 0 λ2=10, x2進基 ， 而 a120， a220， 沒有比值 ， 從而線性規(guī)劃的最優(yōu)解無界 。 多重最優(yōu)解的判斷 :最優(yōu)表中存在非基變量的檢驗數(shù)為零 ,則線則性規(guī)劃具有多重最優(yōu)解。 （ 3 ） 根據(jù)? ? kjjj???