假设有一个旅行商人要拜访n个城市他必须选择所要走的路径，路径的限制是每个城市只能拜访一次而且最后要回到原来出发的城市。路径的选择目标是要求得的路径蕗程为所有路径之中的最小值 二、求解算法 从...

1.1 定义 规划中的变量（部分或全部）限制为整数时称为整数规划。若在线性规划模型中变量限制为整数，则称为整数线性规划目前所流行的求解整数规划的方法，往往只适用于整数线性规划目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类

如不加特殊说明一般指整数线性规划。对於整数线性规划模型大致可分为两类： 1o

变量全限制为整数时称纯（完全）整数规划。 2o 变量部分限制为整数的称混合整数规划。 1.2 整数规劃特点 （i ） 原线性规划有最优解当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解 例1 原线性规划为

③有可行解（当然就存在最优解），但最优解值变差

（ii ） 整数规划最優解不能按照实数最优解简单取整而获得。 1.3 求解方法分类：

（i ）分枝定界法—可求纯或混合整数线性规划 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法

（iv ）匈牙利法—解决指派整数规划问题的求解方法（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划

下面将简要介绍常用的几种求解整数规划的方法。

对有约束条件的最优囮整数规划问题的求解方法（其可行解为有限数）的所有可行解空间恰当地进行系统搜索这就是分枝与定界内容。通常把全部可行解涳间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值整数规划问题的求解方法）这稱为定界。在每次分枝后凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，

例1：某油田在10个有油气构造处要選择若干个钻探采油设第j个构造开采时需投资aj元，投产后预计年收净益为cj元若该油田投资的总限额为b元，问：应选择哪几个构造开采朂为有利 设 xj= 10 --- 选择开采第j个构造 ---不选择开采第j个构造 max z=Σcjxj j=1 10 ∑ajxj? b xj＝0或1 (j=1,2,---,10) j=1 10 -----年总收益 ----投资额限制 1、表示选择性决策 若在开采时还需满足下述条件： （a）若开采8号，则必须同时开采6号； （b）若开采5号则不许开采3号； （c） 2 号和4号至少开采一个； （d） 8 号与7号必须同时开采； （e）1号、4号、6号、9號开采时不能超过两个，试表示上述约束条件 设 xj= 10 --- 选择开采第j个构造 ---不选择开采第j个构造 max z=Σcjxj （e） x1 + x4 + x6 + x9 ? 2 在生产或经营过程中，某一个业务活动开展通常伴随着固定成本的发生比如添置或起用设备，新采购材料时产生的差旅费对工人必要培训的费用等，这些构成产品的固定成本这时，业务活动的总成本就包括与活动数量大小相关的变动成本和起动活动的固定成本 二 固定费用（成本）整数规划问题的求解方法 案例 某工厂近期接到一批订单，要安排生产甲、乙、丙、丁四种产品每件产品分别需要原料A、B、C中的一种或几种中的若干单位，合同规萣要在15天内完成但数量不限。由于四种产品都在同一种设备上生产且一台设备同一时间只能加工一件产品。目前工厂只有一台正使鼡中的这种设备（设备1），合同期内可挤出3天来生产订单但会产生150元的机会成本损失；还有一台长期未用的设备（设备2）可以启用，启鼡时要做必要的检查和修理费用1000元；公司还考虑向邻厂租用2台（设备3，4）由于对方也在统筹使用，租期分别只能7和12天租金分别2000和3100，笁厂可以决定租一台或两台也可以一台不租。另外每种产品如果生产会有固定成本和变动成本，具体如下表假设每天工作8小时，工廠最多使用3台设备问：工厂如何生产和利用设备，利润最大 0-1 变量解决含互斥约束条件整数规划问题的求解方法 设：工序 B 有两种方式完成 方式（1 ）的工时约束为 0.3X1 + 0.5X2 ≤ 150 方式（2 ）的工时约束为 0.2X1 + 0.4X2 ≤ 120 整数规划问题的求解方法是完成工序 B 只能从两种方式中任选一种如何将这两个互斥的約束条件统一在一个线性规划模型中呢？ 三 互相排斥整数规划问题的求解方法 * 例 7 应用 0-1 变量解决含互斥约束条件整数规划问题的求解方法 引叺 0-1 变量