運(yùn)籌學(xué)課件ch3整數(shù)規(guī)劃-在線瀏覽
2025-07-20 19:56本頁面
【正文】 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 17 2020年 6月 16日星期二 分枝定界法的步驟： 1. 求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 2. 若松弛問題的最優(yōu)解滿足整數(shù)要求 ， 得到整數(shù)規(guī)劃的最優(yōu)解 ， 否則轉(zhuǎn)下一步； xi， 在松弛問題中加上約束xi≤[xi]及 xi≥[xi]+1組成兩個(gè)新的松弛問題 ， 稱為分枝 。 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 18 2020年 6月 16日星期二 【 例 】 用分枝定界法求解例 【 解 】 先求對應(yīng)的松弛問題（記為 LP0）： ????????????0,:034m a x21212121xxxxxxLPxxZ用圖解法得到最優(yōu)解 X＝ （ ,） ,Z0=,如下圖所示 。 上述分枝過程可用下圖表示 LP0:X=(,),Z0= LP1:X=(3,) Z1= LP2:X=(4,) Z2= x1≤3 x1≥4 LP3:X=(,6) Z3= x2≤6 LP4:X=(4,6) Z4=34 LP5:X=(5,5) Z5=35 x1≤4 x1≥5 無可行解 x2≥7 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 24 2020年 6月 16日星期二 設(shè)純整數(shù)規(guī)劃 njxbxaxcZ jinjjijnjjj ,10ma x11????? ????且為整數(shù)， 松弛問題 njxbxaxcZ jinjjijnjjj ,10ma x11????? ????，的最優(yōu)解 TmT bbbbBbbBX ),()0,( 2111 ??? ??＝設(shè) xi不為整數(shù)， 為非基變量kkkikii xxabx ??? 求解 IP的割平面法 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 25 2020年 6月 16日星期二 將 分離成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和： iki ab及? ? 10,10,][ ???????? ikiikikikiii fffaafbb則有 kkikkkijiii xfxafbx ?? ???? ][][kkikikkijii xffxabx ?? ???? ][][等式兩邊都為整數(shù)并且有 1??? ? ikkiki fxff 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 26 2020年 6月 16日星期二 加入松弛變量 si得 ikkiki fxfs ??? ?此式稱為以 xi行為源行（來源行）的割平面，或分?jǐn)?shù)切割式，或 (高莫雷 )約束方程。 0?? ? kkiki xff則 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 27 2020年 6月 16日星期二 ?????????324313322354613651xxxxxx例如， 324653651 1)1( ?????? xxxx1行： 移項(xiàng)： 4653653241 1 xxxx ?????令 046536532 ??? xx加入松弛變量 s1得 324653651 ???? xxs同理，對于 x2行有： 324313312 ???? xxs 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 28 2020年 6月 16日星期二 【 例 】 用割平面法求解下列 IP問題 ????????????且為整數(shù)0,102304634m a x21212121xxxxxxxxZ【 解 】 放寬變量約束，對應(yīng)的松弛問題是 ????????????0,102304634m a x21212121xxxxxxxxZ 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 29 2020年 6月 16日星期二 加入松弛變量 x3及 x4后，用單純形法求解，得到最優(yōu)表 33。選擇表 33的第一行 (也可以選第二行 )為源行 252141431 ??? xxx 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Cj 4 3 0 0 b CB XB x1 x2 x3 x4 4 3 x1 x2 1 0 0 1 1/4 － 1/8 － 1/2 3/4 5/2 15/4 λj 0 0 － 5/8 － 1/4 表 33 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 30 2020年 6月 16日星期二 分離系數(shù)后改寫成 212)211(41431 ?????? xxx02141212 4341 ?????? xxxx加入松弛變量 x5得到高莫雷約束方程 22 543 ????? xxx將式 ()作為約束條件添加到表 3－ 3中，用對偶單純形法計(jì)算，如表 3－ 4所示 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 31 2020年 6月 16日星期二 Cj 4 3 0 0 0 b CB XB x1 x2 x3 x4 x5 4 3 0 x1 x2 x5 1 0 0 0 1 0 1/4 － 1/8 － 1 － 1/2 3/4 [－ 2] 0 0 1 5/2 15/4 － 2→ λj 0 0 － 5/8 － 1/4↑ 0 4 3 0 x1 x2 x4 1 0 0 0 1 0 1/2 － 1/2 1/2 0 0 1 － 1/4 3/8 － 1/2 3 3 1 λj 0 0 － 1/2 0 － 1/8 最優(yōu)解 X(1)＝ (3， 3)，最優(yōu)值 Z＝ 21。如果不是整數(shù)解，需要繼續(xù)切割，重復(fù)上述計(jì)算過程。 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 32 2020年 6月 16日星期二 作業(yè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1