运筹学第2章-线性整数.pptx

第二章 线性规划;一、线性整数规划问题与模型; 【例14】 投资项目选择问题 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资和预期收益分别为aj和cj。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中 至少选择一个；第三，项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？; 【例15】运动员选拔问题;运动员;【例16】 固定费用问题; 【例17】垃圾处理问题 某地区有甲乙两个城镇，它们每周分别生产700t和1200 t固体废物，现拟用三种方式（焚烧、填海、掩埋）分别在1、2、3三个场地对这些废物进行处理，每个处理厂的处理费用可以分为固定费用和可变费用两个部分，连同处理厂的处理能力和运费情况分别见下表，试求使两个城镇处理固体废物总费用最小的方案。;; 【例18】厂址选择问题 某地区有m座煤矿，i号矿每年产量为ai，现有火力发电厂一个，每年需用煤b0，每年运行的固定费用（包括折旧费，不包括运费）为h0元。现在规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两个发电厂用。现有几个备用的厂址，若在第j号备选厂址建电厂，每年运行的固定费用为hj，每吨原煤从i号矿运到j号备选厂址的运费为cij，每吨原煤从i号矿运送到原有电厂的运费为ci0，试问，应当把新厂厂址选在何处，m座煤矿开采的原煤应如何分配给两个电厂，才能使每年的总费用（电厂的运行固定费用与原煤运费之和）最小。; 一个徒步旅行者要在背包中选择一些最有价值的物品携带，他最多能携带115kg的物品。现共有5件物品，分别重54kg、35kg、57kg、46kg、19kg， 其价值依次为7、5、9、6、3。问该旅行者携带那些物品，使总价值最大?;2、线性整数规划的一般形式;整数规划一般可以分为三类： （1）纯整数规划：全部决策变量都限定取整数； （2）混合整数规划：部分决策变量为整数，规划中变量一部分取整数，其余部分是连续变量； （3）0-1规划，不仅限定决策变量取整数，而且只允许取0和1两个值。;3、线性整数规划问题解的特点;【例20】;最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 整数可行解远多余于顶点，枚举法不可取;二、线性整数规划的分枝定界法;【例21】;对原问题增加两个约束条件;对B1问题增加两个约束条件;对B2问题增加两个约束条件;问题B Z0=356 X1=4.81 X2=1.82;分枝定界法求解问题的步骤： 将要求解的整数规划问题称为问题A，将其松弛问 题称为问题B，若 （1）B没有可行解，这时A也没有可行解，停止； （2）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解； （3）B有最优解，但不符合A的整数条件，记它目标函数值为最优值上界，观察一下界值。;　第一步：分枝，在Ｂ中选择一个不符合整数条件的变量xj，其值为bj，［bj］表示小于bj的最大整数，构造两个约束条件。;　定界，以每个后继问题为一分枝标明求解结果，与其他问题解的结果中，找出目标函数最大者作为新的上界，从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界，若无作用，下界仍为零。;三、计 算 软 件;;