2第二章线性规划图解法

1、运 筹 学,任课教师：徐咏梅 博士 教授,80613111,Operations Research,第2章 线性规划图解法,第2章 线性规划图解法,2.1 线性规划问题 2.2 图解法 2.3 极点和最优解 2.4 计算机求解 2.5 最小化问题 2.6 特例,2.1 线性规划问题,在一定的约束条件（限制条件）下，使得某一目标函数取得最大（或最小）值，当规划问题的目标函数与约束条件都是线性函数，便称为线性规划。 Linear programming （LP）,2.1 线性规划问题,例1：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,生产计划问题,

2、问题：如何安排生产计划，使得获利最多？ 步骤： 1、确定决策变量：设生产A产品x1kg,B产品x2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件： 人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20,线性规划示意图,maxZ=70X1+120X2 9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20,例2：高尔夫球袋,2.1 线性规划问题,2.1 线性规划问题,决策变量 目标函数 约束条件 设产品标准袋、高档袋分别生产X1、X2个 Obj: maxZ=9X1+

3、10X2 S.t. 0.7X1+ X2 630 0.5X1+0.83333X2 600 1X1+0.33333X2 708 0.1X1+ 0.25X2 135 X10 X20,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,xn0,2.1 线性规划问题,几个概念 可行解：若向量X=(x1,x2,xn) 满足所有的约束条件，则称其

4、为可行解。 最优解：使目标函数达到最大值（或最小值）的可行解称为最优解。 最优值：最优解的目标函数值称为最优值。,T,2.2 图解法,唯一解 无穷多个最优解 无界解 无可行解,Example 1: A Maximization Problem,LP Formulation Max z= 5x1 + 7x2 s.t. x1 0,8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10,Example 1: Graphical Solution,Constraint #1 Graphed,x2,x1,x1 6,(6, 0),8 7 6 5 4 3 2 1 1 2 3 4 5 6 7

5、 8 9 10,Example 1: Graphical Solution,Constraint #2 Graphed,2x1 + 3x2 19,x2,x1,(0, 6 1/3),(9 1/2, 0),Example 1: Graphical Solution,Constraint #3 Graphed,8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10,x2,x1,x1 + x2 8,(0, 8),(8, 0),Example 1: Graphical Solution,Combined-Constraint Graph,8 7 6 5 4 3 2 1 1 2 3 4

6、5 6 7 8 9 10,2x1 + 3x2 19,x2,x1,x1 + x2 12 x1 + x2 4 x1, x2 0,Example 2: Graphical Solution,Constraints Graphed,5 4 3 2 1,1 2 3 4 5 6,x2,4x1 - x2 12 x1 + x2 4,2x1 + 5x2 10,x1,Feasible Region,Example 2: Graphical Solution,Objective Function Graphed,5 4 3 2 1,1 2 3 4 5 6,x2,Min z = 5x1 + 2x2 4x1 - x2

7、12 x1 + x2 4,2x1 + 5x2 10,x1,Example 2: Graphical Solution,Optimal Solution,5 4 3 2 1,1 2 3 4 5 6,x2,Min z = 5x1 + 2x2 4x1 - x2 12 x1 + x2 4,2x1 + 5x2 10 Optimal: x1 = 16/5 x2 = 4/5,x1,2.6 特例,无可行解 无界解 无穷多最优解,无可行解,Max z= 2x1 + 6x2 s.t. 4x1 + 3x2 8 x1, x2 0,无可行解,x2,x1,4x1 + 3x2 8,3,4,4,8,无界解,Max z=3x1 + 4x2 s.t. x1 + x2 5 3x1 + x2 8 x1, x2 0,无界解,x