v1.0 可编辑可修改1第 1 页 共 27 页第一部分线性规划问题的求解——重要算法：图解法、单纯形迭代、大M法单纯形迭代、对偶问题、表上作业法（找初始可行解：西北角法，最小元素法； 最优性检验： 闭回路法， 位势法；）、目标规划： 图解法、 整数规划： 分支定界法 （次重点），匈牙利法 （重点）、第二部分动态规划问题的求解——重要算法：图上标号法第三部分网络分析问题的求解——重要算法：破圈法、TP标号法、寻求网络最大流的标号法第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备： 定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。㈡图解法：图解法采用直角坐标求解：x 1——横轴； x 2——竖轴。 1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。㈢参考例题： （只要求下面这些有唯一最优解的类型）例 1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示： A B C利润（万元）甲乙3 5 99 5 37030设备消耗产品v1.0 可编辑可修改2第 2 页 共 27 页有效总工时540 450 720——问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大（此题也可用“单纯形法”或化“对偶问题”用大M法求解）解：设 x 1、x 2为生产甲、乙产品的数量。max z = 70x1+30x2.072039450555409321212121xxxxxxxx，可行解域为oabcd0，最优解为b 点。由方程组72039450552121xxxx解出 x1=75，x2=15∴X*=21xx=（75，15）T∴max z =Z*= 70 × 75+30× 15=5700例 2：用图解法求解max z = 6x1+4x 2⑴⑵⑶⑷⑸、⑹⑴v1.0 可编辑可修改3第 3 页 共 27 页.0781022122121xxxxxxx，可行解域为oabcd0，最优解为b 点。由方程组81022121xxxx解出 x1=2，x 2=6∴X*=21xx=（2，6）T∴max z = 6 ×2+4×6=36例 3：用图解法求解min z = －3x1+x2.08212523421212121xxxxxxxx，⑵⑶⑷⑸、⑹⑴⑵⑶⑷⑸⑹、⑺v1.0 可编辑可修改4第 4 页 共 27 页解：可行解域为bcdef...
