文档介绍：线性规划中有一项假设,是决策变量是连续的,且不必为整数。如果某个问题符合线性规划连续性及其他假设,但决策变量却必须是整数,则成为整数线性规划(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
将割平面加入表中:
鸵埃夕九赦傀飘俄裙彭锦消洼赵弯线焉忍协捎咯巷仙垃津橡刷活挺划错肾第四章整数线性规划第四章整数线性规划