用對偶單純形法求對偶問題的最優(yōu)解-wenkub
2022-08-21 22:35:22 本頁面
【正文】 （）則 ，基變量 所在的行有三個取負值，其值分別為3，2，5，11.于是由此可知， ，對表21進行一次迭代便得表22，在表22的（1）中，基變量 所取之值 ，故 故 是進基變量；，主元為 .對（1）再作單純形變換，得表31之（2）.由于它的“右邊”已列出全部非負，： ， ；最優(yōu)值 .表31 右邊（1） 0 0 0 （2）0 1 1 0 0 0 然而在有些問題中，我們很容易找到初始基本解，因此使用對偶單純形法求解線性規(guī)劃問題是有一定條件的，其條件是：(1) 單純形表的b列中至少有一個負數(shù).(2) 單純形表中的基本解都滿足最優(yōu)性檢驗.對偶單純形法與原始單純形法相比有兩個顯著的優(yōu)點：(1) 初始解可以是不可行解，當檢驗數(shù)都非正時，即可進行基的變換，這時不需要引入人工變量，因此簡化了計算.(2) 對于變量個數(shù)多于約束方程個數(shù)的線性規(guī)劃問題，、約束較多的線性規(guī)劃問題，可以先將其轉(zhuǎn)化為對偶問題，然后用對偶單純形法求解.對變量多于約束條件的線性規(guī)劃問題，而約束條件很多的線性規(guī)劃問題，可先將此問題轉(zhuǎn)化為對偶問題，要求初始單純形表檢驗數(shù)行的檢驗數(shù)必須全部非正，若不能滿足這一條件，對大多數(shù)線性規(guī)劃問題來說，很難找到一個初始可行基，因此這種方法在求解線性規(guī)劃問題時，很少單獨應用.參考文獻：[1] 吳祈宗．運籌學學習指導及習題集[M] ．北京：機械工業(yè)出版社，2006．[2] 孫君曼，馮巧玲，孫慧君，等．線性規(guī)劃中原問題與對偶問題轉(zhuǎn)化方法探討[J]．鄭州:工業(yè)學院學報（自然科學版），2001，16(2):44~46．[3] 何堅勇．運籌學基礎．北京：清華大學出版社，2000．[4] 周漢良，范玉妹. 數(shù)學規(guī)劃及其應用．北京：冶金工業(yè)出版社．[5] 陳寶林．最優(yōu)化理論與算法(第二版) ．北京：清華大學出版社，2005．[6]
黨政相關相關推薦
鄂ICP備17016276號-1