《运筹学》整数规划.ppt
《《运筹学》整数规划.ppt》由会员分享,可在线阅读,更多相关《《运筹学》整数规划.ppt(63页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Chapter5 整数规划整数规划(Integer Programming)(Integer Programming)整数规划的特点及应用分支定界法分配问题与匈牙利法本章主要内容:本章主要内容:Page 2整数规划的特点及应用整数规划的特点及应用整数规划(简称:整数规划(简称:整数规划(简称:整数规划(简称:IPIP)要求一部分或全部决策变量取整数值的规划问题称为整要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件,由余下的目标函数和约束条件构数规划。不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问成的规划问题称为该整数规划问
2、题的松弛问题。若该松弛问题是一个线性规划,则称该整数规划为整数线性规划。题是一个线性规划,则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式:Page 3整数规划的特点及应用整数规划的特点及应用整数线性规划问题的种类:整数线性规划问题的种类:整数线性规划问题的种类:整数线性规划问题的种类:纯整数线性规划:指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划:决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划。0-1型整数线性规划:决策变量只能取值0或1的整数线性规划。Page 4整数规划的特点及应用整数规划的特点及应用整数规划的典型例子整数规划的典型例子整数
3、规划的典型例子整数规划的典型例子例5.1 工厂A1和A2生产某种物资。由于该种物资供不应求,故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij,见下表:B1B2B3B4年生产能力年生产能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工厂A3或A4开工后,每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4,才能使今后每年的总费用最少。Page 5整数规划的特点及应用整数规划的特点及应用
4、解:这是一个物资运输问题,特点是事先不能确定应该建解:这是一个物资运输问题,特点是事先不能确定应该建A3还是还是A4中哪一个,因而不知道新厂投产后的实际生产物资。中哪一个,因而不知道新厂投产后的实际生产物资。为此,引入为此,引入0-1变量:变量:再设xij为由Ai运往Bj的物资数量,单位为千吨;z表示总费用,单位万元。则该规划问题的数学模型可以表示为:Page 6整数规划的特点及应用整数规划的特点及应用混合整数规划问题Page 7整数规划的特点及应用整数规划的特点及应用例例5.2 现有资金总额为现有资金总额为B。可供选择的投资项目有。可供选择的投资项目有n个,项目个,项目j所需投资额和预期收益
5、分别为所需投资额和预期收益分别为aj和和cj(j1,2,.,n),此外由),此外由于种种原因,有三个附加条件:于种种原因,有三个附加条件:若选择项目若选择项目1,就必须同时选择项目,就必须同时选择项目2。反之不一定。反之不一定项目项目3和和4中至少选择一个;中至少选择一个;项目项目5,6,7中恰好选择中恰好选择2个。个。应该怎样选择投资项目,才能使总预期收益最大。应该怎样选择投资项目,才能使总预期收益最大。Page 8整数规划的特点及应用整数规划的特点及应用解:对每个投资项目都有被选择和不被选择两种可能,因此解:对每个投资项目都有被选择和不被选择两种可能,因此分别用分别用0和和1表示,令表示,
6、令xj表示第表示第j个项目的决策选择,记为:个项目的决策选择,记为:投资问题可以表示为:Page 9整数规划的特点及应用整数规划的特点及应用例例5.3 5.3 指派问题或分配问题。人事部门欲安排四人到四个不指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作,每个岗位一个人。经考核四人在不同岗位的成同岗位工作,每个岗位一个人。经考核四人在不同岗位的成绩(百分制)如表所示,如何安排他们的工作使总成绩最好。绩(百分制)如表所示,如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page 10整数规划的特点及应
7、用整数规划的特点及应用设 数学模型如下:要求每人做一项工作,约束条件为:Page 11整数规划的特点及应用整数规划的特点及应用每项工作只能安排一人,约束条件为:每项工作只能安排一人,约束条件为:变量约束:Page 12整数规划的特点及应用整数规划的特点及应用整数规划问题解的特征:整数规划问题解的特征:整数规划问题解的特征:整数规划问题解的特征:整数规划问题的可行解集合是它松弛问题可行解集合的一个子集,任意两个可行解的凸组合不一定满足整数约束条件,因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解(反之不一定),但其最优解的目标函数值不会优于后者最优解的目标函数值。Page 1
8、3整数规划的特点及应用整数规划的特点及应用例例5.3 设整数规划问题如下设整数规划问题如下首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。Page 14整数规划的特点及应用整数规划的特点及应用用图解法求出最优解为:用图解法求出最优解为:x13/2,x2=10/3,且有,且有Z=29/6现求整数解(最优解):如用舍入取整法可得到4个点即(1,3),(2,3),(1,4),(2,4)。显然,它们都不可能是整数规划的最优解。x1x233(3/2,10/3)按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集,如右图所示。其中(2,2),(
9、3,1)点的目标函数值最大,即为Z=4。Page 15整数规划的特点及应用整数规划的特点及应用整数规划问题的求解方法:整数规划问题的求解方法:分支定界法和割平面法 匈牙利法(指派问题)Page 16分支定界法分支定界法1)求整数规划的松弛问题最优解;)求整数规划的松弛问题最优解;若松弛问题的最优解满足整数要求,得到整数规划的最优解若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转下否则转下一步;一步;2)分支与定界:)分支与定界:任意选一个非整数解的变量任意选一个非整数解的变量xi,在松弛问题中加上约束:,在松弛问题中加上约束:xixi 和和 xixi+1组成两个新的松弛问题,称为分
10、枝。新的松弛问题具有特征:当原问题组成两个新的松弛问题,称为分枝。新的松弛问题具有特征:当原问题是求最大值时,目标值是分枝问题的上界;当原问题是求最小值时,目是求最大值时,目标值是分枝问题的上界;当原问题是求最小值时,目标值是分枝问题的下界。标值是分枝问题的下界。检查所有分枝的解及目标函数值,若某分枝的解是整数并且目标函数检查所有分枝的解及目标函数值,若某分枝的解是整数并且目标函数值大于(值大于(max)等于其它分枝的目标值,则将其它分枝剪去不再计算,若)等于其它分枝的目标值,则将其它分枝剪去不再计算,若还存在非整数解并且目标值大于还存在非整数解并且目标值大于(max)整数解的目标值,需要继续
11、分枝,整数解的目标值,需要继续分枝,再检查,直到得到最优解。再检查,直到得到最优解。分支定界法的解题步骤:分支定界法的解题步骤:Page 17分支定界法分支定界法例例5.4 用分枝定界法求解整数规划问题用分枝定界法求解整数规划问题解:首先去掉整数约束,变成一般线性规划问题(原整数规划问题的松驰问题)LPIPPage 18分支定界法分支定界法用图解法求松弛问题的最优解,如图所示。用图解法求松弛问题的最优解,如图所示。x1x23(18/11,40/11)21123x118/11,x2=40/11Z=218/11(19.8)即Z 也是IP最小值的下限。对于x118/111.64,取值x1 1,x1
12、2对于x2=40/11 3.64,取值x2 3,x2 4先将(LP)划分为(LP1)和(LP2),取x1 1,x1 2Page 19分支定界法分支定界法分支:分支:分别求出(LP1)和(LP2)的最优解。Page 20分支定界法分支定界法先求先求LP1,如图所示。此时在如图所示。此时在B点取得最优解。点取得最优解。x11,x2=3,Z(1)16找到整数解,问题已探明,此找到整数解,问题已探明,此枝停止计算。枝停止计算。x1x233(18/11,40/11)11BAC同理求LP2,如图所示。在C 点取得最优解。即:x12,x2=10/3,Z(2)56/318.7 Z(2)Z(1)16 原问题有比
13、16更小的最优解,但 x2 不是整数,故继续分支。Page 21分支定界法分支定界法在在IP2中分别再加入条件:中分别再加入条件:x23,x24 得下式两支:得下式两支:分别求出LP21和LP22的最优解Page 22分支定界法分支定界法x1x233(18/11,40/11)11BACD先求LP21,如图所示。此时D 在点取得最优解。即 x112/52.4,x2=3,Z(21)-87/5-17.4 Z(211)如对LP212继续分解,其最小值也不会低于15.5,问题探明,剪枝。Page 25分支定界法分支定界法原整数规划问题的最原整数规划问题的最优解为优解为:x1=2,x2=3,Z*=17以上
14、的求解过程可以以上的求解过程可以用一个树形图表示如用一个树形图表示如右:右:LP1x1=1,x2=3Z(1)16LPx1=18/11,x2=40/11Z(0)19.8LP2x1=2,x2=10/3Z(2)18.5LP21x1=12/5,x2=3Z(21)17.4LP22无可行解LP211x1=2,x2=3Z(211)17LP212x1=3,x2=5/2Z(212)15.5x11x12x23x24x12x13Page 26分支定界法分支定界法例例5.5 用分枝定界法求解用分枝定界法求解解:先求对应的松弛问题(记为LP0)用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所示。Pa
15、ge 27分支定界法分支定界法1010松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABCPage 28分支定界法分支定界法10 x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5Page 29分支定界法分支定界法10 x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336Page 30分支定界法分支定界法10 x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212Page 31分支定界法分支定界法上述分枝
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 整数 规划
限制150内