运筹学线性规划.ppt
《运筹学线性规划.ppt》由会员分享,可在线阅读,更多相关《运筹学线性规划.ppt(154页珍藏版)》请在三一办公上搜索。
1、清华大学出版社,赵立强,管理运筹学教程,清华大学出版社,第一章 线性规划 线性规划是运筹学的一个重要分枝。自1947年美国数学家丹捷格()提出了求解线性规划问题的方法单纯形法之后,线性规划在理论上趋于成熟,在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后,它的适用领域更加广泛。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥重要作用;从范围来看,小到一个小组的日常工作和计划安排,大至整个部门以致国民经济计划的最优方案的提出,都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点
2、,是现代管理科学的重要基础和手段之一。,清华大学出版社,第 一 节 线性规划问题及其数学模型一、线性规划问题的数学模型线性规划问题主要解决以下两类问题:1、任务确定后,如何统筹安排,做到应用尽量少的人力和物力资源来完成任务;2、在一定量的人力、物力资源的条件下,如何安排、使用他们,使完成的任务最多。在生产管理和经济活动中,经常会遇到线性规划问题,如何利用线性规划的方法来进行分析,下面举例来加以说明。,清华大学出版社,例11:(计划安排问题)某工厂在计划期内安排生产、两种产品,已知生产单位产品所占用的设备A、B的台时、原材料的消耗及两种产品每件可获利润见表所示:,问如何安排计划使该工厂获利最多?
3、,清华大学出版社,解:假设 x1、x2分别表示在计划期内生产 产品I、II的件数。该问题可用如下 数学模型表示为:目标函数:Max Z=2x1+3x2 约束条件:,清华大学出版社,例12(成本问题)某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A,B两处运回原油提炼,已知两处的原油成分含量见表12;又已知从A处采购的原油价格为每吨(包括运费)200元,B处采购的原油价格为每吨(包括运费)290元,问:该炼油厂该如何从A,B两处采购原油,在满足供应合同的条件下,使购买成本最小。表12,产品来源,成分,清华大学出版社,分析:很明显,该厂可以有多种不同的方案从
4、A,B两处采购原油,但最优方案应是使购买成本最小的一个,即在满足供应合同单位的前提下,使成本最小的一个采购方案。解:设分别表示从A,B两处采购的原油量(单位:万吨),建立的数学模型为:,清华大学出版社,以上两个例子,从数学上来讲,我们会发现此数学模型具有如下特点:(1)有一组非负的决策变量(decision or control variable);(2)有一组约束条件:含有决策变量的线性不等式(或等式)组(linear function constraints);(3)有一个含有决策变量的线性目标函数(objective linear function),按研究问题的不同,要求目标函数实现最
5、大化或最小化。我们把满足上述三个条件的数学模型称为线性规划的数学模型。其一般形式如下:,清华大学出版社,在该数学模型中,方程(1.1)称为目标函数;(1.2)称为约束条件;(1.3)称为变量的非负约束条件。,清华大学出版社,二、线性规划问题的标准型 由前面所举的例子可知,线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的;约束条件可以是“”形式、“”形式的不等式,也可以是等式。决策变量有时有非负限制,有时没有。这种多样性给讨论问题带来了不便。为了便于今后讨论,我们规定线性规划问题的标准型为:,清华大学出版社,标准型具有如下特点:(1)目标函数求最大值;(2)所求的变量都要求
6、是非负的;(3)所有的约束条件都是等式;(4)常数项非负。综合以上的讨论可以说明任何形式的线性规划问题都可以通过上述手段把非标准型的线性规划问题化成标准型。现举例如下:,清华大学出版社,例14 试将如下线性规划问题化成标准型,解:令 x3=x4-x5,x4,x5 0,(1)式左端加上非负松弛变量 x6;(2)式左端减去非负剩余变量 x7,则可将上述线性规划问题化成如下的标准型:,清华大学出版社,第二节 线性规划问题的图解法及几何意义,一、线性规划问题的解的概念 在讨论线性规划问题的求解之前,先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为(1.6)、(1.7)、(1.8)式
7、所示:,清华大学出版社,1.可行解:满足约束条件(1.7),(1.8)的解 X=(x1,x2,xn)称为线性规划问题的可行解;所有可行解的集合称为可行解集或可行域。2.最优解:满足约束条件及目标函数(1.6)的可行解称为线性规划问题的最优解。3.基:假设 A 是约束方程组的系数矩阵,其秩数为 m,B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0),则称 B 是线性规划问题的一个基。基B的第j列 Pj(j=1,2,m)称为基向量,与基向量 Pj 相对应的变量xj(j=1,2,m)称为基变量,否则称为非基变量。,T,清华大学出版社,为了进一步讨论线性规划问题的解,下面研究约束方程
8、组(1.7)的求解问题。假设该方程组系数矩阵 A 的秩为 m,因 m n,所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的,这时(1.7)式可改写为:现若令(1.9)式中的非基变量xm+1=xn=0,并用高斯消去法求出一个解X=(x1,x2,xm,0,0),这个解的非0分量的数目不大于方程的个数m,这时称X为基本解。,T,清华大学出版社,4.基本可行解:满足非负条件(1.8)的基本解称为基本可行解。由此可见,基本可行解的非0分量的数目不大于m,并且都是非负的。5.可行基:对应于基本可行解的基称为可行基。由此可见,满足约束方程组(1.7)的基本解的数目至多是 Cnm 个。一般地讲,
9、基本可行解的数目要小于基本解的数目,至多相等。以上提到的几种解的概念,可用图14来表示:,清华大学出版社,二、线性规划问题的图解法 对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们可以通过图解法对它进行求解。我们以例11具体给出求解的方法。例15 用图解法求解线性规划问题 max Z=2x1+3x2,清华大学出版社,解:对于上述具有两个变量的线性规划问题,图1-2中的OABCD部分描述了满足约束条件的区域;虚线为目标函数Z=2x1+3x2的等值线。沿箭头方向移动目标函数的等值线,平移等值线直至与可行域OABCD相切或融合为一条直线,此时就得到最优解为B点,其坐标可通过解方程组得到
10、:2x1+2x2=14 3x2=15 解得:x1=2 x2=5这就是本线性规划问题的最优解。此时相应的目标函数的最大值为:Z=22+35=19,清华大学出版社,例17 maxZ=2x1+4x2 s.t.2x1+x2 8-2 x1+x2 2 x1,x2 0解:由于可行域无界,作目标函数等值线,如图14中虚线所示,并用箭头标出其函数值增加的方向,由此可以看出,该问题无有限最优解。若目标函数由 max Z=2x1+4x2 改为 min Z=2 x1+4 x2,则可行解所在的范围虽然无界,但有最优解 x1=4,x2=0,即(4,0)点。,清华大学出版社,通过以上各题图解法所得结论可以看出:(1)线性规
11、划的所有可行解构成的可行域一般是凸多边形,有些可行域可能是无界的;(2)若存在最优解,则一定在可行域的某顶点得到;(3)若在两个顶点上同时得到最优解,则在这两点的连线上的任一点都是最优解。(4)若可行域无界,则可能发生最优解无界的情况;(5)若可行域是空集,此时无最优解。上述理论具有普遍意义,对于两个以上变量的线性规划问题都是成立。图解法虽然具有直观、简便等优点,但在变量多的情况下,即在多维的情况下,它就无能为力了。因此,需要介绍一种代数方法单纯型法,为了以后介绍方便,需要研究一下线性规划问题解的概念。,清华大学出版社,三、基本定理 1.凸集:假设K是n维欧氏空间的一个点集,若对于K中的任意两
12、点X1、X2,其连线上的所有点X1+(1-)X2,(0 1)都在集合K中,即:X1+(1-)X2 K(0 1)则称K为凸集。从直观上讲,凸集无凹入部分,其内部没有洞。2.凸组合:设X1,X2,Xk是n维欧氏空间En中的k个点,若存在1,2,k,且0 i 1,i=1,2,k,i=1,使X=1X1+2X2+kXk,则称X为由X1,X2,Xk所构成的凸组合。3.顶点:假设K是凸集,X K;X若不能用不同的两个点X1、X2 K的线性组合表示为:X=X1+(1-)X2,(0 1)则称X为凸集K的一个顶点(或称为极点)。顶点不位于凸集K中的任意不同两点的连线内。,清华大学出版社,定理1.1 若线性规划问题
13、存在可行域,则其可行域:D=X|AX=b,X 0,是凸集。引理1.1 线性规划问题的可行解X为基本可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。定理1.2 线性规划问题的基本可行解对应于可行域的顶点。定理1.3 若可行域有界,则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解。定理1.4 若线性规划问题在k个顶点上达到最优解(k2),则在这些顶点的凸组合上也达到最优解。,清华大学出版社,第 三 节 单纯形算法 单纯形算法的基本思路是:根据问题的标准型,从可行域中某个基本可行解(顶点)开始,转换到另一个基本可行解(顶点),并使得每次的转换,目标函数值均有所改善,最终达到最
14、大值时就得到最优解。现在需要解决的问题是:(1)为了使目标函数逐步变优,应如何从可行域的一个顶点转移到可行域的另一个顶点?(2)目标函数何时达到最优值?判断标准是什么?,清华大学出版社,1确定初始基可行解从中一般可以直接观察到存在一个初始可行基B=(P1,P2,Pm)(1.10)当线性规划的约束条件均为“”形式的不等式时,可以利用标准型的方法,在每个约束条件的左端加上一个松弛变量,其松弛变量的系数矩阵即为单位矩阵;对于约束条件为“”形式的不等式或等式时,若不存在单位矩阵,就采用构造人造基的办法,关于这个方法将在本章第四节讨论。,清华大学出版社,(1.10)式中的P1,P2,Pm称为基向量,在约
15、束条件中把非基变量项移到等式的右边得:,(1.11),令所有非基变量,得 X=(b1,b2,bm,0,0)又由于,故X满足约束条件,所以它是一个基可行解。,T,清华大学出版社,2最优性检验 假定已求得(LP)的一个基本可行解 X(0),假设:目标函数用非基变量表示的形式。,(1.14),其中,称为各非基变量 的检验数。,清华大学出版社,定理1.5 最优解判别定理:若 为对应于基 B 的基本可行解,且对于一切,有 j 0,则 X 为线性规划问题的最优解。定理1.6 无穷多最优解判别定理:若 为对应于基 B 的基本可行解,且对于一切,有 j 0,又存在某个非基变量的检验数,则线性规划问题有无穷多最
16、优解。定理1.7 无有限最优解判别定理:若 为对应于基 B 的基本可行解,有一个,而对于有,则线性规划问题无有限最优解(也称为无最优解)。,(0),清华大学出版社,3.基变换 若上面所求的基可行解还不是最优解,下面我们将介绍,如何通过基变换,求一个新的可行解?(1)换入变量的确定 当某些非基变量的检验数j 0时,如果xj增加,则目标函数值还可以增加。当有两个或两个以上j 0时,为了使目标函数值增加的最快,我们一般选择j 0中的最大者,即:j=max ll 0 j所对应的变量xj为换入变量(就是下一个基的基变量)。,(0),清华大学出版社,(2)换出变量的确定 确定换出变量的原则是保持解的可行性
17、。这就是说,要使原基本可行解的某一个正分量xj变为0,同时保持其余分量均非负。具体实现是按“最小比例原则”进行,也称原则。若 则选基变量xl为换出变量。(3)旋转运算(迭代运算)在确定了换入变量xj与换出变量xl之后,要把xj和xl的位置对换,称alj为旋转元。,清华大学出版社,例18 利用单纯形算法求解例11的线性规划问题。Max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 4x1+x4=12 2x1+2x2x5=14 x1,x2,x3,x4,x50解:(1)由标准型得到初始单纯形表:,清华大学出版社,(2)max1,2=3=2,所以x2为换入变量。(3)因为1=2
18、,2=3都大于0,且p1,p2的坐标有正分量存在因为5与x3那一行相对应,所以x3为换出变量;故x2对应列与x3对应行的相交处的3为主元素;(4)以“3”为主元素进行旋转计算,进行行初等变换,得表15:表15,清华大学出版社,重复以上步骤得表16。表16这时,检验数全部小于等于0,即目标函数已不可能再增大,于是得到最优解:X*=(2,5,0,4,0)目标函数的最大值为:Z*=19,T,清华大学出版社,例1-10,清华大学出版社,例10,清华大学出版社,清华大学出版社,退化,清华大学出版社,第四节 单纯形算法的进一步讨论一、初始基本可行解的确定 利用单纯形算法的一个根本前提是要有一个初始的基本可
19、行解。如果不得到初始的基本可行解时2.对于 AX=b,并且不能够从中观测到一个单位矩阵。这时分别给每一个约束条件加入一个人工变量 xn+1,xn+m,得:由此可以得到一个m阶单位矩阵。以xn+1,xn+m为基变量,令非基变量x1,xn 为0,便可得到一个初始基本可行解X。,(0),清华大学出版社,引入人工变量问题解的判定,若经过基的变换,基变量中不再包含有人工变量,表明原问题有基可行解。若经过基的变换,当所有的检验数都=0时,在基中至少还有一个人工变量,表明原问题无可行解,更无最优解。,清华大学出版社,二、人工变量法(大M法)对于加入人工变量的线性规划问题的目标函数如何处理?我们希望人工变量对
20、目标函数取值不受影响。因此只有在迭代过程中,把人工变量从基变量中换出,让它成为非基变量。为此,就必须假定人工变量在目标函数中的价值系数为(-M)(对于极大化目标),M为充分大的正数。这样,对于要求实现目标函数最大化的问题来讲,只要在基变量中还存在人工变量,目标函数就不可能实现最大化。这就是大M法。以下举例加以说明。,清华大学出版社,例1-11 试用大M法求解如下线性规划问题的最优解。解:在上述问题中加入松弛变量,剩余变量和人工变量得:这里M是一个充分大的正数,取基变量为 x4,x6,x7,可得如下的表115。利用表115得初始单纯形表,单纯形算法得表116 表119。,清华大学出版社,表115
21、,由于x4,x6,x7为基变量,因此它们对应的检验数行的检验数应为0,经变换得初始单纯形表116。初始单纯形表116,清华大学出版社,表119,在表119中,所有的 j 0,故得到最优解:X*=(4,1,9,0,0,0,0)目标函数值 Z=2,原问题的最优目标值为:Z*=-2。,T,清华大学出版社,三、两阶段法:这种方法是在约束条件中加入人工变量,将线性规划问题分为两阶段进行求解。第一阶段是先求出基本可行解(或判断出原线性规划问题无解),第二阶段利用已求出的初始基本可行解来求最优解。具体由如下定理1.8给出。定理1.8 设原线性规划问题记成(LP),由它而引入的新的线性规划问题记成(LP)*。
22、分别表示如下:,清华大学出版社,若(LP)*具有最优基本可行解 则(LP)是可行的,而 即为(LP)的一个基可行解。2)若(LP)*的最优基本可行解 则(LP)必不可行。,定理1.8的具体应用过程是:由(LP)*判断原线性规划问题是否存在基本可行解,利用单纯形算法,若得到 W=0,即所有人工变量为非基变量,这表示原问题已得到了一个基本可行解。于是只需要将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字,就得到了求解原问题的初始计算表,再进行第二阶段的求解。若第一阶段的最终计算表出现 W 0,这就表明原问题无可行解,应停止计算。各阶段的计算方法及步骤与前述单纯形法完全相同,下面用
23、例子说明该方法的应用。,清华大学出版社,例112 试用两阶段法求解如下线性规划问题,清华大学出版社,解:先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量,给出第一阶段的线性规划问题:以x4,x6,x7 为基变量得如下初始表120。表120,清华大学出版社,重复以上步骤得表16。表123,这里 x6、x7 是人工变量。第一阶段我们已求得 W=0,最优解 x5=0,x6=0,x7=0。因人工变量 x6=x7=0,所以(0,1,1,12,0)T 是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表123中的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算
24、检验数行,可得如下第二阶段的初始单纯形表;应用单纯形算法求解得最优解。,清华大学出版社,第五节 应用举例 线性规划的应用非常广泛,特别是在经济管理领域有大量的实际问题可以归纳为线性规划问题来研究,有些问题,它的背景不同,表现各异,但它们的数学模型却有着完全相同的形式。尽可能多地掌握一些典型模型不仅有助于深刻理解线性规划本身的理论,而且有利于灵活地处理千差万别的问题,提高解决实际问题的能力。下面举例说明线性规划在经济管理方面的应用。,清华大学出版社,例113(投资问题)已知某集团有1,000,000元的资金可供投资,该集团有五个可供选择的投资项目,其中各种资料如下:,表1-27,该集团的目标为:
25、每年红利至少是80,000元,最低平均增长率14%,最低平均信用度为6,该集团应如何安排投资,使投资风险最小?,清华大学出版社,解:设xi表示第 i项目的投资额 i=1,2,3,4,5,目标是投资风险最小化,因此目标函数为:min z=(0.1x1+0.06x2+0.18x3+0.12x4+0.04x5)数学模型为:min z=0.1x1+0.06x2+0.18x3+0.12x4+0.04x5 x1+x2+x3+x4+x5=1,000,000 0.05 x1+0.08 x2+0.07 x3+0.06 x4+0.1 x5 80,000 0.1x1+0.17 x2+0.14 x3+0.22 x4+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 线性规划
链接地址:https://www.31ppt.com/p-5319903.html