§6.2线性规划问题的图解法 及解的性质 图解法的步骤: (1)绘制约束条件图 (2)绘制目标函数图 (3)确定最优解
§6.2 线性规划问题的图解法 及解的性质 图解法的步骤: (1) 绘制约束条件图 (2) 绘制目标函数图 (3) 确定最优解
例1求解线性规划问题 max S=41+ 5x2 2x1+x2<8 x2<3.5 S·t x1+2x2≤8 x1≥0,x2≥0 解 (1)绘制约束条件图,得可行域 ABCDO (2)绘制目标函数图形
例1 求解线性规划问题 max S = 4x1+ 5x2 2x1+ x2≤8 x2≤3.5 x1+ 2x2≤8 x1≥0, x2≥0 解 (1) 绘制约束条件图 ,得可行域ABCDO (2) 绘制目标函数图形 s t
令S=0,10,20, 2 作直线4x1+5x2=0 2=3.5 4x1+5x,=10 C 图1 过C的直线l: 4x1+5x2=Sc D 符合要求 5~6`、为 (3)确定最优解 解 x,+2x=8 得最优解为 2x1+x,=8 3 最优值为maxS=4×(8/3)+5×(8/3)=24
令S = 0,10,20,··· 作直线 4x1+5x2= 0 4x1+5x2=10 图1 过C的直线lc : 4x1+5x2 =SC 符合要求 (3) 确定最优解 解 得最优解为 最优值为 max S =4×(8/3)+5×( 8/3) =24. + = + = 2 8 2 8 1 2 1 2 x x x x = = 3 8 3 8 2 1 x x
例2求解线性规划问题 max s=x+ 2x 2x1+x2≤8 x2-35 x1+2x0,x20 解 (1)绘制约束条件图(同例1)得可行域 ABCDO (2)绘制目标函数图形
例2 求解线性规划问题 max S = x1+ 2x2 2x1+ x2≤8 x2≤3.5 x1+ 2x2≤8 x1≥0, x2≥0 解 (1) 绘制约束条件图(同例1)得可行域ABCDO. (2) 绘制目标函数图形 s t
彩 令S=0,2,4 作直线x1+2x2=0 =3.5 x1+2x2=2 6 x1+2x2=4 56 为 过B,C点直线x1+2x2=8符合要求 图2 (3)确定最优解 BC边上每一点的坐标都是最优解当然B点的坐标 x1=1,x2=35是最优解;C点的坐标x1=83,x2=83仍是 最优解,最优值为8
令 S = 0, 2, 4,··· 作直线 x1+ 2x2 = 0 x1+ 2x2 = 2 x1+ 2x2 = 4 过B,C点直线 x1+2x2 = 8符合要求. 图2 (3) 确定最优解 BC 边上每一点的坐标都是最优解.当然B点的坐标 x1=1, x2=3.5是最优解; C点的坐标 x1=8/3 , x2=8/3 仍是 最优解, 最优值为8.
例3求解线性规划问题 min s= 2x1t3 S.t-x1+ 2x x1>0,x20 解 (1)绘制约束条件图得可行域ABCD(无界 (2)绘制目标函数图形
例3 求解线性规划问题 min S = 2x1+3x2 x1–x2≥1 – x1+ 2x2≤2 x1≥0, x2≥0 解 (1) 绘制约束条件图,得可行域ABCD(无界). (2) 绘制目标函数图形 s t
令S=0,2,6, 2 作直线族2x1+3x2=0 A 2x1+3x2=2 2x1+3x2=6 23~456 l2x1+3x2=2符合要求 图3 (3)确定最优解 解x-=1,最优解为x1,x2=最优值为2
令S = 0, 2, 6, ··· 作直线族:2x1+ 3x2 = 0 2x1+ 3x2 = 2 2x1+ 3x2 = 6 lc : 2x1+3x2=2 符合要求. 图3 (3) 确定最优解 解 , 最优解为 x1=1, x2=0, 最优值为2. = − = 0 1 2 1 2 x x x
例4求解线性规划问题 max s=2x +3x x1-x2>1 S·t 1+2x20 解绘制约束条件 图同例3)由于目标函 432 数的平行直线族的直 线可无限远离原点, 23 56D为 图4
例4 求解线性规划问题 max S =2x1+3x2 x1 – x2≥1 – x1+ 2x2≤2 x1≥0, x2≥0 解 绘制约束条件 图(同例3).由于目标函 数的平行直线族的直 线可无限远离原点, 图4 s t
所以目标函数无上界,故此问题无最优解. 例5求解线性规划问题 max s= 2xu+2x St=x1+x221 x1>0,x20 解 在直角坐标系中,画出各约束所表示的半平面 如下图:
所以目标函数无上界,故此问题无最优解. 例5 求解线性规划问题 max S = 2x1+2x2 x1+ x2≤ – 2 – x1+ x2≥1 x1≥0, x2≥0 解 在直角坐标系中, 画出各约束所表示的半平面 如下图： s t
432 图5 O123 由图可知,这一问题无可行解自然也就没有最优解. 由以上几个例子可以看出,两个变量的线性规划 的解可能有以下几种情况: (1)有可行解且最优解是惟一的如图1(可行域有 界)、图3(可行域无界)
图5 由图可知, 这一问题无可行解自然也就没有最优解. 由以上几个例子可以看出, 两个变量的线性规划 的解可能有以下几种情况： (1) 有可行解且最优解是惟一的.如图1 (可行域有 界)、图3 (可行域无界)