運(yùn)籌學(xué)課件ch3整數(shù)規(guī)劃(編輯修改稿)
2025-06-15 19:56 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 xLP1:X=(3,),Z1= 10 10 x1 x2 o A C LP1 3 4 可行域是一條線段即，,40,464:434m a x121121212121??????????????????xxxxxxxxxxLPxxZ：及，到線性規(guī)劃及進(jìn)行分枝，增加約束，選擇由于545431113LPLPxxLPZZ???6 ① ② ????????????????0,65:534m ax2121212121xxxxxxxxLPxxZ，LP4:X=(4,6),Z4=34 LP5:X=(5,5),Z5=35 5 LP1:X=(3,),Z1= LP3 LP5 盡管 LP1的解中 x1不為整數(shù)，但 Z5Z因此 LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。 上述分枝過(guò)程可用下圖表示 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 無(wú)可行解 x2≥7 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 24 2020年 6月 16日星期二 設(shè)純整數(shù)規(guī)劃 njxbxaxcZ jinjjijnjjj ,10ma x11????? ????且為整數(shù)， 松弛問(wèn)題 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行為源行（來(lái)源行）的割平面，或分?jǐn)?shù)切割式，或 (高莫雷 )約束方程。 將 Gomory約束加入到松弛問(wèn)題的最優(yōu)表中，用對(duì)偶單純形法計(jì)算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部為整數(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同理，對(duì)于 x2行有： 324313312 ???? xxs 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 28 2020年 6月 16日星期二 【 例 】 用割平面法求解下列 IP問(wèn)題 ????????????且為整數(shù)0,102304634m a x21212121xxxxxxxxZ【 解 】 放寬變量約束，對(duì)應(yīng)的松弛問(wèn)題是 ????????????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。 最優(yōu)解 X(0)＝ (5/2， 15/4),不是 IP的最優(yōu)解。選擇表 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中，用對(duì)偶單純形法計(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(1)就是 IP的最優(yōu)解。如果不是整數(shù)解，需要繼續(xù)切割，重復(fù)上述計(jì)算過(guò)程。 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming 表 3－ 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1