管理运筹学基础

1管理运筹学第1章绪论什么是管理运筹学??什么是管理运筹学??排课问题?公交线路优化问题运输配送问题管网建设问题旅游线路设计问题投资组合问题机床布置问题设施选址问题生产流程优化问题集装箱码头调度问题古籍中的运筹问题田忌赛马(公元前三百多年)：田忌与齐王多次赛马，屡战屡败，田忌的谋士孙膑比较了六种对策后建议……

最早记载的《对策论》范例。古籍中的运筹问题祥符中,禁火。时丁晋公主营复宫室,患取土远,公乃令凿通衢取土,不日皆成巨堑。乃决汴水入堑中,引诸道竹木排筏及船运杂材,尽自堑中入至宫门。事毕,却以斥弃瓦砾灰壤实于堑中,复为街衢。一举而三役济,计省费以亿万计。

——沈括《梦溪笔谈.补笔谈卷二.权智》(公元九百多年)“运筹”的出典据《史记》记载：汉高祖刘邦称赞张良：夫运筹策帷帐之中，决胜於千里之外，吾不如子房。

——司马迁《史记·高祖本纪》“筹”是古代比算盘还早的计算工具之一。“运筹”是计划、安排、比较、决策优化的一个过程。运筹学简述运筹学（OperationsResearch） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。运筹学简述运筹学的历史“运作研究(OperationalResearch)小组”:解决复杂的战略和战术问题。例如：如何合理运用雷达有效地对付德军的空袭对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。管理运筹学的主要内容数学规划（线性规划、整数规划、目标规划、动态规划等）图论与网络分析存储论网络计划决策分析绪论

历史，代表人物

Erlang1917排队论Harris1920存储论Levinson1930零售贸易线性规划

整数规划动态规划搜索论博弈论（不动点定理）博弈论

非线性规划K－T条件图论随机过程我国当代数学家在《运筹学》中的贡献1957年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。20世纪70年代华罗庚先生在中国大力创导推广“统筹学”当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。凡是讲图论的优化的教科书，多半有专门的一章名：ChinesePostmanProblems,其中无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题(CPP)。TheNatureofManagementScience管理科学（Managementscience）是对与定量因素（quantitativefactors）有关的管理问题通过应用科学的方法（scientificapproach）进行辅助管理决策制定（aidmanagerialdecisionmaking）的一门学科（discipline）。管理者

制定决策管理科学

运用合理的分析来改善决策的制定也常称为OR/MS学科ImpactofManagementScience改善全世界大量组织的效率提高国家的经济生产力促进商业运作的规范性节约大量稀有的资源为管理科学实践者颁发的最负盛名的奖项是弗兰茨·厄德曼(FranzEdelman)奖。这些奖项授予全世界年度管理科学的最佳应用。Interface上发表的部分获奖项目组织应用效果联合航空公司在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排每年节约成本600万美元Citgo石油公司优化炼油程序及产品供应、配送和营销每年节约成本7000万AT&T优化商业用户的电话销售中心选址每年节约成本4.06亿美元，销售额大幅增加标准品牌公司控制成本库存（制定最优再定购点和定购量确保安全库存）每年节约成本380万美元法国国家铁路公司制定最优铁路时刻表并调整铁路日运营量每年节约成本1500万美元，年收入大幅增加。TacoBell优化员工安排，以最低成本服务客户每年节约成本1300万美元Delta航空公司优化配置上千个国内航线航班来实现利润最大化每年节约成本1亿美元杭州电子科技大学管理学院33管理运筹学杭州电子科技大学管理学院34第2章线性规划1.运筹学中应用最广泛的方法之一。2.运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。3.解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。2.1引言杭州电子科技大学管理学院352.2研究对象1.有一定的人力、财力、资源条件下，如何合理安排使用，效益最高。2.某项任务确定后，如何安排人、财、物，使之最省。杭州电子科技大学管理学院362.3线性规划的数学模型1.生产计划的编制问：企业应如何安排生产，能使总收益最大？（1）问题背景杭州电子科技大学管理学院37（2）数学模型决策目标：A、B、C产品各生产多少台使企业总收益最大？

决策变量：设

目标函数：

约束条件：非负条件：杭州电子科技大学管理学院382.合理下料问题

（1）问题背景

现要用长7.4米的圆钢截取长2.9米、2.1米和1.5

米的材料各100根，应如何下料，才能使用料最省？1、各种取料方式2.92.11.50.9杭州电子科技大学管理学院39（2）数学模型

决策目标：如何取料使所用原料最少决策变量：设第j种下料方式所用的原料根数为目标函数：约束条件：非负条件：2.4LP模型的基本特征及一般表达方式1.LP模型的基本特征（1）目标函数常用最大利润或最低成本来表示，反映在数学模型上都涉及极大或极小值问题。（2）有限资源可用线性等式或不等式。（3）问题的联系、各种已知量、未知量之间有着内在的联系，这些联系可用表达式给出。（4）多种方案，一个实际问题的解决往往有多个方案可供选择，而其中必有一个方案或几个方案能获得最佳经济利益。2.LP的一般表达方式（m个约束方程，n个决策变量）LP的矩阵表达方式2.3LP的标准形式（SLP）1.SLP的特征（1）极大化型（2）约束方程为等式（3）所有的决策变量为非负值（4）约束方程的右端项系数为非负值2.形式3.非标准型LP模型转化为标准型LP模型（1）目标函数是极小化的转化例：4.决策变量有上下界的转换2.4LP问题的解1.可行解满足LP模型的约束条件且满足非负条件的解。例：2.最优解

使目标函数达到最大的可行解（存在多个可行解，从中选择最优的解）3.基和基解（1）基：系数矩阵中任意m列所组成的mxm阶非奇异子矩阵。基矩阵为：（2）基解

令非基变量为零，求解由基变量组成的方程组所得到的解。

4.可行基和基可行解可行基：基所对应的解为非负。基可行解：满足非负条件的基解（可行基所对应的解）可行解基解基可行解结论：若LP问题存在最优解，则一定可以在

基可行解中找到。杭州电子科技大学管理学院54管理运筹学1.二个决策变量LP问题的图解法2.5LP问题的几何解释x1x2

50100150

15010050l1l2可行域OABCz=500z=1000z=1260(30,80)最优解结论：若LP问题存在唯一最优解，则必在

可行域的某个极点(角点)上找到。极点——基可行解前提：可行域是个凸集。凸集：设K是n维欧氏空间的一点集，若任意两点2.几种特殊情况

（1）LP存在多个解（2）LP问题无可行解（3）LP问题存在无界解判断：若LP的可行域无界，则该LP存在无界解。小结1、可行域为封闭的有界区域唯一最优解

多个最优解2、可行域为非封闭的无界区域唯一最优解多个最优解无界解3、可行域为空集无可行解

思考题2.6单纯形法一、单纯形原理*可行域的极点对应LP问题的基可行解*LP的最优解一定可以在基可行解中找到1.思路2.举例3.步骤：（1）化标准型（SLP）（2）找初始基可行解（3）判断（4）换基迭代*换基：找一个非基变量作为换入变量，同时确定一个基变量为换出变量。*依据原则：新的基可行解能使目标值增加；新的基仍然是可行基。1）确定换入变量：变量下标最小的（勃兰特法则）变量对应的价值系数最大的2)确定换出变量*迭代（求新的基可行解）主元素（5）判断→代入目标函数得（6）确定进基变量和出基变量（7）换基迭代（8）判断代入目标函数：最优解：2.表格形式的单纯形法（1）表的结构及含义（2）计算步骤1)化标准型，建立初始单纯形表;2)计算非基变量的检验系数，若所有检验系数都小于等于零，则已得到最优解。否则转一步;4)换基迭代，求出新的基可行解，转步骤二;

10500

00

34105201

98cj

5300

bcBxB

x1x2x3x4

05x3x1

c011/5de01

2a

δj

b-1fgZ=10求出a,b,c,d,e,f,g的值。1、z=10=0×2+5×a→a=2

2、c=0,d=1,b=0,f=0;3、g=0-(05)(1/51)’=-54、3-(05)(0e)’=-1→e=4/5小结：单纯形法的前提条件是SLP存在一个初始的单位基矩阵。3.人工变量法（1）思路——人为构造一个单位矩阵人工变量人工变量cj3-250-M-Mbθ

cBxbx1x2x3x4x5x6-M-Mx5x6123410221201737/43/2δj3+3M-2+4M5+4M6M↑00→x5x4

-M

0-3-2101-21111/2101/23/2

δj3-3M–2-2M5+M00-3M↑→13…

53

x3

x102/516/52/51/514/502/5-1/52/511/52/5

δj0-32/50-36/5–7/5-M–11/5-M*若基变量中有非零的人工变量，则该LP无可行解。4.单纯形法的进一步讨论（1）无界解Oz→∞cj2300bθcBxBx1x2x3x400x3x41-110-310124→

δj2↑30020x1x41-1100-231210δj05↑-20结论：若δj﹥0,对应的系数列向量≤0，则该LP存在无界解。（2）多个解cj41400bθcBxBx1x2x3x300x3x42710720121213δj41400140x2x42/711/7045/70-2/71315δj00-20z=42↑21/27/3→144x2x1017/45-2/4510–2/457/457/37/3δj00-20z=42↑21/2→结论：若某个非基变量的检验系数为零，则该

LP存在多个最优解。（3）退化解cj201.5000bθcBxBx1x2x3x4x5x6000x4x5x61-10100201010111001243223δj2↑01.5000→200x1x5x6-10100021-210021-101201δj021.5-200*在单纯形法的计算过程中，确定出基变量时存在两个或两个以上的最小比值，这时会出现退化解。*有时，退化会造成计算过程的循环，永远达不到最优解。*用勃兰特法则一定可以避免出现循环（4）无可行解cj2030000-MbθcBxBx1x2x3x4x5x6

00-Mx3x4x631010001001001100-111503040δj20+M30+M00-M0…3020-Mx2x1x6011/10-3/10000010000-1/10-7/10-116304δj00–3-M/10-11-7M/10–M0xBx1x2x3x4x5bx2x3x5110-40-201-30300a153dδj-300δ0

讨论题在求解极大化LP问题中，得到如下单纯形表：（无人工变量）1、当前解为最优解时，各参数应满足的条件；2、原问题存在无界解时，各参数应满足的条件；3、原问题存在多个解时，各参数应满足的条件；4、当x4

作为进基变量取代x5时，目标值的增量为多少？结论：若基变量中有非零的人工变量，则该LP无可行解。杭州电子科技大学管理学院95管理运筹学2.7对偶理论1.对偶问题的提出例：产品原材料工时定额单位产品收益A2210B31.512现有资源300180问1：如何生产使总收益最大？问2：若企业把资源出租(卖)，应如何确定合理的价格？出租可获得的收益不得低于自行生产的收益在满足上述要求的前提下，所定的价格对方愿意接受目标函数：约束条件：非负条件：产品原材料工时定额单位产品收益A2210B31.512现有资源300180LPDLP2、价值系数资源系数3、资源系数价值系数4、约束方程<=约束方程>=5、目标函数max目标函数min2.LP与DLP的对偶关系（1）对偶问题的标准形式（2）非标准形式的对偶关系见表2.19

minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315≥=≤≥x1≥0,x2≤0,x3无非负要求例：对偶线性规划minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示4.对偶单纯形法（1）思路单纯形法：迭代过程始终保持B的可行性（最小θ规则），逐步满足最优性。对偶单纯形法：迭代过程始终保持最优性（对偶可行性），再逐步满足可行性。（2）计算步骤→3、换基迭代1.化标准型,建立初始单纯形表4、回到第2步(若所有aij≥0,则该LP无可行解）cj-1-2-3000bcBxBx1x2x3x4x5x6000x4x5x6-11-11001120100-11001-48-2

δj-1-2-3000

θj

→13↑x1x5x6-1001-11-100402111040-11001-2→δj0-3-2-100θj3↑cj-1-2-3000bcBxBx1x2x3x4x5x6-100x1x5x61-11-1000211100-1100144-2

δj0-3-2-100

θj

3

x1x5x2-10-2100-10-16003112001-100-12→δj00-5-10-3

↑练习cj-3-5-400bcBxBx1x2x3x4x500x4x5-3-1-210-2-3-101-60-b2δj-3-5-400θj→

152↑-30x1x511/32/3-1/300-7/31/3-2/31

2040-b2δj0-4-2-10→↑-30x1x413/21/20-1/207/2-1/21-3/2b2/2δj0-1/2-5/20-3/2*对偶单纯形法的适用前提能解决形如以下的LP问题：2.6灵敏度分析（优化后分析）1.参数的可变性(cj,bi,aij)2.灵敏度分析的内容（1）参数的变化对原最优解有什么影响？原最优解是否仍为最优解。（2）参数在什么范围变化时，原最优解保持不变？（3）当原最优解已不再最优时，应如何利用原单纯形表，以最简捷的方法求得新的最优解。3.最优性分析4.目标函数cj的变化（1）非基变量cj的变化cj

23100bcBxB

x1x2x3x4x5

23x1x2

10-14/3-1/3012-1/31/3

12δj00-3-5/3-1/3Z=8欲使原问题的最优性保持不变，若要保持最优性不变一般情况：（2）基变量cj的变化cj

23100bcBxB

x1x2x3x4x5

23x1x2

10-14/3-1/3012-1/31/3

12δj00-3-5/3-1/3Z=8

1）讨论c2的变化范围2）一般情况对于所有的非基变量都应满足上述不等式,有(n-m)个,则cj

23100bcBxB

x1x2x3x4x5

23x1x2

10-14/3-1/3012-1/31/3

12δj00-3-5/3-1/3Z=8

问：c2由3变为1时，应如何修改原最优计划？cj

21100bcBxB

x1x2x3x4x5

21x1x2

10-14/3-1/3012-1/31/3

12δj001-7/31/3Z=4↑→cj

21100bcBxB

x1x2x3x4x5

20x1x5

11110036-11

36δj0-1-1-20Z=65.资源系数bi的变化cj

23100bcBxB

x1x2x3x4x5

00x3x41111014701

39δj23100Z=0

23x1x2

10-14/3-1/3012-1/31/3

12δj00-3-5/3-1/3Z=8（2）分别讨论b1由3变为9，b2由9变为15时对原最优解的影响对原问题的可行性无影响（3）一般情况（4）举例

1）确定b1

、b2的变化范围2）b2由9变为15时，应如何修改原最优计划？cj

23100bcBxB

x1x2x3x4x5

23x1x2

10-14/3-1/3012-1/31/3-14δj00-3-5/3-1/3

θj→31↑

03x5x2303-4111110

33δj-10-2-30Z=9cjee-1016-100bcBxBx1x2x3x4x5-1016x1x210-1-1201-1-1162δj00564Z=-282、非基变量cj的变化：3、基变量cj的变化：若最优基发生变化，用单纯形法修改。4、资源系数bi的变化：若最优基发生变化，用对偶单纯形法修改。1、分析思路{小结第三章

运输问题

运输问题是一类特殊的线性规划问题，本章主要从运输问题数学模型、运输问题表上作业法以及运输问题软件求解（Excel/Lingo)三方面内容展开。

3.1运输问题数学模型

运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性。典型背景——单一物资运输调度问题设某种物品有:

m个产地：产量：

n个销地：销量：从产地到销地的单位运价是,

求总运费最小的调度方案。运输问题3.1.1产销平衡运输问题数学模型决策变量表示由到的物品数量。销地产地销量产量运输表运输问题由运出去的物资总量应该等于的产量，即：同样，运到销地的物资总量应该等于的销量，即：产销平衡问题——总产量=总销量，即：

运输问题运输问题此时运输问题的数学模型为：运输问题

在实际问题中，更多的时候往往是产销不平衡的。此时需要把产销不平衡问题转化为产销平衡的问题。(1)产大于销当总产量大于总销量，即时，运输问题的数学模型可写成：3.1.2产销不平衡运输问题数学模型

由于总产量大于总销量，就要考虑多余的物资在哪个产地就地贮存的问题。这个多余物资的贮存地可以看成是一个假想的销地，令这个假想销地的销量为：由于这个模型中，所以这是一个产销平衡的运输问题。将其分别代入，得到：（2）销大于产当总销量大于总产量，即时，运输问题的数学模型可写成：

类似地，当总销量大于总产量时，可以在产销平衡表中增加一个假想的产地，该假想产地产量为因为这个假想的产地事实上并不存在，求出的由它发往各销地的运量，实际上是各销地的物品欠缺额。显然，其相应的单位运价应等于0，即

同样可以转化为一个产销平衡的运输问题，此时，总销量大于总产量的运输问题模型可以表示为：运输问题

运输问题是线性规划问题，但它具有一些特殊的性质。这些性质是运输问题特殊解法的基础。下面给出几个主要性质：

性质1:

运输问题模型的系数矩阵每列只有第行和第行两个元素为1，其余均为0。性质2:

系数矩阵A的秩为，因此运输问题的基变量一定是个。性质3:

产销平衡运输问题一定存在最优解。

性质4:

若各产地的产量和各销地的销量都为整数，则有可行解的运输问题必有整数最优解。3.1.3运输问题的基本性质m行n行运输问题3.1运输问题数学模型结束结束运输问题3.2运输问题的表上作业法由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。表上作业法是单纯形法在求解运输问题的一种简便方法。单纯形法与表上作业法的关系：（1）找出初始基可行解（2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否运输问题——表上作业法例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地3.2.1产销平衡运输问题表上作业法第一步：确定初始基可行解

——最小元素法、伏格尔法方法1：最小元素法最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。

最小元素法举例：4122854396111110销量产量销地产地822010100614868000060最小元素法举例：4122854396111110销量产量销地产地82101468最小元素法缺点：会出现顾此失彼（运费差额问题）考虑运价差

罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。方法2：沃格尔法沃格尔法思路：结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①04-4=0第一次：结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①013-2=1第一次：结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①011第一次：结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①011列罚数4-2=22153①第一次：结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①011列罚数2153①1480优先安排销地，否则运价会更高下次不考虑该列第一次：第二次：结合例1说明这种方法。行罚数②011列罚数213②优先安排销地，否则运价会更高84122854396111110销量产量销地产地148006下次不考虑该行结合例1说明这种方法。行罚数③01列罚数212③84122854396111110销量产量销地产地148006下次不考虑该列802第三次：结合例1说明这种方法。行罚数④76列罚数12④84122854396111110销量产量销地产地1480068024120下次不考虑该列第四次:结合例1说明这种方法。行罚数⑤00列罚数2⑤4284122854396111110销量产量销地产地1480068024120000第五次：例1用沃格尔法得到的初始基可行解4122854396111110销量产量销地产地48148122目标函数值用最小元素法求出的目标函数z=246一般说来，沃格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。第二步：解的最优性检验（闭回路

法、位势法）方法1：闭回路法思路：计算空格（非基变量）的检验数

若令则如何求检验数？分析：——运费的增量即增加1个单位的检验数=相应的运费增量4122854396111110销量产量销地产地82101468从初始表分析：要保证产销平衡，则称为闭回路+1-1+1-1闭回路:从调运方案的某一空格出发，沿水平或垂直的方向前进，遇到一个适当的数字格便按与前进方向垂直的路径前进。经过若干次后，再回到原来出发的那个格，由此形成的封闭折线称为闭回路。当然，闭回路的形状不一定是简单的矩形，可以出现不同的形状：4122854396111110销量产量销地产地8210146821检验数表4122854396111110销量产量销地产地82101468211-11012表中的解不是最优解。方法2：位势法第三步：解的调整

调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。4122854396111110销量产量销地产地82101468-1（-2）（-2）（+2）（+2）调整后的解为：4122854396111110销量产量销地产地821214482209112此时的解为最优解。有无穷多最优解几点说明：当检验数为负的变量超过两个，选择最小者对应的变量换入；在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。在实际问题中，往往会碰到产销不平衡问题。当我们将产销不平衡运输问题转化为产销平衡运输问题时，就同样可以利用表上作业法求解该运输问题，方法步骤同上。3.2.2产销不平衡运输问题表上作业法3.2

运输问题的表上作业法结束结束运输问题——表上作业法3.3运输问题软件求解

运输问题是一类特殊的线性规划问题，用表上作业法手工计算比较繁杂，可以通过一些适当的软解来帮助求解，本节主要介绍利用Excel和Lingo如何求解运输问题。1、产销平衡运输问题Excel求解

用Excel对运输问题进行建模类似于线性规划问题建模。结合产销平衡运输问题例3.1，用Excel对其建模如下：

3.3.1运输问题Excel求解其中：

约束条件格F12、F13、F14的命令分别为：“=sum(B12:E12)”“=sum(B13:E13)”“=sum(B14:E14)”；

约束条件格B15、C15、D15、E15的命令分别为：“=sum(B12:B14)”“=sum(C12:C14)”“=sum(D12:D14)”“=sum(E12:E14)”；目标函数格C17的命令为：

“=sumproduct(B5:E7,B12:E14)”图3.3

给定可变单元格与约束条件后，点击“选项”进行设置：决策问题图3.3

求得该运输问题的最优解为：

2、产销不平衡运输问题Excel求解利用Excel求解运输问题没有利用表上作业法，而是直接采用单纯形法进行求解；利用Excel求解产销不平衡运输问题，我们可以不转化为产销平衡运输问题直接求解。结合例3.2，不转化成产销平衡运输问题，则产地仍然保持三个，只需在约束中将销量约束条件由产销平衡时的$C$5:$E$5=$C$8:$E$8转化为$C$5:$E$5≦$C$8:$E$8。其中：约束条件格F12、F13、F14的命令分别：“=sum(C12:E12)”“=sum(C13:E13)”“=sum(C14:E14)”；约束条件格C15、D15、E15的命令分别为：“=sum(C12:C14)”“=sum(D12:D14)”“=sum(E12:E14)”；目标函数格D17的命令为：“=sumproduct(C5:E7,C12:E14)”给定可变单元格与约束条件后，点击“选项”进行设置：该产销不平衡运输问题求解结果如下：3.3.2运输问题Lingo求解1、产销平衡运输问题Lingo求解对例3.1利用Lingo进行求解，具体程序如下：Lingo程序如下：MODEL:sets:Production/1,2,3/:a;Sales/1,2,3,4/:b;link(Production,Sales):c,x;Endsetsdata:a=8,5,11;b=4,7,6,7;c=4124112103985116;enddata[OBJ]min=@sum(link:c*x);@for(Production(i):@sum(Sales(j):x(i,j))=a(i));@for(Sales(j):@sum(Production(i):x(i,j))=b(j));@for(link(i,j):x(i,j)>=0);end运行Lingo,求解结果为：

Objectivevalue:122.0000X(1,1)0.0000000.000000X(1,2)0.0000002.000000X(1,3)6.0000000.000000X(1,4)2.0000000.000000X(2,1)4.0000000.000000X(2,2)0.0000002.000000X(2,3)0.0000001.000000X(2,4)1.0000000.000000X(3,1)0.0000009.000000X(3,2)7.0000000.000000X(3,3)0.00000012.00000X(3,4)4.0000000.000000特别需要注意的是：在Lingo中，默认的变量均为非负2、产销不平衡运输问题Lingo求解对例3.2利用Lingo进行求解，具体程序如下：Lingo程序如下：MODEL:sets:Production/1,2,3/:a;Sales/1,2,3/:b;link(Production,Sales):c,x;endsetsdata:a=15,25,20;b=20,30,20;c=301002040110808011040;enddata[OBJ]min=@sum(link:c*x);@for(Production(i):@sum(Sales(j):x(i,j))=a(i));@for(Sales(j):@sum(Production(i):x(i,j))<=b(j));@for(link(i,j):x(i,j)>=0);end运行Lingo，求解结果为：Globaloptimalsolutionfound.Objectivevalue:3500.000X(1,1)0.00000010.00000X(1,2)0.00000010.00000X(1,3)15.000000.000000X(2,1)20.000000.000000X(2,2)5.0000000.000000X(2,3)0.00000040.00000X(3,1)0.00000040.00000X(3,2)15.000000.000000X(3,3)5.0000000.0000003.3运输问题软解求解结束结束3.4案例分析3.4.1问题的提出P&T公司是美国一家由家族经营的小公司，它收购生菜并在食品罐头厂中把它们加工成罐头，然后再把这些罐头食品分销到各地卖出去。其中它生产的豌豆罐头分别在贝林翰、尤基尼和艾贝尔.李这三个食品厂进行加工，然后用卡车把这三个工厂生产的豌豆罐头运送到美国西部名为萨克拉门托、盐湖城、赖皮特城、澳尔巴古这四个分销仓库，其地理位置分布如下页图所示：决策问题

贝林翰工厂赖皮特城仓库艾贝尔.李工厂盐湖城仓库萨克拉门托仓库澳尔巴古仓库尤基尼工厂该公司尽管在这几年有所发展，然而利润并没有明显的增长，这引起股东们的不满。公司CEO道格拉斯先生认为是公司的成本控制没有做好，因此下一步的工作重点是努力控制成本。他在浏览公司财务报表时发现，上个季度公司运输成本是178000美元，他记得几年前该数字是100000美元。他找来公司配送经理理查德了解详细情况。理查德汇报说主要原因是货车司机的雇佣费用提高了，而要降低货车司机的工资成本来降低运输成本是很困难的。道格拉斯考虑是否可以采用运筹学的方法，在运输调运方案上作一些调整，以此达到降低目前运输成本的目的。3.4.2问题分析

理查德接受道格拉斯的建议后立即着手工作，请来几个专家对公司目前的配送情况进行诊断。专家们发现，许多年来，公司一直采用如下的配送策略：

（1）因为贝林翰的罐头厂距离仓库最远，所以把它生产的产品运送到离它最近的萨克拉门托仓库，若还有剩余，则运到盐湖城仓库。（2）因为澳尔巴古仓库距离三个工厂都相对较远，故它的需求由离它最近的工厂艾贝尔.李供给，若还有剩余，则运送到赖皮特城仓库中。（3）而其他仓库的需求，则由尤基尼工厂运送满足。其次，专家们查阅公司以往的供需数据发现，三个工厂的生产量分别为：贝林翰75卡车，尤基尼125卡车，艾贝尔.李100卡车，四个仓库获得的配送量分别为：萨克拉门托80卡车，盐湖城65卡车，赖皮特城70卡车，澳尔巴古85卡车。各工厂运送豌豆罐头到各仓库的单位卡车运输成本如下表所示：仓库加工厂萨克拉门托盐湖城赖皮特城澳尔巴古贝林翰464513654867尤基尼352416690791艾贝尔.李995682388685

（单位：美元/卡车）3.4.3问题求解

（1）建立该运输问题模型：根据该公司目前的现状分析和数据收集，三个工厂相当于三个产地，四个仓库可看成四个销地。由于三个工厂的总产量为75+125+100=300，四个仓库的总运送量为80+65+70+85=300，两者恰好相等，故这是一个典型的产销平衡运输问题。建立该运输问题的数学模型为：仓库加工厂萨克拉门托盐湖城赖皮特城澳尔巴古贝林翰75000尤基尼565550艾贝尔.李001585（单位：卡车）根据节点间的的单位运价和具体运量，计算P&T公司目前配送方案所承担的运输成本为：

75*464+5*352+65*416+55*690+15*388+85*685=165595（美元）

（2）求解公司目前配送方案的运输成本结合目前公司的配送方案，其具体的配送数据可如下表所示：（3）利用Lingo对该运输问题进行优化求解MODEL:sets:Production/1,2,3/:a;Warehouse/1,2,3,4/:b;link(Production,Warehouse):c,x;endsetsdata:a=75,125,100;b=80,65,70,85;c=464513654867352416690791995682388685;enddata[OBJ]min=@sum(link:c*x);@for(Production(i):@sum(Warehouse(j):x(i,j))=a(i));@for(Warehouse(j):@sum(Production(i):x(i,j))<=b(j));@for(link(i,j):x(i,j)>=0);end求解结果为：

Globaloptimalsolutionfound.Objectivevalue：152535.0X(1,1)0.00000015.00000X(1,2)20.000000.000000X(1,3)0.00000084.00000X(1,4)55.000000.000000X(2,1)80.000000.000000X(2,2)45.000000.000000X(2,3)0.000000217.0000X(2,4)0.00000021.00000X(3,1)0.000000728.0000X(3,2)0.000000351.0000X(3,3)70.000000.000000X(3,4)30.000000.000000新的配送方案为：从贝林翰工厂运送20卡车到盐湖城，运送55卡车到澳尔巴古；从尤基尼运送80卡车到萨克拉门托，运送45到盐湖城；从艾尔贝.李运送70卡车到赖皮特城，运送30卡车到澳尔巴古，该配送方案的总运输费用为152535美元。可见，P&G公司若采用优化后的配送方案，将节约成本13060美元。3.4案例分析结束结束杭州电子科技大学管理学院195管理运筹学第4章整数规划杭州电子科技大学管理学院1964.1.1整数规划数学模型的一般形式

4.1整数规划的数学模型整数规划中如果所有变量都限制为整数，则称为纯整数规划（pureintegerprogramming）；如果仅一部分变量限制为整数，称为混合整数规划（mixedintegerprogramming）整数规划的一种特殊情况是0-1规划，它的变量取值仅限于取值为0或1。杭州电子科技大学管理学院197例4.1设整数规划问题如下

首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x233(3/2,10/3)

现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)、(2，3)、(1，4)、(2，4)。显然，它们都不可能是整数规划的最优解。

按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。

因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。

目前，常用的求解整数规划的方法有：

分支定界法和割平面法；对于特别的0-1规划问题采用隐枚举法和匈牙利法。杭州电子科技大学管理学院2014.1.2含0-1变量的整数规划0-1整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，也叫二进制变量。一、典型应用例4.2

背包问题一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/kg55261224重要性系数201518148410杭州电子科技大学管理学院202例4.3

集合覆盖和布点问题某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内赶到现场。据实地测定，各区之间消防车行驶的时间（单位：min）见表，请制定一个布点最少的计划。行驶时间地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140杭州电子科技大学管理学院203二、特殊约束的处理1.矛盾约束建模时，有时会遇到相互矛盾的约束，而模型只能两者取一，例如2.多选一约束多个约束里选择一个杭州电子科技大学管理学院2043.固定费用问题含有固定费用（固定成本）的问题一般不能用线性规划来描述，但可改变为混合整数规划来解决1、算法依据:对于目标函数值来讲,整数规划的最优解不会更优于相应线性规划问题的最优解.4.2整数规划模型求解方法

4.2.1分支定界法整数规划与其松弛问题:当放弃整数约束时得到的线性规划称为整数规划的松弛问题。整数规划的可行域是松弛问题的可行域，反之不成立。解：先不考虑x1,x2为整数的条件，得最优解:x1＝3/2，x2=10/3，z0=29/6。它不符合整数条件，Z0作为Z*的上界。显然，(0,0)是问题A的一个整数可行解。0≤z*≤29/6S例4.4132x254x1123132x254x1123S2S1对S分枝：先注意其中一个非负整数变量的解。如：x1构造约束：和形成分枝问题S1和S2，分别得最优解Z1和Z2这时没有得到全部变量都是整数的解。因Z1>Z2，故先考察S1这一枝。且41/9<29/