管理运筹学-第2章-线性规划的图解法只是课件.ppt

管理运筹学-第2章-线性规划的图解法;解：设安排甲、乙产量分别为,总收入为，则模型为：;目标函数：总收入，记为z,则，为体现

对其追求极大化，在z的前面冠以极大号Max；;

线性规划模型的三要素;线性规划模型的一般形式：（以MAX型、约束为例）;则模型可表示为

;回顾例1.1的模型;一般地

其中称为决策变量向量，称为价格系数向量,

称为技术系数矩阵,称为资源限制向量。;二、线性规划模型的图解法;例1用图解法求解线性规划问题;（1）分别取决策变量X1，X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。;*;*;（4）目标函数Z=50X1+100X2，当Z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。;;(2)做目标的图形;（3）求出最优解

将目标直线向使目

标优化的方向移，直

至可行域的边界为止，

这时其与可行域的“切”

点即最优解。

如在例1.1中，

是可行域的一个角点，

经求解交出的

二约束直线联立的方程

可解得;;2.由图解法得到线性规划解的一些特性;（2）线性规划的最优解（若存在的话）必能在可行域的角点（顶点）获得。;本性质重要意义：;（3）线性规划解的几种情形;重要结论：

如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；

无穷多个最优解。

无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；

无可行解。则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。

;小结;重要性：;线性规划的标准化内容之一：——引入松驰变量（含义是资源的剩余量）

例1.1中引入s1，s2，s3模型化为

目标函数：Maxz=7x1+12x2+0s1+0s2+0s3

约束条件：9x1+4x2+s1=360

4x1+5x2+s2=200

s.t.3x1+10x2+s3=300

x1,x2,s1,s2,s3≥0

对于最优解x1=20x2=24，s1=84s2=0s3=0

说明：生产20单位甲产品和24单位乙产品将消耗完所有可能的电和油，但对煤则还剩余84个单位。

;线性规划的标准化

一般形式

目标函数：Max（Min）z=c1x1+c2x2+…+cnxn

约束条件：a11x1+a12x2+…+a1nxn≤（=,≥）b1

a21x1+a22x2+…+a2nxn≤（=,≥）b2

s.t.…………

am1x1+am2x2+…+amnxn≤（=,≥）bm

x1，x2，…，xn≥0

标准形式

目标函数：Maxz=c1x1+c2x2+…+cnxn

约束条件：a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

s.t.…………

am1