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=e W,Lq=e Wq几何解释：稳态时，一个顾客，进入系几何解释：稳态时，一个顾客，进入系统后，每单位时间平均到达统后，每单位时间平均到达 e e顾客。顾客。eeeee进入时刻进入时刻离开时刻
4、离开时刻总时间总时间W队长队长L由时间段内由时间段内W个个 e组成的组成的L=eW5)Little公式公式8同理：同理：Lq=eWq又又 W=Wq+（1/）-W与与Wq只相差一段平均服务时间只相差一段平均服务时间1/L=Lq+(e/)5)Little公式公式 以上公式对一般泊松输入以上公式对一般泊松输入指数排指数排队模型成立。队模型成立。9 对于平均队长和平均队列长，可用下列公对于平均队长和平均队列长，可用下列公式计算式计算 因此，只要知道因此，只要知道 ，则，则 或或 就可由以上两公式求得，从而再由上面四就可由以上两公式求得，从而再由上面四公式就能求得四项主要工作指标。公式就能求得四项主要工
5、作指标。0nnnPL0()qns mn smLns PmP),2,1,0(nPnLqL10排队论求解的主要数量指标排队论求解的主要数量指标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、系统中无顾客的概
6、率：、系统中无顾客的概率：P0=1 2、系统中有、系统中有n个顾客的概率：个顾客的概率：Pn=n.(1 )3、系统中的平均顾客数：、系统中的平均顾客数：L=/(1 )4、顾客在系统中的平均逗留时间：、顾客在系统中的平均逗留时间：W=L/5、顾客花在排队上的平均等待时间：、顾客花在排队上的平均等待时间：Wq=W-1/u6、平均排队的顾客数：、平均排队的顾客数：Lq=Wq 141 1、例子例子 P216P216 某医院急诊室同时只能诊治某医院急诊室同时只能诊治1 1个病人，个病人，诊治时间服从指数分布，每个病人平均需诊治时间服从指数分布，每个病人平均需要要1515分钟。病人按泊松分布到达，平均每分
7、钟。病人按泊松分布到达，平均每小时到达小时到达3 3人。求该排队系统的主要数量指人。求该排队系统的主要数量指标。标。15由题意知：该题是由题意知：该题是M/M/1/FCFS排队系统排队系统3 (人小时人小时)，60154(人小时人小时)故服务强度为故服务强度为75.043 00,25.075.011pppnn 其中，其中，p0是急诊室空闲的概率，也是病人不必是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。等待立即就能就诊的概率。1631L133 LW75.025.011 WWq此模型的平均有效到达率，即是到达率此模型的平均有效到达率，即是到达率 病人在急诊室内外平均逗留时间：病人在急诊
8、室内外平均逗留时间：病人平均等候时间：病人平均等候时间：(小时小时)45(分钟分钟)急诊室内外的病人平均数：急诊室内外的病人平均数：（人）（人）（小时）（小时）30.752.25qqLW急诊室外排队等待的病人平均数：急诊室外排队等待的病人平均数：(人人)172、某医院手术室只能同时诊治一个病人，病某医院手术室只能同时诊治一个病人，病人到达服从泊松分布，每小时病人平均到达率人到达服从泊松分布，每小时病人平均到达率为为2.1(人人/小时小时)。每次手术平均时间。每次手术平均时间0.4(小时小时/人人)，服从负指数分布求：，服从负指数分布求：(1)病房中病人的平均数病房中病人的平均数(L)；(2)排
9、队等待手术病人的平均数排队等待手术病人的平均数(Lq)；(3)病人在病房中平均逗留时间病人在病房中平均逗留时间(W)(4)病人排队等待时间病人排队等待时间(Wq)。18193、某医院急诊室每小时到达一个病人，输入为最简某医院急诊室每小时到达一个病人，输入为最简单流，急诊室仅有一名医生，病人接受紧急护理平单流，急诊室仅有一名医生，病人接受紧急护理平均需均需20分钟，服务时间为负指数分布，试求：分钟，服务时间为负指数分布，试求：（1）稳态情况下：稳态情况下：a)没有病人的概率；没有病人的概率；b)有两个有两个病人的概率；病人的概率；c)急诊室里病人的平均数；急诊室里病人的平均数；d)排队中病排队中
10、病人的平均数；人的平均数；e)病人在急诊室中的平均时间病人在急诊室中的平均时间 （2）为了保证病人急诊所花费的平均时间少于）为了保证病人急诊所花费的平均时间少于25分钟，那么平均紧急护理时间必须降至多少分钟分钟，那么平均紧急护理时间必须降至多少分钟?202122第七章第七章 动态规划动态规划23动态规划的基本概念动态规划的基本概念1 1)阶段和阶段变量阶段和阶段变量 阶段是按决策进行的时间或空间上阶段是按决策进行的时间或空间上先后顺序划分的。先后顺序划分的。用以描述阶段的变量用以描述阶段的变量叫作叫作阶段变量阶段变量，一般以，一般以k表示阶段变表示阶段变量阶段数等于多阶段决策过程从开始量阶段数
11、等于多阶段决策过程从开始到结束所需作出决策的数目。到结束所需作出决策的数目。242 2）状态、状态变量和可能状态集状态、状态变量和可能状态集 描述事物描述事物(或系统或系统)在某特定的在某特定的时间与空间域中所处位置及运动特时间与空间域中所处位置及运动特征的量，称为征的量，称为状态状态。反映状态变化。反映状态变化的量叫做的量叫做状态变量状态变量。25 每个阶段的状态可分为初始每个阶段的状态可分为初始状态和终止状态，或称输入状态和终止状态，或称输入状态状态和输出状态，和输出状态，阶段阶段k的初始状态的初始状态记作记作sk，终止状态记为，终止状态记为sk+1。通常通常定义阶段的状态即指其初始状态定
12、义阶段的状态即指其初始状态。26 一般状态变量的取值有一定的范一般状态变量的取值有一定的范围或允许集合，围或允许集合，称为称为可能状态集可能状态集，可能状态集用相应可能状态集用相应阶段状态阶段状态sk的大的大写字母写字母Sk表示，表示，sk Sk，可能状态集可可能状态集可以是一离散取值的集合，也可以为一连续以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定的取值区间，视具体问题而定273）决策、决策变量和允许决策集合决策、决策变量和允许决策集合 决策决策的实质是关于状态的选择，的实质是关于状态的选择，是决策者从给定阶段状态出发对下是决策者从给定阶段状态出发对下一阶段状态作出的选择。
13、一阶段状态作出的选择。28 用以描述决策变化的量称之用以描述决策变化的量称之决决策变量策变量。决策变量的值可以用数，。决策变量的值可以用数，向量、其它量，也可以是状态变量向量、其它量，也可以是状态变量的函数的函数.记记uk=uk(sk)，表示于阶段，表示于阶段 k 状态为状态为 sk 时的决策变量。时的决策变量。29 决策变量的取值往往也有一定的决策变量的取值往往也有一定的允许范围，称之允许范围，称之允许决策集合允许决策集合。决策。决策变量变量uk(sk)的允许决策集用的允许决策集用Uk(sk)表示表示,uk(sk)Uk(sk)允许决策集合实际是决策的约束条允许决策集合实际是决策的约束条件。件
14、。304）策略和允许策略集合策略和允许策略集合 策略策略(Policy)也叫也叫决策序列决策序列策略策略有全过程策略和有全过程策略和k部子策略之分，全部子策略之分，全过程策略是指由依次进行的过程策略是指由依次进行的n个阶段个阶段决策构成的决策序列，简称决策构成的决策序列，简称策略策略，表示为表示为 p1,nu1,u2,un。31 从从 k 阶段到第阶段到第 n 阶段，依次进行阶段，依次进行的阶段决策构成的决策序列称为的阶段决策构成的决策序列称为 k 部部子策略子策略,表示为表示为pk,n uk,uk+1,un ，显然当显然当 k=1 时的时的 k 部子策略就是部子策略就是全全过程策略过程策略。
15、32 在实际问题中，由于在各个阶在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选它们的不同组合就构成了许多可供选择的决策序列择的决策序列(策略策略)，由它们组成的，由它们组成的集合，称之集合，称之允许策略集合允许策略集合，记作，记作P1,n，从允许策略集中，找出具有最优效果从允许策略集中，找出具有最优效果的策略称为的策略称为最优策略最优策略。335）状态转移方程状态转移方程 系统在阶段系统在阶段k处于状态处于状态sk，执行，执行决策决策uk(sk)的结果是系统状态的转移，的结果是系统状态的转移，即系统由阶段即系统由阶段k
16、的初始状态的初始状态sk转移转移到终止状态到终止状态sk+1。34 系统状态的这种转移，用数学系统状态的这种转移，用数学公式描述即有：公式描述即有：通常称上式为多阶段决策过程的通常称上式为多阶段决策过程的状状态转移方程态转移方程。有些问题的状态转移方程有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。移，还是有一定规律可循的。)(kkkkksusTs,1356)6)指标函数指标函数 用来衡量策略或子策略或决策用来衡量策略或子策略或决策的效果的某种数量指标，就称为的效果的某种数量指标，就称为指指标函数标函数。它是定义在全过
17、程或各子。它是定义在全过程或各子过程或各阶段上的确定数量函数。过程或各阶段上的确定数量函数。对对不同问题，指标函数可以是诸如费用、成本、不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效产值、利润、产量、耗量、距离、时间、效用等等。用等等。36阶段指标函数（阶段效应）阶段指标函数（阶段效应）用用gk(sk,uk)表示第表示第k段处于段处于sk状状态且所作决策为态且所作决策为uk(sk)时的指标，则时的指标，则它就是第它就是第k段指标函数，简记为段指标函数，简记为gk37过程指标函数（目标函数）过程指标函数（目标函数）用用Rk(sk,uk)表示表示k子过程的指标子过程
18、的指标函数。函数。Rk(sk,uk)不仅跟当前状态不仅跟当前状态sk有有关，还跟该子过程策略关，还跟该子过程策略pk(sk)有关，有关，因此它是因此它是sk和和pk(sk)的函数，严格说的函数，严格说来，应表示为来，应表示为:)s(p,s(Rkkkk387)最优解最优解 用用fk(sk)表示第表示第k子过程指标函子过程指标函数数 ，在状态，在状态sk下的最优下的最优值值,即即 称称 fk(sk)为第为第 k 子过程上的最优指子过程上的最优指标函数；标函数；)s(p,s(Rkkkkn,2,1k)s(p,s(Ropt)s(fkkkk)s(PpkkkKk39 相应的子策略称为相应的子策略称为sk状态
19、下的状态下的最优子策略，最优子策略，记为记为pk*(sk)；而构成该子策赂的各段决策；而构成该子策赂的各段决策称为该过程上的称为该过程上的最优决策最优决策，记为，记为有有 简记为简记为)s(u,),s(u),s(unn1k1kkkn,2,1k)s(u,),s(u),s(u)s(pnn1k1kkkkkn,2,1k,u,u,upn1kkk40 特别，特别，当当 k=1 且且 s1 取值唯一时，取值唯一时，f1(s1)就是问题的最优值，而就是问题的最优值，而p1*就是最就是最优策略。优策略。41 最优策略即为最优策略即为s1=s1*状态下的最优状态下的最优策略：策略：我们把我们把最优策略和最优值统称
20、为问最优策略和最优值统称为问题的最优解。题的最优解。111112()(),np ssu suu428)8)多阶段决策问题的数学模型多阶段决策问题的数学模型 适于动态规划方法求解的一类多阶段决策适于动态规划方法求解的一类多阶段决策问题，即具有问题，即具有无后效性的多阶段决策问题无后效性的多阶段决策问题的数的数学模型学模型:n,2,1kUuSs)u,s(Ts.t.s)u,s,u,s,u,s(RRoptkkkkkkk1knn2211uun143常用求最小的加法计算公式常用求最小的加法计算公式：1,2,1n,nk)s(f)s(u,s(gmin)s(f0)s(f1k1kkkkk)s(Uukk1n1nkk
21、k（边界条件）（边界条件）阶段指标阶段指标44动态规划方法的基本步骤动态规划方法的基本步骤用用函数基本方程逆推求解函数基本方程逆推求解是常用的是常用的方法：首先要有效地方法：首先要有效地建立动态规划建立动态规划模型模型,然后再然后再递推求解基本方程递推求解基本方程,最最后后回溯求得最优策略回溯求得最优策略。合理、有效地建立一个动态规划模合理、有效地建立一个动态规划模型型,是解决问题的关键。是解决问题的关键。45（一）动态规划建模要点（一）动态规划建模要点 将实际问题恰当地分割成将实际问题恰当地分割成n个子个子问题问题(n个阶段个阶段)通常是根据通常是根据时间或空间时间或空间而划分，而划分，或者
22、在经由静态的数学规划模型转或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规换为动态规划模型时，常取静态规划划中变量的个数中变量的个数n。46动态规划建模要点动态规划建模要点 正确地定义状态变量正确地定义状态变量sk，使它既能正确，使它既能正确地描述过程的状态，又能满足无后效性地描述过程的状态，又能满足无后效性。在动态规划模型中，一般状态变量要选在动态规划模型中，一般状态变量要选取那种取那种可以进行累计的量可以进行累计的量。47动态规划建模要点动态规划建模要点 正确地定义决策变量及各阶段的正确地定义决策变量及各阶段的允许决策集合允许决策集合Uk(sk)。一般将问题中一般将问题中待求的
23、量待求的量选作动态选作动态规划模型中的决策变量。规划模型中的决策变量。48动态规划建模要点动态规划建模要点 正确地写出状态转移方程正确地写出状态转移方程 要能正确反映状态转移规律。如要能正确反映状态转移规律。如果给定第果给定第 k 阶段状态变量阶段状态变量 sk 的值，的值，则该段的决策变量则该段的决策变量 uk 一经确定，第一经确定，第k+1段的状态变量段的状态变量sk+1的值也就完全的值也就完全确定，即有确定，即有 sk+1=Tk(sk,uk)49动态规划建模要点动态规划建模要点 正确地写出目标函数正确地写出目标函数 目标函数由目标函数由递推关系递推关系构成，因此，构成，因此，它应满足下列
24、性质：它应满足下列性质：函数可分性：函数可分性：阶段指标相对独立阶段指标相对独立；要满足递推关系；要满足递推关系；过程函数严格单调。过程函数严格单调。50动态规划基本方程动态规划基本方程 fn+1(sn+1)=0 (边界条件边界条件)fk(sk)=opt ugk(sk,uk)+fk+1(sk+1)k=n,n-1,151（二）逆序求解动态规划基本方程（二）逆序求解动态规划基本方程 常见三种情况：一种是对于常见三种情况：一种是对于特殊的网络求最优特殊的网络求最优路径路径，可以直接在网络图上，直观地使用，可以直接在网络图上，直观地使用标号标号法法（见下一节）求解；（见下一节）求解；对于对于离散型离散
25、型的动态规划问题，常使用的动态规划问题，常使用列表格列表格（递推方程）（递推方程）的方法求解。的方法求解。当阶段指标与递推公式可表示为解析显函数时，当阶段指标与递推公式可表示为解析显函数时，对于规模较大，特别是对于规模较大，特别是连续型连续型的动态规划问题，的动态规划问题，常直接常直接使用函数求优使用函数求优的方法。的方法。52（三）回溯求得最优策略（三）回溯求得最优策略 从从k=1k=1开始，逐步向后归纳出开始，逐步向后归纳出前一环节各步所选择的决策，得到前一环节各步所选择的决策，得到决策序列，即最优策略。决策序列，即最优策略。531 1、例子例子 P176P176用用递推方程递推方程求解最
26、短路径问题求解最短路径问题54（一）建模（一）建模如图划分成如图划分成 5 个阶段；个阶段；状态变量状态变量sk表示第表示第k阶段开始的位置；阶段开始的位置；决策变量决策变量uk定义为到达下一站所选择的路定义为到达下一站所选择的路径；径；状态转移：决策确定了下一阶段的状态；状态转移：决策确定了下一阶段的状态；阶段指标：图中线段上所标的数值；阶段指标：图中线段上所标的数值；55 最优指标函数最优指标函数 fk(sk)：表示从目前状态到表示从目前状态到E的最短路径。的最短路径。终端条件为终端条件为 f5(s5)=f5(E)=0其含义是从其含义是从E到到E的最短路径为的最短路径为0。11()()mi
27、n(,)()4,3,2,1kkkkkkkkkkuUsfsgs ufsk56（二）逆推求解（二）逆推求解第第4阶段的递推方程为阶段的递推方程为从从 f5(s5)到到 f4(s4)的递推过程用下表表示的递推过程用下表表示 4444444455()()min(,)()uUsf sg s uf s s4U4(s4)s5g4(s4,u4)g4(s4,u4)+f5(s5)f4(s4)最优决策最优决策u4*C1C1EE55+0=5*5C1EC2C2EE88+0=8*8C2E57第第3阶段的递推方程为：阶段的递推方程为：)(),(min)(44333)(33333sfusgsfsUu从从 f4(s4)到到f3
28、(s3)的递推过程用表格表示如下表：的递推过程用表格表示如下表：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)的递推过程用表格表示如下的递推过程用表格表示如下)(),(min)(33222)(22222sfusgsfsUu59s2U2(s2)s3g2(s2,u2)g2(s2,u2)+f3(s3)f2(s2)最优决策最优决策u
29、2*A1A1B1A1B2B1B2 6 56+11=17*5+14=1917A1B1A2A2B1A2B2B1B2 8 68+11=19*6+14=2019A2B1A3A3B1A3B2B1B2 7 47+11=18*4+14=18*18A3B1A3B260第第1 1阶段的递推方程为：阶段的递推方程为：)(),(min)(22111)(11111sfusgsfsUu 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由此得到由此得到
30、f1(s1)=21,即从即从 A 到到 E的最短路径长度为的最短路径长度为21。（三）（三）回溯求最优策略：回溯求最优策略：由由 f1(s1)向向 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的最短路径：的最
31、短路径：ABAB3 3 C C1 1 D D最短长度：最短长度：212164第四章第四章 运输问题运输问题651.求初始基本可行解求初始基本可行解 （西北角法、（西北角法、最小元素法最小元素法）2.求检验数（求检验数（位势法位势法）3.换基（换基（闭回路闭回路）表上作业法：表上作业法：661 1、初始基本可行解的确定、初始基本可行解的确定 （1 1）西北角法）西北角法：从：从西北角（左上角）格西北角（左上角）格开始开始，在格内的右下角标上允许取得的最，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把某行（
32、列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。直至得到一个基本可行解。67 （2）最小元素法）最小元素法：从：从运价最小的格运价最小的格开始开始，在格内的右下角标上允许取得的，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。行下去，直至得到一个基本可行解。68 注注:应用西北角法和最小元素法，每
33、应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有次填完数，都只划去一行或一列，只有最后一个元例外最后一个元例外（同时划去一行和一（同时划去一行和一列）。列）。当填上一个数后行、列同时饱和当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个的列（行）中没被划去的格内标一个0 0。69 由于目标要求极小，因此，由于目标要求极小，因此，当所有的当所有的检验数都大于或等于零时该调运方案就是检验数都大于或等于零时该调运方案就是最优方案最优方案；否则就不是最优，需要进行调；否则就不是最优，需要进行调整。整。2 2、基
34、本可行解的最优性检验、基本可行解的最优性检验 70位势法位势法 位势：设对应位势：设对应基变量基变量xij 的的 m+n-1 个个 ij，存在，存在ui,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-vj i=1,m;j=1,n72位势法求检
35、验数：位势法求检验数：step 1 从从任意基变量对应的任意基变量对应的 cij 开始开始,任取任取 ui 或或 vj，然后利用公式，然后利用公式 cij=ui+vj 依次找依次找出出 m+n 个个 ui,vj step 2 计算非基变量的检验数计算非基变量的检验数 ij=cij-ui-vj；填入圆圈内；填入圆圈内73 当非基变量的检验数出现负值时，当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目调整，即找到一个新的基本可行解使目标函数值下降，
36、这一过程通常称为标函数值下降，这一过程通常称为换基换基(或主元变换或主元变换)过程（过程（闭回路法闭回路法）。3 3、求新的基本可行解、求新的基本可行解7474 （1）选负检验数中最小者）选负检验数中最小者 rk，那么，那么 xrk 为主元，作为为主元，作为进基变量进基变量（上页图中（上页图中 x24）;（2）以以 xrk 为起点找一条闭回路为起点找一条闭回路，除，除 xrk 外其余顶点必须为基变量格（上页图中外其余顶点必须为基变量格（上页图中的回路）的回路）;在运输问题的表上作业法中，换基的过程在运输问题的表上作业法中，换基的过程是如下进行：是如下进行：7575（3）为闭回路的每一个顶点标号
37、，为闭回路的每一个顶点标号，xrk 为为 1号号，沿一个方向（顺时针或逆时针）依次，沿一个方向（顺时针或逆时针）依次给各顶点标号；给各顶点标号；（4）求求 =Minxij xij对应闭回路上的偶数对应闭回路上的偶数标号格标号格=xpq 那么那么确定确定 xpq为为出基变量出基变量，为调整量；为调整量；7676（5）对闭回路的各对闭回路的各奇标号顶点调整为：奇标号顶点调整为：xij+，对各，对各偶标号顶点偶标号顶点 调整为：调整为：xij-，特别，特别 xpq-=0，xpq变为非基变量。变为非基变量。重复重复(2)、(3)步，直到所有检验数均步，直到所有检验数均非负，得到最优解。非负，得到最优解
38、。77 注意：注意：（1）构造闭回路进行换基时，只有）构造闭回路进行换基时，只有一个基变量出基，一个非基变量进一个基变量出基，一个非基变量进基；基；（2）如果偶标号格中两个变量减去）如果偶标号格中两个变量减去调整量后都变为零，则取其中一个调整量后都变为零，则取其中一个为出基变量，另一个填上运量为出基变量，另一个填上运量0。77781、例子例子 P99 798081 所有所有 ij 0，得到，得到最优解最优解 x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余其余 xij=0;最优值最优值：f*=35+102+13+81+46+53=85822、用表上作业法求解下列运输
39、问题用表上作业法求解下列运输问题 销地销地产地产地B1B2B3B4产量产量A1847290A25835100A37729120销量销量7050110808384第三章第三章 线性规划对偶与灵敏度分析线性规划对偶与灵敏度分析85对偶规划的形式对偶规划的形式 有有对称形式对称形式和和非对称形式非对称形式。对称形式对称形式的对偶规划之间具有下面的的对偶规划之间具有下面的对应关系：对应关系：(1)若一个模型为目标求若一个模型为目标求“极大极大”，约，约束为束为“小于等于小于等于”的不等式，则它的的不等式，则它的对偶模型为目标求对偶模型为目标求“极小极小”，约束是，约束是“大于等于大于等于”的不等式。即
40、的不等式。即 “max，”和和“min，”相对应。相对应。86(2)从约束系数矩阵看：一个模型中从约束系数矩阵看：一个模型中为为，则另一个模型中为，则另一个模型中为AT。一个。一个模型是模型是m个约束，个约束，n个变量，则它的个变量，则它的对偶模型为对偶模型为n个约束，个约束，m个变量。个变量。(3)从数据从数据b、C的位置看：在两个规的位置看：在两个规划模型中，划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。87 对称形式：对称形式：互为对偶互为对偶 (LP)Max z=cT x (DP)Min f=bT y s.t.Ax b s.t.
41、AT y c x 0 y 0 “Max-”“Min-”88非对称形式非对称形式的对偶规划的对偶规划:对非对称形式，可以按对非对称形式，可以按照下面的对应关系直接给出其对偶规划照下面的对应关系直接给出其对偶规划(1)将模型统一为将模型统一为“max，”或或“min，”的的形式，对于其中的等式约束按下面形式，对于其中的等式约束按下面(2)、(3)中中的方法处理；的方法处理；(2)若原规划的某个约束条件为等式约束，则在若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有对偶规划中与此约束对应的那个变量取值没有非负限制；非负限制；(3)若原规划的某个变量的值没有非负限制，则若
42、原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。在对偶问题中与此变量对应的那个约束为等式。891、例子例子 P67 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型 没没有有非非负负限限制制321432143143214321,0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ90解解 先将约束条件变形为先将约束条件变形为“”形式形式 没没有有非非负负限限制制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx91根据非对称形式的对应关系，直接写出根据非对称形式的
43、对应关系，直接写出对偶规划对偶规划 0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf没没有有非非负负限限制制922、写出下面线性规划的对偶规划模型、写出下面线性规划的对偶规划模型无符号限制42314321432143214321,0,1067912857653432maxxxxxxxxxxxxxxxxxxxxxZ939494 理解最优单纯形表的含义理解最优单纯形表的含义考虑问题考虑问题 Max z=c1 x1+c2 x2+cn xn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22
44、x2+a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 0灵敏度分析灵敏度分析9595设设最优最优单纯形表单纯形表其中：其中：nmjaaappBppppAbBbaccbcfTmjjjjjjnmiijijjmiii,1,),(,21121111 9696灵敏度分析灵敏度分析 ci 单个变化单个变化保持最优解不变保持最优解不变的允许的允许范围范围 bj 单个变化对单个变化对解的可行性解的可行性的影响的影响 线性规划增加一个变量线性规划增加一个变量 线性规划增加一个约束线性规划增加一个约束9797若若ck是非基变量的系数：是非基变量的系数：设设ck变化为变化为 ck+c
45、k k=k+ck只要只要 k 0,即即 ck -k，则最优解不变；则最优解不变；否则，将否则，将最优单纯形表最优单纯形表中的检验数中的检验数 k 用用 k取代，继续单纯形法的表格计算取代，继续单纯形法的表格计算。9898例例 Max z =-2x1 -3x2 -4x3 S.t.-x1 -2x2 -x3+x4 =-3 -2x1+x2-3x3 +x5 =-4 x1,x2,x3,x4,x5 09999例：最优单纯形表例：最优单纯形表 从表中看到从表中看到3=c3+c3-(c2a13+c1a23)可得到可得到c3 9/5 时，原最优解不变。时，原最优解不变。100100设设 cl 变化为变化为 cl+
46、cl ，那么，那么 j=j-cl alj 只要对所有非基变量只要对所有非基变量 j0，即，即 j clalj，则最优解不变；否则，将则最优解不变；否则，将最优单纯形表最优单纯形表中的检验数中的检验数 j 用用 j取代，继续单纯形取代，继续单纯形法的表格计算法的表格计算。2 2、若若 cl 是基变量的系数是基变量的系数101101Max z=2x1+3x2+0 x3+0 x4+0 x5 s.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2,x3,x4,x5 0例例b增加变量增加变量增加约束增加约束102102下表为最优单纯形表下表为最优单纯形表,考虑考虑基变
47、量系数基变量系数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.25 0 0 0.25 0 这里这里 B B-1-1=-2 0.5 1=-
48、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)T f*=17107107 讨论讨论保持最优基不变保持最优基不变的前提下，的前提下，b2的允许变化范围的允许变化范围 4+b2 0.25 0 b2 -16 4+b2 0.5 0 b2 -8 2+b2 (-0.125)0
49、b2 16于是于是 -8 b2 16108108增加变量增加变量 xn+1,相应有相应有pn+1,cn+1。可可计算出计算出 B-1pn+1,n+1=cn+1-cri ari n+1 填入最优单纯形表：填入最优单纯形表：若若 n+1 0 则则 最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。4、增加新变量增加新变量109109例例 对前例，增加对前例，增加x6,p6=(2,6,3)T,c6=5用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T f*=16.5666616,pccpBpTB110110 首先首先，应把最优
50、解代入新的约束，应把最优解代入新的约束 若满足，则最优解不变，停止；若满足，则最优解不变，停止；否则否则，引入一个新的非负变量（，引入一个新的非负变量（原约原约束若是小于等于形式可引入非负松弛变量，否则引束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量入非负人工变量），填入最优单纯形表作为），填入最优单纯形表作为新的一行，并通过矩阵行变换把对应基新的一行，并通过矩阵行变换把对应基中的列向量变为单位向量。中的列向量变为单位向量。进一步进一步用用对偶单纯形法对偶单纯形法求解。求解。5、增加一个约束条件、增加一个约束条件111111例例 上例增加上例增加 3x1+2x2 15，原最优解不，
