运筹学期末复习.ppt

《运筹学期末复习.ppt》由会员分享，可在线阅读，更多相关《运筹学期末复习.ppt（159页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1运筹学总复习运筹学总复习2第八章第八章排队论排队论3s 系统中系统中并联服务台的数目并联服务台的数目；平均到达率平均到达率（单位时间到达的顾客数）；（单位时间到达的顾客数）；1/平均到达间隔平均到达间隔（相继到达顾客的平均间隔（相继到达顾客的平均间隔时间）。时间）。平均服务率平均服务率（单位时间服务的顾客数）；（单位时间服务的顾客数）；1/平均服务时间平均服务时间（为顾客服务的平均时间）。（为顾客服务的平均时间）。服务强度服务强度，即每个服务台单位时间内的，即每个服务台单位时间内的平均服务时间；平均服务时间；一般有一般有 s ；稳态排队系统的参数稳态排队系统的参数4 Pn=PN=n：稳稳态态

2、系系统统任任一一时时刻刻状状态态为为n（系统中（系统中恰好有恰好有n个顾客个顾客）的概率；）的概率；特特别别当当n=0时时，Pn即即P0，为为稳稳态态系系统统所有服务台全部空闲的概率。所有服务台全部空闲的概率。稳态下系统的基本数量指标稳态下系统的基本数量指标5到到达达的的顾顾客客不不一一定定全全部部进进入入系系统统接接受受服服务务，设设系系统统中中有有n个个顾顾客客时时，每每单单位位时时间间进进入入系系统统的的顾顾客客平平均均数数为为 n，每每单单位位时时间间离离开开系系统统的的顾顾客平均数为客平均数为 n。我们引入：。我们引入：e 有有效效平平均均到到达达率率，即即每每单单位位时时间间实实际

3、际进进入入系系统统的的平平均均顾顾客客数数（期期望值），望值），e=npn对等待制的排队系统，有对等待制的排队系统，有 e 6平均有效离去率平均有效离去率:e=n pn 从平稳系统中均值的意义看，容易理解从平稳系统中均值的意义看，容易理解应有应有平均有效离去率等于平均有效平均有效离去率等于平均有效到达率到达率，即，即 e=e7L,Lq,e,W,Wq 之间的关系：之间的关系：L=eW,Lq=e Wq几何解释：稳态时，一个顾客，进入系几何解释：稳态时，一个顾客，进入系统后，每单位时间平均到达统后，每单位时间平均到达 e e顾客。顾客。eeeee进入时刻进入时刻离开时刻离开时刻总时间总时间W队长队长

4、L由时间段内由时间段内W个个 e组成的组成的L=eW5)Little公式公式8同理：同理：Lq=eWq又又W=Wq+（1/）-W与与Wq只相差一段平均服务时间只相差一段平均服务时间1/L=Lq+(e/)5)Little公式公式以上公式对一般泊松输入以上公式对一般泊松输入指数排指数排队模型成立。队模型成立。9对于平均队长和平均队列长，可用下列公对于平均队长和平均队列长，可用下列公式计算式计算 因此，只要知道因此，只要知道 ，则，则 或或 就可由以上两公式求得，从而再由上面四就可由以上两公式求得，从而再由上面四公式就能求得四项主要工作指标。公式就能求得四项主要工作指标。10排队论求解的主要数量指标

5、排队论求解的主要数量指标P0、Pn、L、Lq、W、Wq11单服务台无限源系统单服务台无限源系统M/M/1/FCFSM/M/1/N/FCFS12M/M/1/FCFS系统系统:参数参数，问题的一般提法：泊松输入泊松输入/负指数分布负指数分布/单服务台单服务台/系统无系统无限制限制/顾客源无限制顾客源无限制求解：(1)系统状态系统状态P0、Pn (2)系统运行指标：系统运行指标：L、Lq、W、Wq13M/M/1/FCFS排队系统模型的主要指标排队系统模型的主要指标1、系统中无顾客的概率：、系统中无顾客的概率：P0=1 2、系统中有、系统中有n个顾客的概率：个顾客的概率：Pn=n.(1)3、系统中的平

6、均顾客数：、系统中的平均顾客数：L=/(1)4、顾客在系统中的平均逗留时间：、顾客在系统中的平均逗留时间：W=L/5、顾客花在排队上的平均等待时间：、顾客花在排队上的平均等待时间：Wq=W-1/u6、平均排队的顾客数：、平均排队的顾客数：Lq=Wq141 1、例子例子 P216P216 某医院急诊室同时只能诊治某医院急诊室同时只能诊治1 1个病人，个病人，诊治时间服从指数分布，每个病人平均需诊治时间服从指数分布，每个病人平均需要要1515分钟。病人按泊松分布到达，平均每分钟。病人按泊松分布到达，平均每小时到达小时到达3 3人。求该排队系统的主要数量指人。求该排队系统的主要数量指标。标。15由题

7、意知：该题是由题意知：该题是M/M/1/FCFS排队系统排队系统(人小人小时时)，60154(人小人小时时)故服务强度为故服务强度为其中，其中，p0是急是急诊诊室空室空闲闲的概率，也是病人不必的概率，也是病人不必等待立即就能就等待立即就能就诊诊的概率。的概率。16此模型的平均有效到达率，即是到达率此模型的平均有效到达率，即是到达率 病人在急病人在急诊诊室内外平均逗留室内外平均逗留时间时间：病人平均等候病人平均等候时间时间：(小小时时)45(分分钟钟)急诊室内外的病人平均数：急诊室内外的病人平均数：（人）（人）（小时）（小时）急急诊诊室外排室外排队队等待的病人平均数：等待的病人平均数：(人人)1

8、72、某医院手术室只能同时诊治一个病人，病某医院手术室只能同时诊治一个病人，病人到达服从泊松分布，每小时病人平均到达率人到达服从泊松分布，每小时病人平均到达率为为2.1(人人/小时小时)。每次手术平均时间。每次手术平均时间0.4(小时小时/人人)，服从负指数分布求：，服从负指数分布求：(1)病房中病人的平均数病房中病人的平均数(L)；(2)排队等待手术病人的平均数排队等待手术病人的平均数(Lq)；(3)病人在病房中平均逗留时间病人在病房中平均逗留时间(W)(4)病人排队等待时间病人排队等待时间(Wq)。18193、某医院急诊室每小时到达一个病人，输入为最简某医院急诊室每小时到达一个病人，输入为

9、最简单流，急诊室仅有一名医生，病人接受紧急护理平单流，急诊室仅有一名医生，病人接受紧急护理平均需均需20分钟，服务时间为负指数分布，试求：分钟，服务时间为负指数分布，试求：（1）稳态情况下：稳态情况下：a)没有病人的概率；没有病人的概率；b)有两个有两个病人的概率；病人的概率；c)急诊室里病人的平均数；急诊室里病人的平均数；d)排队中病排队中病人的平均数；人的平均数；e)病人在急诊室中的平均时间病人在急诊室中的平均时间（2）为了保证病人急诊所花费的平均时间少于）为了保证病人急诊所花费的平均时间少于25分钟，那么平均紧急护理时间必须降至多少分钟分钟，那么平均紧急护理时间必须降至多少分钟?2021

10、22第七章第七章 动态规划动态规划23动态规划的基本概念动态规划的基本概念1 1)阶段和阶段变量阶段和阶段变量 阶阶段段是是按按决决策策进进行行的的时时间间或或空空间间上上先先后后顺顺序序划划分分的的。用用以以描描述述阶阶段段的的变变量量叫叫作作阶阶段段变变量量，一一般般以以k表表示示阶阶段段变变量量阶阶段段数数等等于于多多阶阶段段决决策策过过程程从从开开始始到到结结束所需作出决策的数目。束所需作出决策的数目。242 2）状态、状态变量和可能状态集状态、状态变量和可能状态集 描描述述事事物物(或或系系统统)在在某某特特定定的的时时间间与与空空间间域域中中所所处处位位置置及及运运动动特特征征的的

11、量量，称称为为状状态态。反反映映状状态态变变化化的量叫做的量叫做状态变量状态变量。25 每每个个阶阶段段的的状状态态可可分分为为初初始始状状态态和和终终止止状状态态，或或称称输输入入状状态态和和输输出出状状态态，阶阶段段k的的初初始始状状态态记记作作sk，终终止止状状态态记记为为sk+1。通通常常定义阶段的状态即指其初始状态定义阶段的状态即指其初始状态。26 一一般般状状态态变变量量的的取取值值有有一一定定的的范范围围或或允允许许集集合合，称称为为可可能能状状态态集集，可可能能状状态态集集用用相相应应阶阶段段状状态态sk的的大大写写字字母母Sk表表示示，sk Sk，可可能能状状态态集集可可以以

12、是是一一离离散散取取值值的的集集合合，也也可可以以为为一一连连续续的的取值区间，视具体问题而定取值区间，视具体问题而定273）决策、决策变量和允许决策集合决策、决策变量和允许决策集合 决决策策的的实实质质是是关关于于状状态态的的选选择择，是是决决策策者者从从给给定定阶阶段段状状态态出出发发对对下下一阶段状态作出的选择。一阶段状态作出的选择。28 用以描述决策变化的量称之用以描述决策变化的量称之决策决策变量变量。决策变量的值可以用数，向。决策变量的值可以用数，向量、其它量，也可以是状态变量的量、其它量，也可以是状态变量的函数函数.记记uk=uk(sk)，表示于阶段，表示于阶段k 状态为状态为sk

13、 时的决策变量。时的决策变量。29 决决策策变变量量的的取取值值往往往往也也有有一一定定的的允允许许范范围围，称称之之允允许许决决策策集集合合。决决策策变量变量uk(sk)的允许决策集用的允许决策集用Uk(sk)表示表示,uk(sk)Uk(sk)允允许许决决策策集集合合实实际际是是决决策策的的约约束束条条件。件。304）策略和允许策略集合策略和允许策略集合策策略略(Policy)也也叫叫决决策策序序列列策策略略有有全全过过程程策策略略和和k部部子子策策略略之之分分，全全过过程程策策略略是是指指由由依依次次进进行行的的n个个阶阶段段决决策策构构成成的的决决策策序序列列，简简称称策策略略，表表示为

14、示为p1,nu1,u2,un。31 从从k 阶阶段段到到第第n 阶阶段段，依依次次进进行行的的阶阶段段决决策策构构成成的的决决策策序序列列称称为为k 部部子子策策略略,表表示示为为pk,nuk,uk+1,un，显显然然当当k=1时时的的k 部部子子策策略略就就是是全全过程策略过程策略。32 在实际问题中，由于在各个阶在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选它们的不同组合就构成了许多可供选择的决策序列择的决策序列(策略策略)，由它们组成的，由它们组成的集合，称之集合，称之允许策略集合允许策略集合，记作，记作P1,n

15、，从允许策略集中，找出具有最优效，从允许策略集中，找出具有最优效果的策略称为果的策略称为最优策略最优策略。335）状态转移方程状态转移方程 系系统统在在阶阶段段k处处于于状状态态sk，执执行行决决策策uk(sk)的的结结果果是是系系统统状状态态的的转转移移，即即系系统统由由阶阶段段k的的初初始始状状态态sk转转移移到到终止状态终止状态sk+1。34 系系统统状状态态的的这这种种转转移移，用用数数学学公式描述即有：公式描述即有：通通常常称称上上式式为为多多阶阶段段决决策策过过程程的的状状态态转转移移方方程程。有有些些问问题题的的状状态态转转移移方方程程不不一一定定存存在在数数学学表表达达式式，但

16、但是是它它们们的的状状态态转转移移，还是有一定规律可循的。还是有一定规律可循的。356)6)指标函数指标函数 用用来来衡衡量量策策略略或或子子策策略略或或决决策策的的效效果果的的某某种种数数量量指指标标，就就称称为为指指标标函函数数。它它是是定定义义在在全全过过程程或或各各子子过过程程或或各各阶阶段段上上的的确确定定数数量量函函数数。对对不不同同问问题题，指指标标函函数数可可以以是是诸诸如如费费用用、成成本本、产产值值、利利润润、产产量量、耗耗量量、距距离离、时时间间、效效用等等。用等等。36阶段指标函数（阶段效应）阶段指标函数（阶段效应）用用gk(sk,uk)表表示示第第k段段处处于于sk状

17、状态态且且所所作作决决策策为为uk(sk)时时的的指指标标，则则它就是第它就是第k段指标函数，简记为段指标函数，简记为gk37过程指标函数（目标函数）过程指标函数（目标函数）用用Rk(sk,uk)表表示示k子子过过程程的的指指标标函函数数。Rk(sk,uk)不不仅仅跟跟当当前前状状态态sk有有关关，还还跟跟该该子子过过程程策策略略pk(sk)有有关关，因因此此它它是是sk和和pk(sk)的的函函数数，严严格格说说来来，应表示为，应表示为:387)最优解最优解用用 fk(sk)表表 示示 第第 k子子 过过 程程 指指 标标 函函 数数，在状态，在状态sk下的最优值下的最优值,即即称称fk(sk

18、)为为第第k子子过过程程上上的的最最优优指指标函数；标函数；39相相应应的的子子策策略略称称为为sk状状态态下下的的最最优优子子策策略略，记记为为pk*(sk)；而而构构成成该该子子策策赂赂的的各各段段决决策策称为该过程上的称为该过程上的最优决策最优决策，记为，记为有有 简记为简记为40特别，特别，当当k=1且且s1取值唯一时，取值唯一时，f1(s1)就是问题的最优值，而就是问题的最优值，而p1*就是最就是最优策略。优策略。41 最最优优策策略略即即为为s1=s1*状状态态下下的的最最优优策略：策略：我我们们把把最最优优策策略略和和最最优优值值统统称称为为问问题的最优解。题的最优解。428)8

19、)多阶段决策问题的数学模型多阶段决策问题的数学模型 适适于于动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决决策策问问题题，即即具具有有无无后后效效性性的的多多阶阶段段决决策策问问题题的的数数学模型学模型:43常用求最小的加法计算公式常用求最小的加法计算公式：（边界条件）（边界条件）阶段指标阶段指标44动态规划方法的基本步骤动态规划方法的基本步骤用用函函数数基基本本方方程程逆逆推推求求解解是是常常用用的的方方法法：首首先先要要有有效效地地建建立立动动态态规规划划模模型型,然然后后再再递递推推求求解解基基本本方方程程,最最后后回溯求得最优策略回溯求得最优策略。合合理理、有有效效地地建建

20、立立一一个个动动态态规规划划模模型型,是解决问题的关键。是解决问题的关键。45（一）动态规划建模要点（一）动态规划建模要点 将将实实际际问问题题恰恰当当地地分分割割成成n个个子子问题问题(n个阶段个阶段)通通常常是是根根据据时时间间或或空空间间而而划划分分，或或者者在在经经由由静静态态的的数数学学规规划划模模型型转转换换为为动动态态规规划划模模型型时时，常常取取静静态态规规划划中变量的个数中变量的个数n。46动态规划建模要点动态规划建模要点 正确地定义状态变量正确地定义状态变量sk，使它既能正确，使它既能正确地描述过程的状态，又能满足无后效性地描述过程的状态，又能满足无后效性。在动态规划模型中

21、，一般状态变量要选在动态规划模型中，一般状态变量要选取那种取那种可以进行累计的量可以进行累计的量。47动态规划建模要点动态规划建模要点 正正确确地地定定义义决决策策变变量量及及各各阶阶段段的的允许决策集合允许决策集合Uk(sk)。一一般般将将问问题题中中待待求求的的量量选选作作动动态态规划模型中的决策变量。规划模型中的决策变量。48动态规划建模要点动态规划建模要点 正确地写出状态转移方程正确地写出状态转移方程 要要能能正正确确反反映映状状态态转转移移规规律律。如如果果给给定定第第k阶阶段段状状态态变变量量sk 的的值值，则则该该段段的的决决策策变变量量uk 一一经经确确定定，第第k+1段段的的

22、状状态态变变量量sk+1的的值值也也就就完完全全确定，即有确定，即有 sk+1=Tk(sk,uk)49动态规划建模要点动态规划建模要点 正确地写出目标函数正确地写出目标函数 目目标标函函数数由由递递推推关关系系构构成成，因因此此，它应满足下列性质：它应满足下列性质：函数可分性：函数可分性：阶段指标相对独立阶段指标相对独立；要满足递推关系；要满足递推关系；过程函数严格单调。过程函数严格单调。50动态规划基本方程动态规划基本方程fn+1(sn+1)=0(边界条件边界条件)fk(sk)=optugk(sk,uk)+fk+1(sk+1)k=n,n-1,151（二）逆序求解动态规划基本方程（二）逆序求解

23、动态规划基本方程 常见三种情况：一种是对于常见三种情况：一种是对于特殊的网络求最优特殊的网络求最优路径路径，可以直接在网络图上，直观地使用，可以直接在网络图上，直观地使用标号标号法法（见下一节）求解；（见下一节）求解；对于对于离散型离散型的动态规划问题，常使用的动态规划问题，常使用列表格列表格（递推方程）（递推方程）的方法求解。的方法求解。当阶段指标与递推公式可表示为解析显函数时，当阶段指标与递推公式可表示为解析显函数时，对于规模较大，特别是对于规模较大，特别是连续型连续型的动态规划问题，的动态规划问题，常直接常直接使用函数求优使用函数求优的方法。的方法。52（三）回溯求得最优策略（三）回溯求

24、得最优策略 从从k=1k=1开始，逐步向后归纳出开始，逐步向后归纳出前一环节各步所选择的决策，得到前一环节各步所选择的决策，得到决策序列，即最优策略。决策序列，即最优策略。531 1、例子例子 P176P176用用递推方程递推方程求解最短路径问题求解最短路径问题54（一）建模（一）建模如图划分成如图划分成5个阶段；个阶段；状态变量状态变量sk表示第表示第k阶段开始的位置；阶段开始的位置；决决策策变变量量uk定定义义为为到到达达下下一一站站所所选选择择的的路路径；径；状态转移：决策确定了下一阶段的状态；状态转移：决策确定了下一阶段的状态；阶段指标：图中线段上所标的数值；阶段指标：图中线段上所标的

25、数值；55最优指标函数最优指标函数fk(sk)：表示从目前状态到表示从目前状态到E的最短路径。的最短路径。终端条件为终端条件为f5(s5)=f5(E)=0其其含含义义是是从从E到到E的的最最短短路路径径为为0。56（二）逆推求解（二）逆推求解第第4阶段的递推方程为阶段的递推方程为从从f5(s5)到到f4(s4)的递推过程用下表表示的递推过程用下表表示 s4U4(s4)s5g4(s4,u4)g4(s4,u4)+f5(s5)f4(s4)最最优优决策决策u4*C1C1EE55+0=5*5C1EC2C2EE88+0=8*8C2E57第第3阶段的递推方程为：阶段的递推方程为：从从f4(s4)到到f3(s

26、3)的的递递推推过过程用表格表示如下表：程用表格表示如下表：s3U3(s3)s4g3(s3,u3)g3(s3,u3)+f4(s4)f3(s3)最优决策u3*B1B1C1B1C2C1C2 6 5 6+5=11*5+8=1311B1C1B2B2C1B2C2C1C2 98 9+5=14*8+8=1614B2C158第第2阶段阶段的递推方程为的递推方程为从从f3(s3)到到f2(s2)的递推过程用表格表示如下的递推过程用表格表示如下59s2U2(s2)s3g2(s2,u2)g2(s2,u2)+f3(s3)f2(s2)最最优优决策决策u2*A1A1B1A1B2B1B2 6 56+11=17*5+14=1

27、917A1B1A2A2B1A2B2B1B2 8 68+11=19*6+14=2019A2B1A3A3B1A3B2B1B2 7 47+11=18*4+14=18*18A3B1A3B260第第1 1阶段的递推方程为：阶段的递推方程为：s1U1(s1)s2g1(s1,u1)g1(s1,u1)+f2(s2)f1(s1)最最优优决策决策u1*S S A1S A2SA3A1A2A34334+17=21*3+19=223+18=21*21S A1S A361由此得到由此得到f1(s1)=21,即从即从A 到到E的最短路径长度为的最短路径长度为21。（三）（三）回溯求最优策略：回溯求最优策略：由由f1(s1)

28、向向f4(s4)回溯，得到最短路径为：回溯，得到最短路径为：S A1 B1 C1 ES A3 B1 C1 ES A3 B2 C1 E622 2、见以下有向图，图中数字为两点间距离、见以下有向图，图中数字为两点间距离 要求：要求：用表格（递推方程）计算。用表格（递推方程）计算。（1 1）求出）求出ADAD的最短路径以及最短长度；的最短路径以及最短长度；（2 2）用双箭头在图上注明。）用双箭头在图上注明。63参考答案参考答案A A到到D D的最短路径：的最短路径：ABAB3 3 C C1 1 D D最短长度：最短长度：212164第四章第四章 运输问题运输问题651.求初始基本可行解求初始基本可行

29、解 （西北角法、（西北角法、最小元素法最小元素法）2.求检验数（求检验数（位势法位势法）3.换基（换基（闭回路闭回路）表上作业法：表上作业法：661 1、初始基本可行解的确定、初始基本可行解的确定 （1 1）西北角法）西北角法：从：从西北角（左上角）格西北角（左上角）格开始开始，在格内的右下角标上允许取得的最，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。直至得到一个基

30、本可行解。67 （2）最小元素法）最小元素法：从：从运价最小的格运价最小的格开始开始，在格内的右下角标上允许取得的，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。行下去，直至得到一个基本可行解。68 注注:应用西北角法和最小元素法，每应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有次填完数，都只划去一行或一列，只有最后一个元例外最后一个元例外（同时划去一行和一列

31、）。（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列应任意划去一行（列），在保留的列（行）中没被划去的格内标一个（行）中没被划去的格内标一个0 0。69 由于目标要求极小，因此，由于目标要求极小，因此，当所有的当所有的检验数都大于或等于零时该调运方案就是检验数都大于或等于零时该调运方案就是最优方案最优方案；否则就不是最优，需要进行调；否则就不是最优，需要进行调整。整。2 2、基本可行解的最优性检验、基本可行解的最优性检验 70位势法位势法 位位势势：设设对对应应基基变变量量xij的的m+n-1个个ij，存在，存在ui,

32、vj满足满足ui+vj=cij，i=1,2,m;j=1,2,n.称称这这些些ui,vj为为该该基基本本可可行行解解对对应应的位势。的位势。71由于有由于有m+n个变量（个变量（ui,vj），），m+n-1个方程（基变量个数），个方程（基变量个数），故有一个自由变量，位势不唯一故有一个自由变量，位势不唯一。利用位势求利用位势求非非基变量基变量xij的检验数：的检验数：ij=cij-ui-vji=1,m;j=1,n72位势法求检验数：位势法求检验数：step1从从任意基变量对应的任意基变量对应的cij开始开始,任取任取 ui或或vj，然后利用公式，然后利用公式cij=ui+vj依次找依次找出出m+

33、n个个ui,vjstep2计算非基变量的检验数计算非基变量的检验数 ij=cij-ui-vj；填入圆圈内；填入圆圈内73 当当非非基基变变量量的的检检验验数数出出现现负负值值时时，则则表表明明当当前前的的基基本本可可行行解解不不是是最最优优解解。在在这这种种情情况况下下，应应该该对对基基本本可可行行解解进进行行调调整整，即即找找到到一一个个新新的的基基本本可可行行解解使使目目标标函函数数值值下下降降，这这一一过过程程通通常常称称为为换换基基(或主元变换或主元变换)过程（过程（闭回路法闭回路法）。3 3、求新的基本可行解、求新的基本可行解7474（1）选负检验数中最小者）选负检验数中最小者 rk

34、，那么，那么xrk为主元，作为为主元，作为进基变量进基变量（上页图中（上页图中x24）;（2）以以xrk为起点找一条闭回路为起点找一条闭回路，除，除xrk外其余顶点必须为基变量格（上页图中外其余顶点必须为基变量格（上页图中的回路）的回路）;在运输问题的表上作业法中，换基的过程在运输问题的表上作业法中，换基的过程是如下进行：是如下进行：7575（3）为闭回路的每一个顶点标号，为闭回路的每一个顶点标号，xrk为为1号号，沿一个方向（顺时针或逆时针）依次，沿一个方向（顺时针或逆时针）依次给各顶点标号；给各顶点标号；（4）求求 =Minxij xij对应闭回路上的偶数对应闭回路上的偶数标号格标号格=x

35、pq 那么那么确定确定xpq为为出基变量出基变量，为调整量；为调整量；7676（5）对闭回路的各对闭回路的各奇标号顶点调整为：奇标号顶点调整为：xij+，对各，对各偶标号顶点偶标号顶点调整为：调整为：xij-，特别，特别 xpq-=0，xpq变为非基变量。变为非基变量。重复重复(2)、(3)步，直到所有检验数均步，直到所有检验数均非负，得到最优解。非负，得到最优解。77注意：注意：（1）构造闭回路进行换基时，只有）构造闭回路进行换基时，只有一个基变量出基，一个非基变量进基；一个基变量出基，一个非基变量进基；（2）如果偶标号格中两个变量减去）如果偶标号格中两个变量减去调整量后都变为零，则取其中一

36、个为调整量后都变为零，则取其中一个为出基变量，另一个填上运量出基变量，另一个填上运量0。77781、例子例子P99798081所有所有 ij0，得到，得到最优解最优解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余其余xij=0;最优值最优值：f*=35+102+13+81+46+53=85822、用表上作业法求解下列运输问题用表上作业法求解下列运输问题销地销地产地产地B1B2B3B4产量产量A1847290A25835100A37729120销量销量7050110808384第三章第三章线性规划对偶与灵敏度分析线性规划对偶与灵敏度分析85对偶规划的形式对偶规划的形

37、式有有对称形式对称形式和和非对称形式非对称形式。对对称称形形式式的的对对偶偶规规划划之之间间具具有有下下面面的的对应关系：对应关系：(1)若若一一个个模模型型为为目目标标求求“极极大大”，约约束束为为“小小于于等等于于”的的不不等等式式，则则它它的的对对偶偶模模型型为为目目标标求求“极极小小”，约约束束是是“大于等于大于等于”的不等式。即的不等式。即“max，”和和“min，”相对应。相对应。86(2)从从约约束束系系数数矩矩阵阵看看：一一个个模模型型中中为为，则则另另一一个个模模型型中中为为AT。一一个个模模型型是是m个个约约束束，n个个变变量量，则则它它的的对对偶模型为偶模型为n个约束，个

38、约束，m个变量。个变量。(3)从从数数据据b、C的的位位置置看看：在在两两个个规规划模型中，划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。87对称形式：对称形式：互为对偶互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax bs.t.ATycx0y0“Max-”“Min-”88非非对对称称形形式式的的对对偶偶规规划划:对对非非对对称称形形式式，可可以以按按照下面的对应关系直接给出其对偶规划照下面的对应关系直接给出其对偶规划(1)将将模模型型统统一一为为“max，”或或“min，”的的形形式式，对对于于其其中中的的等等式式

39、约约束束按按下下面面(2)、(3)中中的的方方法法处处理；理；(2)若若原原规规划划的的某某个个约约束束条条件件为为等等式式约约束束，则则在在对对偶偶规规划划中中与与此此约约束束对对应应的的那那个个变变量量取取值值没没有有非负限制；非负限制；(3)若若原原规规划划的的某某个个变变量量的的值值没没有有非非负负限限制制，则则在对偶问题中与此变量对应的那个约束为等式。在对偶问题中与此变量对应的那个约束为等式。891、例子例子P67写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型90解解 先将约束条件变形为先将约束条件变形为“”形式形式91根据非对称形式的对应关系，直接写出根据非对称形式的

40、对应关系，直接写出对偶规划对偶规划922、写出下面线性规划的对偶规划模型、写出下面线性规划的对偶规划模型939494理解最优单纯形表的含义理解最优单纯形表的含义考虑问题考虑问题Maxz=c1 x1+c2 x2+cn xns.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.am1x1+am2x2+amnxn=bm x1，x2，xn0灵敏度分析灵敏度分析9595设设最优最优单纯形表单纯形表其中：其中：9696灵敏度分析灵敏度分析ci单个变化单个变化保持最优解不变保持最优解不变的允许的允许范围范围bj 单个变化对单个变化对解的可行性解的可行性的影响的影响线性规划

41、增加一个变量线性规划增加一个变量线性规划增加一个约束线性规划增加一个约束97971.若若ck是非基变量的系数：是非基变量的系数：设设ck变化为变化为ck+ck k=k+ck只要只要 k0,即即 ck-k，则最优解不变；则最优解不变；否则，将否则，将最优单纯形表最优单纯形表中的检验数中的检验数 k用用 k取代，继续单纯形法的表格计算取代，继续单纯形法的表格计算。9898例例Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x509999例：最优单纯形表例：最优单纯形表 从表中看到从表中看到3=c3+c3-(c2a1

42、3+c1a23)可得到可得到c39/5时，原最优解不变。时，原最优解不变。100100设设cl变化为变化为cl+cl，那么，那么 j=j-cl alj只要对所有非基变量只要对所有非基变量 j0，即，即 j clalj，则最优解不变；否则，将则最优解不变；否则，将最优单纯形表最优单纯形表中的检验数中的检验数 j用用 j取代，继续单纯形法取代，继续单纯形法的表格计算的表格计算。2 2、若若cl是基变量的系数是基变量的系数101101Maxz=2x1+3x2+0 x3+0 x4+0 x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x50例例b增加变量增加

43、变量增加约束增加约束102102下表为最优单纯形表下表为最优单纯形表,考虑考虑基变量系数基变量系数c c2 2发生变化发生变化由由j=cj-(c1a1j+c5a5j+(c2+c2)a2j)j=3,4可得到可得到-3c21时，原最优解不变。时，原最优解不变。103103 设分量设分量br变化为变化为br+br，只要保持，只要保持B-1(b+b)0，则，则最优基不变最优基不变，即对偶价，即对偶价格不变；否则，需要利用格不变；否则，需要利用对偶单纯形法对偶单纯形法继续计算。继续计算。3 3、右端常数的变化右端常数的变化104104上例上例最优单纯形表如下最优单纯形表如下 例例105105 0 0.2

44、5 0 0 0.25 0 这里这里 B B-1-1=-2 0.5 1=-2 0.5 1 0.5-0.125 0 0.5-0.125 0 各列分别对应各列分别对应b1、b2、b3的单一变化的单一变化因此，设因此，设b1增加增加4，则，则x1,x5,x2分别变为：分别变为：4+04=4,4+(-2)4=-40,2+0.54=4用用对偶单纯形法对偶单纯形法进一步求解，可得：进一步求解，可得：106106于是，于是，x*=(4,3,2,0,0)Tf*=17107107讨论讨论保持最优基不变保持最优基不变的前提下，的前提下，b2的允许变化范围的允许变化范围4+b2 0.25 0 b2-164+b2 0.

45、5 0 b2-82+b2(-0.125)0 b2 16于是于是-8 b2 16108108增加变量增加变量xn+1,相应有相应有pn+1,cn+1。可可计算出计算出B-1pn+1,n+1=cn+1-cri arin+1填入最优单纯形表：填入最优单纯形表：若若 n+10则则最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。4、增加新变量增加新变量109109例例 对前例对前例，增加，增加x6,p6=(2,6,3)T,c6=5用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.5110110 首先首先，应把最优解代

46、入新的约束，应把最优解代入新的约束 若满足，则最优解不变，停止；若满足，则最优解不变，停止；否则否则，引入一个新的非负变量（，引入一个新的非负变量（原约原约束若是小于等于形式可引入非负松弛变量，否则引束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量入非负人工变量），填入最优单纯形表作为），填入最优单纯形表作为新的一行，并通过矩阵行变换把对应基新的一行，并通过矩阵行变换把对应基中的列向量变为单位向量。中的列向量变为单位向量。进一步进一步用用对偶单纯形法对偶单纯形法求解。求解。5、增加一个约束条件、增加一个约束条件111111例例上例上例增加增加3x1+2x2 15，原最优解不，原最优解

47、不满足这个约束。于是满足这个约束。于是对表中新的一行利用矩阵初等行变对表中新的一行利用矩阵初等行变换进行处理，可得新的对偶单纯形表：换进行处理，可得新的对偶单纯形表：112112经对偶单纯形法一步，可得最优解为经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为最优值为13.75113113灵敏度分析灵敏度分析 1114114115参考答案参考答案115116116灵敏度分析灵敏度分析 2117118参考答案参考答案118119第二章第二章 单单 纯纯 形形 法法120标准形式标准形式目标函数：目标函数：Maxz=c1x1+c2x2+cnxn约束条件：约束条件：a1

48、1x1 +a12x2 +a1nxn=b1a21x1 +a22x2 +a2nxn=b2.am1x1+am2x2+amnxn=bm x1，x2，xn 0 0121 线线性性规规划划的的标标准准形形式式有有如如下下四四个个特特点点：目目标标最最大大化化、约约束束为为等等式式、决决策策变变量量均均非非负负、右右端端项项非非负。负。对对于于各各种种非非标标准准形形式式的的线线性性规规划划问题，转换成标准形式进行求解。问题，转换成标准形式进行求解。1221.极小化目标函数的问题：极小化目标函数的问题：设目标函数为设目标函数为Minf=c1x1+c2x2+cnxn 则则可可以以令令z-f，该该极极小小化化问

49、问题题与与下下面面的极大化问题有相同的最优解，即的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-cnxn但但必必须须注注意意，尽尽管管以以上上两两个个问问题题的的最最优优解解相相同同，但但他他们们最最优优解解的的目目标标函函数数值值却相差一个符号，即却相差一个符号，即Minf-Maxz1232、约束条件不是等式的问题：、约束条件不是等式的问题：设约束条件为设约束条件为ai1 x1+ai2 x2+ain xnbi可可以以引引进进一一个个新新的的变变量量s，使使它它等等于于约束右边与左边之差约束右边与左边之差s=bi(ai1 x1+ai2 x2+ain xn)显然，显然，s也具有非负

50、约束，即也具有非负约束，即s0，这时新的约束条件成为这时新的约束条件成为ai1 x1+ai2 x2+ain xn+s=bi124 当约束条件为当约束条件为ai1 x1+ai2 x2+ain xnbi时，类似地令时，类似地令s=(ai1 x1+ai2 x2+ain xn)-bi显显然然，s也也具具有有非非负负约约束束，即即s0，这这时时新的约束条件成为新的约束条件成为ai1 x1+ai2 x2+ain xn-s=bi125 为为了了使使约约束束由由不不等等式式成成为为等等式式而而引引进进的的变变量量s称称为为“松松弛弛变变量量”。如如果果原原问问题题中中有有若若干干个个非非等等式式约约束束，则则