第一部分线性规划问题的求解重要算法：图解法、单纯形迭代、大M法单纯形迭代、对偶问题、表上作业法（找初始可行解：西北角法，
最小元素法；最优性检验：闭回路法，位势法；）、目标规划：图解法、整数规划：分支定界法（次重点），匈牙利法（重点）、第二部分动态规划问题的求解
重要算法：图上标号法第三部分网络分析问题的求解
重要算法：破圈法、TP标号法、寻求网络最大流的标号法第一部分线性规划问题的求解
一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。㈡图解法：图解法采用直角坐标求解：x1横轴；x2竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。㈢参考例题：（只要求下面这些有唯一最优解的类型）例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工
所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
设
消
备
A
B
C
耗
产
品
利润（万元）
甲
3
5
9
70
乙
9
5
3
30
有效总工时
540
450
720

问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？
（此题也可用“单纯形法”或化“对偶问题”用大M法求解）
解：设x1、x2为生产甲、乙产品的数量。
maxz70x130x2
st
⑴
3x19x2540
59
x1x1
5x23x2

450720
x1，x20
⑵⑶⑷⑸、⑹
第1页共20页
f可行解域为oabcd0，最优解为b点。由方程组
95xx11

5x23x2

450720
∴X

x1x2

（75，15）T
∴maxzZ70×7530×155700
例2：用图解法求解
maxz6x14x2
st
2x1x210
x1x28

x27
x1，x20
解出x175，x215
⑴⑵⑶⑷⑸、⑹
可行解域为oabcd0，最优解为b点。由方程组
第2页共20页
f2x1x1x2x2810
∴X

x1x2

（2，6）T
∴maxz6×24×636
例3：用图解法求解
mi
z－3x1x2
st
x1
4
2x1

x25x2
312
x12x28
x1，x20
解：
解出x12，x26
⑴⑵⑶⑷⑸⑹、⑺
可行解域为bcdefb，最优解为b点。
由方程组2x1x145x212
4解出x14，x25
∴X

x1x2

（4，
45
）T
41∴mi
z－3×45－115
第3页共20页
f二、标准型线性规划问题的r