《现代物流运筹学（第二版）》 课件 4图解法

图解法《现代物流运筹学》主讲教师：王东辉01图解法ONE图解法线性规划问题的求解方法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式图解法单纯形法只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。图解法基本步骤建立平面直角坐标系，两个决策变量分别为两个坐标轴确定线性规划解可行域。方法为依次做每条约束线，标出可行域的方向，并找出它们共同的可行域。所有约束直线可能形成或不能形成相交区域，若能形成相交区域，相交区域任意点所表示解称为此线性规划可行解，这些符合约束限制的点集合，称为可行集或可行域。图解法基本步骤绘制目标函数等值线。目标函数等值线，就是目标函数取值相同点的集合，通常是一条直线。在可行域内寻找线性规划最优解。对于目标函数的任意等值线，确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域相交又不可能使目标函数值再增加的位置。图解法maxZ=2X1+X2

例：用图解法求解线性规划问题X1+1.9X2≥3.8X1-1.9X2≤3.8X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0s.t.图解法maxZ=2X1+X2

x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域线性规划问题解的几种情况利用图解法可以讨论线性规划解的四种情况。唯一最优解：线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。图解法maxZ=5X1+4X2

x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此点是唯一最优解线性规划问题解的几种情况利用图解法可以讨论线性规划解的四种情况。唯一最优解：线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。无穷多最优解：线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值达到最优的解图解法maxZ=3X1+5.7X2

x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域线性规划问题解的几种情况利用图解法可以讨论线性规划解的四种情况。唯一最优解：线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。无穷多最优解：线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值达到最优的解无有限最优解（无界解）：线性规划问题的无有限最优解是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。图解法maxZ=X1+2X2

246x1x2246无界解(无最优解)x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ线性规划问题解的几种情况利用图解法可以讨论线性规划解的四种情况。唯一最优解：线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。无穷多最优解：线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值达到最优的解无有限最优解（无界解）：线性规划问题的无有限最优解是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。无可行解：当线性规划问题中的约束条件不能同时满足时，将出现无可行域的情况，这时不存在可行解，即该线性规划问题无解。图解法x1x2O10203040102030405050无可行解(即无最优解)maxZ=3X1+5.7X2

学习要点通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；