對偶單純性法(編輯修改稿)
2025-09-01 19:47 本頁面
【文章內容簡介】 利用單純形方法求解線性規(guī)劃時，若得到最優(yōu)解，同時可得對偶問題的最優(yōu)解。反之亦然。 求解線性規(guī)劃時，寫出其對偶規(guī)劃，可以從一對對偶問題中選一個較簡單進行求解。 例如， 給定線性規(guī)劃約束條件都是小于等于的不等式約束，通過添加松弛變量，系數矩陣中可得一單位子陣，利用單純形方法求解即可。 給定線性規(guī)劃約束條件都是大于等于的不等式約束，目標函數中系數為正。通過添加剩余變量，系數矩陣中可得一負單位子陣，方程組兩邊同乘以－ 1，利用對偶單純形方法求解。 給定線性規(guī)劃約束條件是混合的，通過添加剩余變量、松弛變量以及最少的人工變量，用大 M法或兩階段法進行求解。 ??????????????????01 2 m i n54325431543ixxxxxxxxxxxxf例：求解線性規(guī)劃 解：顯然（ P1， P2）是一對偶可行基，應用對偶單純形方法，代入單純形表： 0 0 1 1 1 0 0 x1 x2 1 0 0 1 [1] 1 1 1 1 1 2 1 檢驗數 0 0 1 1 1 迭代，得： 0 0 1 1 1 1 0 x3 x2 1 1 0 1 1 0 1 2 1 2 2 3 檢驗數 1 0 0 2 0 最優(yōu)解為（ 0， 3， 2， 0， 0） T，最優(yōu)值為 2。 該問題的對偶問題為 ?????????????????????111002m a x2121212121uuuuuuuuuu解。于是可求得對偶變量的可得設為對應目標函數中的系數對偶可行基，中的單位子陣，即初始可找對偶問題的解，
職業(yè)教育相關推薦
鄂ICP備17016276號-1