运筹学图解法.ppt
《运筹学图解法.ppt》由会员分享,可在线阅读,更多相关《运筹学图解法.ppt(73页珍藏版)》请在三一文库上搜索。
1、,Linear Programming,线 性 规 划 Chapter 2 Linear Programming,在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划,而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。,自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。,2
2、.1 问题的提出,2.3 图解法的灵敏度分析,2.2 线性规划的图解法,1.1、问题的提出,例1: 某工厂用三种原料生产三种产品,已知的条件如下表所示,试制订总利润最大的生产计划,可控因素:每天生产三种产品的数量,分别设为:,受制条件:每天原料的需求量不超过可用量,目标:每天的利润最大 利润函数:,原料 :,原料 :,蕴含约束:产量非负,原料 :,问题用一组决策变量 表示某一方案;决策变量的值就代表一个具体的方案,一般这些变量是非负的。,从以上例可以看出,其特征是:,3. 都有一个要达到的目标,它可以用决 策变量的线性函数来表示。按问题的 不同要求,目标函数实现最大化或最 小化。,存在一定的约
3、束条件,这些约束都可以用一组线性等式或线性不等式表示。,满足以上三个条件的数学模型称为线性规划的数学模型,其一般形式为:,目标函数,约束条件,上述规划中的决策变量也可以是无约束的。,满足所有约束条件的一组决策变量称为可行解,最优解所对应的目标函数值称为最优值,所有可行解组成的集合称为可行域,使目标函数达到最大的一组决策变量称为最优解,图解法,缺点: 只能求解两个决策变量的线性规划,优点:简单、直观、帮助我 们了解求解线性规划的原理,2.2、图解法,要点:,约束条件用坐标系中的半空间或直线的 交表示,变量用直角坐标系中的点表示,目标函数用一组等值线表示,沿着增加 或减少的方向移动,例1:,B,A
4、,结论:,可行域一定是凸集,若最优解存在,则最优解一定在凸集的顶点达到,上例中求得 问题的解是唯一的,但对一般线性规划问题,求解结果还可能出现以下几种情况:,1、无穷多最优解(多重解) 若将上例中的目标函数 改为则表示目标函数中以参数的等值线与约束条件的边界平行,当值由小变大时,将与此边界重合,线段AB上的所有点都是最优解。,2、无界解 对下述问题用图解法求解结果见下图:,由图可知,该问题的可行域无界,目标函数可以增大到无穷大,称这种情况为无界解或无最优解。,3、无可行解 在上述问题中增加一个约束条件, 该问题可行域为空集,即无可行解,从而不存在最优解。,总之,可能出现的情况: 可行域是空集
5、可行域无界无最优解 最优解存在且唯一,则一定在顶点上达到 最优解存在且不唯一,一定存在顶点是 最优解,注:图解法简便、直观,有助于了解 线性规划问题求解的基本原理,但是当 变量的个数多于三个时,它就无能为力 了,因此我们将介绍单纯形法。为了便 于讨论,我们先规定线性规划问题的数 学模型的标准形式。,线性规划的一般形式,1.3、线性规划问题的标准形式,线性规划有各种不同的形式,现将各种形式都统一变为如下的标准形式:,目标函数为最大,约束为等式,决策变量大于等于0,右端常数项大于0,或者,(向量和矩阵符号表述),用矩阵表述:,其中,目标转换,令自由变量 其中,求最小可以等价的转换为求最大,变量转换
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 图解法
链接地址:https://www.31doc.com/p-2831225.html