线型规划和单纯形法ppt课件.ppt

《线型规划和单纯形法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹帷幄之中决胜千里之外线型规划模型和单纯形法§1什么是线性规划例1(资源利用问题)工厂生产i，ii两种饼干，这两产品分别要在A，B，C三种不同的设备上加工，每生产i产品要用各设备分别为3h，2h，2h；生产ii产品为5h，1h，2h；设备的生产能力分别为：15h，5h，11h每生产一件i产品可以获得利润为5元，每生产一件ii产品可以获得利润为4元，问企业应安排生产两种产品各多少件，使总的利润最大。例2(货物运输问题)东方电视机公司接到上海一家商场B1，青岛一家商场B2，西安一家商场B3的订单，要求给各商场提供电

2、视机，其需求量分别为100台，80台，90台。该公司由在北京和武汉的两国仓库A1，A2来供应，预计下月A1，A2可提供的电视分别为120台，150台，运费如下表。问如何调运电视机才能满足需要，而且运费最少？优化问题，一般指用“最好”的方式，使用或者分配有限的资源，即劳动力，原料，机器，使得费用最小或利润最大。线型规划问题的组成要素：1,决策变量：为实现目标采取的方案，措施，是问题的未知量，记为X;2,目标函数：问题要达到的要求，为决策变量的函数；3,约束条件：决策变量取值时受到的资源的限制，表示为含决策变量的不等

3、式或等式。建立线型规划模型的步骤：确定决策变量；表示目标函数；界定约束条件；能归结为线型规划的模型问题目标能用某种效益指标度量大小，能用线型函数描述目标的要求；为达到目标存在多种方案；目标是在一定约束条件下实现的，条件可以用线型不等式来描述。线性规划模型线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,≤0自由变量线性规划的标准形式目标函数：min约束条件：=变量符号：≥0矩阵型标准型线性规划的标准型(standardmodel)线性规划的标准型：对目标函数求极小，决策变量一律为非负

4、变量，约束条件除变量的非负条件外，一律为等式约束。各种形式的线性规划模型一律为等式约束。①若目标函数为则可令f=-z,此问题转化为求②若约束条件含则引进有称为松弛变量③若约束条件含,则引进新变量，有称为剩余变量。④若约束条件含则引进,于是⑤若变量的符号不受限制，则可引进两个新量,并以代入目标函数及约束中消去，而在约束条件中增加例：把线性规划化为标准型.§2求解线性规划问题的基本定理图解法图解法的步骤1建立直角坐标系2图示约束条件,找出可行域3图示目标函数4确定最优解例3解线性规划注释可能出现的情况：可行域是空集可

5、行域无界无最优解最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一，一定存在顶点是最优解可行域的几何结构基本假设凸集可行域的凸性凸集基本定理基本可行解定义问题基本定理§3单纯形发的基本步骤矩阵形式的单纯形表右端矩阵形式的单纯形表右端单纯形表1单纯性表2例3-1的单纯性表基本定理例3-1的单纯形表算法(表1)例3-1的单纯形表算法(表2)例3-1的单纯形表算法(表3)单纯形算法步骤算例初始单纯形表迭代1迭代2§4人工变量法例1.4-1大M法单纯形表(表1)例1.4-1大M法单纯形表(表2)例1.4-1大M法单纯

6、形表(表3)例1.4-1大M法单纯形表(表4)10例1.4-2两阶段法单纯形表(表1)例1.4-2两阶段法单纯形表(表2)例1.4-2两阶段法单纯形表(表3)0例1.4-2两阶段法单纯形表(表4)例1.4-2两阶段法单纯形表(表5)例1.4-2两阶段法单纯形表(表6)7例1.4-3两阶段法单纯形表(表1)3例1.4-3两阶段法单纯形表(表2)0例1.4-3两阶段法单纯形表(表3)例1.4-3两阶段法单纯形表(表4)例1.4-3两阶段法单纯形表(表5)0例1.4-3两阶段法单纯形表(表6)7例1.4-4两阶段法单纯

7、形表(表1)3例1.4-4两阶段法单纯形表(表2)0例1.4-3两阶段法单纯形表(表3)0例1.4-3两阶段法单纯形表(表4)例1.4-4两阶段法单纯形表(表5)例1.4-4两阶段法单纯形表(表5)§4单纯形法应用的特例1多重最优解例1.5-1用单纯形法解下述LP问题例1.5-1的单纯形表算法(表1)例1.5-1的单纯形表算法(表2)例3-1的单纯形表算法(表3)例1.5-1的单纯形表算法(表4)2退化问题3无可行解问题例1.5-3两阶段法单纯形表(表1)例1.5-3两阶段法单纯形表(表2)4无界可行解问题例1.

8、5-4两阶段法单纯形表(表1)例1.5-4两阶段法单纯形表(表2)例1.5-4两阶段法单纯形表(表3)例1.5-4两阶段法单纯形表(表4)例1.5-4两阶段法单纯形表(表5)