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

一、线性规划问题的提出
例1：工厂每生产一单位产品1获利50，产品
2获利100元，资源限制条件如下表所示，如
何组织生产，获利最多。
产品1
产品2
资源限制
设备
1
1
300台时
原料A
2
1
400kg
原料B
0
1
250kg
第1页/共13页
符合“数学建模”的特征。
目标函数——利润
资源限制条件——材料和设备
决策变量——产品的生产数量。
maxZ=50x1+100x2
x1+x2≤300（设备约束）
2x1+x2≤400（材料约束）
X2 ≤250
x1，x2≥0
第2页/共13页
什么是线性规划模型？
数学模型中包括三个条件：目标函数、约束
条件和决策变量。
（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 x2 + … + amn xn ≤ （ =, ≥ ）bm
决策变量：
x1 ，x2 ，… ，xn ≥ 0
第4页/共13页
二、图解法求解线性规划问题
对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。
适用范围很小，引出求解线性规划问题的一些规律。
第5页/共13页
主要步骤
1、分别取决策变量X1 , X2 为坐标向量建立
直角坐标系。每个约束条件都代表一个半平
面。
x2
x1
X2≥0
X2=0
x2
x1
X1≥0
X1=0
第6页/共13页
对每个不等式(约束条件)，先取其等式在坐
标系中作直线，然后确定不等式所决定的半
平面。
100
200
300
100
200
300
x1+x2≤300
x1+x2=300
第7页/共13页
主要步骤
2、合并各个半平面的交集部分，找到线性规
划问题的可行域。
x1
x2
x2=0
x1=0
x2=250
x1+x2=300
2x1+x2=400
图2-1
第8页/共13页
3、平行移动目标函数值线，直到目标函数值
取得最优值或者无法达到。
x1
x2
z=20000=50x1+100x2
图2-2
z=27500=50x1+100x2
z=0=50x1+100x2
z=10000=50x1+100x2
C
B
A
D
E
第9页/共13页
图解法观察的结论——针对线性规划问题的解
1、如果线性规划有最优解，则一定有一个可
行域的顶点对应一个最优解；
2、无穷多个最优解。
3、无界解。即可行域的范围延伸到无穷远，
目标函数值可以无穷大或无穷小。
4、无可行解。可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。
第10页/共13页