《图解法求解线性规划问题.ppt》由会员分享，可在线阅读，更多相关《图解法求解线性规划问题.ppt（13页珍藏版）》请在三一办公上搜索。
1、第二章 第1节图解法求解线性规划问题,一、线性规划问题的提出二、图解法求解线性规划问题,一、线性规划问题的提出,例1：工厂每生产一单位产品1获利50，产品2获利100元，资源限制条件如下表所示，如何组织生产，获利最多。,符合“数学建模”的特征。目标函数利润资源限制条件材料和设备决策变量产品的生产数量。maxZ=50 x1+100 x2x1+x2300（设备约束）2x1+x2400（材料约束）X2 250 x1，x20,什么是线性规划模型？,数学模型中包括三个条件：目标函数、约束条件和决策变量。（1）决策变量（x1，x2，xn），每一组值表示一个方案。（2）决策变量的线性函数形式写出目标函数，确
2、定最大化或最小化目标。（3）用一组决策变量的线性等式或不等式表示解决问题过程中必须遵循的约束条件。,线性规划模型的一般形式,目标函数：Max（Min）z=c1 x1+c2 x2+cn xn 约束条件：a11 x1+a12 x2+a1n xn（=,）b1 a21 x1+a22 x2+a2n xn（=,）b2 am1 x1+am2 x2+amn xn（=,）bm 决策变量：x1，x2，xn 0,二、图解法求解线性规划问题,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。适用范围很小，引出求解线性规划问题的一些规律。,主要步骤,1、分别取决策变量X1
3、,X2 为坐标向量建立直角坐标系。每个约束条件都代表一个半平面。,对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,主要步骤,2、合并各个半平面的交集部分，找到线性规划问题的可行域。,3、平行移动目标函数值线，直到目标函数值取得最优值或者无法达到。,图解法观察的结论针对线性规划问题的解,1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；2、无穷多个最优解。3、无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。4、无可行解。可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。,线性规划问题解的几种情况,存在最优解唯一最优解 和 无穷多最优解不存在最优解无界解 和 无最优解,
