運籌學第一章14大m法和兩階段法-在線瀏覽
2025-07-13 15:18本頁面
【正文】 X ???0?k?039。 ? ? ?????????3/6,1/3m i n3/61/3222 xxx 進行基變換 （ 1） 選擇進基變量 —— 原則： 正檢驗數 （ 或最大正檢驗數 ） 所對應的變量進基 ， 目的是使目標函數得到改善 （ 較快增大 ） ； 進基變量對應的系數列稱為 主元列 。 主元行和主元列的交叉元素 稱為 主元素 。 例 ： 表格單純形法求解步驟 第一步：將 LP化為標準型， 并加以整理。 （這一步計算機可自動完成） 確定初始可行基，寫出初始基本可行解 第二步：最優(yōu)性檢驗 計算檢驗數，檢查： ?所有檢驗數是否 ≤ 0？ 是 —— 結束，寫出最優(yōu)解和目標函數最優(yōu)值； ?還有正檢驗數 —— 檢查相應系數列 ≤ 0？ 是 —— 結束，該 LP無“有限最優(yōu)解”！ ?不屬于上述兩種情況 ，轉入下一步 — 基變換。 第三步：基變換 確定進基變量和出基變量。 第四步 換基迭代（旋轉運算、樞運算 ) 完成一次迭代，得到新的基本可行解和相應的目標函數值 該迭代過程直至下列情況之一發(fā)生時停止 ? 檢驗數行全部變?yōu)榉钦担? （ 得到最優(yōu)解） 或 ?主元列 ≤ 0 （最優(yōu)解無界） 停止迭代的標志（停機準則） 依據：最優(yōu)性檢驗的兩個定理 最優(yōu)性判別定理；無“有限最優(yōu)解”判斷定理 五 、 各種類型線性規(guī)劃的處理 分類及處理原則： （ 1） 類型一：目標要求是 “ Max”， 約束條件是 “ ≤” 類型 —— 左邊加上非負松弛變量變成等式約束 （ 約束條件標準化 ） ， 將引入的松弛變量作為初始基變量 ， 則初始可行基是一個單位陣 ， 用原始單純形法求解 。 （ 3） 類型三：目標要求是 “ Max”， 約束條件是 “ ≥” 類型 —— 約束條件標準化 ， 左邊減去非負的剩余變量 ， 變成等式約束 ， 化為類型二 。 問題：加入的人工變量是否合理 ？ 如何處理 ？ 在 目標函數中 ， 給人工變量前面添上一個絕對值很大的負系數 M（ M0） ， 迭代過程中 ，只要基變量中還存在人工變量 ， 目標函數就不可能實現極大化 —— 懲罰 ！ ① 最優(yōu)表中 ， 基變量不包含人工變量 ， 則最優(yōu)解就是原線性規(guī)劃的最優(yōu)解 ， 不影響目標函數的取值； ② 最優(yōu)表中 ， 基變量中仍含有人工變量 ， 表明原線性規(guī)劃的約
環(huán)評公示相關推薦
鄂ICP備17016276號-1