第六讲 整数规划.pptVIP

第 六 讲 整 数 规 划 主要内容 整数规划问题的提出 分枝定界法 0-1规划的解 第六讲 整数规划 §6.1 整数规划问题的提出 　　例6-1　某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，　　已知生产单位产品所需的A、B两种原材料的消耗，如右表所示。该工厂每生产一件产品Ⅰ可获利40元，每生产一件产品Ⅱ可获利90元，问应如何安排计划使该工厂获利最多 第六讲 整数规划 §6.1 整数规划问题的提出 一、定义 整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。 根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。 例6.4　投资问题 　某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%， 但要求第一年投资最低金额为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元； 项目 C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额， 使到第五年末拥有的资金本利总额为最大? 解：1) 设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额； 设yiA， yiB，是0—1变量，并规定取 1 时分别表示第 i 年给A、B投资， 否则取 0（ i = 1, 2, 3, 4, 5）。 设yiC 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4； 第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2； 第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0； 这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C=20000y2C D x1D x2D x3D x4D x5D 2）约束条件： 第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000； 第二年：A的投资第二年末才可收回，故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D = 1.06x1D； 第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D； 第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D = 1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D = 1.15x3A+ 1.06x4D。 关于项目A的投资额规定: x1A ≥ 40000y1A ，x1A ≤ 200000y1A ，200000是足 够大的数；保证当 y1A = 0时， x1A = 0 ；当y1A = 1时，x1A ≥ 40000 。 关于项目B的投资额规定: x3B ≥ 30000y3B ，x3B ≤ 50000y3B ； 保证当 y3B = 0时， x3B = 0 ；当y3B = 1时，50000 ≥ x3B ≥ 30000 。 关于项目C的投资额规定: x2C = 20000y2C ，y2C = 0，1，2，3，4。 第八章 整数规划 §8.1 整数规划问题的提出 三、整数规划问题的特征： 可视作是线性规划问题的特殊情况，即变量取值范围是离散的，但经典连续数学中的理论和方法一般无法直接用来求解整数规划问题：最优解不能由去掉整数限制的线性规划问题的最优解取整而得。　 §2　整数规划的分枝定界法 多中选一的约束 例如：模型希望在下列n个约束中，只能有一个约束有效， fi(x) ? 0 i=1,2,….n, 引入 n个0-1变量yi i=1,2,…n则上式可改写为： fi(x) ? M(1-yi) y1+ y2 + … + yn=1 如果希望有k个约束有效 则：fi(x) ? M(1-yi), y1+ y2 +