运筹学线性规划.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+

26、0.07 x5140,000(11 x1+8 x2+10 x3+4 x4+10 x5)/56 xi 0(i=1,2,3,4,5)用单纯形法可计算出结果。,清华大学出版社,例114（配料问题）某工厂要用三种原材料 C、P、H 混合调出三种不同格的产品 A、B、D。已知产品的规格要求、产品单价、每天能供应的原材料数量及原材料单价分别见表1-28、表1-29。问该厂应如何安排生产，使利润收入为最大？,表1-28,表1-29,清华大学出版社,解：我们的目的是使利润最大，即产品价格减去原材料的价格为最大。目标函数：MaxZ=50(x1+x2+x3)+35(x4+x5+x6)+25(x7+x8+x9)-6

27、5(x1+x4+x7)25(x2+x5+x8)35(x3+x6+x9)=-15x1+25x2+15x3 30 x4+10 x5+0 x6 40 x7+0 x8 10 x9 约束条件：-1/2 x1+1/2x2+1/2x3 0-1/4x1+3/4x2 1/4x3 0-3/4x4+1/4x5+1/4x6 0-1/2x4+1/2x5 1/2x6 0 x1+x4+x7 100 x2+x5+x8 100 x3+x6+x9 60 x1，x9 0,清华大学出版社,第六节 线性规划的对偶理论与灵敏度分析一、对偶问题的提出 对偶理论是线性规划问题的最重要的内容之一。每一个线性规划（LP）必然有与之相伴而生的另一

28、个线性规划问题，即任何一个求maxZ的LP都有一个求minW的LP。其中的一个问题叫“原问题”，记为“LP”，另一个称为“对偶问题”，记为“DP”。,清华大学出版社,例117 资源的合理利用问题 某工厂在计划期内安排生产、两种产品，已知资料如表131所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？,表131,清华大学出版社,假设 x1、x2分别表示在计划期内生产产品I、II的件数，其数学模型为：,现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的工时和购买工厂的材料，为其加工生产别的产品，由客户支付工时费和材料费，此时工厂应考虑如何为每种资源定价，同样使其获得的利润最大？

29、分析问题：1、每种资源定价不能低于自己生产时的可获利润；2、定价又不能太高，要使对方能够接受。,清华大学出版社,解:设y1，y2分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金。,上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。,清华大学出版社,原问题（LP）,对偶问题（DP）,相应的矩阵形式为：,清华大学出版社,二、对偶理论1、原问题与对偶问题的关系,原问题与对偶问题之间具有如下关系：(1)原问题中的约束条件个数等于它的对偶问题

30、中的变量数；(2)原问题中目标函数的系数是其对偶问题中约束条件的右端项；(3)约束条件在原问题中为“”，则在其对偶问题中为“”；(4)目标函数在原问题中为求最大值，在其对偶问题中则为求最小值。,清华大学出版社,清华大学出版社,例119 写出下述线性规划问题的对偶问题,按照表将线性规划问题化为对偶问题,清华大学出版社,例120 写出下述线性规划问题的对偶问题,按照表将线性规划问题化为对偶问题,清华大学出版社,2、对偶问题的基本定理（1）（对称性）对偶问题的对偶是原问题。（2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则有C X(0)Y(0)b。（3）（无界性）若原问题

31、（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（4）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，且C X(0)=Y(0)b，则X(0)、Y(0)分别是它们的最优解。（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。,清华大学出版社,（6）（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。,从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：原问题与对偶问题都有最优解，且CX=Yb；一个问题

32、具有无界解，则它的对偶问题无可行解；两个问题均无可行解。,清华大学出版社,一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下结论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。,例121 已知：试通过求对偶问题的最优解来求解原问题的最优解。,清华大学出版社,解：对偶问题为,可求得对偶问题的最优解：Y*=（1，3），W=11。代入对偶约束条件，可知（1），（2），（5）式为紧约束，（3），（4）为松约束。令原问题的最优解为X*=（x1，x2，x3，

33、x4，x5），则根据互补松弛条件，必有x3=x4=0又由于，原问题的约束必为等式，即,清华大学出版社,化简为,此方程组为无穷多解令x5=0,得到x1=1，x2=2，即X*1=（1，2，0，0，0）为原问题的一个最优解，Z=11。再令 x5=2/3，得到x1=5/3，x2=0，即X*2（5/3，0，0，0，2/3）也是原问题的一个最优解，Z=11。,清华大学出版社,三、对偶问题的经济解释影子价格1、影子价格在一对LP和DP中，若LP的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量称为第i个约束条件的影子价格，又称为边际价格。,Z*=CB B-1b=Y*b=y*1b

34、1+y*2b2+y*ibi+y*mbm当bi变为bi+1时，则目标函数最优值变为：Z*=y*1b1+y*2b2+y*i(bi+1)+y*mbm所以有 Z*=Z*Z*=y*i,清华大学出版社,也可以写成：,即表示Z*对bi的变化率。其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第 i 个约束条件的影子价格。影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。资源的影子价格定量的反映了单位资源在最优生产方案中为总收益所做出的贡献，因此，资源的影子价格也可称为在最优方案中投入生产

35、的机会成本。,清华大学出版社,2、影子价格的作用（1）指出企业挖潜革新的途径影子价格0，说明该资源已耗尽，成为短线资源。影子价格=0，说明该资源有剩余，成为长线资源。（2）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给（3）可以预测产品的价格产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。,清华大学出版社,（4）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。通过以上讨论可知：只有某资源对偶解大于0，该资源才有利可图，可增加此种资源量；若某资源对偶解为0，则不增加

36、此种资源量。直接用影子价格与市场价格相比较，进行决策，是否买入该资源。,清华大学出版社,四、对偶单纯形法对偶单纯形的计算步骤：（1）根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，且检验数都为非正，则已得到最优解，停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，转（2）；,（2）确定换出变量按 对应的基变量为换出变量；,（3）确定换入变量在单纯形表中检查所在的行的系数，若所有的，则无可行解，停止计算。若存在，计算,清华大学出版社,按规则，所对应的列变量的非基变量为换入变量；,（4）以 为主元素，按单纯形法进行换基迭代，得到新的单纯形表；重复（1）（4）的步骤进

37、行计算。,例123 用对偶单纯形法求解：,清华大学出版社,对偶单纯形的优点与用途：（1）初始解可以是非可行解，当检验数都是负数时，就可以进行基变换，这样避免了增加人工变量，使运算简便。（2）对变量较少时，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。（3）用于后面的灵敏度分析。,清华大学出版社,五、灵敏度分析在前面的线性规划问题讨论中，都是假定为常数，但实际工作中这些系数往往是估计值和预测值。如市场条件发生变化，价值系数就会发生变化；当资源投入量发生改变时，也随着发生变化；当工艺条件发生改变时，也随着工艺的变化而变化。因此当这些系数有一个或几个发生变化时，已

38、求得的线性规划问题的最优解会有什么变化？或者这些系数在什么范围内变化时，线性规划问题的最优解不发生变化。因此我们在进行灵敏度分析时，要弄清楚：1）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地求得新的最优解。下面分别就各个参数改变后的情形进行讨论。例125 已知某企业计划生产3种产品A、B、C，其资源消耗与利润如表141所示。,清华大学出版社,问：如何安排产品产量，可获最大利润？解：设三种产品的产量分别为x1、x2、x3。其数学模型的标准型为 maxZ=5x1+8x2+6x3x1+x2+x3+x4=12x1+2x2+2x3+x5=20 x1,x2,x3

39、,x4,x50,清华大学出版社,该问题的初始单纯形表如表142所示。表142,清华大学出版社,经过计算得最优表如表143。表143,这时最优方案为 X=(4,8,0)T,目标值为84。,清华大学出版社,1、目标函数中的价值系数Cj的灵敏度分析（1）、非基变量的价值系数的灵敏度分析由于检验数 j=cj CBB-1 Pj，因此 的改变，只使检验数 发生改变，其它不变。如果 的改变，检验数 仍小于零时，这时对最优解方案没有影响。在例125中，如果改变，使 时，原最优方案不发生改变。若改变为10时，这时原方案已不是最优方案。这时单纯形表变为表144。,清华大学出版社,表145,单位产品C3的利润为10

40、时，则最优方案调整为 X=(4,0,8)T,目标值为100。,清华大学出版社,（2）、基变量的价值系数 的灵敏度分析如果 的改变，使全部检验数 仍小于零时，这时对最优解方案没有影响，但对最优值发生改变。在例125中，如果 改变，使,即 解得，这时原最优方案不发生改变。即单位产品A的利润在4,8之间变化时,最优方案不变，但最优值为。,清华大学出版社,若改变为10时，这时需要换基迭代。这时原方案已不是最优方案。这时单纯形表变为表146表146,清华大学出版社,表147,单位产品A的利润为10时，则最优方案调整为 X=(12,0,0)T,目标值为120。,清华大学出版社,2、资源约束数量b的灵敏度分

41、析从矩阵形式的单纯形表148中可以看出，b的变化只影响最优解的变化和最优值的变化。表148,因此，当 时，最优基不变（即生产产品的品种不变，但数量及最优值会变化）。是一个不等式组，从中可以解得b的变化范围，若B-1b中有小于0的分量，则需用对偶单纯形法迭代，以求出新的最优方案。,清华大学出版社,3、添加新变量的灵敏度分析在例125中，若新开发新产品D，该单位产品需要消耗原材料甲：3个单位，乙：2个单位，可以得利润10。问：投产产品D是否有利？,因此最优方案不变。投产产品D无利。（1）、产品D的利润为多少时，投产产品D有利？,只有 时，才能进入基，也就是说产品D才能生产，这时解得。即当 时，投产

42、产品D才有利。,清华大学出版社,4、添加新约束的灵敏度分析在例125中，假设电力供应紧张，若电力供应最多为13单位，而生产产品A、B、C每单位需电力分别为2、1、3个单位，问该公司生产方案是否需要改变？解：先将原问题的最优解x14，x28，x30代入电力约束条件2x1+x2+3x313。因为，故原问题最优解已经不是新约束条件下的最优解。在电力约束条件中加入松弛变量得2x1+x2+3x3x613以x6为基变量，将上式反映到最终单纯形表中得到表153,清华大学出版社,表153,在表153中，x1、x2、x6为基变量，因此所对应的列向量应为单位向量，因此经计算得表154。表154,清华大学出版社,利

43、用对偶单纯形法计算得表155表155,增加电力约束后，这时生产方案为：生产A产品1件，生产B产品9件。目标值为82。,清华大学出版社,5、技术系数改变(计划生产的产品工艺结构发生改变)（1）、非基变量的工艺发生改变当 是非基变量 的系数时，它的变化不会改变,它只影响单纯形表 列，只是对检验数有影响，也就是看检验数是大于零还是小于零，利用新增变量的灵敏度分析的类似方法解决。,2、基变量的工艺发生改变当 是基变量 的系数时，它的变化会使发生改变，所以最终单纯形表 也要发生变化，若在例125中，生产产品A的工艺发生改变，生产产品A对甲、乙原材料的需求分别为2，2。单位产品的利润不变，问最优方案如何变

44、化？,清华大学出版社,先计算,最终单纯形表变为表158。,清华大学出版社,第七节 运输问题,一、运输问题的数学模型 在经济建设中，经常会遇到大宗物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资,在全国有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。这类问题可用以下数学语言来描述：,清华大学出版社,运输问题：假设有m个生产地点，可以供应某种物资(以后称为产地)，用Ai表示，i=1,2,m；有n个销售地，用Bj表示，j=1,2,n；产地的产量和销售地的销售量分别为ai,i=1,2,m和bj，j=1,2,n，从Ai到Bj运输单位物资的运价为cij，

45、这些数据可汇总于如表163。,表163,清华大学出版社,要求使总运费最小的调运方案。如果运输问题的总产量等于其总销量，即,则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。下面建立在产销平衡情况下的运输问题的数学模型。解:假设 xij 表示从Ai到 Bj 的运量,则所求的数学模型为:,清华大学出版社,在该模型中，目标函数表示运输总费用，要求其极小化；第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；第二个约束条件表示由某一产地运往销地的物品数量之和等于该产地的产量；第三个约束条件表示变量的非负条件。,清华大学出版社,二、表上作业法,表上作业法是单纯形法在求

46、解运输问题时的一种简化方法，其实质是单纯形算法。只是具体计算和术语有所不同，可归纳为：（1）找出初始基可行解，即在(mn)产销平衡表上给出m+n-1个有数字的格，这些有数字的格不能构成闭回路，且行和等于产量，列和等于销售量；（2）求各非基变量的检验数，即在表上求出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。（4）重复（2）、（3）步，直到求得最优解为止。以下我们就具体给出求解运输问题表上作业法的计算步骤。,清华大学出版社,（1）、确定初始基可行解确定初始基可行解即首先给出初始的调运方案，

47、方法很多，我们只介绍其中的两种方法：方法一：最小元素法：最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。下面由例题来说明最小元素法确定初始基可行解的具体步骤。例127：某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表167所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。,清华大学出版社,表167,解：第一步：从单位运价表中找出最小运价为1，这表示先将 A2 的产品供应给 B1。由于A2 每天生产4吨，B1 每天只需要 3

48、吨，即 A2 除每日能满足B1 的需要外还余1吨。因此在产销平衡表(A2,B1)交叉处填上3，表示 A2 调运3吨给B1，再在单位运价表中将B1 这一列运价划去，表示 B1 的需求已满足，不需要继续调运(即x21=3=min(a2,b1)=min(4,3)。,清华大学出版社,第二步:从上述未划去的单位运价表的元素中找出最小的运价2，即A2 把剩余的产品供应给B3；B3 每天需要5 吨，A2 只剩余 1 吨，因此在上述产销平衡表的(A2,B3)交叉处填上 1，划去上述运价表中A2 这一行运价，表示 A2的产品已分配完毕。,第三步:从上述第二步所得的单位运价表未划去的元素中找出最小元素为 3。这表

49、示将 A1 的产品供应 B3，A1 每天生产7 吨，B3 尚缺 4 吨，因此在产销平衡表的(A1,B3)交叉处填上 4，由于B3 的需求已满足，将单位运价表中的 B3 这一列运价划去。如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个方案的总运费为 86 元，如表所示。,清华大学出版社,清华大学出版社,方法二、伏格尔法：最小元素法的缺点是，为了节省一处的费用，有时造成在其它地方要花多几倍的运费。伏格尔法考虑到，一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。因

50、此，对于差额最大处，就优先采用最小运费调运。我们还是用例127 来说明伏格尔法的具体实施过程，步骤如下：,第一步：在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格位置相应填入该列的次小运费与最小运费之差，我们称之为列差额。如此可得表173。,清华大学出版社,表173,清华大学出版社,第二步：从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素。比较该元素所在的行和列的产量，取它们最小者填入产销平衡表相应的位置。同时在单位运价表中划去一行或一列。由于B2 的列差额最大。B2 列中最小元素为 4（即 A3 行），可确定 A3 产品优先供