第一章线性规划课件.ppt
《第一章线性规划课件.ppt》由会员分享,可在线阅读,更多相关《第一章线性规划课件.ppt(259页珍藏版)》请在三一办公上搜索。
1、第一章 线性规划,1.1 线性规划的模型与图解法 1.2 单纯形法 1.3 对偶问题与灵敏度分析 1.4 线性整数规划 1.5 运输问题,1.1 线性规划的模型与图解法一、线性规划问题及其数学模型,在生产管理和经营活动中经常需要解决:如何合理地利用有限的资源,以得到最大的效益。,例1.1 某工厂可生产甲、乙两种产品,需消耗煤、电、油三种资源。现将有关数据列表如下:试拟订使总收入最大的生产计划方案。,1)决策变量:需决策的量,即待求的未知数;,2)目标函数:需优化的量,即欲达的目标,用决策变量的表达式表示;,3)约束条件:为实现优化目标需受到的限制,用决策变量的等式或不等式表示。,线性规划模型的
2、三要素,例1.1 某工厂可生产甲、乙两种产品,需消耗煤、电、油三种资源。现将有关数据列表如下:试拟订使总收入最大的生产计划方案。,在本例中,约束条件:分别来自资源煤、电、油限量的约束,和产量非负的约束,表示为,决策变量:甲、乙产品的计划产量,记为;,目标函数:总收入记为,则,为体现对其追求极大化,在 的前面冠以极大号Max;,解:设安排甲、乙产量分别为,总收入为,则模型为:,线性规划模型的一个基本特点:目标和约束均为变量的线性表达式。,如果模型中出现如的非线性表达式,则不属于线性规划。,例1.2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建,各体系资源用量及今年供应量见下表:,要求在
3、充分利用各种资源条件下使建造住宅的总面积为最大,求建造方案。,解:设今年计划修建砖混、壁板、大模住宅各为,为总面积,则本问题的数学模型为:,前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型,共用了12个变量,10个约束条件。,练习:某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下:,试决定买M与N二种饲料各多少公斤而使支出的总费用为最少?,解:设购买M、N饲料各为,则,线性规划模型的一般形式:以MAX型、约束为例,决策变量:目标函数:约束条件:,模型一般式的矩阵形式,则模型可表示为,记,回顾例1.1的模型其中 表示决策变量的向量;表示
4、产品的价格向量;表示资源限制向量;表示产品对资源的单耗系数矩阵。,一般地中 称为决策变量向量,称为价格系数向量,称为技术系数矩阵,称为资源限制向量。,问题:为什么 称为技术系数矩阵?,图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维(两个变量)的问题,但其主要作用并不在于求解,而是在于能够直观地说明线性规划解的一些重要性质。,二、线性规划问题的图解法,1.做约束的图形 先做非负约束的图形;再做资源约束的图形。,以例1.1为例,其约束为,图解法步骤,问题:不等式的几何意义是什么?怎样做图?,1.做约束的图形 先做非负约束的图形;再做资源约束的图形。,以例1.1为例,其约束为,图解
5、法步骤,各约束的公共部分即模型的约束,称可行域。,3.求出最优解 将目标直线向使目标 优化的方向移,直至可行域的边界为止,这时其与可行域的“切”点 即最优解。,练习:用图解法求解下面的线性规划。,-最优解在什么位置获得?,-线性规划的可行域是一个什么形状?,问题:在上两例中,多边形,而且是“凸”形的多边形。,在边界,而且是在某个顶点获得。,(1)线性规划的约束集(即可行域)是一个凸多面体。,凸多面体是凸集的一种。所谓凸集是指:集中任两点的连线仍属此集。试判断下面的图形是否凸集:,凸集中的“极点”,又称顶点或角点,是指它属于凸集,但不能表示成集中某二点连线的内点。如多边形的顶点。,由图解法得到线
6、性规划解的一些特性,因为,由图解法可知,只有当目标直线平移到边界时,才能使目标 z 达到最大限度的优化。,问题:本性质有何重要意义?,(2)线性规划的最优解(若存在的话)必能在可行域的顶点获得。,它使得在可行域中寻优的工作由“无限”上升为“有限”,从而为线性规划的算法设计提供了重要基础。,(3)线性规划解的几种情形,内容回顾与思考1.线性规划解决的是一类什么问题?2.线性规划模型构成的三要素?3.线性规划模型的一般式?4.图解法的一般步骤?5.图解法得到线性规划哪些性质?,单纯形法是求解线性规划的主要算法,1947年由美国斯坦福大学教授丹捷格(G.B.Danzig)提出。尽管在其后的几十年中,
7、又有一些算法问世,但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。,1.2 单纯形法,早在二战期间,在美国空军服役的科学家丹捷格就提出了“单纯形方法”。这个方法当时曾经保密,直到战后的1947年,当丹捷格离开军队,转任斯坦福大学教授之后,才公开发表。丹捷格不仅提出了单纯形法,而且在线性规划相关研究领域做出了一系列杰出的贡献。他被人们誉为“线性规划之父”,以他的名字命名的“丹捷格奖”成为运筹学界的最高奖项之一。,(1914-2005),一、单纯形法的预备知识,1.线性规划的标准型 来自实际问题的线性规划模型形式各异,在用单纯形法求解之前,先要将模型化为统一的形式标准型:,标准型的特征
8、:Max型、等式约束、非负约束,非标准形式如何化为标准?(1)Min型化为Max型 因为,求一个函数的极小点,等价于求该函数的负函数的极大点。,注意:Min化为Max后,最优解不变,最优值差负号。,(2)不等式约束化为等式约束 分析:以例1.1中煤的约束为例,x3 称为松弛变量。问题:它的实际意义是什么?,煤资源的“剩余”。,之所以“不等”是因为左右两边有一个差额,可称为“松弛量”,若在左边加上这个松弛量,则化为等式。而这个松弛量也是变量,记为x3,则有,练习:请将例1.1的约束 化为标准型,解:增加松弛变量,则约束化为,可见:松弛变量的系数恰构成单位阵,问题:松弛变量在目标中的系数为何?,问
9、题:标准型与原来模型解的关系?,例如,可化为,X2为自由变量,2.基本概念(1)可行解与最优解,(2)基矩阵与基变量,基矩阵(简称基):系数阵A中的m阶可逆子阵,记为B;其余部分称为非基矩阵,记为N。,基向量:基B中的列;其余称非基向量。,基变量:与基向量Pj对应的决策变量xj,记其组成的向量为XB;与非基向量对应的变量称非基变量,记其组成的向量为XN。,如 指出A中的基。,记A中的列为Pj,则每个Pj 对应于一个xj,即。,6个。,一般地,mn 阶矩阵A中基的个数最多有多少个?,问题:本例的 中一共有几个基?,(3)基本解与基本可行解,可见:一个基本解是由一个基决定的。注意:基本解仅是资源约
10、束的解,并未要求其非负,因此其未必可行。,称非负的基本解为基本可行解(简称基可行解)。,例1.4 在例1.3的模型,中,求相应于基B1和B2的基本解,它们是否基本可行解?,上二组概念间的联系:,几种解之间的关系:,可行解,基本解,非可行解,基本可行解,问题:基本可行解是可行域中的哪些点?,3.基本定理,(1)线性规划的可行域是一个凸多面体。,(2)线性规划可行域的顶点与基本可行解一 一对应。,(3)线性规划的最优解(若存在的话)必能 在可行域的顶点获得。,二、单纯形法的步骤,确定初始基本可行解,寻找更好的基本可行解,否,是,stop,单纯形法是一种迭代的算法,它的思想是在可行域的顶点基本可行解
11、中寻优。由于顶点是有限个(为什么?),因此,算法经有限步可终止。,方法前提:模型化为标准型,1.确定初始基可行解,由于基可行解是由一个可行基决定的,因此,确定初始基可行解X0相当于确定一个初始可行基B0。,方法:若A中含I,则B0=I;若A中不含I,则要用人工变量法构造一 个I。,问题:若B0=I,则X0=?,2.最优性检验,分析:用什么检验?,目标。,记为,当 0时,当前解为最优。称检验数向量。,而目标,所以,方法:,(1)计算每个xj的检验数,(2)若所有j 0,则当前解为最优;,否则,非最优,转3。,问题:非最优的特征为何?,3.寻找更好的基可行解,由于基可行解与基对应,即寻找一个新的基
12、可行解,相当于从上一个基B0变换为下一个新的基B1,因此,本步骤也称为基变换。,换基后,转2。即再检验,直至满足最优性条件。,以例1.1为例,可按上述单纯形法的步骤求出其最优解,其大致的过程如下。,(1)先将模型化为标准型,A中含I(P3,P4,P5),可以用单纯形法求解。,(2)确定初始基可行解、检验,计算检验数,确定进基向量为P2,再计算检验比,确定出基向量为P5。,(3)换基、计算下一个基可行解、再检验,直 至最优,练习:对于下面的线性规划,(1)先用图解法求解;(2)将模型化为标准型;(3)再用单纯形法步骤求出其最优解,并指出求解过程中每一个基可行解相当于可行域的哪一个角点。,解:(1
13、)图解法求解,(2)将模型化为标准型,A中含I(P3,P4),可以用单纯形法求解。,(3)用单纯形法求解,确定初始基可行解、检验,求解过程中每一个基可行解相当于可行域的哪一个角点?,问题:当模型规模较大时,计算量很大。,事实上,单纯形法的实现是在单纯形表上完成的。,总结上述过程:,三、单纯形表,单纯形表是基于单纯形法的步骤设计的计算表格,是单纯形法的具体实现。,回顾单纯形法步骤,而相邻两个 之间只有一列不同,可分析其逆阵间关系:,即每个 可由上一个 经以 为主元的初等行变换得到,基于此设计了单纯形表。,用单纯形表计算的主要过程:,(2)计算检验数 判断最优:,(3)计算检验比换基:,例1.5
14、用单纯形法解例1.1,标准模型的A中是否含I?,松弛变量系数恰好构成I。,中表示进基列与出基行的交叉元,下一张表将实行以它为主元的初等行变换(也称高斯消去)。方法是:先将主元消成1,再用此1将其所在列的其余元消成0。,(请解释其实际意义),甲乙产品产量的最优计划、相应的最大收入和资源剩余,基变量的检验数和系数列有何特征?,检验数均为0,,系数列均为单位向量列,练习:用单纯形法求解下面的线性规划,前面曾用图解法和单纯形法步骤求解过:,注:1.表上每一列的含义:,2.每张表上B-1的位置在哪?对应于初表中I 的位置。,例1.6:填出下面表中的空白,L,练习:用单纯形法求解下面的线性规划,直观上有什
15、么特点?,目标与某约束斜率相同,问题:本题的单纯形终表检验数有何特点?,非基变量x2 的检验数等于零。,四、大M法设模型已经化为标准型但A中不含I。,添加人工变量,将模型(1)化为(2),用单纯形法求解(2)的结果:-最优解基变量中不含,则(2)的最 优解的前n个分量即(1)的最优解;-最优解基变量中含有,则(1)无解。,M称为罚因子,其作用是迫使 出基。,例1.7:用单纯形法求解下面的线性规划,模型已经是标准型,但A中不含I。,解:增加人工变量 将模型化为,注:(1)解的几种情况在单纯形表上的体现-唯一最优:终表非基检验数均小于零;-多重最优:终表非基检验数有等于零;-无界解:有正检验数相应
16、系数列均非正;-无解:最优基中含有人工变量。,(2)Min型单纯形表与Max型的区别仅在于:检验数反号,即-令负检验数中最小的对应的变量进基;-当检验数均大于等于零时为最优。,问题:Min型模型的大M法人工变量模型是什么?,内容回顾与思考1.基本可行解的概念和几何意义?2.单纯形法的原理步骤?3.单纯形表的原理和结构?4.大M法的原理和步骤?5.Min型单纯形表计算方法?,1.3 对偶问题与灵敏度分析,一、对偶问题及其模型 对偶理论是线性规划的重要基础理论,它揭示了:每一个线性规划都存在与它对偶的一个线性规划,二者之间有密切的联系,以至于把二者放在一起研究往往比单独研究一个问题更有意义。,这时
17、有另一家厂商提出要购买其煤、电、油全部资源,并希望花费尽量少。试建立购买者的线性规划模型。,分析模型的三要素:购买者的决策变量、目标函数、约束条件,(D)称为(P)的对偶问题,(P)称为(D)的原始问题,对偶模型的一般式(对偶定义),这是最常见的对称式对偶模型。例1.8已经显示了二者间具有十分对称的对应关系。,二、对偶性质1.对称性:对偶的对偶就是原始问题。,即(P)和(D)互为对偶,是对称的。,如果模型中含有等式约束或自由变量,则可转化为不等式约束和非负变量的形式分析。,练习:写出下面线性规划的对偶模型,解:既然模型是Min型,可按(D)整理,令,然后按(P)写出其对偶:,设对偶变量为,证:
18、由(P),(D)的约束可得,图示:,问题:若(P),(D)有一为无界解,则另一为何?,证:对任可行解,由弱对偶性,,故,同理,。,图示:,()与()的约束相同,故()的最优解Y*是()的可行解。由弱对偶性,而由解的最优性,故,证:对(P)增加松弛变量Xs,化为,其检验数为,,由解的最优性,。,取,,由对偶定理的证明过程可知,原始问题(P)的单纯形终表可同时得到(P)和(D)的最优解,例如,在 1.2 的练习中已知,xjym+j=0,yixn+i=0(i=1,2,m;j=1,2,n),在一对变量中,一个大于0,另一个一定等于0。,解:先写出其对偶,将 代入约束,第二至四约束为严格不等式,由互补松
19、弛性,,又,故,解得,三、对偶的经济意义,1.对偶最优解的经济解释:资源的影子价格(Shadow Price),对偶问题的最优解:买主最低出价;原问题资源的影子价格:当该资源 增加1单位时引起的总收入的增量:卖主的内控价格。,注意:影子价格是在最优解前提下,并且其他资源不变。,解:(1)煤、电、油的影子价格分别是0,1.36,0.52;其经济意义是当煤、电、油分别增加1单位时可使总收入分别增加0、1.36、0.52。,增量恰好为1.36。,(2)由影子价格的定义,在最优解前提下,电再增加1单位引起总收入由 变化为:,2.对偶约束的经济解释 产品的机会成本,机会成本表示减少一件产品所节省的资源可
20、以增加的收益,3.对偶松弛变量的经济解释产品的差额成本,差额成本=机会成本 利润,在利润最大化的生产计划中(1)影子价格大于0的资源没有剩余;(2)有剩余的资源影子价格等于0;(3)安排生产的产品机会成本等于利润;(4)机会成本大于利润的产品不安排生产。,4.互补松弛关系的经济解释,练习:填空1.根据线性规划的互补松弛定理,影子价格大于零的资源一定 剩余;安排生产的产品机会成本一定 利润。()A没有,小于 B没有,大于C没有,等于 D有,等于,C,2.若线性规划的原始问题增加一个变量,则其对偶问题就增加一个;因而对偶的最优目标值将可能变。()A约束,好 B约束,坏C变量,好 D变量,坏,B,四
21、、对偶单纯形法,能否尝试对称的思路,在保持 下改善可行性?,基变换后再转(2)。效果:出基改善,进基保持。,例1.12:求解下面的线性规划,特点:化为标准型后A中不含I,但能否不用大M法?如果检验数均非正则可。,引入松弛变量,化为标准型,将线性规划与经济问题相关联的研究贡献,使得 T.G.Koopman(库普曼)和 L.V.Kamtorovich(康脱罗维奇)二人共同分享了1975年的第7届诺贝尔经济学奖。,主要讨论C、b和变量结构变化时对解的影响。,对解怎样影响?,只要由 解出 的范围即可。,解:由,解得:,,即油的限量在增加100至减少72范围内变化时,原最优基保持不变。,最优基不变是什么
22、意思?,投产结构不变。,价格 变为 时,因为它只影响最优性,即对检验数 产生影响,故只要其使变化后的 即可。,2.C变化时的分析,当 是非基变量 的价格系数时,只影响自己的检验数,由 一个不等式解得 的范围。,当 是基变量 的价格系数时,要影响所有的检验数,由 一组不等式解得 的范围。,3.增加新变量时的分析 主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产,数学意义是xn+1是否应进基。,方法:计算 的检验数,若,则增加,即投产有利;若,则不增加,即投产无利。,经济意义:,(1)电的影子价格是多少?使最优基仍适用的电的变化范围为何?(2)若有人愿以每度1元的价格向该
23、厂供应25度电,是否值得接受?(3)甲产品的价格在何范围内变化时,现最优解不变?,例1.16 例1.1(煤电油例)的单纯形终表如下:,(4)若现又考虑一新产品丙,其资源单耗为10,2,5,售价为6.5,问该产品是否应投产?,解:(1)电的影子价格是1.36。由解得,即是原最优基B仍适用的电的变化范围。,(2)若有人愿以每度1元的价格向该厂供应25度 电,是否值得接受?,解:(2)值得。因25在B 的适用范围内(即影子价格适用),且。,(3)甲产品的价格在何范围内变化时,现最优解不变?,综合案例:派公司的产品规划,派公司是一个生产高尔夫器材的小型公司,近期推出了高、中价位的高尔夫袋新产品(标准袋
24、和高档袋),经销商对此产品十分感兴趣,并订购了派公司下3个月的全部产品。该高尔夫袋的生产过程主要包括4道工序:切割并印染原材料、缝合、成型(插入支撑架和球棒分离装置等)、检验和包装。有关数据如表1。派公司需决定标准袋和高档袋各生产多少可使公司的总利润最大。,(1)写出此问题的线性规划模型,约束及决策变量依表1中次序;,(2)引入松弛变量(依约束次序)后用单纯形法计算得某单纯形表如表2,请填完表中空白,并判断其是否终表,如果是,请写出最优生产计划、最大利润和资源剩余;,表2,(3)写出此问题的对偶问题的模型,及对偶的最优解与最优值;(4)写出成型时间的影子价格,求使该影子价格不变的成型时间的变化
25、范围;(5)若标准袋的利润可能发生变化,则其在何范围内变化时,可使原最优计划不改变?,解:(1)设标准袋和高档袋的产量分别为,总利润为z,则模型为,是终表,最优生产计划是生产标准袋540个,高档袋252个,最大利润7668美元,缝合时间余120,检验包装余18。,(3)设对偶变量为,对偶目标为w,则对偶模型为,(4)成型时间的影子价格为6.9375;由 解得,从而,即使该影子价格保持不变的成型时间变化范围。,(5)由 和 解得,从而,即使原最优计划不改变的标准袋利润的变化范围。,教材第二章习题和参考书中有很多线性规划的习题,请尽量练习。,线性规划计算软件:CPLEX、LINGO、EXCEL,E
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 线性规划 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-3946572.html