第十一章 线性规划初步.ppt

*第十一章线性规划初步
(一) 本章内容小结
(二) 常见问题分类及解法
(一) 本章内容小结
一、本章主要内容
1、几个概念:线性规划问题,决策变量,约束条件,目标
函数,可行解,可行解域。最优解,可行基,基变量,单纯
形表。
2、建立线性规划问题的数学模型,图解法,单纯形方法。
二、本章重点、难点
1、重点:如何建立线性规划问题的数学模型,用图解法,
单纯形方法求解线性规划问题。
2、难点:决策变量的选取,用图解法求解时可行解域的确
定,单纯形方法的判断。
三、对学习的建议
复习二次不等式的解法及几何意义,掌握线性代数中有
关矩阵的初等变换,向量的线性相关性。
四、本章关键词
线性规划问题
可行解
可行基
标准形
单纯形
(二) 常见问题分类及解法
一、建立线性规划问题的数学模型
应用线性规划方法解决实际问题,其首要的、关键的一
步是建立揭示实际问题本质内容的线性规划问题的数学模型,
通常分以下几个步骤。
①分析问题,搞清实际问题的背景,抓住主要矛盾,明确该
问题所要实现的目标与受到的限制,为了建模方便,可以将已
知条件列成表格的形式。
②将决策中关键的量,即实际问题中待求的量设为决策变量,
并注意到这些决策变量一般都受到非负约束,然后,将问题的
限制条件表示成决策变量的线性等式或不等式。
③明确目标是最大值还是最小值,从所求的实际问题出发,
将目标函数表示为决策变量的线性函数。
例1 某厂用A、B、C三种原材料生产甲、乙两种产品。每生
产一件甲种产品耗费材料A为9kg,B为3kg,C为4kg,可获利
700元;每生产一件乙产品需要消耗4kg的A,10kg的B,5kg
的C,可获利1200元,现在原材料360kg的A、300kg的B和
200kg的C,怎样安排生产才能使获得的利润最大?
解
将已知条件列表见表11-1.
表11-1 原料消耗表/kg
原料
产品
甲
乙
原料
934
4 10 5
ABC
360300200
单利/(百元/件)
7
12
二、用图解法求解线性规划问题
由二元一次不等式的求解方法,将只含两个决策变量的
线性规划问题的解通过作图求出,其求解步骤如下:
(1) 将满足每一个约束条件的解在平面直角坐标系中表示
出来,求出满足所有约束条件的公共解。即可行解域;
(2) 做两条目标函数的等值线,并判断因目标函数值的变
化导致等值线位置变化的情况;
(3) 平移等值线至可行解域,找出距原点(S=0) 最远或
最近的点或线段,若存在,则线性规划问题的最优解存在,
否则,规划问题无解。
解
图11-1 例2示意
解
图11-2 例3示意
三、利用单纯形法求解线性规划问题
利用单纯形方法求解线性规划问题时首先化为规划问题的
标准形,然后利用单纯形方法的求解步骤,判断方法,通过单
纯形表的变化,最终求出规划问题的最优解或判断规划问题无
解。注意,最后一定给出原规划问题的最优解和最优值。
例4 某工厂利用甲、乙、丙三种原料,生产B1、B2、B3、B4
四种产品,每月可供该厂原料甲500t,乙300t,丙200t。生产
一吨不同的产品可获得的利润及生产一吨不同产品所消耗的原
料数量,见表11-2。