运筹学教程课件.ppt

《运筹学教程课件.ppt》由会员分享，可在线阅读，更多相关《运筹学教程课件.ppt（250页珍藏版）》请在三一文库上搜索。

1、运筹学教程课件,运 筹 学 教 程 4.0 版,运筹学教程课件,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。 运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,前言运筹学简介,运筹学教程课件,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英

2、文是Operational Research，在美国称为Operations Research。,运筹学教程课件,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。,运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、整数规划、运输问题、网络优化、动态规划和排

3、队论。,运筹学教程课件,目 录,第一章线性规划 第二章对偶 第三章整数规划 第四章运输问题 第五章网络优化 第六章动态规划 第七章排 队 论,运筹学教程课件,第一章 线性规划,线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示,运筹学教程课件,线性规划模型,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, unr, 0 线性规划的标准形式 目标函数：min 约束条件：= 变量符号：0,运筹学教程课件,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x2

4、0,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,运筹学教程课件,可行域的性质,线性规划的可行域是凸集 线性规划的最优解在极点上,凸集,凸集,不是凸集,运筹学教程课件,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,运筹学教程课件,x3=0,x4=0,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x4

5、0,x1=0, x2=0 x3=3, x4=1,x1=0, x4=0 x2=1, x3=2,x2=0, x3=0 x1=3, x4=1,x3=0, x4=0 x1=2, x2=1,x1=0, x3=0 x2=3, x4=-2,线性规划的基本概念基础解、基础可行解、极点,x2=0,x1=0,O,A,B,C,D,运筹学教程课件,标准化的线性规划问题，有n个变量，m个约束。 令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。 求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这

6、n个变量的值称为线性规划的一个基础解。 如果一个基础解中的所有变量都是非负的，这个基础解称为基础可行解。 线性规划的基础可行解就是可行域的极点。,线性规划的基本概念基础解、基础可行解、极点,运筹学教程课件,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,x1=0, x2=0 x3=3, x4=1 基础可行解,x1=0, x4=0 x2=1, x3=2 基础可行解,x2=0, x3=0 x1=3, x4=1 基础可行解,x3=0, x4=0 x1=2, x

7、2=1 基础可行解,x1=0, x3=0 x2=3, x4=-2 是基础解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,运筹学教程课件,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值： 一组平行线,目标函数值等于一个常数的解,运筹学教程课件,搜索所有基础可行解求出最优解,运筹学教程课件,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0

8、，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=20,运筹学教程课件,基变量x1、x2、x4，非基变量x3、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18,运筹学教程课件,基变量x1、x2、x5，非基变量x3、x4、x6,基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基础解，但不是可行解，不是一个极点。,运筹学教程课件,基变量x1、x2、x6，非基变量x3、x4、x5,基础解为（x1，x2，x3，x4，x5，x6）=（3，4，

9、0，0，0，4） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18,运筹学教程课件,基变量x2、x3、x4，非基变量x1、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基础解，但不是可行解。,运筹学教程课件,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=15,运筹学教程课件,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，11/

10、2，-3/2，0，0，10） 是基础解但不是可行解。,运筹学教程课件, , ,单纯形法原理（1）松弛变量的表示,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x20,max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,x2=0,x1=0,x3=0,x4=0,O,A,B,C,D, , ,运筹学教程课件,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第一次叠代： 目标函数和基变量分别用非基变量表示： z=-x1-2x2 选择x2进基 x3 =3-x1-x2 x4=1 -x2,单纯形法原理(2)第一次叠代,运筹

11、学教程课件,确定离基变量的进一步讨论,设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2,x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2,5/4=1.25 4/3=1.33 2/1=2,min5/4,4/3,2/1=5/4 当x2增加到1.25时 x30离基,x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2,x3增加 4/3=1.33 2/1=2,min4/3,2/1=4/3 当x2增加到1.33时 x40离基,x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2,x3增加 x4增

12、加 2/1=2,min2/1=2/1 当x2增加到2时 x50离基,x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2,x3增加 x4增加 x5增加,x2可以无限增加，可行域是开放区域，目标函数无界,运筹学教程课件,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第二次叠代： 目标函数和基变量分别用非基变量表示： z=-2-x1+2x4 选择x1进基 x3 =2-x1+x4 x2=1 -x4,单纯形法原理（3）第二次叠代,运筹学教程课件,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第三次叠代： 目标函数和基变量分别用非基变量表示： z=-4+

13、x3+x4 x1 =2-x3+x4 x2=1 -x4 非基变量在目标函数中的系数全部大于0，已获得最优解。,单纯形法原理（4）最优解的判定,运筹学教程课件,x2=0,x1=0,x3=0,x4=0,O,A,B,C,单纯形法原理(5)叠代过程回顾,第一次叠代 x2进基，x4离基,第二次叠代 x1进基，x3离基,(x1,x2,x3,x4)= (0,0,3,1), z=0,(x1,x2,x3,x4)= (0,1,2,0), z=-2,(x1,x2,x3,x4)= (2,1,0,0), z=-4 最优解,运筹学教程课件,单纯形法原理（6）单纯形法总结,STEP 0 找到一个初始的基础可行解，确定基变量和

14、非基变量。转STEP 1。 STEP 1 将目标函数和基变量分别用非基变量表示。转STEP 2。 STEP 2 如果目标函数中所有非基变量的系数全部为正数，则已经获得最优解。运算终止。否则，选取系数为负数并且绝对值最大的非基变量进基。转STEP 3。 STEP 3 如果进基变量增加时，基变量都不减少，则可行域开放，目标函数无界。运算终止。否则，随着进基变量的增加，最先下降到0的基变量离基。转STEP 1。,运筹学教程课件,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,=,基变量,运筹学教程课件,进基变量,离基变量,目标函数,约束条件,右边常数,=,运筹学教程课件,目标函数,

15、约束条件,新的基矩阵,右边常数,=,运筹学教程课件,进基变量,离基变量,目标函数,约束条件,基矩阵,=,运筹学教程课件,目标函数,约束条件,新的基矩阵,右边常数,=,运筹学教程课件,线性规划基本概念练习（1）,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,min z=-x1+2x2 s.t. 3x1+2x212(1) x1+2x2 6(2) -2x1+ x2 4(3) x1, x2 0,1、约束条件（1）对应的直线是（ ），对应的半平面是 约束条件（2）对应的直线是（ ），对应的半平面是 约束条件（3）对应的直线是（ ），对应的半平面是,2、这个线性规划的可行域是（

16、 ）。 3、对于z=2和4,分别画出目标函数等值线。 4、这个线性规划的最优解位于（ ）。,ACEF,BCDH,EGHI,CDGE,z=2,z=4,C,D,4,运筹学教程课件,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,D,线性规划基本概念练习（2）,5、x1等于0的直线是( )， x2等于0的直线是( )， x3等于0的直线是( )， x4等于0的直线是( )， x5等于0的直线是( )。 6、A点对应的基变量是( )，非基变量是（ ）； D点对应的基变量是( )，非基变量是（ ）。 7、A点不是可行解， 是由于( )0, F点不是可行解， 是由于( )0, I

17、 点不是可行解， 是由于( )0。,4,x1=0,x2=0,x3=0,x4=0,x5=0,ODGF,IOAB,ACEF,BCDH,EGHI,8、x1,x2,x50, x3,x40的区域是( ) x1,x2,x3,x50, x40的区域是( ) x2,x3,x4,x50, x10的区域是( ) x1,x2,x3,x40, x50的区域是( ),x1,x4,x5,x3,x2,x2,x3,x5,x1,x4,x4,x5,x1,x4,ABC,OACD,DGH,EFG,运筹学教程课件,线性规划基本概念练习（3）,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,D,4,x1=0,x

18、2=0,x3=0,x4=0,x5=0,9、从O到D的单纯形迭代， 进基变量是（ ），离基变量是（ ）。 从D到C的单纯形迭代，进基变量是（ ），离基变量是（ ）。 从C到E的单纯形迭代，进基变量是（ ），离基变量是（ ）。,x2,x4,x1,x3,x4,x5,运筹学教程课件,单纯形表,min z=-x1-2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0,z+x1+2x2 =0 x1+x2+ x3 =3 x2 +x4=1,运筹学教程课件,z=-x1-2x2 x3 =3-x1-

19、x2 x4=1 -x2,z=-2-x1+2x4 x3=2-x1+x4 x2 =1 -x4,z=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4,单纯形法原理,单纯形表,运筹学教程课件,求解线性规划问题,写成标准化形式,运筹学教程课件,写出单纯形表,25/1,36/2,0,-3,-2,0,-2,-72,0,1,1/2,0,1,-1/2,7/1/2,1,x5,1/2,1,0,1/2,18/1/2,0,7,18,1,1/2,1/2,x2,0,x6离基，为主元，进行行变换，将变为1，4和1变为0,x2进基，计算RHS和x2在约束条件中的系数的比值，比值小的基变量离基,x5离基，,x1进基，,

20、运筹学教程课件,0,-4,-2,-2,-1,-86,0,1,1,0,2,-1,1,x1,0,1,-1,1,0,14,11,0,1,0,x2,0,得到最优解，最优解为：,（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0） min z=-86，max z=86,运筹学教程课件,单纯形表的结构 基变量在目标函数中的系数等于0，基变量在约束条件中的系数是一个单位矩阵。,运筹学教程课件,Step 0 获得一个初始的单纯形表，确定基变量和非基变量 Step 1 检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵。 Step 2 如果表中非基变量在目标函数中的系

21、数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基，转step 3。 Step 3 如果进基变量在约束条件中的系数全为负数或0，则可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基，转step 4。 Step 4 确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 2。,单纯形表的运算,运筹学教程课件,标准化。引进松弛变量x4，x5,运筹学教程课件,写出单纯形表,x1进基，x4离基。第二行除以2,运筹学教程课件,行变换

22、。将主元变成1，主元所在列的其他元素变为0,x2进基，x5离基。第三行除以5,运筹学教程课件,行变换。将主元变成1，主元所在列的其他元素变为0,检验数全部为负数或0，获得最优解。 最优解为：（x1，x2，x3，x4，x5）（6，12，0，0，0） min z=-42，max z=42,运筹学教程课件,初始基础可行解,约束条件全部是，右边常数全部是非负的线性规划问题，引进松弛变量后，可以直接得到一个初始基础可行解。在这个解中，原来的变量为非基变量，松弛变量为基变量。例如：,min z=x1+x2-2x3 s.t. 3x1+2x2- x335 x1- x2+2x328 x1, x2, x30,mi

23、n z=x1+x2-2x3 s.t. 3x1+2x2- x3+x4 =35 x1- x2+2x3 +x5=28 x1, x2, x3, x4, x50,x1=x2=x30为非基变量，x4=35，x5=28为基变量，得到初始的基础可行解。,引进松弛变量,运筹学教程课件,约束条件中有约束，右边常数全部是非负的线性规划问题，引进松弛变量（Slack Variables）后，无法直接得到一个初始基础可行解。例如：,min z=x1+x2 s.t. 3x1+2x235 x1- x228 x1, x20,min z=x1+x2 s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 (A)

24、x1, x2, x3, x40,x1=x20为非基变量，x3=-35，x4=-28为基变量，不是可行解。为了得到(A)的基础可行解，在(A)的约束条件中再引进两个变量x5，x60，这两个变量称为人工变量（Artificial Variables）。,min z=x1+x2 s.t. 3x1+2x2 -x3 +x5 =35 x1- x2 -x4 +x6=28 (B) x1, x2, x3, x4, x5, x60,运筹学教程课件,（B）有一个初始的基础可行解： (x1, x2, x3, x4, x5, x6) = (0, 0, 0, 0, 35, 28)，但它不是（A）的可行解。 只有当x5=x

25、6=0时，（B）的可行解才同时也是（A）的可行解。这样的解中x5，x6一定是非基变量。 因此，可以这样来求得（A）的一个初始基础可行解：从（B）以人工变量x5，x6为基变量的初始基础可行解出发，用单纯形法对（B）进行进基离基变换，如果x5，x6都离基，成为非基变量，则（B）的这个基础可行解就是（A）的一个可行解。为了迫使人工变量尽快离基，构造一个新的极小化目标函数，这个目标函数等于所有人工变量之和。,min z=x1+x2 s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 (A) x1, x2, x3, x40,min z=x1+x2 s.t. 3x1+2x2 -x3 +x

26、5 =35 x1- x2 -x4 +x6=28 (B) x1, x2, x3, x4, x5, x60,运筹学教程课件,min z=x5+x6 s.t. 3x1+2x2 -x3 +x5 =35 x1- x2 -x4 +x6=28 x1, x2, x3, x4, x5, x60,min z=x1+x2 s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 x1, x2, x3, x40,求解辅助问题，得到辅助问题的最优解,引进人工变量x5，x6，构造辅助问题，辅助问题的目标函数为所有人工变量之和,min z=0?,人工变量不能离基，原问题没有可行解。,把辅助问题的最优解作为原问题

27、的初始基础可行解,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,运筹学教程课件,两阶段法,STEP 0 引进松弛变量，成为标准形式。 STEP 1 如果约束条件的系数矩阵中没有一个单位矩阵，引进人工变量，构造辅助问题。 STEP 2 求解辅助问题。得到辅助问题的最优解。如果辅助问题的最优解中人工变量都离基成为非基变量，即辅助问题最优解的目标函数值min z=0，则辅助问题的最优解就是原问题的一个初始基础可行解。如果辅助问题最优解中仍有人工变量没有离基，即辅助问题最优解的目标函数值min z0，则原问题没有可行解。 STEP 3 转到第二阶段，从原问题的初始基础可行解出

28、发，求出原问题的最优解。,运筹学教程课件,案例一 食油生产计划,储罐1,储罐2,储罐3,储罐4,储罐5,硬质油1,硬质油2,软质油1,软质油2,软质油3,硬质油精炼,软质油精炼,混合,成品油,原料,加工,成品,运筹学教程课件,第二章 对偶线性规划,对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关系 最优解的Kuhn-Tucher条件 对偶可行基对偶单纯形法 对偶的经济解释,DUAL,运筹学教程课件,一、对偶的定义,原始问题 min z=CTX s.t.AXb X 0,对偶问题 max y=bTW s.t. ATWC W 0,min,b,A,CT,C,AT,

29、bT,max,m,n,m,n,运筹学教程课件,二、对偶问题的性质,1、对偶的对偶就是原始问题,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W 0,min y=-bTW s.t. -ATW-C W 0,max z=-CTX s.t. -AX-b X 0,运筹学教程课件,2、其他形式问题的对偶,原始问题约束条件的性质，影响对偶问题变量的性质。 原始问题变量的性质，影响对偶问题约束条件的性质。,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W 0,min z=CTX s.t. AX=b X 0,max y=bTW s.

30、t. ATWC W :unr,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W 0,运筹学教程课件,min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max y=6w1+12w2+8w3+15w4 s.t. 3w1- w2+2w3+ w4 2 -w1+2w2+ w3+3w4 4 2w1- 3w2+2w3- w4 -1 w1 0,w2 ,w3 0,w4 0,=,unr,=,x10,x20,x3: unr,原始问题变量的个数(3)等于对偶问题约束条件的个

31、数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。,运筹学教程课件,三、原始对偶关系,1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解 z=CTXF WTAXF WTb=y 2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y,运筹学教程课件,3、原始问题和对偶问题最优解之间的互补松弛关系,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. AT

32、W+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,互补松弛关系,XTWS=0 WTXS=0,运筹学教程课件,min z=CTX s.t.AX-XS=b X, XS 0,max y=bTW s.t. ATW+WS=C W, WS 0,XTWS=0 WTXS=0,AT,W,I,Ws,C,m,n,=,n,X,A,-I,Xs,b,=,n,m,m,原始问题和对偶问题变量、松弛变量的维数,运筹学教程课件,w1. wi . wm wm+1 . wm+j . wn+m,x1 . xj . xn xn+1 xn+i xn+m,对偶问题的变量

33、对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n) 在一对变量中，其中一个大于0，另一个一定等于0,运筹学教程课件,3、原始问题和对偶问题最优解的充分必要条件,运筹学教程课件,四、对偶单纯形法,运筹学教程课件,对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 0, 0, -1, -2, -1),不是对偶问题的可行解,运筹学教程课件,对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 2/3, 0, 1/3, 0, -1/3),不是对偶问题的可行解,运筹学教程课件,对偶问题的解（w1, w

34、2, w3, w4, w5,w6）=(1/2, 1/2, 0, 1/2, 0, 0),是对偶问题的可行解,运筹学教程课件,结论 单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解。,运筹学教程课件,1、用单纯形表求解原始问题的四种形式,min z=CTX s.t. AXb X 0,min z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0,max z=CTX s.t. AX

35、 b X 0,（2）,（3）,（4）,（1）,运筹学教程课件,单纯形表和对偶(1),min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,运筹学教程课件,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,WT=CBTB-1 WST=CT-WTA,运筹学教程课件,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,单纯形表和对偶(2),运筹学教程课件,min z=CTX s.t. AX

36、+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,WT=CBTB-1 WST=CT-WTA,运筹学教程课件,max z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW-WS=C W 0, WS0,单纯形表和对偶(3),运筹学教程课件,max z=CTX s.t. AX-XS=b X, XS0,min y=bTW s.t. ATW-WS=C W 0, WS0,WT=CBTB-1 WST=WTA- CT,运筹学教程课件,max z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW-W

37、S=C W, WS0,单纯形表和对偶(4),运筹学教程课件,max z=CTX s.t. AX+XS=b X, XS0,min y=bTW s.t. ATW-WS=C W, WS0,WT=CBTB-1 WST=WTA- CT,运筹学教程课件,min z=6x1+8x2+3x3 s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0,max y=w1-w2 s.t. w1+ w2 6 w1+2w2 8 w2 3 w1, w20,max y=w1-w2 s.t. w1+w2+w3 =6 w1+2w2 +w4 =8 w2 +w5=3 w1, w2, w3, w4, w50,(

38、w1, w2) =(6,0),(w1,w2,w3,w4,w5) =(6, 0, 0, 2, 3),min z=6x1+8x2+3x3 s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x50,(x1, x2, x3 | x4, x5) (w1, w2 | w3, w4, w5),x2=x3=x4=0,x1=1, x5=2,(x1, x2, x3, x4, x5) =(1, 0, 0, 0, 2),运筹学教程课件,min z=6x1+8x2+3x3 s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x

39、3 ,x4, x50,max y=w1-w2 s.t. w1+w2+w3 =6 w1+2w2 +w4 =8 w2 +w5=3 w1, w2, w3, w4, w50,(w1, w2, w3, w4, w5)=(6, 0, 0, 2, 3),(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2),-w3 w4 w5 w1 w2,运筹学教程课件,如何从最优单纯形表中读出对偶问题的解（1）,初始 单纯形表,最优 单纯形表,运筹学教程课件,如何从最优单纯形表中读出对偶问题的解（2）,初始 单纯形表,最优 单纯形表,运筹学教程课件,2、对偶单纯形法（初始解原始不可行的问题）,运筹学教程

40、课件,运筹学教程课件,运筹学教程课件,已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,运筹学教程课件,3、初始解原始、对偶都不可行的问题,运筹学教程课件,解法1：先解决原始可行性,运筹学教程课件,运筹学教程课件,在得到原始可行解时同时得到对偶可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （

41、w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,运筹学教程课件,解法2：先解决对偶可行性,已得到对偶可行解，再用对偶单纯形法求解,运筹学教程课件,运筹学教程课件,得到原始可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,运筹学教程课件,五、对偶的经济解释,1、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产

42、量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,运筹学教程课件,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,运筹学教程课件,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,运筹学教程课件,w1 w2 wm,4、产品的机会成本,机

43、会成本 表示减少一件产品所节省的所有资源可以增加的利润,运筹学教程课件,机会成本,利润,差额成本,5、产品的差额成本（Reduced Cost）,wm+j=(ai1w1+ai2w2+.aimwm)-cj 差额成本机会成本利润,运筹学教程课件,5、互补松弛关系的经济解释,wixn+i=0,如果wi0，则xn+i=0,如果xn+i0，则wi=0,边际利润大于0的资源，在最优生产计划条件下没有剩余,wm+jxj=0,如果wm+j0，则xj=0,如果xj0，则wm+j=0,最优生产计划条件下有剩余的资源，其边际利润等于0,差额成本大于0（机会成本大于利润）的产品，不安排生产,安排生产的产品，差额成本等

44、于0（机会成本等于利润）,运筹学教程课件,和资源有关的量 资源限量（吨） 资源占用（吨） 资源剩余（吨） 资源限量资源占用 资源的影子价格 （资源的边际利润）（元/吨） 和产品有关的量 产品利润（元/件） 产品产量（件） 产品的机会成本（元/件） 产品的差额成本（元/件） 机会成本利润,互补松弛关系,运筹学教程课件,max z=32x1+31x2+55x3+32x4+70 x5 s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1+3x2+5x3 +3x52400 x1，x2，x3，x4，x50,运筹学

45、教程课件,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)45850.00 VARIABLEVALUE REDUCED COST X1 0.000000 7.250000 X2550.000000 0.000000 X3 0.000000 8.000000 X4900.000000 0.000000 X5 0.000000 8.500000 ROW SLACK OR SURPLUS DUAL PRICES 2)200.000000 0.000000 3) 0.00000015.500000 4) 0.000000 8.250000 5

46、) 750.000000 0.000000 NO. ITERATIONS= 2,运筹学教程课件,200,0,0,750,3800,2000,1800,1650,7.25,0,8.0,0,8.5,39.25,31,63.0,32,78.5,产品的机会成本产品对设备的消耗设备的影子价格,资源的占用 产品产量产品对设备的消耗,资源的剩余资源限量资源占用,产品的差额成本产品的机会成本产品利润,产品产量和产品的机会差额成本互补松弛,资源剩余和资源的影子价格互补松弛,运筹学教程课件,第四章 运输问题,运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、对偶变量法 确定进基变量，调整运量，确定离基变量,运筹学教程课件,运输问题网络图,供应地,需求地,供应量,需求量,总供应量60吨,总需求量60吨,供求平衡的运输问题,运筹学教程课件,运输问题线性规划模型,供应地约束,需求地约束,由于前m个供应地约束和后n个