图解法求解线性规划问题PPT课件

1、一、线性规划问题的提出一、线性规划问题的提出例1：工厂每生产一单位产品1获利50，产品2获利100元，资源限制条件如下表所示，如何组织生产，获利最多。产品产品1 1产品产品2 2资源限制资源限制设备设备1 11 1300300台时台时原料原料A A2 21 1400kg400kg原料原料B B0 01 1250kg250kg第1页/共13页符合“数学建模”的特征。 目标函数利润 资源限制条件材料和设备 决策变量产品的生产数量。maxZ=50 x1+100 x2x1+x2300（设备约束）2x1+x2400（材料约束）X2 250 x1，x20第2页/共13页什么是线性规划模型？数学模型中包括三

2、个条件：目标函数、约束条件和决策变量。（1）决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案。（2）决策变量的线性函数形式写出目标函数，确定最大化或最小化目标。（3）用一组决策变量的线性等式或不等式表示解决问题过程中必须遵循的约束条件。第3页/共13页线性规划模型的一般形式线性规划模型的一般形式目标函数：目标函数： 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

3、x2 + + amn xn （ =, ）bm 决策变量：决策变量： x1 ，x2 ， ，xn 0 第4页/共13页二、图解法求解线性规划问题二、图解法求解线性规划问题 对于只有对于只有两个决策变量两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。求解。 适用范围很小，引出求解线性规划问题的一些规律。适用范围很小，引出求解线性规划问题的一些规律。第5页/共13页主要步骤主要步骤1 1、分别取决策变量、分别取决策变量X X1 1 , X , X2 2 为坐标向量建立为坐标向量建立直角坐标

4、系。直角坐标系。每个约束条件都代表一个半平每个约束条件都代表一个半平面。面。x2x1X20X2=0 x2x1X10X1=0第6页/共13页对每个不等式对每个不等式( (约束条件约束条件) )，先取其等式在坐，先取其等式在坐标系中作直线，然后确定不等式所决定的半标系中作直线，然后确定不等式所决定的半平面。平面。100200300100200300 x1+x2300 x1+x2=300第7页/共13页主要步骤主要步骤2 2、合并各个半平面的交集部分，找到线性规、合并各个半平面的交集部分，找到线性规划问题的可行域。划问题的可行域。x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x

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