2025年运筹学重点课件

运筹学

OperationalResearch运筹帷幄，决胜千里

史记《张良传》1目录绪论第一章线性规划第二章运输问题第三章整数规划第四章动态规划第五章目标规划第六章图与网络分析2运筹学的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划、多目标规划图论与网络理论随机服务理论：排队论存储理论决策理论对策论系统仿真：随机模拟技术、系统动力学可靠性理论3三、运筹学解决问题的方法步骤明确问题建立模型设计算法整理数据求解模型评价结果明确问题建立模型设计算法整理数据求解模型评价结果简化？满意？YesNoNo4第一章

线性规划LinearProgramming51.1.1问题的提出例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备时间和原料A、B的消耗量如下表。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划能使该厂获利最多？

§1.1一般线性规划问题及数学模型6建立模型：设产品的产量为

Ⅰ：x1件，Ⅱ：x2件，则Max z=2x1+3x2x1+2x284

x1164

x2

12x10，

x20目标(object)：限制条件(subjectto)：7

1.相关概念

（1）决策变量：指模型中要求解的未知量，简称变量。（2）目标函数：指模型中要达到的目标的数学表达式。（3）约束条件：指模型中的变量取值所需要满足的一切限制条件。此三项内容称为模型结构的三要素。

1.1.2线性规划问题的一般数学模型8

2.线性规划模型的一般要求

（1）目标函数：线性表达式；（2）约束条件：线性的等式或者不等式。9

1.1.4

线性规划模型的标准形式（1）变量：所有变量均xj≥0（2）目标函数：为取“max”形式（3）约束条件：全部约束方程均为“=”连接（4）约束右端项：bi≥0

非标准形式情况有变量：xj≤0,或xj无约束目标函数：min约束条件：“≤”或“≥”约束右端项：bi<0

10LP的标准化：

（1）变量：若xj

0，令xj=-xj

，xj0

若

xj无约束，则令xj=xj

－xj

，xj0，xj0xzzzminz=-zz

max（2）目标函数：若求minz

则令z=-z，等价于求maxz

即有minz=-max(-z)11LP的标准化：（3）约束方程：当“

”时，引进松弛（slack）变量+xs；如x1+x23x1+x2+x3=3

当“

”时，引进剩余（surplus）变量-xs；如x1+2x2

4

x1+2x2－x4=4（4）约束右端项：当bi<0，则不等式两端同乘（-1）

12obj.Minz=2x1-x2+3x3st. x1+2x2+4x36

3x1-2x2+x3=4 2x1-x2-3x35

x1

0,x2无符号限制,x3

0课堂练习1-1：将下面的线性规划问题化为标准型：13解：设z=-z,x2=x2-x2,x20,x20,x3=-x3,x30，

x40,x50,则有

obj.Maxz=-2x1+(x2-x2)+3x3

s.t.x1+2(x2-x2)-4x3

+x4=6 3x1-2(x2-x2)-x3=4 2x1-(x2-x2)+3x3

-x5=5 x10,x20,x20,x30,x40,x50141.1.6线性规划问题解的有关概念设模型nmaxz=

cjxj

j=1ns.t.

aijxj=bi

（i=1,2,……,m)

j=1xj≥0（j=1,2,……,n)（1）可行解：满足所有约束方程和变量符号限制条件的一组变量的取值。（2）可行域：全部可行解的集合称为可行域。（3）最优解：使目标函数达到最优值的可行解。15（4）基：设Am

n(m<n)为线性规划模型约束条件系数矩阵，而B为其m

m子矩阵，若|B|≠0，则称B为该线性规划模型的一个基。（5）基变量：基中每个向量所对应的变量称为基变量。（6）非基变量：模型中基变量之外的变量称为非基变量。（7）基本解（基解）：

令模型中所有非基变量X非基=0后，由模型约束方程组n

aijxj=bi(i=1,2,……,m)得到的一组解。

j=116（8）基本可行解（基可行解）：

在基本解中，同时又是可行解的解称为基本可行解。（9）可行基：对应于基本可行解的基称为可行基。17Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T

等。设B=

1001，令，则|B|=1≠0,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基变量令B=1110x1x3

，则令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解标准化18§1.2线性规划问题的图解方法图解法是直接在坐标系中作图来解线性规划问题的一种方法，适合于求解两个变量或至多三个变量的线性规划问题。

－－－解的几何表示

19图解法举例

实施图解法，以求出最优生产计划（最优解）。

例1maxZ=2x1+3x2s.t.20步骤：

（1）作平面直角坐标系，标上刻度； （2）做出约束方程所在直线，确定可行域； （3）做出一条目标函数等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优值。21

两个约束条件

及非负条件x1,x2

0所代表的公共部分

－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。

第二个约束条件的边界－－直线CD:1/3x1+4/3x2=322

沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点E,E点就是要求的最优解，即x1=1,x2=2就是线性规划模型的最优解，Zmax=8就是相应的目标函数最优值。

23*利用作图方法求解。例：maxz=2x1+3x2 s.t2x1+2x2

12----------①

x1+2x2

8----------② 4x1

16----------③4x2

12----------④ x10,x20

24x1x222468460①②④③Z=6Z=0(4,2)Zmax25第二章运输问题Transportationproblem26

表上作业法是单纯形法在求解运输问题的一种简化方法．确定初始方案也就是寻找一个基本可行解的过程．

3.2运输问题的表上作业算法和程序求解27表上作业法:

初始方案

最优性检验

改进方案一、初始方案的确定

1.西北角法

2.最小元素法

3.Vogel法二、最优性检验

1.闭回路法

2.位势法三、方案改进方法

在闭回路内改进。表上作业法步骤28典例：

某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A1—7吨，A2—4吨，A3—9吨销售量：B1—3吨，B2—6吨，B3—5吨，B4—6吨产地单位运价销地B1B2B3B4

A1A2A3

311 3 10

1 9 2 87 4 10 529模型设xij—第i产地到第j销地之间的调运量，则有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij

0,(i=1,2,┄,3；j=1,2,┄,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=630一、初始方案(基本可行解)的确定初始方案(基本可行解)的确定的方法

1.西北角法

2.最小元素法

3.Vogel法311.西北角法西北角法：从运输表的西北角格子开始，优先安排标号小的产地与销地间的运输。每填一个格后只能划去一行或一列（可以填0以达目的）如有两个以上格子可以填0，此时0应填在运价最小的格子处，这样可以减少调整工作.如此直到安排结束。32(一)西北角法西北角332.最小元素法最小元素法：从单位运价最小的格子开始安排，逐步达到平衡，给出调运方案的方法。每填一个格后只能划去一行或一列（可以填0以达目的）如有两个以上格子可以填0,此时0应填在运价最小的格子处,这样可以减少调整工作.如此直到安排结束。34(二)最小元素法最小元素0.1产量400和销量300最小者35最小元素0.236最小元素0.337最小元素0.438最小元素0.5390.30.10.20.4403.伏格尔(Vogel)法Vogel法步骤：一、分别计算运价表的每行、每列最小元素与次小元素的差并填入该表的最右列和最下行二、在行或列差额中选出最大者，选择这所在的行或列中单位运价最小格开始安排三、划去对应的行或列的元素，再分别计算运价表的每行、每列两最小元素（最小、次小）差并填入该表的最右列和最下行，且不断重复上述步骤，直至给出调运方案。Vogel法求出的初始解即为近似最优解41产地销地A1A2A3B1B2B3B4行两最小元素之差列两最小元素之差31131019287410501125130122-1301-2-1276---12Vogel法:产地销地A1A2A3B1B2B3B4749产量销量3656635213产销平衡表单位运价表42课堂练习:产量产地销地A1A2A3B1B2B3销量6281214910115141437试用Vogel法直接给出近似最优解43课堂练习:产量产地销地A1A2A3B1B2B3销量31211491011210144近似最优解P8344应用举例某百货公司去外地采购A，B，C，D四种规格的服装，数量分别为A--1500套，B--2000套，C--3000套，D--3500套。有三个城市可以供应上述规格服装，供应数量分别为Ⅰ--2500套，Ⅱ--2500套，Ⅲ--5000套。由于这些城市的服装质量、运价的销售情况不同，预计售出后的利润也不同，见下表，请帮该百货公司确定一个预期赢利最大的采购方案。45销地运价产地ABCD产量Ⅰ105672500Ⅱ82762500Ⅲ93485000销量1500200030003500试用Vogel法直接给出近似最优解46第三章整数规划1.整数规划的数学模型及解的特点2.分支定界法、割平面法47

1.整数规划的数学模型及解的特点整数规划数学模型的一般形式一部分或全部决策变量取整数值的规划问题

——整数规划整数规划中不考虑整数条件所对应的规划问题

——该整数规划的松弛问题松弛问题为线性规划的整数规划问题

——整数线性规划48整数线性规划的几种类型纯整数线性规划混合整数线性规划0-1型整数线性规划49例1

一家昼夜服务的饭店，24小时中需要的服务员数如下表所示。每个服务员每天连续工作8小时，且在时段开始时上班。问：最少需要多少名服务员？试建立该问题的线性规划模型。整数规划的例子50模型：设以xj表示第j时段开始上班工作的服务员数，则Minz=x1+x2+x3+x4+x5+x6 st.x6+x14 x1+x2

8 x2+x3

10 x3+x4

7 x4+x5

12 x5+x6

4 xj0,xj为整数(j=1,2,---,6)51解的特点整数线性规划与其松弛问题比较，前者的最优解的目标函数值不会优于后者的。例：考虑下面的整数规划问题且取整数52从图上分析：012345678BPC整数规划最优解53

分支定界法(既适合于纯整数规划,又适合于混合整数规划)

割平面法(适用于纯整数规划)

枚举法(一般用于变元较少的问题)整数规划问题的解法通常有:542.

整数规划的分枝定界法

分枝定界法是解整数规划（包括纯整数规划和混合整数规划）的一种重要方法。它是LandDoing

和Dakin等人于20世纪60年代提出的。55分支定界法是枚举法基础上的改进。分支定界法的关键是分支和定界。思路：利用其松弛问题的最优解（值）来分支定界。562.1

解题步骤

1、在全部可行性域上解松弛问题

--只解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解57

2、分枝过程

(1)若松弛问题最优解中某个xk=bk

不是整数，令

bk

为bk

的整数部分

(2)构造两个新的约束条件xk

bk

和xk

bk+1，分别加于原松弛问题，形成两个新的整数规划583、求解分枝的松弛问题

—定界过程

设两个分枝的松弛问题分别为问题1

和问题

2

，它们的最优解有如下情况(7种)5960情况1无最优解情况2,4,5

找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或5情况7后面介绍61注意：1）松驰问题的解可能存在多个变量都是非整数解的情况，则取对应分数部分最大的变量进行分枝。62

2）可能存在两个分枝都是非整数解的情况，则比较对应的最优解，记其中较优的问题为活问题，另一为暂时希望问题。对活问题继续分枝求解，所得结果比暂时希望问题优，则暂时希望问题删除（剪枝）。否则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程(情况7)

63课堂习题

某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙2 2 33 1 2

14 米3 9吨托运限制64建模：解：设托运甲货物x1箱，乙货物x2箱

Maxz=3x1+2x2

st.2x1+3x2

14 2x1+x2

9 x1

0，x2

0，且为整数6524624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=6Maxz=3x1+2x2

666724624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)Maxz=3x1+2x2

68分枝问题的松弛解对问题1先继续进行分支,问题2为暂时希望问题问题1的最优解为

x1=3.5,x2=2,OBJ=14.5问题2的最优解为

x1=2.5,x2=3,OBJ=13.5697024624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)Maxz=3x1+2x2

71问题1的分支问题松弛解问题4的解为最优解.问题3的最优解为

x1=3,x2=2,OBJ=13问题4的最优解为

x1=4,x2=1,OBJ=1472分枝定界法:L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥4

73第四章0-1规划与指派问题740-1规划问题及模型一、0-1规划问题的概念在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。

0-1变量通常用来表示逻辑性选择的决策。75二、0-1变量的应用

例：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？76设xj=10---选择开采第j个构造---不选择开采第j个构造j=110∑ajxj

bxj＝0或1(j=1,2,---,10)maxz=Σcjxjj=110-----年总收益----投资额限制77三、解法---隐枚举法思路:

不需要列出所有组合，只关心目标函数值的最优可行组合，按目标值从优到劣依次列出组合，逐个检验其可行性，最先满足所有约束条件的组合为最优解.78步骤：化标准形：

1)目标函数极小化

2)约束条件化成

3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj

4)使目标函数按变量系数由小→大顺序排列，约束条件变量排列的顺序要与之对应。79②检验:

化标准形令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约束条件，若满足，即为最优解；否则，分枝计算。80分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后检查是否满足所有约束，若满足，转下步；否则继续分枝。81剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。

(a)对可行解，保留边界值最小的一枝zmin，其余全剪掉；

(b)>zmin分枝，剪掉；

(c)能判断出为无可行解的分枝，剪掉；

(d)非上述情况，继续分枝。

82例：Maxz=8x1+2x2-4x3-7x4-5x5 s.t.3x1+3x2+x3+2x4+3x5

4 5x1+3x2-2x3-x4+x54 xj=0或1(j=1,2,3,4,5)831)目标函数极小化:minz

=-8x1-2x2+4x3+7x4+5x5①化标准形：2)约束条件：-3x1-3x2-x3-2x4-3x5

-4 -5x1-3x2+2x3+x4-x5-4 xj=0或1(j=1,2,3,4,5)843)使目标函数系数皆为正：令x1=1-x1

，x2=1-x2

minz

=-8+8x1

-2+2x2

+4x3+7x4+5x5st.-3+3x1

-3+3x2

-x3-2x4-3x5

-4-5+5x1

-3+3x2

+2x3+x4-x5-4x1,x2,xj=0或1(j=3,4,5)854)变量按顺序排列：minz

=2x2

+4x3+5x5+7x4+8x1

-10st.3x2

-x3-3x5-2x4+3x1

23x2

+2x3-x5+x4+5x14x1,x2,xj=0或1(j=3,4,5)86求解图示：1234567891011z=-10z

=-8z=-4z=-10z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0x3=1x3=0x3=1x3=0x5=1x5=0x5=1x5=0z=-3√×××××87上述问题的最优解为

x1=1,x2=0,x3=1,x4=0，x5=0。最优值为Maxz=488课后练习：Maxz=2x1-x2+5x3-3x4+4x5 s.t.3x1-2x2+7x3-5x4+4x5

6 x1-x2+2x3-4x4+2x50 xj=0或1(j=1,2,3,4,5)89上述问题的最优解为

x1=0,x2=0,x3=1,x4=1，x5=1。最优值为Maxz=690

现实生活之中，我们经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂。TheAssignmentProblem指派问题91指派问题的形式表述:

给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务

TheModelforAssignmentProblem指派问题模型

92被指派者的数量和任务的数量是相同的

每一个被指派者只完成一项任务

每一项任务只能由一个被指派者来完成

每个被指派者和每项任务的组合有一个相关成本

目标是要确定怎样进行指派才能使得总成本最小

指派问题的假设:93典型问题例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。

94甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139问：如何分配，能使所需的总时间最少？95建立模型：Minz=aijxij (aij---效率)i=1j=144设xij=10若第i项工作交与第j个人完成若第i项工作不交与第j个人完成96译英文：x11+x12+x13+x14=1译日文：x21+x22+x23+x24=1译德文：x31+x32+x33+x34=1译俄文：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1丁：x14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)97解法一、匈牙利方法由匈牙利数学家Konig提出。98

思路：克尼格定理(konig)

如果从效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui,从每一列中分别减去(或加上)一个常数vj,得到一个新的效率矩阵[bij],其中bij=aij-ui-vj,则以[bij]为效率矩阵的最优解等价于以[aij]为效率矩阵的最优解.99证明:以[aij]为效率矩阵的目标函数值：z0=aijxij以[bij]为效率矩阵的目标函数值：z

=

bijxijmmi=1j=1i=1j=1mm∵bij=aij-ui-vj100∴z=(aij-ui-vj)xijmm=z0-ui-vj=z0-constantmmi=1j=1i=1j=1=aijxij-uixij-vjxij

mmmmi=1j=1i=1j=1i=1j=1mm=z0-uixij-

vjxijmmmi=1j=1j=1i=1m101步骤⑴使每行、每列都出现0元素方法：每行减该行最小元素；2109715414813141611415139-2-4-11-4min0875110104235001195min-0-0-5-0082511054230001145-2-2

-2+2+2080311032450001123每列减该列最小元素。102⑵寻找位于不同行不同列的0元素准则：A）从第一行开始，若只有一个0，则记（0），同时作直线覆盖该列的元素。否则，转下行；B）从第一列开始，若只有一个0，则记（0），同时作直线覆盖该行的元素。否则，转下列；C）重复A）、B），至再找不出这样的0元素，转D）103D）可能出现以下情况： ①每行均有（0）元素，则在有（0）位置构成最优解中xij=1； ③多于两行和两列存在未被直线覆盖的0元素，即存在0元素的闭回路，则沿回路顶点每间隔一个0记（），同时作直线覆盖该列的元素；②所有0元素均有直线覆盖，但记（0）的个数<m个，转⑶。000000104⑶迭代，寻找新的位于不同行不同列的0元素a）从未被直线覆盖的元素中找出一个最小的元素amin； b）将示划去元素均减去amin，被一条直线划去的元素保持不动，被两条直线划去的元素加上

amin；⑷转⑵105今有5辆Bi货车装货待卸，调度员分配五个装卸货组Ai卸货，由于各组技术专长不同，各组所需时间表如下，调度员应如何分配，使所花时间最少？课堂练习106107习题求解108学生A，B，C，D的各门成绩如下表，将该四名学生派去参加各门课的单项竞赛。由于竞赛同时举行，故每人只能参加一项，若以他们的成绩作为选派依据，应如何分派最为有利？课堂练习109数学物理化学英语A89926881B87886578C95708572D75788996110GoalProgramming

第五章目标规划线性规划：单一目标目标规划：多目标、优先次序、 综合规划1115.1问题的提出和数学模型引例：某企业生产Ⅰ、Ⅱ两种产品，其生产的参数如表中所示。在制定生产计划时要考虑如下内容：（1）依据市场反馈信息，预测表明，两种产品的生产比例大致保持1:1为宜；（2）设备能力尚有机动的余地，B设备必要时可以加班，但希望加班时间愈少愈好；A设备较为重要，所以既希望能力能够被充分利用，同时又尽量少加班；112（3）企业将利润指标定位12元，并力求超过。企业认为，在上述考虑的目标中，利润要求最为重要；产量比例次之；A设备的重要性是B设备的三倍。试建立该问题的数学模型。

产品设备ABCD利润ⅠⅡ21402204加工能力128161223113弹性约束的处理方法实际量＋d－－d+

=目标值负偏差变量正偏差变量最好等于：最好不大于：最好不小于：114

目标值d1-d1+实际值实际值d1-

0，d1+

0d1-

d1+=0正偏差变量负偏差变量115思考题若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确？（1）（2）（3）（4）maxz=（

d1-+d1+

）minz=（

d1-+d1+

）maxz=（

d1--d1+

）minz=（

d1--d1+

）116产品设备ABCD利润ⅠⅡ21402204加工能力128161223二、建立模型设x1——Ⅰ产品的产量x2——Ⅱ产品的产量（1）x1-x2=0+d1--d1+min（d1-+d1+）（2）B：x1+2x2=8A：2x1+2x2=12（3）2x1+3x2=12+d2--d2++d3--d3++d4--d4+mind2+min（d3-+d3+）mind4-C：4x1

16D：4x2

12117x1-x2+d1--d1+

=0x1+2x2+d2--d2+

=82x1+2x2+d3--d3+=124x1

164x2

122x1+3x2+d4--d4+

=12Minz=P1d4-+P2(d1-+d1+)+3P3(d3-+d3+)+P3d2+St.x1,x2

0,di-,di+

0,(i=1,2,3,4)Pi——优先级系数，i越小，则级别越高。目标规划模型如下：①②③④⑤⑥118⑴引进偏差变量，表示实际值与目标值之间的差距。其中，di-表示负偏差，体现实际值低于目标的大小； di+表示正偏差，体现实际值高于目标的大小。⑵约束分两种形式：系统约束——刚性约束，严格限制；可以不出现；目标约束——柔性约束，弹性限制。必须存在。⑶目标函数只出现偏差变量，而不含决策变量。⑷模型引进优先级系数的概念。三、模型的特点119

某市准备在下一年度预算中购置一批救护车,已知每辆救护车购置价为20万元.救护车用于所属的两个郊区县，各分配xA和xB台，A县救护站从接到求救电话到救护车出动的响应时间为（40-3xA）秒，B县相应的响应时间为（50-4xB）秒，该市确定如下优先级目标。

P1：救护车购置费用不超过400万元

P2：A县的响应时间不超过5秒

P3：B县的响应时间不超过5秒要求（1）建立目标规划模型。（2）若对优先级目标作出调整，P2变成P1，P3变成P2，P1变P3，重新建立模型。典型例题12020xA-20xB+d1--d1+

=40040-3xA+d2--d2+

=550-4xB+d3--d3+=5Minz=P1d1++P2d2++P3d3+St.xA,xB

0,di-,di+

0,(i=1,2,3)Pi——优先级系数，i越小，则级别越高。目标规划模型如下：①②③121x1-x2+d1--d1+

=0x1+2x2+d2--d2+

=82x1+2x2+d3--d3+=124x1

164x2

122x1+3x2+d4--d4+

=12Minz=P1d4-+P2(d1-+d1+)+3P3(d3-+d3+)+P3d2+St.x1,x2

0,di-,di+

0,(i=1,2,3,4)Pi——优先级系数，i越小，则级别越高。例1：目标规划模型如下①②③④⑤⑥122例1：目标规划模型的图解法描述①作平面直角坐标系；②作出系统约束所在直线,确定可行范围(由约束4,5及变量约束确立)③作出目标约束所在直线，标出偏差方向；按优先级次序，确定满意解。

1.首先对P1的d4-尽量小的区域在直线6的右上方

2.其次对P2的d1-+d1+尽量小，它恰好在直线1上

3.再于P3的d1-+d1+尽量小，它在直线3上，则在直线1和3的交点F处,123

4.又d2-尽量小，应在直线2的下方，无法满足。由于d1-+d1+有权系数3，从而应先满足它，则下一级目标舍弃，这样所求解为F点，坐标F(3,3)。这里d2-尽量小未能满足，这样F(3,3)不能算最优解，为了区别，称之为满意解.

显然,有时上述解可能是某个区域，某个线段。如果全部目标达到，且范围缩为一点，此时为最优解.124x1x224680246①②③④⑤⑥d1-d2-d3-d4-d1+d2+d3+d4+ABCDEF(3,3)G图解法125模型－顾客访问策略例2：目标规划模型如下126X100300200600500400X21002003004005001(1)(2)(3)(4)(5)例2：目标规划模型的图解法描述127第六章图与网络分析图是最直观的模型128图论

GraphTheory哥尼斯堡七桥问题(KönigsbergBridgeProblem)BACD129瑞士数学家LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文，讨论了哥尼斯堡七桥问题，奠基了图论中的一些基本定理。130图的基本概念和模型一、概念（1）图：点V和边E的集合，用以表示对某种现实事物的抽象。记作G=｛V,E｝,

V=｛v1,v2,···,vn｝,

E=｛e1,e2,···,em｝点：表示所研究的事物对象边：表示事物之间的联系v1v2v3v4v0e1e2e3e4e5e6e7e0131（2）环：若边e的两个端点重合，则称e为环。（3）多重边：若某两端点之间多于一条边，则称为多重边。（4）简单图：无环、无多重边的图称为简单图。132（5）途径：点和边的交替序列。（6）迹：点和边的交替序列，其中点可重复，但边不能重复（7）路：点和边的交替序列，但点和边均不能重复。（8）圈：始点和终点重合的路。133（10）连通图：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。（11）子图：设图G1=｛V1,E1｝,G2={V2,E2},如果有V1

V2，E1

E2，则称G1是G2的一个子图；若V1=V2，E1

E2，则称G1是G2的一个支撑子图。134（12）度：某点vi的关联边的个数称为该点的度，以d(vi)表示。（13）关联的：边与它的两个端点称为关联的。（14）相邻的：与同一条边关联的两个端点或者与同一个顶点关联的两条边。135二、图的模型

例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表中所示，打“√”的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？136甲乙丙丁戊己项目人A B C D E F √ √√ √ √ √ √ √ √ √ √ √ √137建立模型：解：项目作为研究对象，排序。设点：表示运动项目。边：若两个项目之间无同一名运动员参加。ABCDEFA—C—D—E—F—BA—F—E—D—C—BA—C—B—F—E—DA—F—B—C—D—E顺序：138中国邮递员问题ChinesePostmanProblem

CPP139中国邮递员问题(ChinesePostmanProblem,CPP)是Euler问题的推广:

中国数学家管梅谷于1962年提出。邮差从邮局出发送信,再转回邮局,每条街道都必須走过至少一次,则其最短路径为何?adgbehcfiadgbehcfi140如果街区图不含奇点，根据定理，一定有欧拉回路，CPP问题也就迎刃而解了若街区图中有奇点，则必然有一些街道要被重复走过才能回到原出发点

1)显然要在奇次点间加重复边

2)如何使所加的边长度最少

3)归结为求奇次点间的最小匹配(minimumweightedmatch)—由Edmons

和Johnson(1975)给出多项式算法141问题：一名邮递员从邮局出发，试选择一条最短的投递路线？v1v2v3v4v5v6v8v7v9v10v11v12v13邮局44455124125447422142结论：

最短投递路线应具有下述特征：⑴若图中所有的点均为偶点，则可不重复走遍所有街道；⑵重复走的路线长度应不超过所在回路总长度的一半。143奇偶点作业法步骤：两两连接所有的奇点，使之均成为偶点；2.检查重复走的路线长度，是否不超过其所在回路总长的一半，若超过，则调整连线，改走另一半。144v1v2v3v4v5v6v8v7v9v10v11v12v13邮局44455124125447422投递距离：L=60+18=78145奇偶点算法的特点

能求出中国邮递员问题的最优解

算法要检查图中诸圈添加边的权，当图中点、边、圈个数较多时，算法较复杂。146奇偶点算法改进（二）

----（初始方案的改进）

在所给的图的奇点处做标记，如加“·”

求该图最小生成树（用避圈法或破圈法,破圈原则:1.从权数最长边的圈开始,2.尽可能多保留与奇点相连的边,3.已为偶点者的边尽可能不去掉）在最小生成树上的奇点处添加重复边（原则是点从权数最小的边开始），以消灭奇点.

回到原问题，且按判别准则检验和调整，直至最优。147v1v2v3v4v5v6v7v8v9邮局524634549434148v1v2v3v4v5v6v7v8v9邮局5243454434149v1v2v3v4v5v6v7v8v95243454434最优解投递距离：L=53+15=68150v1v2v3v4v5v6v7v8v9邮局524634549434投递距离：L=53+15=68经检验为最优解.还原并检验151习题4231324332554134152答案4231324332554134153最短路问题

154给定带权有向图（或无向）G＝<V，E，W>和源点v0∈V，求从v0到G中其余各顶点的最短路径。下面叙述的Dijkstra算法是Moore(1957)，Dijkstra(1959)，Danzig(1960)以及whiting&Hillier(1960)各自发现的。1.求任意一点到其余各顶点的最短路径155算法的基本思想是：

设置两个顶点的集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S是空集，从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中。集合S每加入一个新的顶点u，都要修改v0到集合T中剩余顶点的最短路径长度值。再从T中选取到顶点v0路径长度最短的顶点u加入到集合S中，此过程不断重复，直到集合T的顶点全部加入到S中为止。156Dijkstra算法的实现（1）S为已找到从v0出发的最短路径的终点的集合，它的初始状态为空集，T=V-S,。引进一个辅助向量D，它的每个分量D[i]表示始点v0到每个终点vi

的最短路径的长度。它的初态为：若从v0到vi有弧（边），则D[i]为弧上的权值；否则置

D[i]为∞。(2)顶点选取，D[u]=Min{D[i]|vi∈T},S=S+{vu},T=T-{vu}157(3)修改D[j]D[j]=Min{D[j],D[u]+wuj}Vj∈V-S

其中，D[i]或者弧（v0,vj）上的权值，或者是D[u]和弧（vu,vj）上的权值之和。

(4)重复操作⑵、⑶共n-1次。由此求得从v到图上其余各顶点的最短路径158SABCDET25241431755702447891413594最短路线：S

A

B

E

D

T最短距离：Lmin=13159SABCDET10∞

∞∞∞∞∞22S*54∞∞∞34A*49∞∞44S*97∞597B*∞68B*14713D*160交通图上的选址问题

161选址问题使所选地址到最远的服务对象距离尽可能小——中心点使所选地址到各服务对象的总距离最小——中位点典例建立一个消防站负责某一地区的消防工作，使得该消防站尽快到达它所负责的地区的任意一地点，该消防站就应建在何处？162二、树型图上的选址问题例：设某物资有7个产地，分布在一个树型交通图上，各地产量分别标在产地编号旁边。现要求在此交通图上选择一地建立加工厂，加工各地运来的物资，问选取址在何处，可使总运费最省？16350132465720015015010012060164基本思想：

将树型图通过割断某一连线，分