运筹学大学课件1-2线性规划图解法-讲文档.pptx

1、v 图解法图解法v 线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果v 由图解法得到的启示由图解法得到的启示第二节第二节 线性规划的图解法线性规划的图解法继续继续继续继续返回返回返回返回上页上页上页上页下页下页下页下页返回返回返回返回数学模型数学模型 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0 x1 x2上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2 8(0,4)(8,0)目标函数目标函数目标函数目标函数 Max M

2、ax Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 04x1 164 x2 12v图解法图解法上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12

3、 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2 84x1 164 x2 12可行域可行域v图解法图解法上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0|123456789x1x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x1+2x2 84x1 164 x2 12可行域可行域BCD

4、EAv图解法图解法上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2 84x1 164 x2 12BCDEA2x1+3x2=6v图解法图解法上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0 x2 目标函

5、数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2 84x1 164 x2 12BCDEAx1+2x2=8 4x1=16最优解最优解(4,2)v图解法图解法上页上页上页上页下页下页下页下页返回返回返回返回图解法求解步骤n n由全部约束条件作图求出可行域；由全部约束条件作图求出可行域；n n作目标函数等值线，确定使目标函数最优作目标函数等值

6、线，确定使目标函数最优的移动方向；的移动方向；n n平移目标函数的等值线，找出最优点，算平移目标函数的等值线，找出最优点，算出最优值。出最优值。上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题求解的几种可能结果(a)唯一唯一最优解最优解 x26 5 4 3 2 1 0|123456789x1上页上页上页上页下页下页下页下页返回返回返回返回(b)无穷多无穷多最优解最优解6 5 4 3 2 1 0 x2|123456789x1线性规划问题求解的几种可能结果上页上页上页上页下页下页下页下页返回返回返回返回(c)无界解无界解Max Max Z Z=x x1 1+x x2 2 -2-2-2-

7、2x x1 1+x x2 2 4 4 x x1 1-x x2 2 2 2 x x1 1、x x2 2 0 0 0 0 x2x1线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果上页上页上页上页下页下页下页下页返回返回返回返回(d)无可行解无可行解Max Max Z Z=2=2x x1 1+3+3x x2 2 x x1 1+2 +2 x x2 2 8 8 4 4 x x1 1 16 16 4 4x x2 2 12 12 -2-2-2-2x x1 1+x x2 2 4 4 x x1 1、x x2 2 0 0 0 0n n可行域为空集可行域为空集可行域为空集可行域为空集线性规划问题求解的

8、线性规划问题求解的 几种可能结果几种可能结果上页上页上页上页下页下页下页下页返回返回返回返回图解法的几点结论:（由图解法得到的启示）n n可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。n n若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在可行域的顶点得到。可行域的顶点得到。可行域的顶点得到。可行域的顶点得到。n n若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其

9、连线上的若两个顶点同时得到最优解，则其连线上的所有点都是最优解。所有点都是最优解。所有点都是最优解。所有点都是最优解。n n解题思路：解题思路：解题思路：解题思路：找出凸集的顶点，计算其目标函找出凸集的顶点，计算其目标函找出凸集的顶点，计算其目标函找出凸集的顶点，计算其目标函数值，比较即得。数值，比较即得。数值，比较即得。数值，比较即得。上页上页上页上页下页下页下页下页返回返回返回返回练习：用图解法求解LP问题 Max Z=34 x1+40 x24 x1+6 x2 48 2 x1+2 x2 182 x1+x2 16x1、x2 0 0上页上页上页上页下页下页下页下页返回返回返回返回图解法（练习）

10、18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16上页上页上页上页下页下页下页下页返回返回返回返回图解法（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16可行域可行域ABCDE上页上页上页上页下页下页下页下页返回返回返回返回图解法（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(

11、0,6.8)34x1+40 x2=272上页上页上页上页下页下页下页下页返回返回返回返回图解法（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)上页上页上页上页下页下页下页下页返回返回返回返回图解法（练习）x218 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)最优解最优解(3,6)4x1+6x2=48 2x1+2x2=18线性规划的图解法线性规划的图解法返回返回返回返回