chapter3對偶理論dualtheory-資料下載頁
2025-10-09 04:05本頁面
【導(dǎo)讀】限量及價值系數(shù)如下表：。建立總收益最大的數(shù)學(xué)模型。設(shè)x1，x2，x3分別為產(chǎn)品。A，B，C的產(chǎn)量，則線性規(guī)劃?，F(xiàn)在從另一個角度來考慮企業(yè)的決策問題。慮自己生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源標(biāo)價出售，問題：決策者。應(yīng)怎樣給定資源一個合理的價格？設(shè)y1，y2，y3及y4分別表示四種資源的單位增值價格(售價＝成本。和7個單位，利潤是100,企業(yè)出售這些數(shù)量的資源所得的利潤不。劃模型的對偶線性規(guī)劃模型,這一問題稱為對偶問題。線性規(guī)劃問題稱為原始線性規(guī)劃問題或原問題。價格不可能小于零，即有yi≥0(i=1,…數(shù)據(jù)參數(shù)，只是位置有所。不同，所描述的問題實際。源，以產(chǎn)品數(shù)量和單位產(chǎn)。格，實際上在構(gòu)成產(chǎn)品的。潤的貢獻(xiàn)也不同，它是企。業(yè)生產(chǎn)過程中一種隱含的。原問題的約束個數(shù)等于對偶變量的個數(shù)。原問題不等式約束符號為“≤”,對偶問題不等式約束符號為“≥”
【正文】 變量 xj的檢驗數(shù)的相反數(shù)對應(yīng)于 (DP)中第 j個松弛變量 的解 ， 第 i個松弛變量 的檢驗數(shù)的相反數(shù)對應(yīng)于第 i個對偶變量 yi的解 。 反之 ， (DP)的檢驗數(shù) (注意：不乘負(fù)號 )對應(yīng)于 (LP)的一組基本解 。 jSyiSx 對偶性質(zhì) Dual property 注： 應(yīng)用性質(zhì) 6 的前提是線性規(guī)劃為規(guī)范形式，而性質(zhì) 15則對所有形式線性規(guī)劃有效。 Chapter3 對偶理論 Dual Theory 【 例 】 線性規(guī)劃 1 2 31 2 3131 2 3m a x 6 22244, , 0z x x 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) 因為表 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ù) ， 即 ?????? ??0211B?????????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 已知檢驗數(shù) 檢驗數(shù)乘以－ 1 求得基本解 性質(zhì) 6 對偶性質(zhì) Dual property Chapter3 對偶理論 Dual Theory 作業(yè)：教材 P62 3 線性規(guī)劃的對偶模型 Dual model of LP 1. 如何寫規(guī)范與非規(guī)范問題的對偶問題 。 6個性質(zhì)都是原問題與對偶問題的有關(guān)解的對應(yīng)關(guān)系； 5和性質(zhì) 6可用來已知一個問題的最優(yōu)解求另一個問題的最優(yōu)解；
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1