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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,运筹学习题,1,运筹学习题1,主要内容,一、线性规划,二、运输问题,三、目标规划,四、整数规划,五、网络规划,2,主要内容一、线性规划2,一、线性规划,1LP问题的数学模型,2图解法,3. LP问题解的基本概念,4单纯形法,5. 对偶问题(LP的对偶问题、对偶单纯形法),6. 灵敏度分析,3,一、线性规划3,建立坐标系，将约束条件在图上表示；,确立满足约束条件的解的范围（可行域）；,绘制出目标函数的图形；,确定最优解。,图解法的步骤,4,建立坐标系，将约束条件在图上表示；图解法的步骤4,最优解的确定：,唯一最优解,5,最优解的确定：唯一最优解5,无穷多最优解的情况：,目标函数与某个约束条件恰好平行,6,无穷多最优解的情况：目标函数与某个约束条件恰好平行6,无界解（或无最优解）的情况：,可行域上方无界,7,无界解（或无最优解）的情况：可行域上方无界7,无可行解的情况：,约束条件不存在公共范围,8,无可行解的情况：约束条件不存在公共范围8,检验数,单纯形表,9,检验数单纯形表9,（最优解判定定理）,LP的典式（,）,，如果有,则对应于基B的基可行解,是线性规划的最优解，记为,相应的目标函数最优值,特别,则 是,唯一最优解,其中有一个,则该LP问题有,无穷多最优解,（无界解判定定理）,如果某个非基变量的检验数,且,则该LP问题解无界,10,则对应于基B的基可行解是线性规划的最优解，记为相应的目标函数,解的几种情况在单纯形表上的体现（max型）：,唯一最优解,：终表非基变量检验数均小于零；,多重最优解,：终表非基变量检验数中有等于零的；,无界解,：任意表有正检验数相应的系数列均非正。,无解,：最优解的基变量中含有人工变量,11,解的几种情况在单纯形表上的体现（max型）：唯一最优解：终表,c,j,1,6,4,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,0,x,4,x,5,x,6,13,20,17,-1,4,1,2,*,-4,2,2,1,1,1,0,0,0,1,0,0,0,1,13/2,-,17/2,检验数,j,0,1,6,4,0,0,0,12,cj164000cBxBbx1x2x3x4x5x60x413,非基变量得检验数,j,0,，,3,=,0, 有无穷多最优解，,x,*,=(2,15/2,0,0,42,0),T,z,*,=47,c,j,1,6,4,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,0,x,4,x,5,x,6,13,20,17,-1,4,1,2,*,-4,2,2,1,1,1,0,0,0,1,0,0,0,1,13/2,-,17/2,检验数,j,0,1,6,4,0,0,0,6,0,0,x,2,x,5,x,6,13/2,46,4,-1/2,2,2,*,1,0,0,1,5,-1,1/2,2,-1,0,1,0,0,0,1,-,23,2,检验数,j,-39,4,0,-2,-3,0,0,6,0,1,x,2,x,5,x,1,15/2,42,2,0,0,1,1,0,0,3/4,6,-1/2,1/4,3,-1/2,0,1,0,1/4,-1,1/2,检验数,j,-47,0,0,0,-1,0,-2,13,非基变量得检验数j0， 3=0, 有无穷多最优解，x*,练习1：,某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见下表：,I,II,III,设备能力（台时）,A,B,C,1,10,2,1,4,2,1,5,6,100,600,300,单位利润（元）,10,6,4,(1)求获利最大的产品生产计划；,(2)产品III每件的利润增加到多大时才值得安排生产；,(3)如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小时，预期每件的利润为8元，是否值得安排生产。,14,练习1：某工厂生产I、II、III三种产品，分别经过A、B、,解：（1）设,x,1,，x,2,，x,3,分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：,标准型,c,j,10,6,4,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,0,x,4,x,5,x,6,100,600,300,1,10,2,1,4,2,1,5,6,1,0,0,0,1,0,0,0,1,100,60,150,检验数,j,0,10,6,4,0,0,0,15,解：（1）设x1，x2，x3分别为I、II、III三种产品的,c,j,10,6,4,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,0,x,4,x,5,x,6,100,600,300,1,10,2,1,4,2,1,5,6,1,0,0,0,1,0,0,0,1,100,60,150,检验数,j,0,10,6,4,0,0,0,0,10,0,x,4,x,1,x,6,40,60,180,0,1,0,0.60.4,1.2,0.5,0.5,5,1,0,0,-0.1,0.1,-0.2,0,0,1,200/3,150,150,检验数,j,-600,0,2,-1,0,-1,0,6,10,0,x,2,x,1,x,6,200/3,100/3,100,0,1,0,1,0,0,5/6,1/6,4,5/3,-2/3,-2,-1/6,1/6,0,0,0,1,检验数,j,-2200/3,0,0,-8/3,-10/3,-2/3,0,所以最优解为,x,* =(100/3，200/3，0，0，0，100),T,，,即产品I、II、III的产量分别为：100/3，200/3，0；最优解目标函数值,z,* =2200/3,16,cj1064000cBxBbx1x2x3x4x5x60x41,（2）设,产品III每件的利润为,c,3,产品III每件的利润增加到20/3时才值得安排生产。,17,（2）设产品III每件的利润为c3产品III每件的利润增加到,（3）设,x,7,为新产品的产量。,c,j,10,6,4,0,0,0,8,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,6,10,0,x,2,x,1,x,6,200/3,100/3,100,0,1,0,1,0,0,5/6,1/6,4,5/3,-2/3,-2,-1/6,1/6,0,0,0,1,1,0,1,200/3,-,100,检验数,j,-2200/3,0,0,-8/3,-10/3,-2/3,0,2,18,（3）设x7为新产品的产量。cj10640008cBxBbx,c,j,10,6,4,0,0,0,8,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,6,10,0,x,2,x,1,x,6,200/3,100/3,100,0,1,0,1,0,0,5/6,1/6,4,5/3,-2/3,-2,-1/6,1/6,0,0,0,1,1,0,1,200/3,-,100,检验数,j,-2200/3,0,0,-8/3,-10/3,-2/3,0,2,c,j,10,6,4,0,0,0,8,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,8,10,0,x,7,x,1,x,6,200/3,100/3,100/3,0,1,0,1,0,-1,5/6,1/6,19/6,5/3,-2/3,-11/3,-1/6,1/6,1/6,0,0,1,1,0,0,检验数,j,-2600/3,0,-2,-13/3,-20/3,-1/3,0,0,所以最优解为,x,* =(100/3，0，0，0，0，100/3,，,200/3)T，即产品 I 的产量：100/3，新产品的产量：200/3；最优解目标函数值,z,* =2600/3,19,cj10640008cBxBbx1x2x3x4x5x6x76,练习2：,已知下列线性规划问题，求：,（1）用单纯形法求解，并指出问题属于哪一类解；,（2）写出该问题的对偶问题，并求出对偶问题的最优解；,20,练习2：已知下列线性规划问题，求：20,解：（1）,将原问题划为标准形式：,c,j,6,-3,3,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,0,x,4,x,5,x,6,60,20,60,3,2,3,1,-2,3,1,4,-3,1,0,0,0,1,0,0,0,1,20,10,20,检验数,j,0,6,-3,3,0,0,0,21,解：（1）将原问题划为标准形式：cj6-33000cBxBb,0,x,4,10,0,0,1,1,-1/2,-2/3,6,x,1,15,1,0,1/2,0,1/4,1/6,-3,x,2,5,0,1,-3/2,0,-1/4,1/6,检验数,j,-75,0,0,-9/2,0,-9/4,-1/2,所以最优解为,x,* =(15，5，0，10，0，0),T, 最优解目标函数值,z,* =75,非基变量的检验数0, 为唯一最优解.,c,j,6,-3,3,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,0,x,4,x,5,x,6,60,20,60,3,2,3,1,-2,3,1,4,-3,1,0,0,0,1,0,0,0,1,20,10,20,检验数,j,0,6,-3,3,0,0,0,0,6,0,x,4,x,1,x,6,30,10,30,0,1,0,4,-1,6,-5,2,-9,1,0,0,-3/2,1/2,-3/2,0,0,1,15/2,-,5,检验数,j,-60,0,3,-9,0,-3,0,22,0x4100011-1/2-2/36x115101/201/,0,x,4,10,0,0,1,1,-1/2,-2/3,6,x,1,15,1,0,1/2,0,1/4,1/6,-3,x,2,5,0,1,-3/2,0,-1/4,1/6,检验数,j,-75,0,0,-9/2,0,-9/4,-1/2,（2）对偶问题为：,y,* =(0，9/4，1/2),对偶问题的最优解：,23,0x4100011-1/2-2/36x115101/201/,建,立,模,型,决策变量个数,决策变量取值,右端项,等式或,不等式,极大或极小,新加变量系数,两,个,三个,以上,x,j,0,x,j,无,约束,x,j,0,b,i,0,b,i,0，边从j到i的方向是不饱和的；,（5，3）是不饱和的,间隙为,53,=f,53,=5,对于后向弧来讲(正向为3-5）,饱和弧、不饱和弧、流量的间隙,84,53fij=0cij=553fij=5cij=53、如果fi,设f=（f,ij,）是D中的一个可行流,若存在一条(v,s,- v,i,)链, 满足:,1.,对一切(i,j),+,有f,ij,c,ij,2.,对一切(i,j),-,有f,ij,0.,则称是一条关于f的(v,s,- v,i,)增广链,特别地,当v,i,= v,t,时,就称为一条关于f的增广链.,增 广 链,增广链由不饱和弧组成,85,设f=（fij）是D中的一个可行流,若存在一条(,步骤如下：,第二步：对点进行标号找一条增广链。,（1）发点标号,（）,（2）选一个点,v,i,已标号并且另一端未标号的弧沿着某条链向收点检查：,A如果弧的方向向前（前向弧）并且有,f,ij,0，则,v,j,标号:,j,f,ji,当收点已得到标号时，说明已找到增广链，依据,v,i,的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。,第一步： 找出第一个可行流，例如所有弧的流量,f,ij,=0,Ford-Fulkerson标号算法,86,步骤如下：第二步：对点进行标号找一条增广链。第一步： 找出第,第三步：调整流量,（1）求增广链上点,v,i,的标号的最小值，得到调整量,（2）调整流量,得到新的可行流,f,1,，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止,87,第三步：调整流量（2）调整流量得到新的可行流f1，去掉所有标,8,14,5,6,3,3,8,10,7,6,3,图619,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),【例】求图619发点,v,1,到收点,v,7,的最大流及最大流量,【解】,88,8145633810763图619(10)(,8,14,5,6,3,3,8,10,7,6,3,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),2,3,3,7,第一轮标号：,c,12,f,12,v,2,标号2,c,ij,=,f,ij,，,v,4,、,v,5,不能标号,后向弧,f,32,0,v,3,标号,3,=,f,32,增广链(1,2)，(3,2)，(3,4)，(4,7) ,+,=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值,min，2，3，3，72,89,8145633810763(10)(6)(3),8,14,5,6,3,3,8,10,7,6,3,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),调整后的可行流：,90,8145633810763(10)(8)(1),8,14,5,6,3,3,8,10,7,6,3,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),4,4,1,5,第二轮标号：,C,ij,=,f,ij,，,v,4,、,v,5,不能标号，返回到,v,3,增广链,(1,3)，(3,4)，(4,7) ，调整量为,min，4，1，51,91,8145633810763(10)(8)(1),8,14,5,6,3,3,8,10,7,6,3,图623,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),调整后得到可行流：,92,8145633810763图623(11)(,8,14,5,6,3,3,8,10,7,6,3,图622,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),3,1,4,第三轮标号：,增广链,(1,3)，(3,6)，(6,4)，(4,7) ，调整量为,min，3，1，2，41,2,93,8145633810763图622(11)(,8,14,5,6,3,3,8,10,7,6,3,图625,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),调整后得到可行流：,94,8145633810763图625(12)(,8,14,5,6,3,3,8,10,7,6,3,图622,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),2,第四轮标号：,v,7,得不到标号，不存在,v,1,到,v,7,的增广链，图6-22所示的可行流是最大流，最大流量为,vf,12,+,f,13,8+12=20,C,ij,=,f,ij,，,v,4,、,v,5,不能标号,C,ij,=,f,ij,，,v,4,、,v,6,不能标号,4,95,8145633810763图622(12)(,1）求,v,1到,v,10的最大流及最大流量；（2）求最小割集和最小割量。,96,1）求v1到v10的最大流及最大流量；（2）求最小割集和最小,第一轮标号：得到一条增广链，调整量等于5，如下图所示,97,第一轮标号：得到一条增广链，调整量等于5，如下图所示97,第二轮标号：得到一条增广链，调整量等于2，如下图所示,98,第二轮标号：得到一条增广链，调整量等于2，如下图所示98,第三轮标号：得到一条增广链，调整量等于3，如下图所示,99,第三轮标号：得到一条增广链，调整量等于3，如下图所示99,第四轮标号：不存在增广链，最大流量等于45，如下图所示,取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45。,100,第四轮标号：不存在增广链，最大流量等于45，如下图所示100,练习：,求网络的最大流与最小截集， 图中每条弧傍括号中的数字是（,C,ij,x,ij,),101,练习： 求网络的最大流与最小截集，,