线性规划整数规划0–1规划.ppt

一、引言 二、线性规划模型 线性规划模型的三种形式 ②．为了把一般形式的LP问题变换为标准形式，必须消除其不等式约束和符号无限制变量. 运输问题 例2. 设要从甲地调出物资2000吨，从乙地调出物 数学模型： 背包问题 例4. 有 n 个物品，编号为1, 2, …, n，第 i 件物品 指派问题 例5. 有n 项任务，由 n 个人来完成，每个人只能 DVD在线租赁第二个问题的求解 问题二的分析 问题二的模型及求解 ? 只要在模型中的产量限制约束（后n个不等式约束）中引入n个松弛变量xm+1j j = 1,2,…,n即可，变为： m ?xij+xm+1j=bj j=1,2,…m i=1 然后，需设一个产地A m+1,它的销量为： n m am+1= ?bj- ?ai j=1 i=1? ? 这里，松弛变量 x m+1,j 可以视为从产地 A m+1 运往销地 B j 的运输量，由于实际并不运送，它们的运费为 c m+1,j = 0 j = 1,2,…,n。于是，这个运输问题就转化成了一个产销平衡的问题。 显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解. 但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解. 关于运输问题及其解法的进一步介绍参考文献[2]. 对于线性规划问题，如果要求其决策变量取 整数值，则称该问题为整数线性规划问题. 平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解，其难度和运 三、整数线性规划模型 算量远大于同规模的线性规划问题. Gomory割 规划问题的方法（见文献[1]）. 此外，同线性规 划模型一样，我们也可以运用LINGO和LINDO软 件包来求解整数线性规划模型. 以1988年美国大学生数学建模竞赛B题为例，说明整数线性规划模型的建立及用LINGO软件包如何求解整数线性规划模型。 例3. 有七种规格的包装箱要装到两节铁路平板车 上去。包装箱的宽和高是一样的，但厚度（t，以 cm 计）及重量（w，以kg计）是不同的. 表1给出 了每种包装箱的厚度、重量以及数量。每节平板 车有10.2m 长的地方可用来装包装箱（像面包片 那样），载重为40t. 由于当地货运的限制，对于 C5, C6, C7 类包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能超过302.7cm. 试 把包装箱装到平板车上，使得浪费的空间最小. 8 4 6 6 9 7 8 n/件 1000 2000 4000 500 1000 3000 2000 w/kg 64.0 52.0 48.7 72.0 61.3 53.0 48.7 t/cm C7 C6 C5 C4 C3 C2 C1 种类 为在第 节车上装载第 件包装箱的 解 令 下面我们建立该问题的整数线性规划模型。 1) 约束条件 两节车的装箱数不能超过需要装的件数，即： 每节车可装的长度不能超过车能提供的长度： 每节车可装的重量不超过车能够承受的重量： 对于C5, C6, C7类包装箱的总数的特别限制： 2) 目标函数 浪费的空间最小，即包装箱的总厚度最大： 3) 整数线性规划模型 由上一步中的求解结果可以看出， 4) 模型求解 运用LINGO软件求解得到： 5) 最优解的分析说明 的装车方案，此时装箱的总长度为1019.7cm， 两节车共装箱的总长度为2039.4cm. 即为最优 但是，上述求解结果只是其中一种最优的 装车方案，即此答案并不唯一. 0-1整数规划是整数规划的特殊情形，它要求 线性规划模型中的决策变量xij只能取值为0或1. 单隐枚举法，该方法是一种基于判断条件（过滤 0-1整数规划模型的求解目前并没有非常好的 四、0-1整数规划模型 算法，对于变量比较少的情形，我们可以采取简 条件）的穷举法. 我们也可以利用LINGO和LINDO软件包来求 解0-1整数规划模型. 重 ai 千克，价值为 ci 元，现有一个载