清华大学运筹学课件整数线性规划

《清华大学运筹学课件整数线性规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整数线性规划数学模型割平面法分枝定界法0-1变量的作用数学模型整数线性规划问题nmaxormincjxjj1ns.t.aijxjororbi,i1,2,,mj1x0,j1,2,,nj部分或所有变量是整数变量纯整数线性规划：所有变量是整数变量混合整数线性规划：同时包含整数和非整数变量0-1型整数线性规划：所有变量只能等于0或1例、有资金B，可以投资n个项目，投资额和收益分别为aj和cj，要考虑三个条件：1）若选择项目1就必须选择项目2；2）项目3和项目4至少选一个；3）项目5、6、7中选两个，如

2、何投资使总效益最大？变量：，x1投资项目j，，x0不投项目jjj条件1）x2x1条件2）x3x41条件3）x5x6x720-1型整数规划模型nmaxcjxj总投资效益j1ns.t.ajxjB投资总额约束j1xx条件1）21x3x41条件2）x5x6x72条件3）x0,1,1jnj整数线性规划的松弛问题去除整数规划的整数约束后的问题称为其松弛问题如前面的一般性整数规划问题的松弛问题为nmaxormincjxjj1ns.t.aijxjororbi,i1,2,

3、,mj1x0,j1,2,,nj一般情况，原问题的解并不一定是其松弛问题的最优解附近的整数解例:maxx4x12s.t.2x3x312x2x812x,x非负且取整数值121819x,277P94x4x12A1A2A7*1x1012345678P是松弛问题最优解，附近可行解是A1,A2，最优解是A*如果改变第二个不等式约束:maxx4x12s.t.2x3x3124x15x5112x1,x2非负且取整数值x21819,P9477x4x127A1A2Ax14x21

4、394*,017A*x101234567891011121314最优解变成A*，离松弛问题最优解更远！割平面法例:maxx14x2s.t.2x3x312x2x812x1,x2非负且取整数值x松弛问题最优2最优解1x1012345678可用一个约束割去松弛问题最优解，不改变可行集例:max3x1x2s.t.3x12x233x12x2x335x14x2105x14x2x4102x1x252x1x2x55x2x,x非负且取整数值1254目标函数增加3松弛问题可行集及2

5、139最优解如左图所示,177不满足整数约束0123x1最优解的表示式3x2xx312312135x14x2x410x1x3x57772xxx5125239xxx235x7772532231xxx43547773如果右边常数都是整数2139已经得到原问题最优解,177否则一定可以用直线分0123x割红点和所有可行黄点1取第一个等式约束（右边常数不是整数）1213xxx135777将所有系数变成一个整数和一个非负小数之和：11221360,0,177

6、7777上述等式可以写成612xxx001xx13535777612记()Xx35x则xX11()777T61213931()Xxx将最优解X,,0,,0代入357777776()X07612将整数规划的任何可行解代入()Xxx35777()0X约束()0X可割去当前最优解，保留所有原可行解新的优化问题为max3xx12s.t.323xx12541xx01225xx12x2()

7、0X()Xx115xx12,非负且取整数值4目标函数增加3新的松弛问题可行集及原松2弛可行集被切割部分见左图139,1771）原最优解被切割掉x2）所有可行解被保留01231max3xx12sts.t.3x12x233x12x2x335x14x2105x14x2x4102x1x252x1x2x55xx11x1x6125x1,x2非负且取整数值4目标函数增加3松弛问题可行集及2最优解如右图所示51,14仍不满足整数约束0123x13x12x2x33

8、最优解的表示式5x4xx101241552x1x2x55x24x44x64xx1161115xxx34622251374x5x4x64443xx116251,如果右边常数都是整数14已经得到原问题最优解0123x1取第三个等式约束（右边常