运筹学chap4 整数规划.ppt

Chapter4 整数规划( Integer Programming ) 整数规划的特点及应用 整数规划的特点及应用 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。 不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为整数规划的松弛问题。 若松弛问题是一个线性规划，则称整数规划为整数线性规划。 整数规划的特点及应用 整数规划的特点及应用 整数线性规划问题的种类： 整数规划的特点及应用 整数线性规划问题的种类： 整数规划的特点及应用 整数线性规划问题的种类： 整数规划的典型例子 整数规划的特点及应用 解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 整数规划的特点及应用 整数规划的特点及应用 例4.2 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2。反之不一定 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。 整数规划的特点及应用 解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第 j 个项目的决策选择，记为： 整数规划的特点及应用 例4.3 指派问题或分配问题。 人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 整数规划的特点及应用 整数规划的特点及应用 每项工作只能安排一人，约束条件为： 整数规划的特点及应用 例 设整数规划问题如下 整数规划的特点及应用 用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6 整数规划的特点及应用 整数规划问题解的特征： 整数规划的特点及应用 整数规划问题的求解方法： 分配问题与匈牙利法 典型的分配问题（又称为指派问题）： 分配问题与匈牙利法 分配问题的标准形式： 标准指派问题的数学模型： 匈牙利法 解分配问题的匈牙利法是从这样一个明显的事实出发的： 如果效率矩阵的所有元素非负，而其中存在一组位于不同行 不同列的零元素，则只要令对应于这些零元素位置的xii=1,其他 的xij=0，则对应的目标函数值就是最优值。 匈牙利法 克尼格定理 : 如果从分配问题效率矩阵(cij)的每一行元素中分别减去(或加 上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一 个新的效率矩阵(bij)，其中 bij=aij-ui-vj , 则以(bij)为效率矩阵的分配 问题与以(cij)为效率矩阵的分配问题具有相同的最优解。 匈牙利法 (bij) 、(cij)为效率矩阵的分配问题具有相同的最优解。 匈牙利法 (bij) 、(cij)为效率矩阵的分配问题具有相同的最优解。 匈牙利法： 利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变， 在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。 若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩 阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素 取值为0。将其代入目标函数中得到zb=0，它一定是最小。 这就是以(bij)为系数矩阵的指派问题的最优解。也就得 到了原问题的最优解。 匈牙利法指派问题的求解步骤 分配问题与匈牙利法 例4.6 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 分配问题与匈牙利法 解：1）变换系数矩阵，增加0元素。 匈牙利法指派问题的求解步骤 找独立0元素，常用的步骤为： 匈牙利法 分配问题与匈牙利法 解：1）变换系数矩阵，增加0元素。 分配问题与匈牙利法 分配问题与匈牙利法 3）作最少的直线覆盖所有0元素 分配问题与匈牙利法 4) 变换矩阵(bij)以增加0元素 在没有被直线通过的所有元素中找出最小值， 没有被直线通过的所有元素减去这个最小元素； 直线交点处的元素加上这个最小值。 其他元素不变 新系数矩阵的最优解和原问题仍相同。 转回第2步，再进行指派。 分配问题与匈牙利法 分配问题与匈牙利法 分配问题与匈牙利法 例4.7 已知四人分别完成四项工作所需时间如下表，求最优分配方案。 分