算法设计与分析 课件 第八章 线性规划_第1页
算法设计与分析 课件 第八章 线性规划_第2页
算法设计与分析 课件 第八章 线性规划_第3页
算法设计与分析 课件 第八章 线性规划_第4页
算法设计与分析 课件 第八章 线性规划_第5页
已阅读5页，还剩18页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

计算机算法设计与分析第八章

线性规划学习目标掌握线性规划的一般形式、标准形式掌握求解线性规划问题的单纯性法掌握求解线性规划问题的对偶单纯性法

8.1线性规划模型例8.1生产计划问题。某工厂生产甲、乙两种产品，销售后的利润分别为4千元/件与3千元/件。生产甲产品每件需要A、B两种原材料均为1吨；生产乙产品每件需要A、C两种原材料分别为2吨和1吨。若工厂A、B、C三种原材料分别有6吨，4吨和2吨，问该厂应如何安排生产，才能使总利润最大？解：建立数学模型。设该厂生产件甲产品和件乙产品时总利润z最大，则x1，x2应满足：

8.1线性规划模型从以上的例子可以看出：目标函数和约束条件都是线性形式。下面给出线性规划问题的一般形式：

8.2线性规划标准形

8.2线性规划标准形

8.2线性规划标准形

8.3.4单纯形表1.单纯形法基本步骤单纯形法的求解线性规划问题的基本步骤如下：（1）确定初始的基可行解；（2）检查当前的基可行解，判断若是最优解或无最优解，计算终止；否则做基变换，找一个非基变量换入，一个基变量换出，得到新的可行基和对应的基可行解，且要求目标函数的值减少（至少不能增加）；（3）重复步骤（2）。

8.3.4单纯形表

8.3.4单纯形表2.例8.8用单纯性法求解下列线性规划问题。解：列单纯性表如下：所有检验数均≥0，停止计算。最优解为=(4,1,0,0,1)T，最优值为-19。

8.3.4单纯形表

8.4人工变量和两阶段法

8.4人工变量和两阶段法

8.4人工变量和两阶段法

8.4人工变量和两阶段法

8.4人工变量和两阶段法所有检验数均≥0，停止计算。最优解为(4,1,9,0,0)T，最优值为-2。

8.6.3对偶单纯形法

2.例8.12用对偶单纯形法求解。解：将模型转化为：列对偶单纯形表如下：

8.6.3对偶单纯形法

8.6.3对偶单纯形法最终b列均为非负，检验数也均为非负，迭代终止，问题的最优解为(11/5,2/5,0,0,0)T,最优值为28/5。

8.7整数线性规划在线性规划的实际问题中，有时要求最优解是整数情况，例如要求的解是机器的台数，人员的人数，物品的件数等。此时，如果仅仅是将所求的进行最优解四舍五入，这样可能不是可行解，或者是可行解但不是最优解。因此，对这样的问题要进一步的探讨。这类问题，称之为整数线性规划（IntegerLinearProgramming，ILP）。在整数规划中，要求所有的变量都限制为非负整数，就称为纯整数规划或全整数规划。如果仅一部分变量限制为非负整数，则称为混合整数规划。整数规划中还有一种最特殊的情况，就是限定变量只能取0或1，就称为0-1规划。下面主要讨论全整数规

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论