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

《图解法求解线性规划问题.ppt》由会员分享，可在线阅读，更多相关《图解法求解线性规划问题.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 第第1 1节节图解法求解线性规划问题图解法求解线性规划问题一、线性规划问题的提出一、线性规划问题的提出二、图解法求解线性规划问题二、图解法求解线性规划问题一、线性规划问题的提出一、线性规划问题的提出例例1：工厂每生产一单位产品：工厂每生产一单位产品1获利获利50，产品，产品2获利获利100元，资源限制条件如下表所示，如元，资源限制条件如下表所示，如何组织生产，获利最多。何组织生产，获利最多。产品产品1 1产品产品2 2资源限制资源限制设备设备1 11 1300300台时台时原料原料A A2 21 1400kg400kg原料原料B B0 01 1250kg250kg符合“数学建模”

2、的特征。目标函数利润资源限制条件材料和设备决策变量产品的生产数量。maxZ=50 x1+100 x2x1+x2300（设备约束）2x1+x2400（材料约束）X2 250 x1，x20什么是线性规划模型？什么是线性规划模型？数学模型中包括三个条件：目标函数、约束条件和决策变量。（1）决策变量（x1，x2，xn），每一组值表示一个方案。（2）决策变量的线性函数形式写出目标函数，确定最大化或最小化目标。（3）用一组决策变量的线性等式或不等式表示解决问题过程中必须遵循的约束条件。线性规划模型的一般形式线性规划模型的一般形式目标函数：目标函数：Max（Min）z=c1 x1+c2 x2+cn xn 约

3、束条件：约束条件：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 1、分别取决

4、策变量、分别取决策变量X X1 1,X,X2 2 为坐标向量建立为坐标向量建立直角坐标系。直角坐标系。每个约束条件都代表一个半平每个约束条件都代表一个半平面。面。x2x1X20X2=0 x2x1X10X1=0对每个不等式对每个不等式(约束条件约束条件)，先取其等式在坐，先取其等式在坐标系中作直线，然后确定不等式所决定的半标系中作直线，然后确定不等式所决定的半平面。平面。100200300100200300 x1+x2300 x1+x2=300主要步骤主要步骤2 2、合并各个半平面的交集部分，找到线性规、合并各个半平面的交集部分，找到线性规划问题的可行域。划问题的可行域。x1x2x2=0 x1=

5、0 x2=250 x1+x2=3002x1+x2=400图2-13、平行移动目标函数值线，直到目标函数值取得最优值或者无法达到。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE图解法观察的结论图解法观察的结论针对线性规针对线性规划问题的解划问题的解1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；2、无穷多个最优解。3、无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。4、无可行解。可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。线性规划问题解的几种情况线性规划问题解的几种情况存在最优解存在最优解唯一最优解唯一最优解 和和 无穷多最优解无穷多最优解不存在最优解不存在最优解无界解无界解 和和 无最优解无最优解