运筹学 整数规划

《运筹学 整数规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学OperationsResearchChapter3整数规划IntegerProgramming姜海副教授博导清华大学工业工程系3.1整数规划数学模型MathematicalModelofIPCh3整数规划3.1整数规划的数学模型IntegerProgrammingMathematicalModelofIP2012年1月30日星期一一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划很多实际规划问题都属于整数规划问题1.变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员

2、的合理安排问题，当变量x=1表示安排第i人去做j工作，x=0表示ijij不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。分类：纯整数规划：要求全部变量取整数值混合整数规划：要求一部分变量取整数值的整数线性规划：要求模型是线性的本章只讨论整数线性规划。Page3Ch3整数规划3.1整数规划的数学模型IntegerProgrammingMathematicalModelofIP2012年1月30日星期一【例】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问两种物品各装多少件，所装物品的总价值最大？重量体积价值

3、物品（公斤/每件）（m3/每件）(元/每件)甲1.20.0024乙0.80.00253【解】设甲、乙两种物品各装x、x件，则数学模型为：12maxZ4x3x121.2x10.8x2102x12.5x225x,x0,且均取整数12Page4Ch3整数规划3.1整数规划的数学模型IntegerProgrammingMathematicalModelofIP2012年1月30日星期一如果删除原问题中x、x取整数的约束，我们得到原问题的12松弛问题，该问题是一个线性规划问题，其可行域如图所示Page5Ch3整数规划3.1整数规划的数学模型IntegerProgramming

4、MathematicalModelofIP2012年1月30日星期一用图解法求得点B为最优解：X＝(3.57，7.14)，Z＝35.7由于xx必须取整数值，尝试用凑整法来求解1，2•（4，7）不可行•（4，8）不可行•（3，8）不可行•（3，7）是可行解目标函数Z=33（3，7）是最优解么？Page6Ch3整数规划3.1整数规划的数学模型IntegerProgrammingMathematicalModelofIP2012年1月30日星期一实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。但点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题

5、的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。Page7Ch3整数规划3.1整数规划的数学模型IntegerProgrammingMathematicalModelofIP2012年1月30日星期一【例】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问两种物品各装多少件，所装物品的总价值最大？重量体积价值物品（公斤/每件）（m3/每件）(元/每件)甲1.20.0024乙0.80.00253在上例中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立数学模型，

6、使所装物品价值最大。Page8Ch3整数规划3.1整数规划的数学模型IntegerProgrammingMathematicalModelofIP2012年1月30日星期一【解】此问题可以建立两个整数规划模型，也可引入0-1变量yi，令1,采用第i种方式装载时yii1,20，不采用第i种方式装载时i=1,2分别是采用背包及旅行箱装载。maxZ4x3x121.2x0.8x10y＋12y12122x12.5x225y120y2yy112x0,且取整数,y0或1i1,2iiPage9Ch3整数规划3.1整数规划的数学模型IntegerProgram

7、mingMathematicalModelofIP2012年1月30日星期一另一个等效的模型maxZ4x3x4x3x12341.2x0.8x10y1212xxy2.5251211.2x0.8x12y3422x2.5x20y342yy112x0,且取整数,y01或i1,2iiPage10Ch3整数规划3.1整数规划的数学模型IntegerProgrammingMath