运筹学期末复习课件.ppt

第一章线性规划 线性规划在工商管理中的应用 1套裁下料问题 2人力资源分配的问题 3生产计划的问题 4配料问题 线性规划的三个要素 决策变量决策问题待定的量值取值要求非负约束条件任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数衡量决策优劣的准则 如时间最省 利润最大 成本最低目标函数是决策变量的线性函数有的目标要实现极大 有的则要求极小 线性规划的标准化一般形式目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0标准形式目标函数 Maxz c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 bi 0 可以看出 线性规划的标准形式有如下四个特点 目标最大 小 化 约束为等式 决策变量均非负 右端项非负 例1 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 300 A 2x1 x2 400 B x2 250 C x1 0 D x2 0 E 得到最优解 x1 50 x2 250最优目标值z 27500 2图解法 对于只有两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规划问题的有关概念 并求解 下面通过例1详细讲解其方法 两个关键点 1 可行域的确定 关键点 准确找出约束条件表示哪半个平面 2 目标函数线平移的过程中 函数值的变化趋势 关键点 目标函数直线的斜率 松驰变量 含义是资源的剩余量 剩余变量 资源最低限的超出量 单纯形法 10 基本思路 从可行域中某一个顶点开始 判断此顶点是否是最优解 如不是 则再找另一个使得其目标函数值更优的顶点 称之为迭代 再判断此点是否是最优解 直到找到一个顶点为其最优解 就是使得其目标函数值最优的解 或者能判断出线性规划问题无最优解为止 1单纯形法的基本思路和原理 如果线性规划有最优解 则一定有一个可行域的顶点对应一个最优解 11 基 已知A是约束条件的m n系数矩阵 其秩为m 若B是A中m m阶非奇异子矩阵 即可逆矩阵 则称B是线性规划问题的一个基 基向量 基中的一列即称为一个基向量 B中共有m个基向量 非基向量 在A中除了B之外的一列则称之为B的非基向量 基变量 与基向量pi相应的变量xi叫基变量 基变量有m个 非基变量 与非基向量pj相应的变量xj叫非基变量 非基变量有n m个 基本概念 自由变量 12 基本解 令非基变量为零 再求解剩下的m元线性方程组 得到的解基本可行解 若一个基本解是可行解 即满足非负条件的一个基本解可行基 基本可行解对应的基 注 基本解 可以是可行解 也可以是非可行解 它们之间的主要区别在于其所有变量的解是否满足非负的条件 13 在本例题中我们就找到了一个基是单位矩阵 在第一次找可行基时 所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成 称之为初始可行基 其相应的基本可行解叫初始基本可行解 14 所谓最优性检验就是判断已求得的基本可行解是否是最优解 1 最优性检验的依据 检验数 j在目标函数中用非基变量来表示基变量 此时目标函数中所有变量的系数即为各变量的检验数 把变量xi的检验数记为 i 二 最优性检验 思考 所有基变量的检验数必为零 为什么 15 证 设用非基变量表示的目标函数为如下形式由于所有的xj的取值范围为大于等于零 当所有的都小于等于零时 可知是一个小于等于零的数 要使z的值最大 显然只有为零 即令非基变量xj的值为零 所求得的基本可行解就使目标函数值最大为z0 2 最优解判别定理 对于求最大目标函数的问题中 对于某个基本可行解 如果所有检验数 0 则这个基本可行解是最优解 16 通过检验如果不是最优解 从可行基中换一个列向量 得到一个新的可行基 1 入基变量的确定选检验数中最大正数对应的非基变量换到基变量中去 称之为入基变量 三 基变换 17 2 出基变量的确定 用已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项的值 把其中最小比值所在的约束方程中的原基变量确定为出基变量 基本思路 找顶点 判最优 找顶点基本概念 最优性检验检验数 最优解判别定理 基本解 与可行解区别 基本可行解初始基本可行解 基 基向量 非基向量 基变量 非基变量 可行基初始可行基 基变换入基变量的确定 出基变量的确定 20 s1s2s3 000 zj j cj zj 000000 50100000 300 1400 1250 1 思考 初始基本可行解是多少 21 s1s2x2 00100 zj j cj zj 01000010025000 50000 100 50 1150 2 01001250 2001 1150 1010 150 思考 基本可行解是多少 22 zj j cj zj s1s2x2 00100 01000010025000 50000 100 50 1150 2 x1s2x2 500100 zj j cj zj 501005005027500 00 500 50 01001250 00 21150 1010 150 由于检验数都非正 因此z 27500为最优值 x1 50 x2 250 s1 0 s2 50 s3 0为最优解 思考 基本可行解是多少 第五章运输问题 A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物质的n个销地 si表示产地Ai的产量 dj表示销地Bj的销量 cij表示把物资从产地Ai运往销地Bj的单位运价 设xij为从产地Ai运往销地Bj的运输量 得到下列一般运输量问题的模型 一般运输模型 产销平衡 变化情况 1 有时目标函数求最大 如求利润最大或营业额最大等 2 当某些运输线路上的能力有限制时 在模型中直接加入约束条件 等式或不等式约束 3 产销不平衡时 可加入假想生产地 销大于产时 或假想销地 仓库 产大于销时 例2 题目及要求同题1 解 总产量 600 总销量 500 这是一个产大于销问题 增加一个假想的销地B4 其为A1 A2各自的仓库 运输费用为0 可得产销平衡的运价表 注意 理解x14 x24表示的含义 例3 题目及要求同题1 解 总产量 500 总销量 550 这是一个销大于产问题 增加一个假想的产地A3 其为 空头支票 打白条 运输费用为0 可得产销平衡的运价表 注意 理解x31 x32 x33表示的含义 1 运输模型的一般线性规划模型 产销平衡 2 产大于销时 加入假想销地 运价为0 规划标准型x11 x12 x13 x14 300 x21 x22 x23 x24 300 线性规划一般形式x11 x12 x13 300 x21 x22 x23 300 B4可理解为产地各自的仓库xi4可理解为各产地产量中的剩余量 3 销大于产时 加入假想生产地 运价为0 线性规划一般形式x11 x21 200 x12 x22 150 x13 x23 250 A3为假想产地x3i为销地销售量中的欠缺量 线性规划标准型x11 x21 x31 200 x12 x22 x32 150 x13 x23 x33 250 运输问题都存在最优解 表上作业法是一种求解运输问题的特殊方法 其实质是单纯形法 计算过程 假设产销平衡 1 找出初始基本可行解 m n个约束方程 基变量个数为m n 1 2 求各非基变量的检验数3 确定入基变量和出基变量 找出新的基本可行解 在表上用闭回路法调整 4 重复2 3直到得到最优解 3 运输问题的表上作业法 一 确定初始基本可行解1 西北角法 先从表的左上角 即西北角 的变量x11开始分配运输量 并使x11取尽可能大的值x11 min 7 3 3 当行或列分配完毕后 再在表中余下部分的左上角赋值 依次类推 直到右下角元素分配完毕 2 最小元素法最小元素法的思想是就近优先运送 即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束 依次下去 直到最后得到一个初始基可行解 注意问题 当取定xij的值之后 会出现Ai的产量与Bj的销量都改为零的情况 这时同时划去Ai行和Bj列 并且在这一行和列中除去已填上的数外均填上零 以保证填过数或零的空格为m n 1个 即保证基变量的个数为m n 1个 二 最优解的判别求最小值的运输问题的最优判别准则是 所有非基变量的检验数都非负 则运输方案最优 即为最优解 1 闭回路法所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发 沿水平或垂直方向前进 只有遇到代表基变量的填入数字的格才能向左或右转90度 当然也可以不改变方向 继续前进 这样继续下去 直至回到出发的那个空格 由此形成的封闭折线叫做闭回路 一个空格存在唯一的闭回路 所谓闭回路法 就是对于代表非基变量的空格 其调运量为零 把它的调运量调整为1 由于产销平衡的要求 必须对这个空格的闭回路的顶点的调运量加上或减少1 最后计算出由这些变化给整个运输方案的总运输费带来的变化 即检验数 如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零 则已求得最优解 否则继续迭代找出最优解 3 11 3 10 8 5 10 2 9 4 7 1 10 检验数 奇数点运价之和 偶数点运价之和 三 改进运输方案的办法 闭回路调整法选取所有负检验数最小的非基变量作为入基变量 在以x24为出发点的闭回路中 找出所有偶数的顶点的调运量 x14 3 x23 1 x24 min 3 1 1 把所有闭回路上为偶数顶点的运输量都减少这个值 奇数顶点的运输量都增加这个值 3 11 3 10 8 5 10 2 9 4 7 1 四 如何找多个最优方案只需看最优方案中是否存在非基变量的检验数为零 二 最优性检验 运输问题的表上作业法 一 初始基本可行解 1 西北角法2 最小元素法3 元素差额法 1 闭回路法 2 位势法 三 闭回路调整 1 入基变量 负检验数中最小 负的绝对值最大 2 出基变量 闭回路偶数顶点中运量最小 x 的顶点3 调整 奇 原运量 x偶 原运量 x 1整数规划的图解法 2整数规划的应用 3整数规划的分枝定界法 第三章整数规划 性质1 任何求最大目标函数值的整数规划的最优值小于或等于相应的线性规划 松弛问题 的最优值 任何求最小目标函数值的整数规划的最优值大于或等于相应的线性规划 松弛问题 的最优值 处理与一对变量之间逻辑关系的特殊约束 xi Myi yi为0 1变量 M充分大 一方面 当yi 0时 xi 0 另一方面 当yi 1时 约束不起作用 类似 x1要么不生产 要么至少生产3件 则约束条件可表示为 3y1 x1 My1 三 指派问题把n项不同任务指派给n个人 每个人去完成一项任务 并且每个人完成各项任务的效率情况不同 怎样指派才能使得完成n项任务的总效率最高 这就是指派问题 分枝定界法既能解决纯整数规划的问题 又能解决混合整数规划的问题 分枝定界法是先求解整数规划的线性规划问题 如果其最优解不符合整数条件 则求出整数规划的上下界 用增加约束条件的办法 把相应的线性规划的可行域分成子区域 称为分枝 再求解这些子区域上的线性规划问题 不断缩小整数规划的上下界的距离 最后得整数规划的最优解 3分枝定界法 例9用分枝定界法求解整数规划Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0且x1 x2为整数解 一 先求出以下线性规划的解 线性规划1 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0得z1 14 66 x1 2 44 x2 3 26 二 将线性规划1分解为两枝x1 2或x1 3 如下 线性规划2 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 2x1 x2 0解得z2 13 90 x1 2 x2 3 30线性规划3 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 3x1 x2 0解得z3 14 58 x1 3 x2 2 86 三 将线性规划3分解为线性规划4和线性规划5 如下 线性规划4 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 3x2 2x1 x2 0解得z4 14 x1 4 x2 2线性规划5 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 3x2 3x1 x2 0无可行解 用图8 2表示例9的求解过程与求解结果 1目标规划问题举例 2目标规划的图解法 3复杂情况下的目标规划 第四章目标规划 GoalProgramming 是研究企业考虑现有的资源条件下 在多个目标中去寻求满意解 即使得完成目标的总体结果离事先制定目标的差距最小 目标规划是由美国学者查纳斯 A Charnes 和库伯 W W Cooper 在1961年首次提出 目标规划 d 为未达到目标值的差值 称为负偏差变量d 为超过目标值的差值 称为正偏差变量 d 0 d 0 设d1 未超过风险目标的差值 d1 为超过目标的差值 当风险小于700时 d1 且d1 0 有0 5x1 0 2x2 d1 700成立当风险大于700时 d1 且d1 有0 5x1 0 2x2 d1 700成立当风险恰好等于700时 d1 且d1 0 有0 5x1 0 2x2 700成立实际只有上述三种情形之一发生 因而可将三个等式写成一个等式 0 5x1 0 2x2 d1 d1 700 1 针对优先权最高的目标建立线性规划优先权最高 P1 的目标是总风险不超过700 建立线性规划模型如下 Mind1 s t 20 x1 50 x2 900000 5x1 0 2x2 d1 d1 7003x1 4x2 d2 d2 10000 x1 x2 d1 d1 d2 d2 0 思考 为什么不是Mind1 2 针对优先权次高的目标建立线性规划优先权次高 P2 的目标是总收益超过10000 建立线性规划如下 Mind2 s t 20 x1 50 x2 900000 5x1 0 2x2 d1 d1 7003x1 4x2 d2 d2 10000d1 0 x1 x2 d1 d1 d2 d2 0 目标规划的这种求解方法可以表述如下 1 确定解的可行区域 系统约束 刚性约束 绝对约束 2 对优先权最高的目标求解 如果找不到能满足该目标的解 则寻找最接近该目标的解 3 对优先权次之的目标进行求解 注意 必须保证优先权高的目标不变 把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中4 重复第3步 直至所有优先权的目标求解完 目标规划是考虑在现有的资源条件下 在多个目标中去寻求满意解 使得完成目标的总体结果离事先制定目标的差距最小 目标函数求最小 问题的反面 优先级 最短路问题 最小生成树问题 最大流问题 第六章图与网络模型 最短路问题 在一个赋权的有向图D中的指定两个点vs和vt 找到一条从vs到vt的路 使得这条路上所有弧的权数的总和最小 这条路被称之为从vs到vt的最短路 这条路上所有弧的权数的总和被称为从vs到vt的距离 一 求解最短路的Dijkstra 狄克斯屈拉 算法 双标号法 双标号 对图中vj赋予两个标号 lj kj 第一个标号lj表示从起点到该点的最短距离 第二个标号kj表示在最短路上vj前面邻点的下标 2最短路问题 Dijkstra算法主要特点是以起始点为中心向外层层扩展 直到扩展到终点为止 1 给出点vs以标号 0 s 2 找出从已标号的点到没标号的点的弧的集合3 如果上述弧的集合是空集 则计算结束 如果上述的弧的集合不是空集 则转下一步 4 对上述弧的集合中的每一条弧 计算sij 在所有的sij中 找到其值为最小的弧 并写出此弧终点的双标号 返回步骤2 如果vt已标号 lt kt 则vs到vt的距离为lt 而从vs到vt的最短路径 则可以从kt反向追踪到起点vs而得到 如果vt未标号 则可以断言不存在从vs到vt的有向路 Dijkstra算法 双标号法 步骤 li cij 例2求下图中v1到v6的最短路 解 采用Dijkstra算法 3 1 8 4 3 3 3 1 2 1 0 s 1 在给定的赋权的连通图上任找一个圈 2 在所找的圈中去掉一个权数最大的边 如果有两条或两条以上的边都是权数最大的边 则任意去掉其中一条 3 如果所余下的图已不包含圈 则计算结束 所余下的图即为最小生成树 否则返回第