第3章、第5章复习.ppt

第一章 线性规划及单纯形法 第三章 运输问题 复习 目 录 一、运输问题及其数学模型 网络图、线性规划模型、运输表 二、用表上作业法求解运输问题 初始解、解的检验、解的改进 三、运输问题的进一步讨论 产销不平衡 一、运输问题及其数学模型 运输问题运输表 运输问题线性规划模型 二、表上作业法 1、找出初始基可行解 练习西北角法： 最小元素法： 沃格尔法： 沃格尔法： 2、解的最优性检验 2、解的最优性检验 解的最优性检验——闭回路法： 解的最优性检验－－对偶变量法（位势法） 位势法计算步骤 1.在表中添加位一势列ui和位势行vj 2.计算位势 3.计算检验数 位势法计算步骤 1.在表中添加位一势列ui和位势行vj 2.计算位势 3.计算检验数 3、解的改进－闭回路调整法 练习：用位势法检验下表给出的解是否是最优解，若不是请对其进行改进 4、需要说明的几个问题 例：退化解 三、运输问题的进一步讨论 产销不平衡的运输问题 运用举例 应用举例 运用举例 运用举例 运用举例 判断 按最小元素法（或沃格尔法）给出的初始基可行解，从每一空格找出的闭回路不唯一。 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。 已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。 已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。 第五章　整数规划 复习 整数线性规划(Integer programming) 如果所有的变量都为整数，则该线性规划称为纯整数线性规划； 如果有一部分变量必须取整数，另一部分可以不取整数值的线性规划，则称之为混合整数线性规划。 如果所有的变量只能取0或1，则称之为0-1规划。 割平面法 该方法的基本思想是首先求解整数规划（IP）对应的松弛问题（LP），如果（LP）的最优解不是整数解，则逐次增加一个新约束（即割平面），它能割去松弛问题可行域中不含整数解的区域.逐次切割，直到得到一个整数最优极点（即整数解）为止. 割平面法 割平面寻找方法： 在最终单纯形表中选择具有最大小数部分的非整分量所在的行构造割平面： 整数＝非负真分数-正数 若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中， x1为基变量，所在行方程为 则以X1行构造的割平面方程为 分枝定界法 分枝定界法是求解整数规划的一种常用的有效方法，它不仅能针对纯整数规划问题求解，也能对混合整数规划问题求解.分枝定界法由“分枝”和“定界”两部分组成. 分枝定界法 求解步骤 求解整数规划相应的线性规划问题； 如果其最优解符合整数条件，则线性规划问题的最优解就是整数规划问题的解. 如果其最优解不符合整数条件，则求出整数规划的上下界用增加约束条件的方法，并把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题. 不断缩小最优目标函数值上下界的距离，当上下界的值相等时，整数规划的解就被求出 分枝定界法 在分枝定界法中，若选X1=4／3进行分支，则构造的约束条件应为 ？ 用分枝定界法求极小化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的？ 第四节 0—1规划 如果线性规划中的所有变量的取值只能取0、1，则这类线性规划问题是一种特殊的整数规划问题，我们把它称为0—1规划，把只取0或1值的变量称为0—1变量. 求解0—1规划常用隐枚举法. 第五节 指派问题 在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignment problem)。 例 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作，使所需总时间最少? 指派问题 指派问题的最优解有这样性质，若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)， 那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同 。 指派问题（匈牙利法） 第一步：变换系数矩阵，使各行各列中都出现0元素。 第二步：进行试指派。（确定独立0元素） (1) 从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。这表示对这行所代表的人，只有一种任务可指派。然后划去◎所在列(行)的其他0元素，记作Φ。这表示这列所代表的任务已指派完，不必再考虑别人了。 (2) 给