运筹学学习题胡运权版课件.ppt

1、 运筹学习题运筹学习题2主要内容主要内容一、线性规划一、线性规划二、运输问题二、运输问题三、目标规划三、目标规划四、整数规划四、整数规划五、网络规划五、网络规划3一、线性规划一、线性规划 1LP问题的数学模型 2图解法 3.LP问题解的基本概念 4单纯形法 5.对偶问题(LP的对偶问题、对偶单纯形法)6.灵敏度分析41.建立坐标系，将约束条件在图上表示；建立坐标系，将约束条件在图上表示；2.确立满足约束条件的解的范围（可行域）；确立满足约束条件的解的范围（可行域）；3.绘制出目标函数的图形；绘制出目标函数的图形；4.确定最优解。确定最优解。图解法的步骤图解法的步骤5最优解的确定：最优解的确定：

2、唯一最优解唯一最优解6无穷多最优解的情况：无穷多最优解的情况：目标函数与某个约束条件恰好平行目标函数与某个约束条件恰好平行7无界解（或无最优解）的情况：无界解（或无最优解）的情况：可行域上方无界可行域上方无界8无可行解的情况：无可行解的情况：约束条件不存在公共范围约束条件不存在公共范围9 检验数jcnmmcccc11BcBxb mcc 1mxx 11 mbbnmmxxxx 11im 1iicb0 0min(0)iikikbaa1 mn1,11,11001mnm mmnaaaa 1iiBzcbc B b jjBjjiijcc Pcc a1N12 (,)NBmmncc B N单纯形表10（最优解判

3、定定理）LP的典式（），如果有0(1,2,)jjmmn则对应于基B的基可行解(0)12(,0,0)Tmxb bb12(,0,0)Tmxb bb是线性规划的最优解，记为(0)zz相应的目标函数最优值特别 则 是唯一最优解(0)x0(1,2,)jjmmn其中有一个0(1)kmkn 则该LP问题有无穷多最优解（无界解判定定理）0(1)kmkn 如果某个非基变量的检验数且则该LP问题解无界0(1,2,)ikaim 11解的几种情况在单纯形表上的体现（解的几种情况在单纯形表上的体现（max型）：型）：唯一最优解唯一最优解：终表非基变量检验数均小于零；多重最优解多重最优解：终表非基变量检验数中有等于零的；

4、无界解无界解：任意表有正检验数相应的系数列均非正。无解无解：最优解的基变量中含有人工变量12123123123123max6422134420.2170,1,2,3jzxxxxxxxxxstxxxxj123456123412351236max6400022 1344 20.2 170,1,2,3jzxxxxxxxxxxxxxxstxxxxxjcj164000cBxBbx1x2x3x4x5x6000 x4x5x6132017-1412*-4221110001000113/2-17/2检验数j016400013非基变量得检验数j0，3=0,有无穷多最优解，x*=(2,15/2,0,0,42,0)T

5、,z*=47cj164000cBxBbx1x2x3x4x5x6000 x4x5x6132017-1412*-4221110001000113/2-17/2检验数j0164000600 x2x5x613/2464-1/222*10015-11/22-1010001-232检验数j-3940-2-300601x2x5x115/24220011003/46-1/21/43-1/20101/4-11/2检验数j-47000-10-214练习练习1：某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见下表：III

6、III设备能力（台时）ABC1102142156100600300单位利润（元）1064(1)求获利最大的产品生产计划；(2)产品III每件的利润增加到多大时才值得安排生产；(3)如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小时，预期每件的利润为8元，是否值得安排生产。15解：（1）设x1，x2，x3分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：123123123123123max10641001045600.226300,0zxxxxxxxxxstxxxx x x123456123412351236max1064000 1001045 600.22

7、6 3000,1,2,6jzxxxxxxxxxxxxxxstxxxxxj标准型标准型cj1064000cBxBbx1x2x3x4x5x6000 x4x5x6100600300110214215610001000110060150检验数j0106400016cj1064000cBxBbx1x2x3x4x5x6000 x4x5x6100600300110214215610001000110060150检验数j010640000100 x4x1x640601800100.60.41.20.50.55100-0.10.1-0.2001200/3150150检验数j-6000 2 -1 0 -10610

8、0 x2x1x6200/3100/31000101005/61/645/3-2/3-2-1/61/60001检验数j-2200/30 0 -8/3-10/3 -2/30所以最优解为x*=(100/3，200/3，0，0，0，100)T，即产品I、II、III的产量分别为：100/3，200/3，0；最优解目标函数值z*=2200/3171333333335/66,10,01/620/3020/34BBcC B PcC Pccc（2）设产品III每件的利润为c3产品III每件的利润增加到20/3时才值得安排生产。18（3）设x7为新产品的产量。1777110 28(,0)42 03 33Bcc

9、B P 值得投产1775/31/60112/31/604020131PB P cj10640008cBxBbx1x2x3x4x5x6x76100 x2x1x6200/3100/31000101005/61/645/3-2/3-2-1/61/60001101200/3-100检验数j-2200/300-8/3-10/3-2/30219cj10640008cBxBbx1x2x3x4x5x6x76100 x2x1x6200/3100/31000101005/61/645/3-2/3-2-1/61/60001101200/3-100检验数j-2200/300-8/3-10/3-2/302cj10640

10、008cBxBbx1x2x3x4x5x6x78100 x7x1x6200/3100/3100/301010-15/61/619/65/3-2/3-11/3-1/61/61/6001100检验数j-2600/30-2-13/3-20/3-1/300所以最优解为x*=(100/3，0，0，0，0，100/3，200/3)T，即产品 I 的产量：100/3，新产品的产量：200/3；最优解目标函数值z*=2600/320练习练习2：已知下列线性规划问题，求：（1）用单纯形法求解，并指出问题属于哪一类解；（2）写出该问题的对偶问题，并求出对偶问题的最优解；12312312312312363336022

11、420.33360,0maxzxxxxxxxxxstxxxx x x21解：（1）将原问题划为标准形式：cj6-33000cBxBbx1x2x3x4x5x6000 x4x5x66020603231-2314-3100010001201020检验数j06-33000123456123412351236max6330003 60224 20.333 600,1,2,6jzxxxxxxxxxxxxxxstxxxxxj220 x4100011-1/2-2/36x115101/201/41/6-3x2501-3/20-1/41/6检验数j-7500-9/20-9/4-1/2所以最优解为x*=(15，5，

12、0，10，0，0)T ,最优解目标函数值z*=75非基变量的检验数0,为唯一最优解.cj6-33000cBxBbx1x2x3x4x5x6000 x4x5x66020603231-2314-3100010001201020检验数j06-33000060 x4x1x63010300104-16-52-9100-3/21/2-3/200115/2-5检验数j-6003-90-30230 x4100011-1/2-2/36x115101/201/41/6-3x2501-3/20-1/41/6检验数j-7500-9/20-9/4-1/2（2）对偶问题为：123123123123123min6020603

13、236233.433,0wyyyyyyyyystyyyy yy y*=(0，9/4，1/2)对偶问题的最优解：24建立模型决策变量个数决策变量取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj0 xj无约束xj 0 bi 0bi 0，边从，边从j到到i的方向是不饱和的；的方向是不饱和的；（5，3）是不饱和的）是不饱和的间隙为间隙为53=f53=5对于后向弧来讲对于后向弧来讲(正向为正向为3-5）饱和弧、不饱和弧、流量的间隙饱和弧、不饱和弧、流量的间隙85 设设f=（fij）是）是D中的一个可行流中的一个可行流,若存若存在一条在一条(vs-vi)链链,满足满足:1.对一切对一切(i,j

14、)+,有有fijcij,2.对一切对一切(i,j)-,有有fij0.则称则称是一条关于是一条关于f的的(vs-vi)增广链增广链,特别地特别地,当当vi=vt时时,就称就称为一条关于为一条关于f的增广链的增广链.增增 广广 链链增广链由不饱和弧组成增广链由不饱和弧组成86步骤如下：步骤如下：第二步：对点进行标号找一条增广链。第二步：对点进行标号找一条增广链。（1）发点标号）发点标号（）（2）选一个点）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收已标号并且另一端未标号的弧沿着某条链向收点检查：点检查：A如果弧的方向向前（前向弧）并且有如果弧的方向向前（前向弧）并且有fij0，则，则v

15、j标号标号:jfji当收点已得到标号时，说明已找到增广链，依据当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。链，计算结束。第一步：第一步：找出第一个可行流，例如所有弧的流量找出第一个可行流，例如所有弧的流量fij=0 Ford-Fulkerson标号算法标号算法87第三步：调整流量第三步：调整流量（1）求增广链上点）求增广链上点vi 的标号的最小值，得到调整量的标号的最小值，得到调整量 minjj（2）调整流量）调整流量),(),(),(1jifj

16、ifjiffijijij得到新的可行流得到新的可行流f1，去掉所有标号，返回到第二步从发点重新，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止标号寻找增广链，直到收点不能标号为止 888145633810763图图619(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例】求图【例】求图619发点发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量【解【解】898145633810763(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)2337第一轮标号：第一轮标号：c12f12,v2标号标号2cij=fi

17、j，v4、v5不能标号不能标号后向弧后向弧f320,v3标号标号3=f32增广链增广链(1,2)，(3,2)，(3,4)，(4,7),+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值，调整量为增广链上点标号的最小值min，2，3，3，72908145633810763(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)调整后的可行流：调整后的可行流：918145633810763(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)4415第二轮标号：第二轮标号：Cij=fij，v4、v5不能标号，返回到不能标号

18、，返回到v3增广链增广链(1,3)，(3,4)，(4,7)，调整量为，调整量为 min，4，1，51928145633810763图图623(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)调整后得到可行流：调整后得到可行流：938145633810763图图622(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)314第三轮标号：第三轮标号：增广链增广链(1,3)，(3,6)，(6,4)，(4,7)，调整量为，调整量为 min，3，1，2，412948145633810763图图625(12)(8)(1)(6)(3)(8)(3)(6)(2)

19、4(7)(1)(7)调整后得到可行流：调整后得到可行流：958145633810763图图622(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)2第四轮标号：第四轮标号：v7得不到标号，不存在得不到标号，不存在v1到到 v7的增广链，图的增广链，图6-22所示的可行流所示的可行流是最大流，最大流量为是最大流，最大流量为 vf12+f138+12=20Cij=fij，v4、v5不能标号不能标号Cij=fij，v4、v6不能标号不能标号4961）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。97第一轮标号：得到一条增广链，调整量等于5，如下图所示98 第二轮标号：得到一条增广链，调整量等于2，如下图所示99 第三轮标号：得到一条增广链，调整量等于3，如下图所示100 第四轮标号：不存在增广链，最大流量等于45，如下图所示 取，最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45。101练习：求网络的最大流与最小截集，图中每条弧傍括号中的数字是（Cij,xij)