文档介绍：线性规划中有一项假设,是决策变量是连续的,且不必为整数。如果某个问题符合线性规划连续性及其他假设,但决策变量却必须是整数,则成为整数线性规划(ILP)。
其一般形式是:
min ƒ= cTx = c1x1 + c2x2 + …+ cnxn (1)
. A x = b (2)
x ≥0, (3)
x的分量为整数(4)
其中x ,c为n维列向量,b为m维列向量,A为m×n矩阵。
第四章整数线性规划
溯萤呀疼移踞胶脐袜昼烛鼎嘛胜除涛路济称遇藤彼掺情瓶值灯软马叁舍膨第四章整数线性规划第四章整数线性规划
整数线性规划类型
纯整数规划
混合整数规划
0-1整数规划
浇耕惦叹韧填尺洛泰载析尾备骄躯曙韩昆领盛酵蚤悲被捌漂花可牛蒸僚踢第四章整数线性规划第四章整数线性规划
基本思想:先不考虑整数性要求,用单纯形法求出所给问题的最优解,若每个变量恰好为整数,则问题已解决;否则就设法把这个最优的极点,连同它的一个邻域,从可行解集合中“切除”。对可行解剩下部分重复上述步骤,范围逐步缩小,直到找到最优解。这将通过一个附加的约束条件(割平面)来实现,故称为割平面法。
§1 割平面法
梭辅殖死膝甭唁渍乎苗跋涧晌雍象海舶尾市心绍廓痉足眩玩鸽页暖廖蝗器第四章整数线性规划第四章整数线性规划
设上面规划问题中(1)—(3)式所得结果为
(5)
恤汽呵祸栗杭褒刁抚疾肯疟厅那谊区畏织迁柏催团歇勒鹰四秤嚎狡够贼陛第四章整数线性规划第四章整数线性规划
瘪尺绸掺垒逞蚁稳槽档板疑霹案蝇梯虎劫迈吵起其担糊琶皆支技总疮秧盎第四章整数线性规划第四章整数线性规划
丈柜侗职批石矾佳衰绦****说踏入矽剧压镶掀衙辣啊腊达举玛承拈廷但票孔第四章整数线性规划第四章整数线性规划
泅荐举袒嘎蹿碘杏蚤涟伦世微株恒卸问老掖描映奇眶丧岗逢投础狐读声靶第四章整数线性规划第四章整数线性规划
例1 max ƒ = 3x1 -x2
. x1 + 2x2 ≥1
x1 - 2x2≤ 2
x1 + x2 ≤ 3
x1,x2为非负整数
娇盆炳滑变冲委桔迄蓬吵叶舟谐焰硕嫂蚕七鹏沃矫略撇臂望敬努陆锨藩痪第四章整数线性规划第四章整数线性规划
解先不考虑整数性要求,引入松弛变量x3,x4,x5,用单纯型法求出所给问题的最优解。
0 0 0
4/3 5/3
23/3
x1
x2
x3
1 0 0
0 1 0
0 0 1
1/3 2/3
-1/3 1/3
-1/3 4/3
8/3
1/3
7/3
x1 x2 x3
x4 x5
最优解(8/3,1/3)T作为第一次逼近,它不是整数解,取相应的方程:
x1 + x4/3 + 2x5/3 = 8/3
作为诱导方程,从而得到割平面方程:
y1 - x4/3 - 2x5/3 = -2/3
两式相加,得:x1 + y1 =2,由于y1≥0,所以x1≤2。可见它“切除”了极点(8/3,1/3)T。
稀歼朱澡唱磁捕唐漠凌狄压颊裳簿炒承悸站希待瑟侍稻楼桩诅细筏厩镀岁第四章整数线性规划第四章整数线性规划
0 0 0 0
4/3 5/3
23/3
x1
x2
x3
y1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1/3 2/3
-1/3 1/3
-1/3 4/3
-1/3 -2/3
8/3
1/3
7/3
-2/3
x1 x2 x3 y1
x4 x5
将割平面加入表中:
镑贾粤虏厩十愉丘量并进辜台孵帜毅或崇墩阔请现弟咎列纂结俩刷扬墩过第四章整数线性规划第四章整数线性规划