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

《运筹学学习题胡运权版课件.ppt》由会员分享，可在线阅读，更多相关《运筹学学习题胡运权版课件.ppt（101页珍藏版）》请在三一办公上搜索。

1、,运筹学习题,2,主要内容,一、线性规划二、运输问题三、目标规划四、整数规划五、网络规划,3,一、线性规划,1LP问题的数学模型2图解法3. LP问题解的基本概念4单纯形法5. 对偶问题(LP的对偶问题、对偶单纯形法)6. 灵敏度分析,4,建立坐标系，将约束条件在图上表示；确立满足约束条件的解的范围（可行域）；绘制出目标函数的图形；确定最优解。,图解法的步骤,5,最优解的确定：,唯一最优解,6,无穷多最优解的情况：,目标函数与某个约束条件恰好平行,7,无界解（或无最优解）的情况：,可行域上方无界,8,无可行解的情况：,约束条件不存在公共范围,9,单纯形表,10,（最优解判定定理） LP的典式（

2、） ，如果有,则对应于基B的基可行解,是线性规划的最优解，记为,相应的目标函数最优值,（无界解判定定理）,11,解的几种情况在单纯形表上的体现（max型）：,唯一最优解：终表非基变量检验数均小于零；多重最优解：终表非基变量检验数中有等于零的；无界解：任意表有正检验数相应的系数列均非正。无解：最优解的基变量中含有人工变量,12,13,非基变量得检验数j0， 3=0, 有无穷多最优解，x*=(2,15/2,0,0,42,0)T , z*=47,14,练习1：,某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利

3、润见下表：,(1)求获利最大的产品生产计划；(2)产品III每件的利润增加到多大时才值得安排生产；(3)如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小时，预期每件的利润为8元，是否值得安排生产。,15,解：（1）设x1，x2，x3分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：,标准型,16,所以最优解为x* =(100/3，200/3，0，0，0，100)T，即产品I、II、III的产量分别为：100/3，200/3，0；最优解目标函数值z* =2200/3,17,（2）设产品III每件的利润为c3,产品III每件的利润增加到20/3时才值得安排生产

4、。,18,（3）设x7为新产品的产量。,19,所以最优解为x* =(100/3，0，0，0，0，100/3 ，200/3)T，即产品 I 的产量：100/3，新产品的产量：200/3；最优解目标函数值z* =2600/3,20,练习2：,已知下列线性规划问题，求：（1）用单纯形法求解，并指出问题属于哪一类解； （2）写出该问题的对偶问题，并求出对偶问题的最优解；,21,解：（1）将原问题划为标准形式：,22,所以最优解为x* =(15，5，0，10，0，0)T , 最优解目标函数值z* =75非基变量的检验数0, 为唯一最优解.,23,（2）对偶问题为：,y* =(0，9/4，1/2),对偶问

5、题的最优解：,24,根据上表列出初始单纯形表,线性规划小结,25,找出初始基可行解列出初始单纯形表,计算非基变量的检验数,唯一最优解,所有,是,否,否,否,对某一个 有,是,无界解,是,无可行解,是,无穷多最优解,否,用非基变量替换基变量列出新的单纯形表,循环,26,原问题P与对偶问题D的关系表,27,对偶规划的求解利用原问题的最优单纯形表求对偶最优解对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。对称形式的对偶问题，用单纯形法得到(P)问题的最优解的同时，也得到（D）问题的最优解。,(D)问题最优解的负值,28,利用互补松弛定理求对偶最优解,定理2.4 互补松弛定理：

6、 设 和 分别是问题(P)和(D)的可行解，则它们是最优解的充要条件是,同时成立,一个线性规划的某一约束是某个最优解的松约束（严格不等式），对应的对偶规划中的变量取0，当某个变量不为0时，对应的对偶规划中约束是紧约束（严格等式）。,29,练习3：,已知线性规划问题： 求：（1）用图解法求解； （2）写出其对偶问题； （3）根据互补松弛定理，写出对偶问题的最优解。,30,解：（1）图解法,由上图可知：在B(2,4)处，目标函数达到最大值。即最优解为x*=(2,4)T 最优解目标函数值z*=10, 为唯一最优解,31,（2）该问题的对偶问题为：,（3）原问题的最优解x*=(2,4)T 代入约束条件

7、，可知约 束条件取等式，因为x1*，x2*不为0，在对偶问题中相应的约束条件为紧约束，即,对偶问题的最优解及最优目标函数值为：,32,这说明yi是右端项bi每增加一个单位对目标函数z 的贡献。对偶变量的值 yi*所表示的第i种资源的边际价格，称为影子价格。,bi 表示第 i种资源的拥有量； 对偶变量yi*代表在资源最优利用条件下，对单位第 i种资源的估价。是根据资源在生产中作出的贡献而作的估价。,对偶定理：若 (P)和(D)的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。,对偶问题的经济解释影子价格,33,原始单纯形法与对偶单纯形法的对应关系,对偶单纯形法,34,用对偶单纯形法

8、求解LP,（P）,初始对偶单纯形表,35,b=B-1b0 ，最优解 x*=(11/5，2/5，0，0，0)T , z *= - 28/5 z*= 28/5,确定进基变量= min-2/-2, -,-4/-3=1,确定出基变量min-3,-4=-4,确定出基变量min-1,2= -1,确定进基变量= min-2/(-5/2), -,-1/(-1/2)=4/5,36,二、运输问题表上作业法,适合于产销平衡的运输问题产销不平衡问题要转化为产销平衡问题求解步骤：（1）求一个初始调运方案（初始基可行解）：在mn维产销平衡表上给出m+n-1个数字。用西北角法、最小元素法、 Vogel法（2）判断当前方案是

9、否为最优（最优性检验）：计算各非基变量的检验数，当ij0最优。用闭回路法、位势法（3）方案调整与改进：确定进基变量和离基变量，找出新的基可行解(闭回路调整法)。返回（2）,37,某百货公司到甲、乙、丙三地采购A、B、C、D四种规格服装，预计销售后每套服装可得利润如下表：,请帮助该公司设计一个预期利润最大的方案。,练习：,38,解：产量销量，假想一个销地E，销量为1000,该问题求最大利润，将极大化问题化为极小化问题,39,接着再用表上作业法求解：用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。,4

10、0,三、目标规划数学模型,基本概念回顾1、目标值和偏差变量2、目标约束和绝对约束3、优先因子（优先等级）与优先权系数4、达成函数（即目标规划中的目标函数）5、满意解（具有层次意义的解）,41,某工厂计划生产A、B两种产品，需要消耗甲、乙、丙三种资源、单位产品利润及资源限量如表所示：,该厂的经营目标是：首先要求总利润必须超过2500元；然后考虑到产品受市场影响，为避免积压，A、B的产量不超过60件和100 件；由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型。,练习：,42,解：设x1，x2 为产品A、B产量，以产品 A、B 的单件利润比 2.5:1 为权系数，目标规划模型如下：

11、,43,四、整数规划,101整数规划的数学模型2指派问题3. 分枝定界与割平面法,44,在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用见下表，假定每一项已经批准的工程要在整个3年内完成，目标是要选出使总收入达到最大的那些工程，试将这个问题表示成0-1整数规划模型。,练习1：,45,解：设,该问题的0-1整数规划模型为：,46,分配甲、乙、丙、丁、戊五个人去完成A、B、C、D、E五项工作，每个人完成各项任务的时间如下表所示。 (表中单位：小时),已知甲不可能完成任务D，丁只可以完成任务B、C，试确定最优分配方案，使完成任务的总时间为最少。,练习3：,47,有五个车队将分赴五个地区，

12、各车队去各地区的收入如下表：,每个车队去一个地区，每个地区有一个车队去。求使总收入最大的指派方案。,练习4：,48,五、网络规划,1 最小支撑树问题2 最短路问题3 最大流问题,49,1 最小支撑树（最小树）,设T=(,) 是赋权图（网络） G=(,)的一棵支撑树， 的所有边的权数之和称为支撑树T的权数。图G的所有支撑树中，具有最小权数的支撑树是图G的最小支撑树（最小树）。最小树的应用：例如设计长度最小的公路网把若干城市联系起来；设计用料最省的电话线网把有关单位联系起来等。,50,破圈法,在图中找圈，并删除其中最大边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条边）。如此进行下去

13、，直至图中不存在圈。,51,避圈法（Kruskal算法）,把边按权从小到大依次添入图中（若有两条或两条以权数相同且最小，则任取一条），要求添加的边不构成圈，直至填满n-1条边为止（n为结点数）,例6.5,52,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,破圈法,53,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,54,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,55,v1,v7,v4,v3,v2,v5,v6,20,15

14、,9,16,25,3,28,17,4,1,23,56,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,57,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,58,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,59,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,60,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,61,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,62,v1,

15、v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,总造价=1+4+9+3+17+23=57,63,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,避圈法,64,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,65,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,66,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,67,v1,v7,v4,v3,v2,v

16、5,v6,20,15,9,16,25,3,28,17,4,1,23,36,68,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,69,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,总造价=1+4+9+3+17+23=57,70,最小树的权数 w(T) =18,71,2 最短路问题,问题描述： 求网络中起点vs到其它点（终点vt ）之间的一条最短路线。最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为

17、一个基本工具，用于解决其它的优化问题.,72,狄克斯屈拉(Dijkstra)标号算法,点标号b(i)起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+cij，,步骤：(1)令起点的标号；b(1)0。,先求有向图的最短路，设网络图的起点是vs ,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为cij,(2)找出所有vi已标号vj未标号的弧集合 B=(i，j)，如果这样的弧不存在或vt已标号则计算结束；,(3)计算集合B中弧k(i，j)=b(i)+cij的标号,(4)选一个点标号 返回到第(2)步。,73,6,10,12,3,2,14,6,7,5,8,11,16,5,图6

18、6,9,0,6,10,12,9,20,9,18,6,16,12,17,16,24,32,18,29,29,【例】用Dijkstra算法求图66 所示v1到v7的最短路及最短路长,v1 到v7的最短路为：p17=v1, v2, v3, v5, v7，最短路长为L17=29,14,74,(0,0),(s, +),(s, 3),(s, +),(s, +),(s, +),(s, +),(s, +),(s, 7),(s, 4),(1, 5),(1, 7),(3, 11),(2, 11),(4, 8),(5, 10),75,例：用标号法求下图网络最短路,3,9,4,7,3,2,6,1,4,1,2,8,7,

19、1,10,76,第一步：,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,77,第二步：,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,78,第三步：,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,79,最终：依此类推，重复上述标号过程。得最短路。,3,9,4,7,3,2,6,1,4,1,2,8,7,1,10,80,求A到H、I的最短路及最短路长,81,A到H的最短路PAH=A,B,F,H,A,C,F,H最短路长22；A到I的最短路PAI=A,B,F,I,A,C,F,I最短路长21。,82,A到H的最短路PAH=A,C,G,F,H,最短路长21；A

20、到I的最短路PAI=A,C,G,F,I,最短路长20,83,3 最大流问题,问题描述：网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。 许多流量问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。,84,3、如果fij=0，边从j到i的方向是饱和的；,（5，3）是饱和的,4、如果fij0，边从j到i的方向是不饱和的；,（5，3）是不饱和的间隙为53=f53=5,对于后向弧来讲(正向为3-5）,饱和弧、不饱和弧、流量的间隙,85,设f=（fij）是D中的一个可行流,若存在一条(vs- vi)链, 满足:

21、1. 对一切(i,j)+,有fijcij,2. 对一切(i,j)-,有fij0.则称是一条关于f的(vs- vi)增广链,特别地,当vi= vt时,就称为一条关于f的增广链.,增 广 链,增广链由不饱和弧组成,86,步骤如下：,第二步：对点进行标号找一条增广链。（1）发点标号（）（2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查： A如果弧的方向向前（前向弧）并且有fij0，则vj标号: jfji当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。,第一步： 找出第一个可行流，例如所有弧的流量fij

22、=0,Ford-Fulkerson标号算法,87,第三步：调整流量（1）求增广链上点vi 的标号的最小值，得到调整量,（2）调整流量,得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止,88,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发点v1到收点v7的最大流及最大流量,【解】,89,8,14,5,6,3,3,8,10,7,6,3,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1

23、),(7),2,3,3,7,第一轮标号：,c12f12,v2标号2,增广链(1,2)，(3,2)，(3,4)，(4,7) ,+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值min，2，3，3，72,90,8,14,5,6,3,3,8,10,7,6,3,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),调整后的可行流：,91,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,第二轮标号：,增广链

24、(1,3)，(3,4)，(4,7) ，调整量为 min，4，1，51,92,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),调整后得到可行流：,93,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,94,8,14,5,6,3,3,8,10,7,6,3,图

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