運(yùn)籌學(xué)02對偶理論1線性規(guī)劃的對偶模型,對偶性質(zhì)-資料下載頁
2025-05-12 15:05本頁面
【正文】 xx x xxxx x x? ? ?? ? ?????????(1) 用單純形法求最優(yōu)解； (2) 寫出每步迭代對應(yīng)對偶問題的基本解； (3) 從最優(yōu)表中寫出對偶問題的最優(yōu)解； (4) 用公式 Y=CBB1求對偶問題的最優(yōu)解 。 【 解 】 (1) 加入松弛變量 x x5后 ， 單純形迭代 如表 35所示 。 對偶性質(zhì) Dual property Chapter3 對偶理論 Dual Theory XB x1 x2 x3 x4 x5 b 表 （ 1） x4 x5 [2] 1 － 1 0 2 4 1 0 0 1 2→ 4 σj 6↑ － 2 1 0 0 表 （ 2） x1 x5 1 0 － 1/2 [1/2] 1 3 1/2 － 1/2 0 1 1 3→ σj 0 1↑ － 5 － 3 0 表 （ 3） x1 x2 1 0 0 1 4 6 0 － 1 1 2 4 6 σj 0 0 － 11 － 2 － 2 表 35 對偶性質(zhì) Dual property 最優(yōu)解 X=(4， 6， 0)T， 最優(yōu)值 Z=6 4－ 2 6=12； Chapter3 對偶理論 Dual Theory (2) 設(shè)對偶變量為 y y2, 松弛變量為 y y y5 , Y=(y y y y y5)， 由性質(zhì) 6得到對偶問題的基本解 (y y y y y5) =(－ σ4,－ σ5,－ σ1,－ σ2,－ σ3)， 即 表 2－ 5(1)中 σ=(6， － 2， 1， 0， 0)， 則 Y(1)=(0， 0， 6， 2， － 1) 表 2－ 5(2)中 σ=(0， 1， － 5， － 3， 0)， 則 Y(2)=(3， 0， 0， － 1， 5) 表 3－ 5(3)中 σ=(0， 0， － 11， － 2， － 2)， 則 Y（ 3） =(2， 2， 0， 0， 11) 對偶性質(zhì) Dual property Chapter3 對偶理論 Dual Theory (3) 因?yàn)楸?3－ 2(3)為最優(yōu)解 ， 故 Y（ 3） =(2， 2， 0， 0，11)為對偶問題最優(yōu)解； CB=(6， － 2)， 因而 (4) 表 3－ 2(3)中的最優(yōu)基 B1 為表 3－ 2(3)中 x4， x 5兩列的系數(shù) ， 即 2110B???? ?????????????21101B)2,2(2110)2,6(),(121?????????????BCyyYB 對偶性質(zhì) Dual property Chapter3 對偶理論 Dual Theory 根據(jù)對偶性質(zhì)；可將原問題與對偶問題解的對應(yīng)關(guān)系列表如下： 表 3－ 6 一個問題 max 另一個問題 min 有最優(yōu)解 有最優(yōu)解 性質(zhì) 4 無 無最優(yōu)解 無最優(yōu)解 性質(zhì) 4 最 優(yōu) 無界解 (有可行解 ) 無可行解 性質(zhì) 2 解 無可行解 無界解 (有可行解 ) 應(yīng)用 已知最優(yōu)解 通過解方程 求最優(yōu)解 性質(zhì) 5 已知檢驗(yàn)數(shù) 檢驗(yàn)數(shù)乘以－ 1 求得基本解 性質(zhì) 6 對偶性質(zhì) Dual property Chapter3 對偶理論 Dual Theory 作業(yè)：教材 P80 (1) 線性規(guī)劃的對偶模型 Dual model of LP 1. 如何寫規(guī)范與非規(guī)范問題的對偶問題 。 6個性質(zhì)都是原問題與對偶問題的有關(guān)解的對應(yīng)關(guān)系； 5和性質(zhì) 6可用來已知一個問題的最優(yōu)解求另一個問題的最優(yōu)解； Chapter3 對偶理論 Dual Theory 互補(bǔ)松弛定理的解釋： 若原問題 (LP)最優(yōu)解 X*中第 j個變量 Xj*為正 ,則對偶問題(DP)與之對應(yīng)的第 j個約束在最優(yōu)情況下呈嚴(yán)格等式（ 即松弛變量為 0） ； 若對偶問題 (DP)中第 j個約束在最優(yōu)情況下呈嚴(yán)格不等式 ， 則原問題 (LP)最優(yōu)解 X*中第 j個變量 Xj*必為 0。 對偶性質(zhì) Dual property
試題試卷相關(guān)推薦
鄂ICP備17016276號-1