[經管營銷]1-3單純形法第2部分-wenkub.com
2024-10-16 03:14 本頁面
【正文】 對于主元列的 0元素或負元素是否也要計算比值 ？ （ 此時 解的可行性自然滿足 ， 不必計算 ；如果 主元列元素全部為 0元素或負元素 ，則 最小比值失效 ， 線性規(guī)劃 無 “ 有限最優(yōu)解 ” ） 出現(xiàn)若干個相同的最小比值怎么辦 ？ （ 說明 出現(xiàn)了退化的基本可行解 ， 即非 0分量的個數(shù)小于約束方程的個數(shù) 。 ② 在大 M法中，當人工變量出基后能否 立即劃去 該人工變量所在的系數(shù)列？ 兩階段法舉例 例 :求解線性規(guī)劃問題 解： 對標準化后的問題，增加人工變量，并構造第一階段的目標： 51 2 3 51 2 4 51 2 3 4 543m a x0 0 0 3. . 2 0 2, , , , 0Zxx x x xs t x x x xx x xxxxx??? ? ? ? ? ? ? ???? ? ? ? ? ? ??? ??約束系數(shù)矩陣 1 0 0 1 01 2 1 0 1?????????A1212112m in 222. . 3,0Z x xxxs t xxx??? ? ?????? ??1 2 322Z x x x? ? ? ? ? CB XB Cj b xj 0 0 0 0 1 x1 x2 x3 x4 x5 ?j 0 1 X4 X5 3 2 1 0 0 1 0 1 2 1 0 1 1 Z 2 1 2 1 0 0 0 2 X4 X2 3 1 1 0 0 1 0 1/2 1 1/2 0 1/2 Z 0 0 0 0 0 1 第二階段 ：劃去人工變量所在的列，得到原問題的初始基本可行解和約束條件的等價變形。 1 1 2 21 1 1 1 2 2 1 11 1 1 1 2 2 1 21 1 1 1 2 2 112m a x.., , , 0nnnnnnn n mnZ c x c x c xa x a x a x ba x a x a x bsta x a x a x bx x x? ? ?? ? ? ???? ? ? ?????? ? ? ?????121 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 21212 1m in.., , , , , 0nnnnmmn n nmnmnnnmn n mnmnWa x a x a x ba x a x a x bsta x a xx x xxxxxa x bxx x x? ? ???????? ? ? ? ???? ? ? ? ?????? ? ??????????原問題 輔助線性規(guī)劃 求解結果 ① W最優(yōu)值 =0—— 即所有人工變量取值全為 0（ 為什么 ？ ） ， 均為非基變量 ， 最優(yōu)解是原線性規(guī)劃的一個基本可行解 ， 轉入第二階段； ② W最優(yōu)值 =0—— 但人工變量中有等于 0的基變量 ， 構成退化的基本可行解 ， 可以 轉化為情況 ① ； 如何轉化 ？ 選一個不是人工變量的非基變量進基 ， 把在基中的人工變量替換出來 ③ W最優(yōu)值 0—— 至少有一個人工變量取值0,說明 基變量中至少有 1個人工變量 ,表明 原問題沒有可行解 ,討論結束 。1 2 3 4 5141 2 3 51 2 3 4 5m a x 2 0 0322.., , , , 0Z x x x x M xxxx x x xstx x x x x? ? ? ? ? ? ? ?????? ? ? ? ? ??? ??39。 1 1 2 21 1 1 1 2 2 1 11 1 1 1 2 2 1 211212121 1 1 2 2 112,m a x.., , , 0 , 0,n n n mnnnnnnnn n mnnnmn n n mZ c x c x c xa x a x a x ba x a x a x bsta x a x a x bxM x M x M xxxxxx xx x? ? ????? ? ?? ? ?? ? ? ? ???? ? ? ?
教學課件相關推薦
鄂ICP備17016276號-1