运筹学期末复习PPT课件

1、1第八章 排队论第1页/共159页2s 系统中并联服务台的数目； 平均到达率（单位时间到达的顾客数）；1/ 平均到达间隔（相继到达顾客的平均间隔 时间）。 平均服务率（单位时间服务的顾客数）；1/ 平均服务时间（为顾客服务的平均时间）。 服务强度，即每个服务台单位时间内的 平均服务时间； 一般有 s ；稳态排队系统的参数稳态排队系统的参数第2页/共159页3 Pn=PN=n：稳态系统任一时刻状态为n（系统中恰好有n个顾客）的概率； 特别当 n = 0 时，Pn即P0，为稳态系统所有服务台全部空闲的概率。 稳态下系统的基本数量指标稳态下系统的基本数量指标第3页/共159页4 到达的顾客不一定全部

2、进入系统接受服务，设系统中有n个顾客时，每单位时间进入系统的顾客平均数为 n，每单位时间离开系统的顾客平均数为 n。我们引入： e 有效平均到达率，即每单位时间实际进入系统的平均顾客数（期望值）， e= npn 对等待制的排队系统，有 e 第4页/共159页5平均有效离去率 : e = n pn 从平稳系统中均值的意义看，容易理解应有平均有效离去率等于平均有效到达率，即 e = e第5页/共159页6L , Lq, e ,W , Wq 之间的关系： L = e W, Lq = e Wq几何解释：稳态时，一个顾客，进入几何解释：稳态时，一个顾客，进入系系统后，每单位时间平均到达统后，每单位时间平

3、均到达 e e顾客。顾客。eeeee进入时刻进入时刻离开时刻离开时刻总时间总时间W队长队长L由时间段内由时间段内W个个 e组成的组成的L= eW5) Little公式第6页/共159页7同理：Lq= eWq又 W=Wq+（1/ ）-W与Wq只相差一段平均服务时间1/ L=Lq+( e / )5) Little公式公式 以上公式对一般泊松输入以上公式对一般泊松输入指数排指数排队模型成立。队模型成立。第7页/共159页8对于平均队长和平均队列长，可用下列公式计算 因此，只要知道 ，则 或 就可由以上两公式求得，从而再由上面四公式就能求得四项主要工作指标。0nnnPL0()qns mn smLns

4、PmP), 2 , 1 , 0(nPnLqL第8页/共159页9排队论求解的主要数量指标P0 、Pn 、L 、 Lq 、W 、Wq第9页/共159页10单服务台无限源系统M/M/1/FCFSM/M/1/N/FCFS第10页/共159页11M/M/1/ / /FCFS系统: 参数 ， 问题的一般提法： 泊松输入/负指数分布/单服务台/系统无限制/顾客源无限制 求解： (1)系统状态P0 、Pn (2)系统运行指标：L 、 Lq 、W 、Wq第11页/共159页12M/M/1/ / /FCFS排队系统模型的主要指标1、系统中无顾客的概率：P0 =1 2、系统中有n个顾客的概率： Pn =n .(1

5、 )3、系统中的平均顾客数：L= /(1 )4、顾客在系统中的平均逗留时间：W = L / 5、顾客花在排队上的平均等待时间：Wq = W-1 /u6、平均排队的顾客数： Lq= Wq 第12页/共159页131 1、例子 P216P216 某医院急诊室同时只能诊治1 1个病人，诊治时间服从指数分布，每个病人平均需要1515分钟。病人按泊松分布到达，平均每小时到达3 3人。求该排队系统的主要数量指标。第13页/共159页14由题意知：该题是M/M/1/ / /FCFS排队系统3 (人小时)， 60154(人小时)故服务强度为75. 043 00,25. 075. 011pppnn 其中，p0是

6、急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。第14页/共159页1531L133 LW75. 025. 011 WWq此模型的平均有效到达率，即是到达率 病人在急诊室内外平均逗留时间：病人平均等候时间：(小时)45(分钟)急诊室内外的病人平均数：（人）（小时）30.752.25qqLW急诊室外排队等待的病人平均数：(人)第15页/共159页162、 某医院手术室只能同时诊治一个病人，病某医院手术室只能同时诊治一个病人，病人到达服从泊松分布，每小时病人平均到达率人到达服从泊松分布，每小时病人平均到达率为为2.1(人人/小时小时)。每次手术平均时间。每次手术平均时间0.4(小时小时/人人

7、)，服从负指数分布求：，服从负指数分布求：(1) 病房中病人的平均数病房中病人的平均数(L)；(2) 排队等待手术病人的平均数排队等待手术病人的平均数(Lq )；(3) 病人在病房中平均逗留时间病人在病房中平均逗留时间(W)(4) 病人排队等待时间病人排队等待时间(Wq)。第16页/共159页17第17页/共159页183、某医院急诊室每小时到达一个病人，输入为最简单流，急诊室仅有一名医生，病人接受紧急护理平均需20分钟，服务时间为负指数分布，试求： （1） 稳态情况下：a)没有病人的概率；b)有两个病人的概率；c)急诊室里病人的平均数；d)排队中病人的平均数；e)病人在急诊室中的平均时间 （

8、2）为了保证病人急诊所花费的平均时间少于25分钟，那么平均紧急护理时间必须降至多少分钟?第18页/共159页19第19页/共159页20第20页/共159页21第七章 动态规划第21页/共159页22动态规划的基本概念动态规划的基本概念1 1) ) 阶段和阶段变量阶段和阶段变量 阶段是按决策进行的时间或空间阶段是按决策进行的时间或空间上先后顺序划分的。上先后顺序划分的。用以描述阶段的用以描述阶段的变量叫作变量叫作阶段变量阶段变量，一般以，一般以k表示阶段表示阶段变量阶段数等于多阶段决策过程从变量阶段数等于多阶段决策过程从开始到结束所需作出决策的数目。开始到结束所需作出决策的数目。第22页/共1

9、59页232 2）状态、状态变量和可能状态集状态、状态变量和可能状态集 描述事物描述事物( (或系统或系统) )在某特定在某特定的时间与空间域中所处位置及运的时间与空间域中所处位置及运动特征的量，称为动特征的量，称为状态状态。反映状。反映状态变化的量叫做态变化的量叫做状态变量状态变量。第23页/共159页24 每个阶段的状态可分为初每个阶段的状态可分为初始状态和终止状态，或称输入始状态和终止状态，或称输入状态和输出状态，状态和输出状态，阶段阶段k的初始的初始状态记作状态记作sk，终止状态记为，终止状态记为sk+1。通常定义阶段的状态即指其初通常定义阶段的状态即指其初始状态始状态。第24页/共1

10、59页25 一般状态变量的取值有一定的一般状态变量的取值有一定的范围或允许集合，范围或允许集合，称为称为可能状态集可能状态集，可能状态集用相应可能状态集用相应阶段状态阶段状态sk的的大写字母大写字母Sk表示，表示，sk Sk，可能状态集可以可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定第25页/共159页263）决策、决策变量和允许决策集决策、决策变量和允许决策集合合 决策决策的实质是关于状态的选择，的实质是关于状态的选择，是决策者从给定阶段状态出发对下是决策者从给定阶段状态出发对下一阶段状态作出的选择。一

11、阶段状态作出的选择。 第26页/共159页27 用以描述决策变化的量称之用以描述决策变化的量称之决决策变量策变量。决策变量的值可以用数，。决策变量的值可以用数，向量、其它量，也可以是状态变量向量、其它量，也可以是状态变量的函数的函数. 记记uk= uk(sk)，表示于阶段，表示于阶段 k 状态状态为为 sk 时的决策变量。时的决策变量。第27页/共159页28 决策变量的取值往往也有一定决策变量的取值往往也有一定的允许范围，称之的允许范围，称之允许决策集合允许决策集合。决。决策变量策变量uk(sk)的允许决策集用的允许决策集用Uk(sk)表表示示, uk(sk) Uk(sk) 允许决策集合实际

12、是决策的约束允许决策集合实际是决策的约束条件。条件。第28页/共159页294）策略和允许策略集合策略和允许策略集合 策略策略(Policy)也叫也叫决策序列决策序列策策略有全过程策略和略有全过程策略和k部子策略之分，部子策略之分，全过程策略是指由依次进行的全过程策略是指由依次进行的n个个阶段决策构成的决策序列，简称阶段决策构成的决策序列，简称策策略略，表示为，表示为 p1,nu1,u2,un。第29页/共159页30 从从 k 阶段到第阶段到第 n 阶段，依次进阶段，依次进行的阶段决策构成的决策序列称为行的阶段决策构成的决策序列称为 k 部子策略部子策略, 表示为表示为pk,n uk, uk

13、+1, , un ，显然当，显然当 k = 1 时的时的 k 部子策部子策略就是略就是全过程策略全过程策略。第30页/共159页31 在实际问题中，由于在各个在实际问题中，由于在各个阶段可供选择的决策有许多个，因阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多此，它们的不同组合就构成了许多可供选择的决策序列可供选择的决策序列(策略策略)，由它，由它们组成的集合，称之们组成的集合，称之允许策略集合允许策略集合，记作记作P1,n ，从允许策略集中，找出，从允许策略集中，找出具有最优效果的策略称为具有最优效果的策略称为最优策略最优策略。第31页/共159页325）状态转移方程状态转移方程

14、 系统在阶段系统在阶段k处于状态处于状态sk，执，执行决策行决策uk(sk)的结果是系统状态的的结果是系统状态的转移，即系统由阶段转移，即系统由阶段k的初始状态的初始状态sk转移到终止状态转移到终止状态sk+1 。第32页/共159页33 系统状态的这种转移，用数系统状态的这种转移，用数学公式描述即有：学公式描述即有：通常称上式为多阶段决策过程的通常称上式为多阶段决策过程的状状态转移方程态转移方程。有些问题的状态转移方程不一定存在数学表达式，有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。但是它们的状态转移，还是有一定规律可循的。)(kkkkksusTs,

15、1第33页/共159页346)6)指标函数指标函数 用来衡量策略或子策略或决策用来衡量策略或子策略或决策的效果的某种数量指标，就称为的效果的某种数量指标，就称为指指标函数标函数。它是定义在全过程或各子。它是定义在全过程或各子过程或各阶段上的确定数量函数。过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用等等。时间、效用等等。第34页/共159页35阶段指标函数（阶段效应）阶段指标函数（阶段效应） 用用gk(sk,uk)表示第表示第k段处于段处于sk状态且所作决策

16、为状态且所作决策为uk(sk)时的指标，时的指标，则它就是第则它就是第k段指标函数，简记为段指标函数，简记为gk第35页/共159页36过程指标函数（目标函数）过程指标函数（目标函数） 用Rk(sk,uk)表示k子过程的指标函数。Rk(sk,uk) 不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:)s(p,s(Rkkkk第36页/共159页377) 最优解最优解 用fk(sk)表示第k子过程指标函数 ，在状态sk下的最优值,即 称 fk(sk) 为第 k 子过程上的最优指标函数；)s(p,s(Rkkkkn,2 , 1k)s(p,s

17、(Ropt)s(fkkkk)s(PpkkkKk第37页/共159页38相应的子策略称为sk状态下的最优子策略，记为pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策，记为有 简记为)s(u,),s(u),s(unn1k1kkkn, 2 , 1k)s(u,),s(u),s(u)s(pnn1k1kkkkkn,2 , 1k,u,u,upn1kkk第38页/共159页39 特别， 当 k = 1 且 s1 取值唯一时，f1(s1)就是问题的最优值，而p1* 就是最优策略。 第39页/共159页40 最优策略即为s1=s1* *状态下的最优策略： 我们把最优策略和最优值统称为问题的最优解。

18、111112()(),np ssusuu第40页/共159页418) 8) 多阶段决策问题的数学模型多阶段决策问题的数学模型 适于动态规划方法求解的一类多阶段决策问题，即具有无后效性的多阶段决策问题的数学模型:n,2,1kUuSs)u,s(Ts. t . s)u,s,u,s,u,s(RRoptkkkkkkk1knn2211uun1第41页/共159页42常用求最小的加法计算公式常用求最小的加法计算公式：1 , 2 , 1n,nk)s(f)s(u,s(gmin)s(f0)s(f1k1kkkkk)s(Uukk1n1nkkk（边界条件）（边界条件）阶段指标阶段指标第42页/共159页43动态规划方法

19、的基本步骤动态规划方法的基本步骤用用函数基本方程逆推求解函数基本方程逆推求解是常用的是常用的方法：首先要有效地方法：首先要有效地建立动态规划建立动态规划模型模型, ,然后再然后再递推求解基本方程递推求解基本方程, ,最最后后回溯求得最优策略回溯求得最优策略。合理、有效地建立一个动态规划模合理、有效地建立一个动态规划模型型, ,是解决问题的关键。是解决问题的关键。第43页/共159页44（一）动态规划建模要点（一）动态规划建模要点 将实际问题恰当地分割成将实际问题恰当地分割成n个子个子问题问题(n个阶段个阶段) 通常是根据时间或空间而划分，或者在经由静态的数学规划模型转换为动态规划模型时，常取静

20、态规划中变量的个数n。第44页/共159页45动态规划建模要点动态规划建模要点 正确地定义状态变量正确地定义状态变量sk，使它既能正，使它既能正确地描述过程的状态，又能满足无后效性确地描述过程的状态，又能满足无后效性。 在动态规划模型中，一般状态变量要选取那种可以进行累计的量。第45页/共159页46动态规划建模要点动态规划建模要点 正确地定义决策变量及各阶段的正确地定义决策变量及各阶段的允许决策集合允许决策集合Uk(sk)。 一般将问题中待求的量选作动态规划模型中的决策变量。第46页/共159页47动态规划建模要点动态规划建模要点 正确地写出状态转移方程正确地写出状态转移方程 要能正确反映状

21、态转移规律。如果给定第 k 阶段状态变量 sk 的值，则该段的决策变量 uk 一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有 sk+1 = Tk ( sk , uk )第47页/共159页48动态规划建模要点动态规划建模要点 正确地写出目标函数正确地写出目标函数 目标函数由递推关系构成，因此，它应满足下列性质：函数可分性：阶段指标相对独立；要满足递推关系；过程函数严格单调。 第48页/共159页49动态规划基本方程 fn+1(sn+1) = 0 (边界条件边界条件) fk(sk) = opt ugk ( sk , uk ) + fk+1(sk+1) k = n , n-1, ,

22、1第49页/共159页50（二）逆序求解动态规划基本方程（二）逆序求解动态规划基本方程 常见三种情况：一种是对于特殊的网络求最优路径，可以直接在网络图上，直观地使用标号法（见下一节）求解； 对于离散型的动态规划问题，常使用列表格（递推方程）的方法求解。 当阶段指标与递推公式可表示为解析显函数时，对于规模较大，特别是连续型的动态规划问题，常直接使用函数求优的方法。第50页/共159页51（三）回溯求得最优策略（三）回溯求得最优策略 从k=1k=1开始，逐步向后归纳出前一环节各步所选择的决策，得到决策序列，即最优策略。第51页/共159页521 1、例子例子 P176P176用用递推方程递推方程求

23、解最短路径问题求解最短路径问题第52页/共159页53（一）建模（一）建模如图划分成如图划分成 5 个阶段；个阶段；状态变量状态变量sk表示第表示第k阶段开始的位置；阶段开始的位置；决策变量决策变量uk定义为到达下一站所选择的定义为到达下一站所选择的路径；路径；状态转移：决策确定了下一阶段的状态；状态转移：决策确定了下一阶段的状态；阶段指标：图中线段上所标的数值；阶段指标：图中线段上所标的数值；第53页/共159页54 最优指标函数最优指标函数 fk(sk) ：表示从目前状态到表示从目前状态到E的最短路径。的最短路径。终端条件为终端条件为 f5 ( s5 ) = f5 ( E ) = 0其含义

24、是从其含义是从E到到E的最短路径为的最短路径为0。 11()()min (,)()4,3,2,1kkkkkkkkkkuUsfsgs ufsk第54页/共159页55（二）逆推求解（二）逆推求解第第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*8C2E第55页/共159

25、页56第第3阶段的递推方程为：阶段的递推方程为：)(),(min)(44333)(33333sfusgsfsUu从 f4(s4) 到f3(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=1614B2C1第56页/共159页57第第2阶段阶段的递推方程为的递推方程为从f3(s3) 到f2(s2) 的递推过程用表格表示如下 )(),(min)(33222)(22222sfu

26、sgsfsUu第57页/共159页58s2U2(s2)s3g2(s2,u2) g2(s2,u2)+f3(s3) f2(s2)最优决策最优决策u2*A1A1B1A1B2B1B2 6 56+11=17*5+14=1917A1B1A2A2B1A2B2B1B2 8 68+11=19*6+14=2019A2B1A3A3B1A3B2B1B2 7 47+11=18*4+14=18*18A3B1A3B2第58页/共159页59第第1 1阶段的递推方程为：阶段的递推方程为：从从 f2(s2)到到 f1(s1)的递推过程用表格的递推过程用表格 表示如下：表示如下： )(),(min)(22111)(11111sf

27、usgsfsUu 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 A3第59页/共159页60由此得到由此得到 f1(s1) =21 , 即从即从 A 到到 E的最短路径长度为的最短路径长度为21。（三）（三）回溯求最优策略：回溯求最优策略： 由由 f1(s1) 向向 f4(s4) 回溯，得到最短路径回溯，得到最短路径为：为：S A1 B1 C1 ES A3 B1 C1 ES A3 B2 C1 E第60页/共159页612 2、见

28、以下有向图，图中数字为两点间距、见以下有向图，图中数字为两点间距离离 要求：要求：用表格（递推方程）计算。用表格（递推方程）计算。（1 1）求出）求出ADAD的最短路径以及最短长度；的最短路径以及最短长度；（2 2）用双箭头在图上注明。）用双箭头在图上注明。第61页/共159页62参考答案A A到到D D的最短路径：的最短路径：ABAB3 3 C C1 1 D D最短长度：最短长度：2121第62页/共159页63第四章 运输问题第63页/共159页641. 求初始基本可行解求初始基本可行解 （西北角法、（西北角法、最小元素法最小元素法）2. 求检验数（求检验数（位势法位势法）3. 换基（换基

29、（闭回路闭回路）表上作业法：第64页/共159页651 1、初始基本可行解的确定、初始基本可行解的确定 （1 1）西北角法）西北角法：从：从西北角（左上角）西北角（左上角）格开始格开始，在格内的右下角标上允许取得，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。此进行下去，直至得到一个基本可行解。第65页/共159页66 （2）最小元素法）最小元素法：从：从运价最小的运价最小的格

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

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

32、ui ,vj 满足满足 ui+vj=cij ，i=1,2 ,m ; j=1,2 ,n . 称这些称这些 ui , vj 为该基本可行解对为该基本可行解对应的位势。应的位势。 第69页/共159页70由于有由于有m + n 个变量（个变量（ ui , vj ），）， m + n - 1 个方程（基变量个数），个方程（基变量个数）， 故有一个自由变量，位势不唯一故有一个自由变量，位势不唯一。 利用位势求利用位势求非非基变量基变量xij的检验数：的检验数： ij = cij - ui - vj i = 1, , m ; j = 1, , n第70页/共159页71位势法求检验数：位势法求检验数：st

33、ep 1 从从任意基变量对应的任意基变量对应的 cij 开始开始,任取任取 ui 或或 vj ，然后利用公式，然后利用公式 cij = ui + vj 依依次找出次找出 m + n 个个 ui , vj step 2 计算非基变量的检验数计算非基变量的检验数 ij = cij - ui - vj ；填入圆圈内；填入圆圈内第71页/共159页72 当非基变量的检验数出现负值时，当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解行调整，即找到一个新的基本可

34、行解使目标函数值下降，这一过程通常称使目标函数值下降，这一过程通常称为为换基换基( (或主元变换或主元变换) )过程（过程（闭回路闭回路法法）。3 3、求新的基本可行解、求新的基本可行解第72页/共159页7373 （1）选负检验数中最小者）选负检验数中最小者 rk，那么，那么 xrk 为主元，作为为主元，作为进基变量进基变量（上页图中（上页图中 x24 ）; （2）以以 xrk 为起点找一条闭回路为起点找一条闭回路，除，除 xrk 外其余顶点必须为基变量格（上页外其余顶点必须为基变量格（上页图中的回路）图中的回路）; 在运输问题的表上作业法中，换基的过程在运输问题的表上作业法中，换基的过程是

35、如下进行：是如下进行：第73页/共159页7474（3）为闭回路的每一个顶点标号，为闭回路的每一个顶点标号， xrk 为为 1号号，沿一个方向（顺时针或逆时针），沿一个方向（顺时针或逆时针）依次给各顶点标号；依次给各顶点标号；（4）求求 =Minxij xij对应闭回路上的偶对应闭回路上的偶数标号格数标号格= xpq 那么那么确定确定 xpq为为出基变量出基变量， 为调整量；为调整量；第74页/共159页7575（5）对闭回路的各对闭回路的各奇标号顶点调整奇标号顶点调整为：为：xij + ，对各，对各偶标号顶点偶标号顶点 调整为：调整为：xij - ，特别，特别 xpq - = 0， xpq变

36、为非变为非基变量。基变量。 重复重复(2)、(3)步，直到所有检验数步，直到所有检验数均非负，得到最优解。均非负，得到最优解。第75页/共159页76注意： （1）构造闭回路进行换基时，只）构造闭回路进行换基时，只有一个基变量出基，一个非基变量有一个基变量出基，一个非基变量进基；进基； （2）如果偶标号格中两个变量减）如果偶标号格中两个变量减去调整量后都变为零，则取其中一去调整量后都变为零，则取其中一个为出基变量，另一个填上运量个为出基变量，另一个填上运量0。76第76页/共159页771、例子 P99 第77页/共159页78最小元素法最小元素法 B1 B2 B3 B4 产量 ai A1 3

37、 11 3 4 10 3 7 A2 1 3 9 2 1 8 4 A3 7 4 6 10 5 3 9 销量 bj 3 6 5 6 20 第78页/共159页79 vj -3 4 -2 5 ui B1 B2 B3 B4 产量产量 ai 5 A1 3 1 11 2 3 4 10 3 7 4 A2 1 3 9 1 2 *1 8 -1 4 0 A3 7 10 4 6 10 12 5 3 9 销量销量 bj 3 6 5 6 20 第79页/共159页80 所有所有 ij 0，得到，得到最优解最优解 x13 = 5,x14 = 2,x21 = 3,x24 = 1, x32 = 6, x34 = 3, 其余其

38、余 xij = 0 ; 最优值最优值： f* = 35+102+13+81+46+53 = 85第80页/共159页812、用表上作业法求解下列运输问题 销地销地产地产地B1B2B3B4产量产量A1847290A25835100A37729120销量销量705011080第81页/共159页82第82页/共159页83第三章 线性规划对偶与灵敏度分析第83页/共159页84对偶规划的形式对偶规划的形式 有有对称形式对称形式和和非对称形式非对称形式。 对称形式对称形式的对偶规划之间具有下面的的对偶规划之间具有下面的对应关系：对应关系： (1) 若一个模型为目标求若一个模型为目标求“极大极大”，约

39、束为约束为“小于等于小于等于”的不等式，则它的不等式，则它的对偶模型为目标求的对偶模型为目标求“极小极小”，约束，约束是是“大于等于大于等于”的不等式。即的不等式。即 “max，” 和和 “min，” 相对相对应。应。第84页/共159页85(2) 从约束系数矩阵看：一个模型中从约束系数矩阵看：一个模型中为为，则另一个模型中为，则另一个模型中为AT。一个。一个模型是模型是m个约束，个约束，n个变量，则它个变量，则它的对偶模型为的对偶模型为n个约束，个约束，m个变量。个变量。(3) 从数据从数据b、C的位置看：在两个规的位置看：在两个规划模型中，划模型中，b和和C的位置对换。的位置对换。(4)

40、两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。第85页/共159页86 对称形式：对称形式： 互为对偶互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”第86页/共159页87非对称形式非对称形式的对偶规划的对偶规划: :对非对称形式，可以按照下面对非对称形式，可以按照下面的对应关系直接给出其对偶规划的对应关系直接给出其对偶规划(1) 将模型统一为将模型统一为“max，”或或“min，” 的形式，对于其中的等式约束按下面的形式，对于其中的等式约束按下面(2)、(

41、3)中的方法处理；中的方法处理；(2) 若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；值没有非负限制；(3) 若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。为等式。第87页/共159页881、例子例子 P67 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型 没没有有非非负负限限制制321432143143214321, 0,1053042260272252375m

42、axxxxxxxxxxxxxxxxxxxZ第88页/共159页89解 先将约束条件变形为先将约束条件变形为“”形式形式 没有非负限制没有非负限制4321443214314321, 0, 051030422602722523xxxxxxxxxxxxxxxx第89页/共159页90根据非对称形式的对应关系，直接写根据非对称形式的对应关系，直接写出对偶规划出对偶规划 0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf没没有有非非负负限限制制第90页/共159页912、写出下面线性规划的对偶规划模、写出下面线性

43、规划的对偶规划模型型无符号限制42314321432143214321, 0,1067912857653432maxxxxxxxxxxxxxxxxxxxxxZ第91页/共159页92第92页/共159页9393理解最优单纯形表的含义理解最优单纯形表的含义考虑问题考虑问题 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0灵敏度分析灵敏度分析第93页/共159页

44、9494设设最优最优单纯形表单纯形表其中：其中：nmjaaappBppppAbBbaccbcfTmjjjjjjnmiijijjmiii, 1,),(,21121111 第94页/共159页9595灵敏度分析灵敏度分析ci 单个变化单个变化保持最优解不变保持最优解不变的允许的允许范围范围bj 单个变化对单个变化对解的可行性解的可行性的影响的影响线性规划增加一个变量线性规划增加一个变量线性规划增加一个约束线性规划增加一个约束第95页/共159页96961.若若ck是非基变量的系数：是非基变量的系数：设设ck变化为变化为 ck + ck k= k+ ck只要只要 k 0 ,即即 ck - k ，则最

45、优解不则最优解不变；否则，将变；否则，将最优单纯形表最优单纯形表中的检验中的检验数数 k 用用 k取代，继续单纯形法的表取代，继续单纯形法的表格计算格计算。第96页/共159页9797例 Max z = -2x1 - 3x2 - 4x3 S.t. -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 +x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0第97页/共159页9898例：最优单纯形表例：最优单纯形表 cI -2 -3 -4 0 0 cB xB b x1 x2 x3 x4 x5 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/

46、5 1 0 7/5 -1/5 -2/5 j 0 0 -9/5 -8/5 -1/5 cI -2 -3 -4+c3 0 0 cB xB b x1 x2 x3 x4 x5 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 0 0 -9/5+c3 -8/5 -1/5 从表中看到从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到可得到c3 9/5 时，原最优解不变。时，原最优解不变。第98页/共159页9999设设 cl 变化为变化为 cl + cl ，那么，那么 j= j - cl alj 只要对所有非基变量只要对所有非

47、基变量 j0，即，即 j clalj ，则最优解不变；否则，将则最优解不变；否则，将最优单纯形最优单纯形表表中的检验数中的检验数 j 用用 j取代，继续单纯取代，继续单纯形法的表格计算形法的表格计算。 2 2、若若 cl 是基变量的系数是基变量的系数第99页/共159页100100Max 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增加变量增加变量增加约束增加约束第100页/共159页101101下表为最优单纯形表下

48、表为最优单纯形表, ,考虑考虑基变量系数基变量系数c c2 2发生变化发生变化c i 2 3 0 0 0 cB xB B x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -1/8 0 ci 2 3+c c2 0 0 0 cB xB B x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3+c c2 x2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -C C2/2 -1/8+C C2/8 0 由由j=c

49、j-(c1a1j+c5a5j+(c2+c2)a2j) j=3,4可得到可得到 -3c21时，原最优解不变。时，原最优解不变。第101页/共159页102102 设分量设分量 br 变化为变化为 br + br ，只要保持，只要保持 B-1(b + b)0 ，则，则最优基不变最优基不变，即对，即对偶价格不变；否则，需要利用偶价格不变；否则，需要利用对偶单纯对偶单纯形法形法继续计算。继续计算。3 3、 右端常数的变化右端常数的变化第102页/共159页103103上例上例最优单纯形表如下最优单纯形表如下 ci 2 3 0 0 0 cB x B b x1 x2 x3 x4 x5 2 x1 4 1 0

50、 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -1/8 0 例例第103页/共159页104104 0 0.25 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用用对偶单纯形法对偶单纯形法进一步求解，可得：进一

51、步求解，可得：第104页/共159页105105c i 2 3 0 0 0 cB xB B x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 -4 0 0 -2 1/2 1 3 x2 4 0 1 1/2 -1/8 0 j -20 0 0 -1.5 -1/8 0 2 x1 4 1 0 0 1/4 0 0 x3 2 0 0 1 -1/4 -1/2 3 x2 3 0 1 0 0 1/4 j -17 0 0 0 -1/2 -3/4 于是，于是，x* = ( 4, 3, 2, 0, 0 )T f* = 17第105页/共159页106106讨论讨论保持最优基不变保持最优基不变

52、的前提下，的前提下， b2的允许变化范围的允许变化范围 4 + b2 0.25 0 b2 -16 4 + b2 0.5 0 b2 -8 2 + b2 (- 0.125) 0 b2 16于是于是 -8 b2 16第106页/共159页107107增加变量增加变量 xn+1, 相应有相应有pn+1, cn+1 。 可可计算出计算出 B-1pn+1, n+1=cn+1-cri ari n+1 填入最优单纯形表：填入最优单纯形表：若若 n+1 0 则则 最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。4、 增加新变量增加新变量第107页/共159页108108例例对前例

53、对前例，增加，增加x6 , p6=( 2, 6, 3 )T, c6=5ci 2 3 0 0 0 5 cB xB b x1 x2 x3 x4 x5 x6 2 x1 4 1 0 0 1/4 0 1.5 0 x5 4 0 0 -2 1/2 1 2 3 x2 2 0 1 1/2 -1/8 0 0.25 j 0 0 -1.5 -1/8 0 1.25 用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5666616,pccpBpTB第108页/共159页109109 首先首先，应把最优解代入新的约束，应把最优解代入新的约束 若满足，则最

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

55、是不满足这个约束。于是ci 2 3 0 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x1 4 1 0 0 1/4 0 0 0 x5 4 0 0 -2 1/2 1 0 3 x2 2 0 1 1/2 -1/8 0 0 0 x6 15 3 2 0 0 0 1 j 0 0 -1.5 -1/8 0 0 对表中新的一行利用矩阵初等行变对表中新的一行利用矩阵初等行变换进行处理，可得新的对偶单纯形表：换进行处理，可得新的对偶单纯形表：第110页/共159页111111经对偶单纯形法一步，可得最优解经对偶单纯形法一步，可得最优解为（为（3.5, 2.25, 0, 0, 3, 2 )T，最

56、优值为最优值为 13. 75ci 2 3 0 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x1 4 1 0 0 1/4 0 0 0 x5 4 0 0 -2 1/2 1 0 3 x2 2 0 1 1/2 -1/8 0 0 0 x6 -1 0 0 -1 -1/2 0 1 j 0 0 -1.5 -1/8 0 0 第111页/共159页112112灵敏度分析 1第112页/共159页113113第113页/共159页114参考答案114212(2)0cb(1)(3) 影响第114页/共159页115115灵敏度分析 2第115页/共159页116第116页/共159页117参考

57、答案117第117页/共159页118第二章 单 纯 形 法第118页/共159页119标准形式标准形式目标函数：目标函数：Max z = c1x1 + c2x2 + + cnxn 约束条件：约束条件：a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0 0第119页/共159页120 线性规划的标准形式有如下四个线性规划的标准形式有如下四个特点：特点：目标最大化、约束为等目标最大化、约束为等式、决策变量均非负、右端项式、决策变量均非负、

58、右端项非负。非负。 对于各种非标准形式的线性规划对于各种非标准形式的线性规划问题，转换成标准形式进行求解。问题，转换成标准形式进行求解。 第120页/共159页1211.极小化目标函数的问题：极小化目标函数的问题： 设目标函数为设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令则可以令z-f ，该极小化问题与下面，该极小化问题与下面的极大化问题有相同的最优解，即的极大化问题有相同的最优解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值优解相同，但他们

59、最优解的目标函数值却相差一个符号，即却相差一个符号，即 Min f - Max z第121页/共159页1222、约束条件不是等式的问题：、约束条件不是等式的问题： 设约束条件为设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量可以引进一个新的变量s ，使它等于，使它等于约束右边与左边之差约束右边与左边之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，显然，s 也具有非负约束，即也具有非负约束，即s0， 这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi第122页/共159页1

60、23 当约束条件为当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令时，类似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 显然，显然，s 也具有非负约束，即也具有非负约束，即s0，这时，这时新的约束条件成为新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi 第123页/共159页124 为了使约束由不等式成为等式为了使约束由不等式成为等式而引进的变量而引进的变量 s 称为称为“松弛变量松弛变量”。如果原问题中有若干个非等式约束，如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对则将其转化为标准形式时，必须