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