《管理运筹学》整数规划.ppt

三、找出能覆盖非最优阵中所有0元的最少直线集合 第6章 整数规划 * (1) 对没有 元的行打√号； 0 (2) 对打√号的行上所有 元所在的列打√号； 0 (3) 对打√号的列上所有 元所在的行打√号； 0 (4) 重复(2)、(3)步骤，直到找不出新的打√ 号的行、列为止； (5) 对没有打√号的行画横线，对所有打√号 的列画竖线，这就是能覆盖所有0元的最少 直线的集合。 三、用最少的直线数覆盖矩阵中的所有0元素 第3章 整数规划 * √ √ √ 四、增加矩阵中的0元素 在没有被直线覆盖的部分中找出最小元素。然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素。 若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。 第3章 整数规划 * √ √ √ √ √ √ 最优解 可令 bij=M-cij 。其中M是足够大的常数(如选（cij）中最大元素为M即可)，这时系数矩阵可变换为B=(bij) 第3章 整数规划 * 目标函数经变换后，即解 所得(bij)最小解即为原问题(cij)的最大解。 例3-8某航空公司是一家经营小型飞机、短途航线的运输企业。管理层准备拓展经营领域，面临的问题是：是采购更多的小型飞机来开辟一些新的短途航，还是开始通过为一些跨地区航线购买大型飞机来进军全国市场，或者两种方法同时进行，已知采购成本、年利润、最多购买的数量限制如下表。并且可用资金为1亿元，如何进行决策，能使年利润达到最大？ 第3章 整数规划 * 小飞机 大飞机 每个飞机年利润 100万元 500万元 每个飞机采购成本 500万元 5000万元 最多采购数量 2 无限制 x1 x2 第3章 整数规划 * 整数规划模型为： 例3-9 某速递公司的线路选择问题。公司提供快递服务，所有快件两天内都能送到。快件在晚上到达各收集中心，并于第二天早上装上送往该区域地区的几辆汽车。因为快递行业竞争激烈，为了减少平均送货时间，必须将各快件根据目的地的地理位置加以分类，并分装到不同的汽车上。假设每天有三辆汽车，汽车可行的路线有10条，如下表所示。表中的各列的数字表示送达的顺序，最后一行是各方案的汽车运行时间（小时），现假设有9个不同地点的快件需要送出，试求出总运行时间最短的方案。 第3章 整数规划 * 第3章 整数规划 * 地点 可行路线 1 2 3 4 5 6 7 8 9 10 A 1 1 1 B 2 1 2 2 2 C 3 3 3 3 D 2 1 1 E 2 2 3 F 1 2 G 3 1 2 3 H 1 3 1 I 3 4 2 时间 6 4 7 5 4 6 5 3 7 6 该问题可视为0-1规划问题。设 表示第i个方案是否被选择（0表示不选择，1表示选择） 第3章 整数规划 * * 第3章 整数规划 第3章 整数规划 第3章 整数规划 第3章 整数规划 第 3 章 Integer Programming I P 整 数 规 划 3.1 整数规划问题及其建模 3.2 分支定界法 3.3 割平面法 3.4 0-1型整数线性规划的解法 3.5 指派问题 3.6 整数规划应用 第3章 整数规划 * 整数规划：变量取整数的线性规划； 纯整数规划：所有变量都取整数的线性规划； 混合整数规划：部分变量取整数的线性规划； 0-1规划：所有变量都取0、1两个值的规划； 0-1混合规划：部分变量取0、1两个值的规划。 例3-1背包问题 * 线性规划最优解为: x1=0，x2=0，x3=2.5 而整数规划的最优解是 x1=1，x2=0，x3=2 max z= 17x1 +72x2 +35x3 s.t. 10x1 +42x2 +20x3 ≤50 x1, x2, x3 ≥0 x1, x2, x3为整数 例3-2厂址选择问题 在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，…，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。 设 * 整数规划模型为: 0-1规划 例3-3 考虑固定成本的最小生产费用问题 在最小成本问题中，设第j种设备的固定成本为 ，运行的变动成本为 ，则生产成本与设