数据、模型与决策课件：线性规划模型的图解法.ppt

例如，例2.1广州电器厂生产优化问题，它的线性规划模型为：o.b.max3X+8Y（利润最大化）s.t.6X+2Y≤1800（原材料约束）Y≤350（原材料约束）2X+4Y≤1600（劳动时间约束）X，，,Y≥0（非负约束）1.有惟一解线性问题的图解法2004006008001002003004005006007008009006X+2Y=18002X+4Y=16000ODCBAY=350XY3X+8Y=Z线性问题的图解法步骤在坐标图上作出代表各约束条件的直线；确定满足所有约束条件的可行域；作出任意一条等利润直线；朝着使目标函数最优化的方向，平行移动该等利润直线，直到再继续移动就会离开可行域为止。线性规划问题的解的讨论唯一解无穷多解目标函数为：MaxZ=2X+4Y时线性规划问题无可行域的情况：线性规划问题可行域无界的情况：6X+2Y=18002X+4Y=1600Y=350X=400max3X+8Ys.t.X+Y=350X，Y≥0本问题是利润最大化，所以应在可行域内选择使利润达到最大值的解。不妨考虑一下哪些解可以使利润达到3X+8Y=1200，可作出等利润线3X+8Y=2400；可得出：3X+8Y=k，k取不同的值表示不同的利润。不难发现所有的等利润都相互平行，且离原点越远的等利润线，利润最高。因此，最优解应是在可行域内离原点最远的那条等利润直线上的点。可见B点就是。而B点是直线②和直线③的交点。解此方程组可得：X=100，Y=350。例如下面一个线性规划模型：o.b.max3X+8Y（利润最大化）s.t.6X+2Y≤1800（原材料约束）Y≤350（原材料约束）2X+4Y≤1600（劳动时间约束）X≥350X，,Y≥0（非负约束）松弛变量与线性规划模型的标准式若在约束条件左边加上一个变量，使原来的“≤”约束不等式变为等式约束Max3X+8Y+0S1+0S2+0S36X+2Y+S1＝1800Y+S2=3502X+4Y+S3=1600X,Y,S1,S2,S3≥0标准型线性规划模型变量S1,S2,S3为松弛变量，表示可提供资源与实际消耗资源之差，即闲置的那部分资源将最优解X=100,Y=350带入约束条件左边，得到三种资源的实际使用量如下：6X+2Y=1300≤1800（原材料1约束）（1）Y=350≤350（原材料2的约束）（2）2X+4Y=1600≤1600（劳动时间约束）（3）原材料1有多余，原材料2、劳动时间没有多于约束1称为非紧约束，表示这时资源有多于约束2和约束3称为紧约束，表示这时资源已全部使用完毕2.有无穷多解这里，线性规划问题有无穷多解是指该规划问题无穷多个既在可行域内，又使目标值达到最优的解，即有无穷多个最优解。2.有无穷多解例如下面一个线性规划模型：o.b.max4X+8Y（利润最大化）s.t.6X+2Y≤1800（原材料约束）Y≤350