第二講（1）線性規(guī)劃及其對偶(文件)
【正文】 性規(guī)劃有下述幾種可能： 1．不存在可行解或無解，例如規(guī)劃 x1=－１ x1≥ 0 無可行解 3 x1=min Operations Research Prof. Wang School of Economics amp。 Management page 24 17 August 2022 第二講 167。 Management page 25 17 August 2022 第二講 167。 2 線性規(guī)劃解的求解方法之一：圖解法 （ 2） 圖 12中 ， 陰影部分為可行域 ， 若要求出最優(yōu)點 ， 必須作出目標 函數(shù)的等值線 ， 然后令等值線向最小值方向 （ 即最優(yōu)方向 ） 移 動 ， 直到離開可行域的瞬間為止 ， 此時的交點即為最優(yōu)點 。 很 幸運 ， 該法已經(jīng)找到 ， 這就是以后將要介紹的單純形法 。 Operations Research Prof. Wang School of Economics amp。 同理 ， 設(shè) Y是對偶問題任一可行解 ， 則 ， 故 是對偶問題最優(yōu)解 。 Management page 30 17 August 2022 第二講 167。 Management page 32 17 August 2022 第二講 167。 于是得出 ， 或 xj=0；或 xj0， 必使 。 亦即 ， 在若干個問題的可行解 X中 ， 若是有一組解所對應(yīng) 的對偶可行解 ， 使得 Xj0所對應(yīng)的對偶約束條件為等式 ， 則 此時的解必為最優(yōu)解 。 例如 ， 令 x1=x4=0， 則得： m a x16 ( 15 ) 1392y( 14 ) 26y4( 13 ) 56( 12 ) 15 2212 12121??????????yyyyyyy????????????32x 166046x323232xxxx＝Operations Research Prof. Wang School of Economics amp。 即令 將 y1,y2值代入式 (12)及式 (15)， 看是否滿足 。 Management page 36 17 August 2022 第二講 167。 以后將重點闡述有實用價值的單純形法 。 最壞情況 ， 本例需 次才能找到 。此時目標函數(shù)值 CTX=YTb=16。 3 對偶性質(zhì)及平衡定理 （ 9） 故此時 X=(0,2,3,0)T是原問題可行解 。 Management page 34 17 August 2022 第二講 167。 Management page 33 17 August 2022 第二講 167。 故每一項都 ≥ 0。 Management page 31 17 August 2022 第二講 167。 Management page 29 17 August 2022 第二講 167。 3 對偶性質(zhì)及平衡定理 （ 2） 2． 強對偶性 （ 對偶最優(yōu)性 ） 若 分別是原問題與對偶問題可行解 ， 且 ， 則 必分別是原問題及對偶問題的最優(yōu)解 。 Management page 27 17 August 2022 第二講 167。 圖解法簡單易行 ， 但只適于兩維問題 （ 本題雖是三維 ， 但很容 易變?yōu)閮删S ） 。 Operations Research Prof. Wang School of Economics amp。例 如 規(guī)劃 x1+x2=1 x1， x2≥ o x1+ x2=min 顯然 兩點連線上的所有點 都是最優(yōu)解，（見圖 11） 4． 一般情況有無窮多可行解，但有唯一最優(yōu)解。 1 初步分析線性規(guī)劃解的幾種可能性 （ 2） 2．存在可行解，但找不到最優(yōu)解，例如規(guī)劃 x1－ x2=0 x1， x2≥0 － 2 x1=min 顯然，令 x1=x2=λ,λ為任意非負值都是可行解， 當(dāng) λ→+∞ ，則目標函數(shù)－ 2 x1→∞ ，故找不出使目標函數(shù) 取極小值的具體解 X。 Management page 22 17 August 2022 第二講 167。 Management page 21 17 August 2022 第二講 第二講（ 2） 用對偶分析原問題最優(yōu)解 167。 5 線性規(guī)劃的標準型及其轉(zhuǎn)換 （ 3） 2．若出現(xiàn) xj不限，即－ ∞xi∞,(j?J2) 則令 xj=uj－ vj (j?J2),uj≥0， vj≥0 這樣，便使所有約束變?yōu)榈仁?，且自變量全大于或等?0。 Management page 19 17 August 2022 第二講 167。 2 321313 121321?????????????xxxxxxxxxm a x10540,0y3y 2 321y 321213 121321???????????????yyyyyyyyyOperations Research Prof. Wang School of Economics amp。 3 線性規(guī)劃的規(guī)范型 （ 4） 按照前面定義，知： I={1,2,3}， J={1,2,3}， I1={1,2}， I2={3}， J1={1,3}， J2={2} 于是相應(yīng)的對偶形式為： m in39。 3 線性規(guī)劃的規(guī)范型 （ 3）
物理相關(guān)推薦
鄂ICP備17016276號-1