运筹学线性规划.ppt

1、Operations Research 运筹学（OR）,主讲：邢延铭,管理科学与工程学院信息管理及信息系统,第一章 线性规划,1,一、线性规划（Linear Programming),1947年由美国人丹齐克（Dantzing）提出,线性,x,y,O,x+y=1,1,1,x=2,y=3,2,3,规划,LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。 LP有三个要素: 决策变量、目标函数、约束条件,二、 LP的数学模型难点,例题1生产计划问题,美佳公司计划制造I、II两种家电产品。已知各制造一件时分别占用设备

2、A、B的台时、调试时间、调试工序每天可用于这种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使其获取的利润最大。,该计划的数学模型,目标函数 Max Z = 2x1 + 1x2 约束条件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,x1,x2,例2 营养配餐问题,假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择(当然可以扩充到n种食品），它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分

3、表,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为： min Z=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 0,例3. 运输问题,某名牌饮料在国内有三个生产厂，分布在城市A1、A2, A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问

4、题，求运费最小的调运方案。,(1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数。则运费最小的目标函数为 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件。产量之和等于销量之和,故要满足： 供应平衡条件,x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3,销售平衡条件,x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=1,非负性约束 xij0 (i=1,2,3；j=1,2,

5、3,4),例4.仓库租用问题 捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表1.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小.,表1,表2,解:1)设决策变量xij表示捷运公司在第i(i=1,2,3,4)个月初签订的租借期为j(j=1,2,3,4)个月的仓库面积的合同(单位为100m2). 因5月份起该

6、公司不需要租借仓库,故x24,x33,x34,x42,x43,x44均为零,2)目标函数:使总的租借费用最小,3)约束条件:每个月份所需仓库面积的限制,s.t.,例5.合理下料问题,合理下料问题（Reasonably Cutting Problem）某型号的圆钢8米长，需截取长2.5米、长2.0米、长1.3米的毛坯分别为100根、150根、200根。 问： 如何下料，才能既满足需求，又使总用料最少 如何下料，才能既满足需求，又使总余料最少,此型号的圆钢8米长，截取的方案有：,四、线性规划的一般形,线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化和极小化； 约束条件有“”、“”和“”

7、三种情况； 决策变量一般有非负性要求，有的则没有。,为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。 标准形式为： 目标函数极大化， 约束条件为等式， 右端常数项bi0， 决策变量非负。,五、线性规划问题的标准形式,标准形式为:,目标函数最大 约束条件等式 决策变量非负 右端常数非负,目标函数极小化问题 minZ=CX，只需将等式两端乘以 -1 即变为极大化问题。 右端常数项非正 两端同乘以 -1 约束条件为不等式 -当约束方程为“”时，左端加入一个非负的松弛变量； -当约束条件为“”时，左端减去一个非负的剩余变量。 决策变量xk无约束 令xk=xk-x k，xk，x k

8、 0，用xk、x k 取代模型中xk 决策变量xk0 令xk=-xk,显然xk 0,非标准型向标准型转化,例：目标函数 Max Z = 2x1 + 1x2 约束条件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,化为标准型：目标函数 Max Z = 2x1 + 1x2 约束条件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,+0 x3+0 x4+0 x5,Max,例 2：,解 ：化为标准形为,作业：习题1.2中的（1）（2）,简写为,用矩阵表示,C价值向量 b资源向量 X决

9、策变量向量 A技术矩阵 P 技术向量,用向量表示,六、线性规划的图解法,由中学知识可知：y=ax+b是一条直线，同理：Z=2x1+x2x2=Z-2x1也是一条直线，以Z为参数的一族等值线。 5x2 15 x2 3 是直线 x2=3 下方的半平面。 所有约束的半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。,例：目标函数 Max Z = 2x1 + 1x2 约束条件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,目标函数 Max Z = 2x1 + 1x2,可以先假设 2x1 + 1x2=4,再假设 2x1 + 1x2=6,2

10、x1 + 1x2=8,由图中可知目标函数相交于Q2这一点上，由6x1 + 2x2 = 24 x1 + x2 = 5 联合求解得到为（x1,x2)=(3.5,1.5),则目标函数为z=8.5,图解法求解步骤,由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的移动方向； 平移目标函数的等值线，平行线移出可行域之前的最后一个交点，就是最优点，算出最优值。,七、线性规划问题求解的 几种可能结果,1、唯一最优解（见上页） 2、多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。,3、无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏

11、必要的约束条件）,4、无解（或无可行解）：若约束条件相互矛盾，则可行域为空集。,图解法的几点结论:（由图解法得到的启示）,可行域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,练习：用图解法求解LP问题,图解法 （练习）,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,可行域,A,B,C,D,E,图解法 （

12、练习）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),34x1 + 40 x2 = 272,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),图解法 （练习）,x2,18 16 14 12 10 8 6 4 2 0,| 246810121

13、41618,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,(0,6.8),最优解 (3,6),4x1+ 6x2=48 2x1+ 2x2 =18,1.3线性规划解的概念及基本定理,可行解：满足约束条件AX=b,X0的解。 最优解：使目标函数最优的可行解，称为最优解。,基 mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。 若B是矩阵A中mm阶非奇异子矩阵（B0），则B是线性规划问题的一个基。不妨设：, j=1，2，,m 基向量。 ，j=1，2，,m 基变量。 , j=

14、m+1,n 非基变量。,线性方程组的增广矩阵,例LP的标准型 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0,基矩阵： 系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。 或称为一个基，用B表示。 称基矩阵的列为基向量，用Pj表示(j=1,2,m) 。,的基矩阵B，如下：,基变量： 与基向量Pj相对应的m个变量xj称为基变量， 其余的n-m个变量为非基变量。 基解： 令所有非基变量等于零，对m个基变量所求的解， 对应一个

15、特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。,基变量是x3, x4, x5 非基变量是x1, x2 令非基变量x1=x2=0，得到一个基解 x3=8，x4=12， x5=36,基可行解：满足非负性约束的基解称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优基：最优解对应的基矩阵，称为最优基。,非 可 行 解,可 行 解,基 解,例：求基解、基可行解、最优解。,最优解,解：,二、凸集及其顶点,凸集概念： 设D是n维线性空间Rn的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。 即：若D中的任意两点x(1),x(2) D，存在01 使得

16、 x= x(1)+(1- )x(2) D,则称D为凸集,顶点:若K是凸集，XK；若X不能用不同的两点的线性组合表示为： 则X为顶点.,凸集,三、几个基本定理的证明,证明:,定理1: 若线性规划问题存在可行域, 则其可行域: 是凸集.,只要验证X在D中即可,引理：可行解X为基可行解 X的正分量对应的列向量线性无关,定理3：若可行域有界，线性规划 问题的目标函数一定可以在 其可行域的顶点上达到最优。,定理2：线性规划问题的基可性解X 对应于可行域D的顶点。,几点结论：,线性规划问题的可行域是凸集。 基可行解与可行域的顶点一一对应，可行域有有限多个顶点。 最优解必在顶点上得到。,1.4单纯形法的基本

17、原理,单纯形法(Simplex Method)是美国人丹捷格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。,例1的标准型 ： 目标函数 Max Z = 2x1 + 1x2+0 x3+0 x4+0 x5 约束条件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,LP的代数方法,定理1.线性规划问题如果存在可行域，则其 可行域一定是一个凸集。 定理2.线性规划问题的基可行解与凸集顶点是一一对应的。 定理3.线性规划问题如果存在最优解，则一定存在一个基可

18、行解是最优解。（或者说最优解如果存在，一定出现在凸集的顶点上）。,线性规划问题求最优解思路,step1.找到一个初始的基可行解。 step2.判断是否最优。 如果最优，则结束。否则转step3。 Step3.转到与初始基可行解相邻的下一个基可行解，转化时应遵循目标函数值增大的原则。,1.确定初始基可行解,对标准型线性规划问题 在约束中总存在一个单位矩阵 我们以这个单位矩阵为基矩阵，令非基变量都=0，得到一个初始基解 因为b=0，所以这个基解是一个基可行解。,标准形式为:,2.从一个基可行解转换为相邻的基可行解,定义：如果两个基可行解之间的变换只需要变换一个基变量，则称这两个基可行解相邻。,3.

19、最优性检验,将两个基可行解分别带入目标函数中得：,代入目标消去基变量，得到非基变量xj的检验数 j。,判断最优（即规则） 会出现以下四种情况： （1）若对于一 切非基变量的解指数j均有j 0 则当前基本 可行解为最优解。 （2）若所有非基变量的检测验数 j 0，其中某个基变量的检验数 k=0，而该变量的系数列向量Pk中存在正分量，则说明该问题在两个顶点上同时达到最优，该问题有无穷多最优解。,（3）若某个非基变量XK的检验数k 0，但其对应的列向量PK中，每一个元素aik(I=1,2,3m)均为非正数，这时该线性规划问题无解。 （4）若存在非基变量检验数k 0，其对应的系数列向量Pk中，至少有一

20、个aik0,则问题还没有得到最优解，应进行下步。,基变换,（1）换入变量的确定 以k对应的非基变量xk做为换入变量，当然任选也可以，或选取脚标最小的一个 （2）换出变量的确定 改进目标 换入变量xk原是非基变量，取值为0，现在将其作为基变量，取值为正。要保持除xk以外的原非基变量继续为0，迫使某个原基变量为0，当xk取值超过任一bi/aik时，将使第i个基变量xBi0，就破坏了非负性约束条件。所以，比值i=bi/aik表示用xk去替换xBi时的取值限度，为保持解的可行性，取,即原其变量xl出基，为了表示清楚用Xbl表示换出变量，即规则 若不存在, 则Z，没有有限最优解。,主元变换（迭代或旋转变

21、换） xk进基， xl出基，其相应的系数列向量分别是,为了使Xk和XBl进行对换，须把Pk变为单位列向量，这可以通过系数矩阵的初等变换变来完成,1,alk,将上式中的第L行除以alk,得到,用第I行减去aik与上式的乘积，各行元素的变换关系式为,变换后新的增广矩阵为：,这样就进行了一次新的变换。另非基变量都为0，就会得到新的一组其可行解。,LP的表格法,表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。,一、单纯形法表,将线性规划问题化成标准型。 找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。 计算各非基变量xj的检验数j=Cj-CBB-1Pj ，若所有j0，

22、则问题已得到最优解，停止计算，否则转入下步。 在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无解，停止计算，否则转入下步。 根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik| aik0=bl/ alk 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。 以alk为主元素进行迭代，把xk所对应的列向量变为单位列向量，即alk变为1，同列中其它元素为0，转第 步。,二、单纯形法的计算步骤,三、单纯形法计算举例,例：目标函数 Max Z = 2x1 + 1x2 约束条件 5x2 15 6x1 + 2x2 24 x

23、1 + x2 5 x1、 x2 0,化为标准型：目标函数 Max Z = 2x1 + 1x2+0 x3+0 x4+0 x5 约束条件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,填入初始单纯形表,最优解 :X*=(3.5,1.5,7.5,0,0)T，Z*=8.5,表准化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x1 , x2 , x3, x4 0,此时，检验数2=11 0，还没有得到最优解。 确定x2进基，但x2所在列的系数向量元素非正，无界

24、 值不存在，有进基变量但无离基变量。,1.5人工变量问题,一、人工变量,用单纯形法解题时，需要有一个单位阵作为初始基。 当约束条件都是“”时，加入松弛变量就形成了初始基。 但实际存在“”或“”型的约束，没有现成的单位矩阵。,问题：线性规划问题 化为标准形时，若约束 条件的系数矩阵中不存 在单位矩阵，如何构造 初始可行基？,采用人造基的办法：人工构造单位矩阵 在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。 人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。,加入 人工变量,设线性规划问题的标准型为：,系数矩阵为 单位矩阵， 可构

25、成初始 可行基。,约束条件已改变， 目标函数如何调整？,“惩罚” 人工变量！,（1）大M法 （2）两阶段法,一、大 M 法,人工变量在最大化的目标函数中的系数为 M（最小化的为+M）, 其中，M 为任意大的正数。,目标函数中添加“罚因子” 最大化-M（M是任意大的正数） 为人工变量系数，只要人 工变量0，则目标函数 不可能实现最优。,例: 求解线性规划问题,加入松弛变量和剩余变量,化成标准型,加入人工变量构造初始可行基.,求解结果出现检验数非正 若基变量中含非零的人工变量， 则无可行解； 否则，有最优解。,用单纯形法求解（见下页）。,目标函数中添加“罚因子” -M为人工变量系数，只要人 工变量

26、0，则目标函数 不可能实现最优。,表1（初始单纯形表）,主元,表2,主元,表3,主元,表4,最优解为 目标函数 值 z=2,检验数均非正，此为最终单纯形表,M在计算机上处理困难。 分阶段处理 先求初始基，再求解。,二、两阶段法,第一阶段: 构造如下的线性规划问题,加入人工变量 后的系数矩阵 为单位矩阵， 可构成初始 可行基。,目标函数仅含人工变量，并要求实现最小化。 若其最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。,用单纯形法求解上述问题,若=0,进入第二阶段,否则,原问题无可行解。 第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。

27、用单纯形法求解即可。,下面举例说明，仍用大M法的例。,例：,加入松弛变量和剩余变量,化成标准型,解：,构造第一阶段问题并求解,注意，此时目标函数不满足标准型条件，所以应将目标函数也化成标准型 用单纯形法求解,（第一阶段、求min ）,表1,主元,1 0 0 0 -1 1 0 0 0,0 -1 0,0 0 -1,x4 x5 x6,（第一阶段、求min ）,表2,主元,1 -2 2 0 -1 1 0 0 0,0 0 -1,0 0 -1,x4 x5 x6,（第一阶段、求min ）,表3：最终单纯形表,进 入 第 二 阶 段,不含人工变量且=0,第二阶段,将去掉人工变量， 还原目标函数系数，做 出初始

28、单纯形表。,1 0 0 0 -1,1/3 -2/3 0 -1 2/3 -4/3,0 0,x4 x5,第二阶段,0 0 0 -1/3 -1/3,最优解为 目标函数 值 z=2,最优基,x3,x1,x2,最优基的逆,LP补遗,进基变量相持： 单纯形法运算过程中，同时出现多个相同的j最大。 在符合要求的j(目标为max：j0，min：j0)中，选取下标最小的非基变量为换入变量；,离基变量相持： 单纯形法运算过程中，同时出现多个相同的最小值。 继续迭代，便有基变量为0，称这种情况为退化解。 选取其中下标最大的基变量做为换出变量。,多重最优解： 最优单纯形表中，存在非基变量的检验数j=0。 让这个非基变

29、量进基，继续迭代，得另一个最优解。,无界解： 在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解。,无可行解： 最终表中存在人工变量是基变量。,1.6单纯形法矩阵描述,为进一步加深对单纯形法的理解以及为对偶理论和灵敏度分析打基础，现在用矩阵形式描述单纯形法的求解过程。前面讲过线规划标准型的矩阵表达式为,对于上式移项得,再左乘以B-1,代入目标函数得,单纯形表的矩阵形式,例：,(1)、, 1 =C1 - CB B-1P1 =40 -(0 0 50) = 40 -(0,0,25) =40, A= C - CB B-1A=(40, 50, 0, 0, 0)- (0, 0, 50)

30、 =(40, 50, 0, 0, 0) -(0 0 25) = (40, 50, 0, 0, 0) -(0, 50, 0, 0, 25) = (40, 0, 0, 0, -25),1 2 1 0 0 3 2 0 1 0 0 2 0 0 1,1 2 1 0 0 3 2 0 1 0 0 2 0 0 1,B1-1,B2-1,B3-1,(1)、只须存贮原始数据A、B、C，每步需知B-1 。,(2)、每步必须计算的数据, 当某个 m+k 0时，需关键列：,1.6单纯形法小结,基本概念,线性规划模型 三个要素： 决策变量、目标函数、约束条件 线性性 线性规划解的性质 线性规划问题的可行域是凸集。,最优解必

31、在顶点上得到。 线性规划求解方法 图解法 单纯形法,本次习题课内容,单纯形法小结,一般线性规划问题的标准化及初始单纯形法表.,变量, 约束条件,目标函数,单纯形法计算步骤框图（下页）,单纯形法小结,LP的习题课,极小化线性规划求解方法,极小化问题与极大化问题的解法，主要有一点区别，那就是进基变量的选取。由式 可知，若以极大化为目标，则当所有非基变量的检验数j0时，Z值达到最大。反之，若以极小化为目标，则当某个非基变量检验数j0时，若取xj0，将使Z值进一步变小，即使目标进一步优化；,当所有非基变量检验数j0时，若使任意非基变量xj0都会导致目标函数的增加从而偏离了极小化目标，于是可以认定此时的

32、解为最优解。 总而言之，极小化问题的判别准则是：j0 (j=1，2，n)时为最优，进基变量的选取是在负检验数中选取最小的一个k，它所对应的变量xk为换入变量。,举例：,填入初始单纯形表,所有的检验数大于0,得到最优解 X1=2/5 X2=38/5 Z=-30,一、已知某LP的初始单纯形表和单纯形法 迭代的表，求未知数al的值。,b=2,1 0,2,c/2=2 c=4,4,d/2=-1 d=-2,-2,-2a-1=-7 a=3,3,3,5,0,g=1 h=0,1=-1+e e=2,2,5,-3/2,解：,二、考虑LP问题 模型中 为参数，要求： （a）组成两个新的约束(1)=(1)+(2), (

33、2)= (2)- 2(1) , 根据 (1),(2) ，以 为 基变量，列出初始单纯形表；,（b）在表中，假定 ，则 为何值时， 为问题的最优基； （c）在表中，假定 ，则 为何值时， 为问题的最优基；,解：（a）两个新的约束,以 为基变量，初始单纯形表如下：,（b） 时， 最优基不变,（c） 时， 最优基不变,三、设线性规划问题 （1）分别用图解法和单纯形法求解； （2）对照指出单纯形表中的各基本可行 解对应图解法中可行域的哪一顶点。,续,（3）若目标函数变为 讨论c、d的值如何变化，使每个顶 点依次使目标函数达到最优。,解：化为标准型,1,2,2,1,最优解,10 5 0 0 0 9 3

34、4 1 0 0 8 5 2 0 1 10 5 0 0 0 21/5 0 14/5 1 -3/5 10 8/5 1 2/5 0 1/5 0 1 0 -2 5 3/2 0 1 5/14 -3/14 10 1 1 0 -1/7 2/7 0 0 -5/14 -25/14,O（0，0）,1,2,2,1,o,c d c/d 最优解的顶点 c/d5/2 Q1 c/d=5/2 Q1,Q2 0 0 3/40 不限 Q3 0 =0 - Q1 0 0 不限 Q1 0 0 不限 O,线性规划的对偶理论与灵敏度分析,1.7线性规划的对偶问题,一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应

35、关系,对偶问题概念 任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,一、对偶问题的提出,实例：某家电厂家利用现有资源生产两种 产品， 有关数据如下表：,(1)如何组织生产,获利最大 （2）如果外公司收购其资源，收购价格最低,如何安排生产， 使获利最多？,设 产量 产量,设：设备A 元时 设备B 元时 调试工序 元时,付出的代价最小， 且对方能接受。

36、,出让代价应不低于 用同等数量的资源 自己生产的利润。,美佳能接受的条件： 收购方的意愿：,对 偶 问 题,原 问 题,厂 家,改写成向量式,例2,例2,假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出卖工时和材料 ?,出卖资源获利应不少于生产产品的获利; 约束 价格应该尽量低，这样，才能有竞争力; 目标 价格应该是非负的,用y1和y2分别表示工时和材料的出售价格,总利润最小 min W=3y1+9y2 保证A产品利润 y1+y22 保证B产品利润 y1+4y23 保证C产品利润 y1+7y23

37、售价非负 y10 y20,min,max,3个约束 2个变量,2个约束 3个变量,一般规律,对偶问题对应表,例:,对偶问题为,写出下面的线性规划问题的对偶问题,对偶问题为：,对称形式的对偶问题,对称形式的对偶问题,对偶问题的特点 若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然 原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。,一般线性规划问题的对偶问题,1.8对偶问题的基本性质,对 偶 问 题,原 问 题,收 购,厂 家,引例,（ ）,原问题，最终单纯形表：,对偶问题用两阶段法求解的最终的

38、单纯形表,（ ）,（x1,x2）原问题 最优解,对偶问题 最优解,原问题与对偶问题对比，最终单纯形表：,相反数！,两个问题作一比较: 1.两者的最优值相同 2.变量的解在两个单纯形表中互相包含 原问题最优解（决策变量） 对偶问题最优解（决策变量）,从引例中可见： 原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。,理论证明： 原问题与对偶问题解的关系,二、对偶问题的基本性质,（1）对称定理： 定理： 对偶问题的对偶是原问题。,设原问题（1） 对偶问题（2）,（2）弱对偶性定理： 若 和 分别是原问题（1）及对偶问题（2）的可行解，则有,从弱对偶性

39、可得到以下重要结论： （1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。 （2）若原问题可行，但其目标函数值无界（无上界），则对偶问题无可行解。 （3）若对偶问题可行，但其目标函数值无界（无下界），则原问题无可行解。 （4）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 （5）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,原问题,对偶问题,（3）最优性定理： 若 和 分别是（1）和（2）的 可行解，且有 则 分别是（1）和（2）的最优解 。

40、,则 为（1）的最优解， 反过来可知： 也是（2）的最优解。,证明：因为（1）的任一可行解 均满足,（4）强对偶性定理 若原问题和对偶问题都有可行解，则两者都有最优解，且最优解的目标函数值相等。,证明：设X*是原问题的最优解，则必有所有检验数0即,设Y=CBB-1，则,这表示Y*满足对偶问题的约束条件。Y*是对偶问题的可行解，代入目标函数得,根据最优性，Y*是对偶问题的最优解，两者最优值相等,（5）互补松弛性： 若 分别是原问题（1）与对偶问题（2）的可行解， 分别为（1）、（2）的松弛变量，则： 即：,为最优解,原问题第i条约束,A的第i行,说明：即如原始变量XJ*0 ，则与之相应的第J个对

41、偶约束方程为等式，即剩余变量YSJ=0；如果第J个对偶约束为严格不等式，即剩余变量YSJ0，则与之相对应的原始变量XJ*=0,另一方面：,对偶问题的第j条约束,证明：,充分性：设原问题为,对偶问题为：,原问题的目标函数可以变为,同理对偶目标函数可表示为：,互补松弛定理应用： （1）从已知的最优对偶解，求原问题最优解，反之亦然。 （2）证实原问题可行解是否为最优解。 （3）从不同假设来进行试算，从而研究原始、对偶问题最优解的一般性质。 （4）非线性的方面的应用。,以上性质同样适用于非对称形式。,例,化为标准型时：分别加上松驰变量X4，X5，X6构成标准型,化为标准型时：分别减去剩作变量y4，y5

42、，y6构成标准型,已知上例中对偶问题的最优解Y1*=0,Y2 * =8,Y3 * =2,利用互补松驰定理求原问题的最优解。,解： 将最优解Y1*=0,Y2 * =8,Y3 * =2代入对偶问题的数学模型，知Y40,Y5=0,Y6=0.剩余变量Y40，根据互补松驰性X*YS=0，则原始变量X1=0。 对偶变量Y1=0，而XSY*=0，则松驰变量X4=0,相应约束条件为不起作用约束。 同理，对偶变量Y2，Y30,则松驰变量X5=0，X6=0。 于是原问题约束条件为 2X1+X2=50 4X1+3X3=150 解之得X2=50，X3=50,当线性规划原问题求得最优解 时，其对偶问题也得到最优解 ，且

43、代入各自的目标函数后有：,是线性规划原问题约束条件的 右端项，它代表第 种资源的拥有量；,（3）,1.9影子价格,影子价格的定义,对偶变量 的意义代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。,影子价格的经济意义,1资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。,2影子价格是一种边际价格。 在（3）式中， 。 说明 的值相当于在资源得到最优利用的生产条件下， 每增

44、加一个单位时目标函数 的增量。,（3）,几何解释,3资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,4在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,5从影子价格的含义上考察单纯形表的 检验数的经济意义。,（4）,第j种产品的产值,生产第j中产品所消耗各项资源的

45、 影子价格的总和。（即隐含成本）,6一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。,经济学研究如何管理 自己的稀缺资源,1.10对偶单纯形法,一、对偶单纯形法的基本思路 单纯形法是在原问题为可行解(表格bi列0)、对偶问题为非可行解(部分检验数j0）的条件下，逐步进行变量替换，改善目标函数值，最终达到全部检验数j0，即对偶问题也是可行时，根据对偶问题性质3，原问题和对偶问题均得到最优解。 对偶单纯形法是根据线性规划问题的对偶性质设计的一种解题方法。其基本思路是：原问题不是可行解，保持对偶问题为可行解，逐步进

46、行变量替换，当原问题变为可行解时，即得到问题的最优解。,单纯形法的基本思路： 原问题基可行解 最优解判断,对偶问题的可行解,对偶问题 最优解判断,对偶单纯形法 基本思路,对偶单纯形法的优点是可以从非可行解开始迭代，而不需添加人工变量去造基，这样对一些特殊类型的线性规划问题求解起来更加便捷。,对偶单纯形法的解题步骤,根据线性规划问题列出初始单纯形表，表中所有检验数j0，b列中至少有一个分量为负。,确定换出变量，在b列的负分量中选出一个最小值（也可任选）bl，其对应的基变量xB1为出基变量。,对应基变量 为换出基的变量,例：用对偶单纯形法求解线性规划问题,初始可行基,初始可行基,使对偶问题基变量可

47、行,主元,主元,最优解,例2.12 用对偶单纯形方法求解：,解: （1）引入松弛变量 x3 , x4 , x5 化为标准形，并在约束等式两侧同乘-1，得到,例2.13 用对偶单纯形法求解下面线性规划,解: 构造对偶单纯形表进行迭代，,从最后的表可以看到，B-1b列元素中有-20，并且，-2所在行各元素皆非负，因此，原规划没有可行解。,用对偶单纯形法求解线性规划问题：,对偶单纯形法的优点： 不需要人工变量； 在灵敏度分析中，有时需要用对偶单纯形法处理简化。 对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。 因此，对偶单纯形法一般不单独使用。,1.11灵敏度

48、分析,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，这些因素不变时企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。 在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,当系数A，b，C发生改变时，目前最优基是否还最优？ 为

49、保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？ 假设每次只有一种系数变化 目标系数C变化 基变量系数发生变化； 非基变量系数发生变化； 右端常数b变化 增加一个变量 增加一个约束 技术系数A发生变化,列出初始单纯形表,列出最终单纯形表,Z0= CBB-1b, A = C - CBB-1 A N = CN - CBB-1 N j = Cj- CBB-1 Pj, b= B-1b, j = Cj- CBB-1 Pj,Z0= CBB-1b, b= B-1b,灵敏度分析只要满足以下两把尺子： j =Cj-CBB-1pj 0； b= B-1b 0,一、价值系数CJ的变化,（一）非基变量Xj的

50、价值系数Cj的改变,只要满足：,（二）基变量Xbi的价值系数Cbi的变化 由j=Cj-CBB-1Pj看出：某一基变量价值系数CBi的变化将引起CB变化，CB变了则所有非基变量的检验数也随之发生变化。基变量的检验数(CB+CB)-(CB+CB)B-1B0不受变动影响。非基变量的检验数变为,为确保所有 的允许变化范围是,例：在第一章的美佳公司例子中， （1）若家电I的利润降至1.5元/件，而家电II的利润增至2元/件时，美佳公司最优生产计划有何变化； （2）若家电I的利润不变，家电II的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化。,6 14 -,即Z=(2,3,0,6,0),6 14 -,设家电II的利润为（1+),为使表中为最优解则： -1/4+1/40, -1/2-3/2 0,解得：-1/3 1 即2/3 C2 2,二、右端资