用對偶單純形法求對偶問題的最優(yōu)解(編輯修改稿)
2024-08-20 22:35 本頁面
【文章內(nèi)容簡介】 ，直到找到最優(yōu)解為止.我們可以用另一種思路，使在單純形法每次迭代的基本解都滿足最優(yōu)檢驗，但不一定滿足非負約束，就得到了最優(yōu)解，這種算法就是對偶單純形法.因此，單純形法是從一個可行解通過迭代轉(zhuǎn)到另一個可行解，:第一，把所給的線性規(guī)劃問題轉(zhuǎn)化為標準型；第二，找出一個初始正則基，要求對應的單純形表中的全部檢驗數(shù) ，但“右邊”列中允許有負數(shù)；第三，若“右邊”列中各數(shù)均非負，則已是最優(yōu)基，于是，已求得最優(yōu)解，；第四，換基：“右邊”列中取值最小（即負的最多），則該列所對應的變量即為進基變量，換基后得新基，以出基變量的行和進基變量列交點處的元素為主元進行單純形迭代，再轉(zhuǎn)入第三步.下面用一個例子具體說明用對偶單純形法求線性規(guī)劃問題最優(yōu)解的步驟： 例1 求解線性規(guī)劃問題min 。添加松弛變量以后的標準型min 將每個等式兩邊乘以1，則上述問題轉(zhuǎn)化為min 。如果取作為初試基變量，有如下初試單純形表（表）表31右邊032210505120141551100由此可見，兩個基變量均取負值，所以，所確定的基本解不是基可行解，并通過例題來說明方法步驟.對偶單純形法的基本思想：是保證檢驗數(shù)行全部非正的條件下，逐步使得“右邊”“右邊”一列各數(shù)均滿足了非負條件（即可行性條件），則就獲得最優(yōu)解.現(xiàn)在，不是可行基（稱為正則基），為保證上述方法的實現(xiàn)，可按下面的方法確定出基變量和進基變量.出基變量的確定 可以取任意一個具有負值的基變量（一般可取最小的），兩個基變量都取負值，且最小，故 為出基變量.現(xiàn)在考慮出基變量所對應的負所有元素 ，對每個這樣的元素作比值 ，令 （）則 ，基變量 所在的行有三個取負值，其值分別為3，2，5，11.于是由此可知， ，對表21進行一次迭代便得表22，在表22的（1）中，基變量 所取之值 ，故 故 是進基變量；，主元為 .對（1）再作單純形變換，得表31之（2）.由于它的“右邊”已列出全部非負，： ， ；最優(yōu)值 .表31 右邊（1）
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1