图解法求解线性规划问题.ppt

《图解法求解线性规划问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章第1节图解法求解线性规划问题一、线性规划问题的提出二、图解法求解线性规划问题一、线性规划问题的提出例1：工厂每生产一单位产品1获利50，产品2获利100元，资源限制条件如下表所示，如何组织生产，获利最多。产品1产品2资源限制设备11300台时原料A21400kg原料B01250kg符合“数学建模”的特征。目标函数——利润资源限制条件——材料和设备决策变量——产品的生产数量。maxZ=50x1+100x2x1+x2≤300（设备约束）2x1+x2≤400（材料约束）X2≤250x1，x2≥0什么是线性规划模型？数学模型

2、中包括三个条件：目标函数、约束条件和决策变量。（1）决策变量（x1，x2，…，xn），每一组值表示一个方案。（2）决策变量的线性函数形式写出目标函数，确定最大化或最小化目标。（3）用一组决策变量的线性等式或不等式表示解决问题过程中必须遵循的约束条件。线性规划模型的一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bm决策变量：x1，

3、x2，…，xn≥0二、图解法求解线性规划问题对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。适用范围很小，引出求解线性规划问题的一些规律。主要步骤1、分别取决策变量X1,X2为坐标向量建立直角坐标系。每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=300主要步骤2、合并各个半平面的交集部分，找到线性

4、规划问题的可行域。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-13、平行移动目标函数值线，直到目标函数值取得最优值或者无法达到。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE图解法观察的结论——针对线性规划问题的解1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；2、无穷多个最优解。3、无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。4、无可

5、行解。可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。线性规划问题解的几种情况存在最优解唯一最优解和无穷多最优解不存在最优解无界解和无最优解