运筹学》复资料
参考
《习精品资料
第一部分 线性规划问题的求解
——重要算法：图解法、单纯形迭代、大M法单纯形迭代、对偶问题、表上作业法（找初始可
行解：西北角法，最小元素法；最优性检验：闭回路法，位势法；）、目标规划：图解法、整数规划：分支定界法（次重点），匈牙利法（重点）、 第二部分 动态规划问题的求解
——重要算法：图上标号法
第三部分 网络分析问题的求解
——重要算法：破圈法、TP标号法、寻求网络最大流的标号法
第一部分 线性规划问题的求解
一、两个变量的线性规划问题的图解法：
㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。 定义：达到目标的可行解为最优解。 ㈡图解法：
图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出； 2、确定可行解域；
3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。 4、确定最优解及目标函数值。
㈢参考例题：（只要求下面这些有唯一最优解的类型）
例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
仅供学习与交流，如有侵权请联系网站删除 谢谢2
精品资料 消 设 备 A B C 耗 品 甲 乙 3 5 9 9 5 3 540 450 720 70 30 —— 利润 （万元） 产 有效总工时 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？ （此题也可用“单纯形法”或化“对偶问题”用大M法求解） 解：设x1、x2为生产甲、乙产品的数量。
max z = 70x1+30x2
s.t.
⑴
?3x1?9x2?540?5x?5x?450?12? 9x?3x?72012???x1，x2?0 ⑵ ⑶ ⑷ ⑸、⑹
可行解域为oabcd0，最优解为b点。 由方程组
仅供学习与交流，如有侵权请联系网站删除 谢谢3
精品资料
?5x1?5x2?450? 解出x1=75，x2=15 9x?3x?7202?1?x1?T
∴X=??x??=（75，15）
?2?*
∴max z =Z*= 70×75+30×15=5700
例2：用图解法求解
max z = 6x1+4x2
s.t.
⑴
?2x1?x2?10?x?x?8?12? x?72???x1，x2?0 ⑵ ⑶ ⑷ ⑸、⑹
可行解域为oabcd0，最优解为b点。 由方程组
?2x1?x2?10? 解出x1=2，x2=6 x?x?8?12?x1?T
∴X=??x??=（2，6）
?2?*
∴max z = 6×2+4×6=36 例3：用图解法求解
仅供学习与交流，如有侵权请联系网站删除 谢谢4
精品资料
min z =－3x1+x2
⑴
s.t.
?4?x1?x2?3???2x1?5x2?12 ?x?2x?82?1??x1，x2?0解：
⑵ ⑶ ⑷ ⑸ ⑹、⑺
可行解域为bcdefb，最优解为b点。
?x1?44由方程组? 解出x1=4，x2=
2x?5x?1252?14?x1?*??∴X=??=（4，）T
5?x2?41∴min z =－3×4+=－11
55仅供学习与交流，如有侵权请联系网站删除 谢谢5
《运筹学》复习参考资料教学文稿
