第八章--整数规划.pptVIP

第八章 整数规划 整数规划问题 线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。 例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(Integer Programming)。 全部决策变量的取值都为整数，则称为全整数规划(All IP)； 仅要求部分决策变量的取值为整数，则称为混合整数规划(Mixed IP)； 要求决策变量只能取0或1值，则称为0-1规划(0-1 rogramming)。 整数规划问题 为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。 “舍入化整”一般是不可行的： 化整后的解有可能成为非可行解； 虽是可行解，却不是最优解。 例如 整数规划问题 解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2取整数 不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。 不考虑整数约束的最优解：x1 *=28/9=3.111， x2 * =25/9=2.778，Z * =293/9=32.556 舍入化整 x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 ≤35，非可行解； x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解； x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。 第一节、 整数规划的图解法 第一节、 整数规划的图解法 步骤： 在线性规划的可行域内列出所有决策变量可能取的整数值， 求出这些变量所有可行的整数解， 比较它们相应的目标函数值，最优的目标函数值所对应的解就是整数规划的最优解。 实用性： 只有两个决策变量， 可行的整数解较少。 第一节、 整数规划的图解法 例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 第一节、 整数规划的图解法 得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值。 第二节、 整数规划的计算机求解 例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x1,x2,x3 ≥ 0 为整数 例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x3 ≤1 x1,x2,x3 ≥ 0 x1，x3 为整数 x3 为 0-1变量 第三节、整数规划的应用 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 第三节、整数规划的应用 第三节、整数规划的应用 第三节、整数规划的应用 例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 第三节、整数规划的应用 第三节、整数规划的应用 第三节、整