原問題與對偶問題ppt課件(參考版)
2025-05-09 18:02本頁面
【正文】 * * * *1 3 42 2 3 2 0 ( 1 )x x x x? ? ? ?* * * *1 2 3 42 3 2 2 0 ( 2 )x x x x? ? ? ?**12 2 1 . 2 0 . 4 1 . 6 1yy? ? ? ? ?**122 2 . 4 0 . 2 2 . 6 2yy ? ? ? ? ?**342 3 2 0xx??**343 2 2 0xx??所以 x1*=x2*=0. 解：由于 y1* 0, y2* 0,由互補松弛性知 解得 x3*= x4*=4. 所以 (L)的最優(yōu)解為X*=(0,0,4,4)T 因為 代入 (1),(2)得 。 即： 如果 則 如果 則 ,0? ?iy 。 ???miii yb15. 互補松弛性 在線性規(guī)劃問題的最優(yōu)解中 , 如果對應(yīng)某一約束條件的對偶變量值為非零 , 則該約束條件取嚴格等式 。 ????? ? jnjjjnjj xcxc11imiiimii ybyb ??????11?是其對偶問題的可行解 ,且有 若原問題 (對偶問題 )具有無界解 , 則其對偶問題 (原問題 )無可行解 . 說明 逆命題不成立。 原問題 對偶問題 bYXC ?bYCX ?? ? ),1(? njx j ??),1(? miy i ??若 是原問題的可行解， imiijnjj ybxc ??11?????提示 ),1(? njx j ??),1(? miy i ??是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。 ? （ 5）若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界。 ? （ 3）若原問題可行，但其目標函數(shù)值無界，則對偶問題無可行解。 理論證明： 原問題與對偶問題解的關(guān)系 在下面的討論中 , 假定線性規(guī)劃原問題和對偶問題分別如下 原問題 對偶問題 ??????????????),1(0),1(..m a x11njxmibxatsxczjnjijijnjjj????????????????),1(0),1(..m i n11miynjcyatsybwimijiijmiii??1. 弱對偶性 是其對偶問題的可行解，則恒有 ),1( njx j ??),1( miy i ??若 是原問題的可行解， imiijnjj ybxc ?????11證明： jmiinjijjnjimiij xyaxya ? ?? ?? ?? ???1 11 1)(? ?? ?? ?? ???mijinjijimijnjji xyayxa1 11 1)(jnjj xc??1imii yb??1從弱對偶性可得到以下重要結(jié)論：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1