12
Example 1: A Maximization Problem

LP Formulation Max z= 5x1 + 7x2 s.t. x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1, x2 > 0
13
Example 1: Graphical Solution
Objective Function 5x1 + 7x2 = 46 Optimal Solution (x1 = 5, x2 = 3)
1
2
3
4
5
6
7
8
9
10
x1
20
画图求解
2）Max
z= 7x1 + 5x2 3）Max z= 5x1 + 10x2 4）Max z= 5x1 + 5x2
2x1 + 3x2 < 19
(9 1/2, 0)
1 2 3 4 5 6 7 8 9 10
x1
15
Example 1: Graphical Solution

Constraint #3 Graphed x2 (0, 8)
8 7 6 5 4 3 2 1
x1 + x2 < 8
(8, 0)
1 2 3 4 5 6 7 8 9 10
9


2.1 线性规划问题
一般形式 目标函数：Objective Function Max(min)z=c1x1+c2x2+…+cnxn 约束条件：Constraint a11x1+a12x2+…a1nxn≤(=,≥)b1 a21x1+a22x2+…a2nxn≤(=,≥)b2 …… am1x1+am2x2+…amnxn≤(=,≥)bm x1,x2,…,xn≥0
21
Example 1: Graphical Solution

Optimal Solution x2
8 7 6 5 4 3 2 1
Objective Function 5x1 + 7x2 Optimal Solution (x1 = 5, x2 = 3)
1
2
3
4
5
6
7
8
9
10
x1
22
图解法求最大化问题概要
5 4 3 2 1 1 2 3 4 5 6
Min z = 5x1 + 2x2
4x1 - x2 > 12 x1 + x2 > 4 2x1 + 5x2 > 10
x1
31
Example 2: Graphical Solution

Optimal Solution x2
5 4 3 2 1 1 2 3 4 5 6
在一定的约束条件（限制条件）下，使得 某一目标函数取得最大（或最小）值，当 规划问题的目标函数与约束条件都是线性 函数，便称为线性规划。 Linear programming （LP）

4
2.1 线性规划问题
生产计划问题
例1：某厂生产两种产品，需要三种资源， 已知各产品的利润、各资源的限量和各产品 的资源消耗系数如下表：
Min z = 5x1 + 2x2
4x1 - x2 > 12 x1 + x2 > 4 2x1 + 5x2 > 10 Optimal: x1 = 16/5 x2 = 4/5 x1
32
2.6 特例
无可行解 无界解 无穷多最优解

33
无可行解
Max s.t.
z= 2x1 + 6x2 4x1 + 3x2 < 12 2x1 + x2 > 8 x1, x2 > 0
28
2.5 最小化问题

Example 2: A Minimization Problem LP Formulation Min z=5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0
29
Example 2: Graphical Solution
资源限制 630小时 600小时 708小时 135小时
8
2.1 线性规划问题



决策变量 目标函数 约束条件 设产品标准袋、高档袋分别生产X1、X2个 Obj: maxZ=9X1+10X2 S.t. 0.7X1+ X2 ≤ 630 0.5X1+0.83333X2 ≤ 600 1X1+0.33333X2 ≤ 708 0.1X1+ 0.25X2 ≤ 135 X1≥0 , X2≥0
2.67
5
x1
37
无穷多最优解

？？？？
38
作业
39

确定每个约束条件的可行解的图
确定可以满足全部约束条件的可行解的范 围
根据特殊的目标函数的值，画两条目标函 数线 通过平行移动目标函数线，使目标函数值 增大，直到可行域全在直线的一侧 在目标函数线上，使目标函数的值最大的 解就是最优解
23
二维线性规划的几何特征
若可行域非空，它是一个凸集 若线性规划存在最优解（最优解之一），它 一定在可行域的某个（某几个）顶点（极点 ）得到 这两个特征对高维的线性规划也适用。 解题思路：先找出凸集的一个顶点，计算在 顶点处的目标函数值。比较周围相邻顶点的 目标函数值是否比这个值大，如果为否，则 这个顶点就是最优解的点（或之一），否则 转到比这个点的目标函数值更大的另一顶点 ，重复上述过程，一直找到使目标函数最大 的顶点为止。
(0, 5)
Objective Function max Z= 5x1 + 7x2 5x1 + 7x2 = 35
(7, 0)
1 2 3 4 5 6 7 8 9 10
x1
19
Example 1: Graphical Solution

Optimal Solution x2
8 7 6 5 4 3 2 1
B(2,3)
A(0,3)
C (4,2)
A(0,3) S (0,3) 12, B ( 2,3) : S ( 2,3) 18, C ( 4,2) : S ( 4,2) 20, D (6,0) : S (6,0) 18, O : S (0,0) 0.
O
D(6,0)
当x1 4, x2 2时，S max 20.
6
线性规划示意图
maxZ=70X1+120X2 9X1+4X2≤360 4X1+5X2 ≤200 3X1+10X2 ≤300 X1≥0 X2≥0
7
2.1 线性规划问题
例2：高尔夫球袋
标准袋 切割印染 缝合 完成 检查包装 单位产品利 润（美元） 7/10 1/2 1 1/10 9
高档袋 1 5/6 2/3 1/4 10

Constraints Graphed x2
5
4 3 2 1 1 2 3 4 5 6
Feasible Region 4x1 - x2 > 12 x1 + x2 > 4 2x1 + 5x2 > 10
ical Solution

Objective Function Graphed x2
运筹学
Operations Research
任课教师：徐咏梅博士 副教授 硕士生导师
80613111@
1
第 2章
线性规划图解法
2
第2章 线性规划图解法



2.1 2.2 2.3 2.4 2.5 2.6
线性规划问题 图解法 极点和最优解 计算机求解 最小化问题 特例
3
2.1 线性规划问题

Feasible Solution Region x2
8 7 6 5 4 3 2 1
Feasible Region
1 2 3 4 5 6 7 8 9 10
x1
18
Example 1: Graphical Solution

Objective Function Line x2
8 7 6 5 4 3 2 1
x1
16
Example 1: Graphical Solution

Combined-Constraint Graph x2
8
7 6
x1 + x2 < 8 x1 < 6
5
4 3 2 1
2x1 + 3x2 < 19
x1
17
1
2
3
4
5
6
7
8
9
10
Example 1: Graphical Solution
产品A
劳动力 设备 原材料 9 4 3
产品B
4 5 10
资源限制
360工时 200台时 300公斤
单位产品利润 （元）
70
120
5

问题：如何安排生产计划，使得获利最多？ 步骤：
1、确定决策变量：设生产A产品x1kg,B产品x2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件： 人力约束 9X1+4X2≤360 设备约束 4X1+5X2 ≤200 原材料约束3X1+10X2 ≤300 非负性约束X1≥0 X2≥0