第1章 绪论1
1.1 运筹学的起源与影响1
1.2 运筹学的分支3
1.3 运筹学的工作程序4
1.4 运筹学的应用软件介绍6第2章 线性规划模型13
2.1 典型问题举例13
2.2 线性规划模型的一般形式18
2.3 线性规划的假设22
2.4 一些应用案例建模26
习题41第3章 线性规划的解法46
3.1 线性规划的图解法46
3.2 单纯形法原理59
3.3 表格形式的单纯形法65
3.4 单纯形法的进一步讨论70
3.5 改进单纯形法80
3.6 线性规划问题的Excel求解83
习题97第4章 对偶理论与灵敏度分析1044.1 对偶问题的提出1044.2 线性规划的对偶理论1124.3 对偶解的经济解释和影子价格1164.4 对偶单纯形法1234.5 灵敏度分析1324.6 参数线性规划1524.7 用Excel作灵敏度分析160习题163第5章 运输问题及其解法1705.1 运输问题的一般模型1715.2 表上作业法1725.3 表上作业法计算中的相关问题1835.4 产销不平衡的运输问题及其解法1855.5 转运问题及其解法1895.6 运输问题的Excel求解192习题195第6章 目标规划2026.1 目标规划问题的数学模型2026.2 解目标规划问题的图解法2056.3 解目标规划问题的单纯形法2066.4 目标规划问题的Excel求解208
...
直属事业部
扫描关注官方微博
扫描关注官方微信
版权所有(C)2014 清华大学出版社有限公司 京ICP备号 京公网安备48号运筹学　精品课程
|||||课程录像||||教学研究|||效果评价|&&&
运筹教学大纲
　一、教学的目的和要求
《运筹学》是管理类专业必修的专业基础课，是一门为决策机构决策时提供以数量化科学方法为基础的学科，是应用数学的一个分支。其教学目的，是让学生掌握运筹学的思维方式，能应用系统的、科学的数学分析方法对系统进行定量化分析。通过建立数学模型和模拟模型，应用计算机技术求解数学模型来解决现实生活中比较复杂的问题，达到资源优化配置、获得最优决策的目的。
通过本课程的学习，要求学生掌握线性规划、线性规划的对偶理论、运输问题、目标规划、整数规划、动态规划、图与网络分析、网络计划技术的基本概念、基本理论和基本方法，熟悉运筹学模型在实践中的应用，能够熟练运用运筹学软件进行复杂问题的求解。
　二、本课程与其他课程的相互关系
在开设本课程之前，学生应当首先掌握《高等数学》和《线性代数》等课程的内容。本课程中决策论的内容在《预测与决策》中讲授。
教学内容与学时分配
&绪论（２课时）
１．基本要求：了解运筹学的性质及特点、运筹学的发展历史、运筹学方法的应用、学习运筹学的意义。
２．重点：运筹学的性质特点和应用
线性规划及单纯形法(15课时）
基本要求：
&&& （1）了解线性规划模型的特点、线性规划问题的标准型；
&&& （2）掌握求解线性规划问题的图解法；
&&& （3）掌握线性规划问题解的概念、有关解的基本定理；
&&& （4）熟练掌握单纯形法的的原理和求解方法，包括：初始基可行解的确定、最优性判别定理、基变&&&&&&&& 换，单纯形法的计算步骤；
&&& （5）熟练掌握求解线性规划问题的人工变量法；
&&& （6）了解退化、循环，掌握Bland规则；
&&& （7）熟练掌握实践中常见问题的建模方法。
重点：本章全部是重点；难点：单纯形法原理的理解
说明：应用部分可以考虑安排自学。
第三章　对偶理论与灵敏度分析（10课时）
基本要求：
&&& （1）了解单纯形法的矩阵描述；
&&& （2）了解改进的单纯形法；
&&& （3）了解对偶问题的提出，掌握写出对偶问题的规则，掌握对偶问题的基本性质；
&&& （4）了解影子价格的含义；
&&& （5）熟练掌握对偶单纯形法、灵敏度分析的方法。
重点、难点：对偶问题的基本性质、对偶单纯形法、灵敏度分析方法。
第四章　运输问题（８课时）
1．基本要求：
&&& （1）了解运输问题及其数学模型的特点；
&&& （2）熟练掌握表上作业法，包括初始调运方案的确定、检验数的计算方法、迭代方法；
&&& （3）熟练掌握对退化的处理方法；
&&& （4）熟练掌握产销不平衡问题的处理方法；
&&& （5）掌握运输问题在实践中的典型应用。
2．重点：本章所有内容均为重点；难点：表上作业法的思想。
．说明：应用部分可以考虑安排自学。
&目标规划(3课时)
基本要求：
&&& （1）了解目标规划问题的提出，掌握目标规划数学模型的建立方法和特点；
&&& （2）熟练掌握求解目标规划问题的图解法；
&&& （3）熟练掌握求解目标规划问题的单纯形法；
&&& （4）了解目标规划的灵敏度分析方法；
&&& （5）了解目标规划在实践中的应用。
重点：目标规划数学模型的建立方法、求解目标规划问题的图解法、单纯形法。
说明：本章可以考虑安排自学
整数规划（8课时）
基本要求:熟练掌握分枝定界法、割平面法、求解0－1规划的隐枚举法、求解指派问题的匈牙利法。了解用匈牙利法和分枝定界法求解货郎担问题的思想。
重点：分枝定界法、割平面法、匈牙利法，难点：割平面法、匈牙利法。
第七章& 动态规划(4课时)
&&& （1）掌握动态规划的基本概念；
&&& （2）熟练掌握最短路问题的动态规划求解方法；
&&& （3）掌握动态规划的基本思想和基本方程；
&&& （4）理解动态规划的最优性定理和最优化原理；
重点：动态规划的基本概念、基本方程；难点：动态规划的最优化原理和最优性定理
第八章& 动态规划的应用举例(８课时)
主要内容：熟练掌握下列问题的动态规划求解方法：机器负荷分配问题、某些非线性规划问题、一维资源分配问题、生产计划问题、背包问题、TSP问题。
重点、难点：
生产计划问题、问题。
第九章& 图与网络分析(10课时)
基本要求：
&&& （1）了解图、树的基本概念，掌握相关的基本定理；
&&& （2）熟练掌握求解最短路问题的Dijkstra算法、DP算法；
&&& （3）熟练掌握最大流问题的求解方法；
&&& （4）熟练掌握最小费用最大流问题的求解方法；
&&& （5）熟练掌握中国邮路问题的求解方法。
重点：各类问题的求解方法，难点：各类求解方法的原理、求解方法的应用。
<img border="0" src="img/BJ-green.jpg" width="11" height="11"
第十章 网络规划 (8课时)
1．基本要求：
&&& （1）了解网络计划问题的发展和应用；
&&& （2）熟练掌握CPM，包括网络图的绘制、网络时间参数的图上计算法和表格计算法、四种时差的概&&&&&&&& 念；
&&& （3）熟练掌握网络计划的时间优化方法；
&&& （4）熟练掌握网络计划时间－资源优化方法，包括ACTIM、TIMRES等；
&&& （5）熟练掌握网络计划工期－费用优化方法，包括LP方法。
&&& （6）掌握PERT的思想和有关计算方法；
&&& （7）了解GERT的方法；
&&& （8）掌握一种商业软件（Project2000，等）的使用。
．重点：、网络计划的优化方法，难点：时差的概念、网络计划在实践中的应用
考试（２课时）））
&&&&&&&&&&&&&
本课程是一门专业基础课，主要以课堂讲授为主，辅以WinQSB、LINGO等软件的自学和辅导
1、钱颂迪主编《运筹学（修订版）》，（北京）：清华大学出版社，1990.1
2、沈荣芳主编《运筹学》（北京）：机械工业出版社，1997.5
3、吴祈宗主编:《运筹学》，机械工业出版社，2003.1
4、胡运权主编《运筹学习题集(第三版)》（北京）：清华大学出版社，2002.9
5、Vaserstein,
L.N.等《Introduction
to Linear Programming》,机械工业出版社,
6、[美]弗雷德里克·S·希利尔等《数据、模型与决策》中国财政经济出版社，2001.9
建议使用：分辨率　IE5.0以上版本浏览器浏览器
西安电子科技大学经济管理学院　 版权所有& 网页设计:
Copyright &
All rights reserved. 　出自 MBA智库百科()
运筹学(operations research)，又称作业研究
　　运筹学是近代应用数学的一个分支，主要是研究如何将、等事件中出现的运筹问题加以提炼，然后利用进行解决的学科。运筹学是和的跨领域研究，利用像是、和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。运筹学经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的。
　　运筹学的思想在古代就已经产生了。但是作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是在二十世纪四十年代才开始兴起的一门分支。
　　运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容已经深入到日常生活当中去了。
　　随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是包括好几个分支的数学部门了。
　　运筹学在英国称为operational research，在美国称为operations research，英文缩写是OR。中国科学工作者取“运筹”一词作为OR的意译，包含运用筹划、以策略取胜等意义。
　　Operational research（运筹学）一词最早出现于1938年。当时英国波德塞雷达站负责人A.P.罗提出对整个防空作战系统的运行研究，以解决雷达站合理配置和整个空军作战系统协调配合来有效地防御德机入侵的问题。1940年9月英国成立了由物理学家P.M.S.布莱克特领导的第一个运筹学小组。后来发展到每一个英军指挥部都成立运筹学小组。1942年美国和加拿大都相继建立了运筹学小组。这些运筹学小组在确定护航舰队的规模、开展反潜艇战的侦察、有效的对敌轰炸等方面作了大量研究，为运筹学有关分支的建立作出了贡献。
　　第二次世界大战后，在这些军事运筹学小组中工作过的科学家转向研究在民用部门应用的可能性,从而促进了在民用部门应用运筹学的发展。1947年G.B.丹齐克在研究美国空军问题时提出及其通用解法──。50年代初用电子计算机求解线性规划问题获得成功。1951年P.M.莫尔斯和G.E.金布尔合著《运筹学方法》一书正式出版，标志着运筹学这一学科已基本形成。到50年代末，美国大企业在中大量应用运筹学。开始时主要用于制订，后来在、、、等方面应用和发展了许多新的方法和模型。60年代中期，运筹学开始用于服务性行业和公用事业。一些发达国家的企业、政府、军事等部门都拥有相当规模的运筹学研究机构，专门从事有关方法和建模的研究，为决策提供科学的依据。英国在1948年成立了运筹学俱乐部，1954年改名为英国运筹学会，出版《运筹学季刊》。美国在1952年成立了美国运筹学会，出版《运筹学》杂志。1957年在召开第一届国际运筹学会议，以后每隔3年举行一次。1959年成立()。
　　中国在1956年曾用过“运用学”的名字，于1957年正式定名为“运筹学”，于1980年成立中国运筹学会（ORSC），并于1982年加入国际运筹学联合会（IFORS）。
　　运筹学研究的内容十分广泛，其主要分支有：、、、、、、、、、、、、等。
　　应用运筹学处理问题时分为5个阶段。
　　①规定目标和明确问题：包括把整个问题分解成若干子问题，确定问题的尺度、有效性度量、可控变量和不可控变量，以及用来表示变量界限和变量间关系的常数和参数。
　　②收集数据和建立模型：包括定义关系、经验关系和规范关系。
　　③求解模型和优化方案：包括确定求解模型的数学方法,程序设计和调试,仿真运行和方案选优。
　　④检验模型和评价解答：包括检验模型的一致性、灵敏度、似然性和，并用试验数据来评价模型的解。一致性是指主要参数变动时（尤其是变到极值时）模型得出的结果是否合理；灵敏度是指输入发生微小变化时输出变化的相对大小是否合适；似然性是指对于真实数据的案例，模型是否适应；工作能力则是指模型是否容易解出，即在规定时间内算出所需的结果。
　　⑤方案实施和不断优化：包括应用所得的解解决实际问题，并在方案实施过程中发现新的问题和不断进行优化。上述5个阶段往往需要交叉进行，不断反复。
　　现代运筹学方法强调、和。它重视系统的输入输出关系，即问题所处的环境条件和问题中主要因素与环境间的关系，而不追求系统内部机理，因而易于达到从系统整体出发来研究问题的目的。常用的数学模型有：、、、、、、、、等。模型求解往往成为应用计算机程序进行仿真运行。现在已有各种运筹学软件包供应，使运筹学可以处理相当复杂的大型问题。随着运筹学应用于社会大系统，仅靠已难以找到合理的优化方案，人们常采用定量与定性相结合、在的基础上进行的方法。因此，在许多情况下已很难划分运筹学、系统分析与政策分析的界限。
　　运筹学正朝着3个领域发展：运筹学应用、运筹科学和运筹数学。
　　现代运筹学面临的新对象是经济、、社会、生态和政治等因素交叉在一起的复杂系统，因此必须注意大系统、注意与系统分析相结合，与未来学相结合，引入一些非数学的方法和理论，采用软系统的思考方法。总之，运筹学还在不断发展中，新的思想、观点和方法不断出现。
　　运筹学作为一门新兴科学，其应用范围是十分广泛的。对于不同类型问题，运筹学都有着不同的解决方法，因而形成了许多分支学科。它们虽然各有特性，但在运用系统观念分析问题，并对问题建立模型求解这两点上都是共同的。这些分支学科包括线性规划、非线性规划、动态规划、决策分析等等，在此主要介绍线性规划和动态规划在经济管理中的一些应用。
　　1.线性规划。
　　线性规划是目前在经济管理中应用最广泛的一种优化法，它的理论已经十分成熟，可以应用于生产计划、物资调用、资源优化配置等问题。它主要研究的是中经常遇到的两类问题：一类是在有限的劳动力、设备、等下，研究如何合理安排，取得最大的（如生产经营利润）；另一类是为了达到一定的目标（生产指标或其它指标），研究如何组织生产，或合理安排工艺流程，或调整产品的成份等等，以使消耗资料（人力、设备台数、资金原材料等）为最少去实现目标。这类统筹规划的问题用数学语言表达（即数学模型），先根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式表示(称为目标函数)，对问题的限制条件用有关变量的等式或不等式表达(称为约束条件)。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的数学模型。下面举例说明线性规划在经济管理中的应用。
　　【例1】生产计划问题(资源配置)。某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量及所占设备时间见表1。该厂每周所能得到的维生素量为160kg、每周设备最多能开15个台班。且根据，甲种产品每周产量不应超过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。问该厂应如何安排两种产品的产量才能使每周获得的利润最大？
每吨产品的消耗每周资源总量
维生素/kg3020160
设备/台班5115
　　解：设该厂每周安排生产甲种药品的产量为x1(t)，乙种产量为x2(t)，则每周所能获得的为Z = 5x1 + 2x2数学模型为 maxZ = 5x1 + 2x2（目标函数）
　　用图解法或单纯型方法解略，本题的最优解X *
= (2,5),最优值即该厂每周安排生产甲种药品生产量为2t，乙种产量为5t，每周可获得最大利润为20万元。
　　2.动态规划。
　　动态规划是运筹学的一个分支，是一种解决多阶段决策过程最优化的数学方法，它把困难的多阶段的决策问题分解成一系列相互联系的较容易解决的单阶段决策问题，通过解决这一系列单阶段决策问题来解决多阶段决策问题。以寻求最优决策序列的方法，动态规划研究多阶段决策过程的总体优化，即从系统总体出发，要求各阶段决策所构成的决策序列使目标函数值达到最优。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、问题、库存问题、装载问题、排序问题、设备更新问题、问题等等、所以它是现代经济管理中的一种重要的决策方法。
　　动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法(如是一种算法)，现举例说明动态规划在经济管理中的应用。
　　【例2】库存-销售问题。某公司计划在1月至4月份从事某种商品的。已知它的最多可存储1000件这种商品，该公司开业时有500件，并根据预测知道，该种商品1月至4月的进价和售价如表2所示。问如何安排进货量和，使该公司获得最大利润?（假设四月底库存为零。）
　　解：若将1月至4月份的购销安排作为阶段k(k=1,2,3,4)，那么该问题就是一个四阶段决策问题。
月份(k)1234
进价Ck(百元/件)1091115
售价Pk(百元/件)1291317
　　选择第k月初公司的存货量作为状态变量S_k，第k月的销售量和进货量分别作为决策变量U_k和V_k。
　　状态转移方程是
　　Sk = Sk + Vk & Uk
　　由已知，S1 = 500；假想有第五价段，S5 = 0。
　　阶段收益函数为rk(Sk;Uk,Vk) = PkUk & CkVk
　　动态规划基本方程为
　　采用逆序法递推计算（略）
　　最后得到该问题的最优策略见表3
月份月初存货量S_k(件)销售量U_k(件)进货量V_k(件)
3100010001000
4100010000
　　则该公司获得的最大利润为f1(s1) = f1(500) = 16000(百元)=160（万元）
伍学滨,邓小英.运筹学在经济管理中的应用.企业经济.2005.11
本条目对我有帮助145
&&如果您认为本条目还有待完善，需要补充新内容或修改错误内容，请。
本条目相关文档
& 50页& 309页& 319页& 294页& 575页& 171页& 127页& 7页& 10页& 40页
本条目由以下用户参与贡献
(window.slotbydup=window.slotbydup || []).push({
id: '224685',
container: s,
size: '728,90',
display: 'inlay-fix'
评论(共4条)提示:评论内容为网友针对条目"运筹学"展开的讨论，与本站观点立场无关。
发表评论请文明上网，理性发言并遵守有关规定。
以上内容根据网友推荐自动排序生成当前位置： >>
运筹学讲课
运筹帷幄 决胜千里? 主讲：蔡天鸣 ?电话：560227 ?办公室：21-404 ?Email:运筹学课程目的? 我们学习这门课程的目的是 要树立优化思想，认识运筹 学对实现管理的科学化和现 代化的重要意义和作用，掌 握运筹学的基本思想和方法， 并能结合相关软件的使用解 决管理中的实际问题。主导教材和主要参考书主导教材：《管理运筹学》(第三版) ，韩伯棠编著，高等教 育出版社。主要参考书： 1.《运筹学》（修订版），钱颂迪主编，清华大学出版社; 2.《数据模型与决策》(第 11版 )，David R. Anderson, etc.， 侯文华等译，机械工业出版社； 3.《运筹学教程》，胡运权主编，清华大学出版社 4.《运筹学应用案例集》, 胡运权主编，清华大学出版社； 5.《运筹学导论》（第 9 版） , 弗雷德里克 .S. 希利尔，杰拉 尔德.J.利伯曼著，胡运权等译，清华大学出版社； 6.《实用管理运筹学 ― 基于 Excel》, 陈士成主编 , 清华大学 出版社.第一章 绪 论? “运筹学”的释义运 筹 学 (Operational Research( 英 式 ) ； Operations Research(美式))直译为“运作研 究”、“作业研究”或“运用研究”，简称 OR。中文“运筹”二字取自《史记?高祖本记》 中，刘邦“夫运筹帷幄之中，决胜于千里之 外，吾不如子房”。运筹学是一门决策科学， 优化科学。第一章 绪 论? 我国古代运筹思想运用的典故1．“田忌赛马”“田忌赛马”是家喻户晓的历史故事。战国时齐威王与齐 相田忌赛马，双方各出三匹马比赛，每胜一场赢得一千金。由 于王府的马比相府的马好，所以田忌每次比赛都要输掉三千金。后来田忌的谋士孙膑献了一计：在每次开赛前要求对方先 报马名，由此区分对方参赛的是上马、中马还是下马；然后以 自己的上马对对方的中马、自己的中马对对方和下马、自己的 下马对对方的上马。这样，两胜一负反而赢得一千金。第一章 绪 论? 我国古代运筹思想运用的典故2．晋国公重建皇城晋国公重建皇城的施工方案， 体现了运筹学的朴素思想。要 使重建工程的各个工序 , 在时间、空间上彼此协调 , 环 环相扣,就需要运用行列式的相关知识,进行精确计算.2．晋国公重建皇城距今约1000年前，开封一场大火，北宋皇城毁于一旦。宋真宗命晋国公丁渭，主持重建全部宫室殿宇。 当时，皇城都是砖木结构的，建筑材料必须从远地通过汴水运来。由于时间紧、任务重， 按一般的操作法肯定不能按时完成。丁渭深思熟虑，规划并实施了一个至今令人拍案叫绝的施工方案。?先在皇宫前的大道上挖土烧砖备料；待把大道挖成深沟后，引进 城外汴水，使之与汴水连通成为“临时运河”，用船把其他建筑 材料直接运入工地；等到皇宫修复后，将碎砖石填入河道，修复 原来皇宫前的大道。按照这一方案，挖街取土，就地烧砖，渠成 恢复街道。这就巧妙地解决了取土之难，运输之难，清场之难， 可谓“一石三鸟”，使重建皇城事半功倍。引水，运送建材（本地砖瓦和外地石木），宫殿完工，渣土回填，第一章 绪 论?运筹学的产生和发展? 运筹学作为一门系统的科学，产生的背景 为第二次世界大战。主要用于解决如何在 与德军的对抗中最大限度地杀伤敌人，减 少损失。? 二战期间英国为解决空袭的早期预警，作好反侵略战争准备，积极进行“雷达”的 研究。但随着雷达性能的改善和配置数量 的增多，出现了来自不同雷达站的信息以 及雷达站同整个作战系统的协调配合问题。第一章 绪 论? 1938 年 7 月，波得塞（ Bawdsey ）雷达站的负责人 罗伊（ A.P.Rowe ）提出立即进行整个防空作战系统 运行的研究，并用“Operational Research” 一词作为 这方面研究的描述，这就是O.R. 名词的起源。? 1940年9月英国成立了由物理学家布莱克特（P.M.S. Blackett ）领导的第一个运筹学小组，后来发展到每 一个英军指挥部都成立运筹学小组。 ? 1942年美国和加拿大也都相继成立运筹学小组。这 些小组在确定扩建舰队规模、开展反潜艇战侦察和组 织有效对敌轰炸等方面作了大量研究，为取得反法西 斯战争的胜利及运筹学有关分支的建立作出了贡献。第一章 绪 论? 运筹学在第二次世界大战中成功运用的例子：如雷达的设置、运输船队的护航、反潜作战 中深水炸弹的深度、飞行员的编组、军事物资的 存储等。典型战例： 1．不列颠之战 2．盟军封锁直布罗陀海峡第一章 绪 论不列颠之战1941年，希特勒为了实施在英伦三岛登陆的计 划，命令德国空军轮番对英国进行狂轰滥炸。当时 英国皇家空军以一比七的数量劣势迎战，为此需要 尽可能地保持飞机处于飞行状态。于是，空军司令 部规定保持 70% 的飞机在天上巡逻。但是，英军很 快发现要保持这么高的飞行比例有困难，因为飞机 的被击落的、有需要维修的，飞行员也有伤亡。这 一决策的后果是在空中飞行的飞机数量越来越少。第一章 绪 论不列颠之战究竟保持多大比例的飞机在巡逻才能持久作战 呢？OR小组的专家纷纷研究这个问题，这个问题最 后被生物学家康顿解决了。他根据计算生物平均寿 命的方法，运用飞机飞行时间、维修时间、空战特 点和飞机被落击伤状况等数据，得出的结论是：只 要保持 35% 的飞机在飞行状态，就能使全部飞机的 飞行战斗时间最多。这一研究成果为取得不列颠之 战的胜利作出了贡献。第一章 绪 论盟军封锁直布罗陀海峡（猎潜战例）1944 年 初 ， 为帮助美国海军 在连接大西洋和 地中海的直布罗 陀海峡封锁过往 的德军潜艇 ，美 军 OR 小 组 的 约 翰? 佩芝姆博士提 出了一种“屏障 巡逻”飞行战术。第一章 绪 论盟军封锁直布罗陀海峡（猎潜战例）在深水航道的最 窄处划出一个4英里长、 1英里宽的长方形，两 架飞机保持在长方形 两边线的对称位置上， 同时以 115 英里 / 小时 的速度绕长方形飞行。 这样，在长 方形上的每一点，每隔3分钟就有一架飞机巡逻通过。潜 艇通过这个区域时，巡逻的飞机至少有两次机会去发现它。 就这样，在2月24日到3月16日短短三个星期内，一个巡逻 机中队击沉击伤德军潜艇3艘，自己无一伤亡。第一章 绪 论二战以后，运筹学得到了快速的发展， 形成了许多分支，并且计算机的应用极大地 推动了运筹学的应用与普及。 ? 运筹学有广泛应用 运筹学不仅在军事上，而且在生产、决 策、运输、存储等经济管理领域有着广泛的 应用。第一章 绪 论? 运筹学的定义C运筹学是运用分析，试验，量化的方法，对经济管理 系统中人、财、物(时间)等有限资源，进行统筹安排， 为决策者提供有依据的最优方案（满意方案），以实 现最有效地管理。――《中国企业管理百科全书》 C《辞海》对运筹学解释为：“二十世纪四十年代开始 形成的一门科学，主要研究经济活动与军事活动中能 用数量来表达的有关运用，筹划与管理方面的问题， 它根据问题的要求，通过数学的分析与运算，作出综 合性的合理的安排，以达到较经济、较有效地使用人 力、物力。近年来，它在理论与应用方面都有较大发 展。其主要分支有规划论、对策论、排队论及质量控 制等。”第一章 绪 论运筹学的特点(1) 科学性：运筹学是以研究事物内 在规律，并从定量分析的角度探求更好地解决问题的一门科学。第一章 绪 论运筹学的特点(2) 应用性：运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；第一章 绪 论运筹学的特点(3)多学科的交叉性、综合性：运筹学研究中吸收了来自不同领域的经验，并被广泛应用于工商企业、军事部门、民政事业等 研究组织内的统筹协调问题，故其应用不 受行业、部门之限制；《运筹学》课程的专业地位概率论与数理统计线性代数高等数学管理学基础会计经济学财务会计运筹学行为科学 生产与运作管理 质量管理 生产现场管理 企业战略管理 企业税收实务 财务管理市场营销人力资源管理第一章 绪 论运筹学的特点(4) 系统性和最优性 : 它以整体最优为目 标 , 从系统的观点出发 , 力图以整个系统 最佳的方式来解决该系统各部门之间的 利害冲突。对所研究的问题求出最优解 , 寻求最佳的行动方案 ,所以它也可看成是 一门优化技术 ,提供的是解决各类问题的 优化方法。第一章 绪论?§1 决策、定量分析与管理运筹学?§2 运筹学的分支?§3 运筹学在管理中的应用?§4 学习运筹学必须使用相应的计算机软件，必须注重于学以致用的原则§1.1 决策、定量分析与管理运筹学?决策的定义――现代管理科学创始人，诺贝尔奖金获得者世界 著名经济学家西蒙（ H.A.Simon ）：管理就是决策。 ――原中国社会科学院副院长于光远：决策就是作 决定。 ――为了实现一定目标，运用科学的理论和方法， 系统地分析主、客观条件，在掌握大量有关信息的 基础上，提出若干预选方案并从中选择出最优方案 （满意方案）的分析判断过程(科学的决策)。解决问题与制定决策明确问题 确定目标 提出方案 决策 解决问题 分析方案 选择方案检查 确定目标或评估方案的标准 评估各个方案：解的检 验、灵敏性分析等。 决策结果 执行此方案：回到实践中 不满意 进行后评估：考察问 题是否得到圆满解决.实施方案分析结果§1.1 决策、定量分析与管理运筹学?决策方法? 定性分析方法 ―― 借助决策者的知识、经验、 分析和判断能力等进行决策的方法。 ? 定量分析方法 ―― 量化决策问题并建立数学 模型进行决策的方法。 ? 定性与定量相结合的分析方法学习运筹学能够培养和提高定量分析能力§1.2运筹学的分支? 决策分析 ? 排队论 ? 对策论 ? 动态规划 ? 预测? 线性规划 ? 整数(线性)规划 ? 目标规划 ? 图与网络模型 ? 排序与统筹方法 ? 存储论*非线性规划、多目标规划、随机规划、模糊规划等§1.3 运筹学在管理中的应用? 生产计划 : 生产作业的计划、日程表的编 排、合理下料、配料问题、物料管理等; ? 库存管理 : 多种物资库存量的管理 , 库存 方式、库存量等; ? 运输问题 : 确定最小成本的运输线路、物 资的调拨、运输工具的调度以及建厂地址的 选择等; ?人事管理 : 对人员的需求和使用的预测， 确定人员编制、人员合理分配，建立人才评 价体系等;§1.3 运筹学在管理中的应用? 市场营销: 广告预算、媒介选择、定 价、产品开发与销售计划制定等; ? 财务和会计: 预测、贷款、成本分析、 定价、证券管理、现金管理等; *** 设备维修、更新，项目选择、评 价，工程优化设计与管理等;§1.3 运筹学在管理中的应用? 由国际运筹与管理科学协会（ INFORMS ）和它 的 管 理 科 学 实 践 学 会 （ College for the Practice of the Management Sciences ） 主 持 评 奖 的 负 有 盛 名 的 弗 兰 茨 ?厄 德 曼 （ Frany Edlman）奖，就是为奖励优秀的运筹学在管理中 的应用的成就设立的，该奖每年举行一次，在对 大量富有竞争力的入闱者进行艰苦的评审后，一 般有六位优胜者获奖。关于这些获奖项目的文章 都在第二年发表在著名刊物 Interfaces 的第一期 上，下面列表就是发表在 Interfaces 期刊的一些 获奖项目。组织 联合航空公司Citgo石油 荷马特发展公司AT&T 标准品牌公司应用 满足乘客需求前提下,以最低成本进行 订票及安排机场工作班次 优化炼油程序及产品供应、配送及营 销 优化商业区和办公楼销售程序 优化商业用户的电话销售中心选址每年节支(美元) 600万7000万 4000万4.06亿,更多销售控制成品库存（制定最优再订购点和 380万 订购量，确保安全库存） 通过战略调整，缩短维修机器的反应 生产率提高50%以 施乐公司 时间,改进维修人员的生产率 上 重新设计北美生产和分销系统以降低 2亿 宝洁公司 成本并加快了市场进入速度 制定最优铁路时刻表并调整铁路日运 1500万更多年收入 法国国家铁路 营量 进行上千个国内航线的飞机优化配置 1亿 Delta航空公司 来最大化利润 重组全球供应链，保持最小库存的同 第一年7.5亿 IBM 时满足客户需求 安装统计销售预测和成品库存管理系 更优的服务 Merit青铜制品公司 统，改进客户服务70运筹学方法使用情况(美1983)6050从不使用40有时使用 经常使用3020100统计计算机模拟 网络计划线性规划排队论非线性规划 动态规划对策论90运筹学方法在中国使用情况(随机抽样)807060从不使用50有时使用 经常使用403020100统计计算机模拟 网络计划线性规划排队论非线性规划 动态规划对策论§1.4 学习管理运筹学必须使用相应的计算机 软件，必须注重于学以致用的原则? 学习运筹学要结合实际的应用，不要被一 些概念、理论的困难吓倒。 ? 学习运筹学要把注意力放在“结合实际问 题建立运筹学模型”和“解决问题的方案 或模型的解”两头，中间的计算过程尽可 能让计算机软件去完成。 ? 学习运筹学是为了用于实践，解决实际问 题。以前重视人工计算是因为没有计算机， 现在有了就应该好好利用。课程考核方式平时成绩分布考核成绩比例课堂表现 10%考 勤 5%30%实验报告 15%70%平时期末第二章 线性规划的图解法? §2.1 问题的提出 ? §2.2 图解法第二章 线性规划的图解法线性规划（Linear program，LP)解决以下两类问题 ?资源一定 ? 任务一定 产出最大 投入最小 (产出：如产量、销售量、利润等) (投入：如资金、人员、时间、原材料等)§2.1线性规划问题的提出在工商管理，生产计划安排，交通运输，财贸 工作等各项经济活动中，如何应用科学的方法统筹安 排，合理利用资源（包括人力、物力、财力等资源）, 并使其经济效益达到最优，这些正是现代社会生产规 模日益扩大以及各部门和各系统之间的关系日益复杂 所面临的新问题。1939年前苏联数学家康托洛维奇 提 出 了 生 产 组 织 与 计 划 中 的 线 性 规 划 （ Linear Programming 简写为： LP ）模型，为以上问题的 解决提出了一种可行的方法。四十年代末旦茨基和查 恩斯等人提出的线性规划问题求解方法 ―单纯形法， 为线性规划的理论和应用奠定了基础，这些都是线性 规划的最卓著的开创性工作。§2.1线性规划问题的提出线性规划研究的内容和问题线性规划是研究在线性不等式或等式的限 制条件下，使得某一个线性目标函数取得最大 （或最小）的问题。常见的线性规划问题有： （一） 运输问题 （二） 生产的组织与计划问题 （三） 合理下料问题 （四） 配料问题 （五） 分派问题例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产， 已知生产单位产品所需的设备台时及A、B两种原材料的 消耗、资源的限制，如下表：设备 原料 A 原料 B 单位产品获利 Ⅰ 1 2 0 50 元 Ⅱ 1 1 1 100 元 资源限制 300 台时 400 千克 250 千克问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获 利最多？问题分析: 如何安排Ⅰ、Ⅱ两种产品的生产使得工厂 获利最大？ 设定决策变量：设Ⅰ、Ⅱ产品的产量分别为x1 , x2 目标：获利最大的利润 制约条件：生产能力和原材料的供给量例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已 知生产单位产品所需的设备台时及A、B两种原材料的消耗、 资源的限制，如下表：设备 原料 A 原料 B 单位产品获利 Ⅰ 1 2 0 50 元 Ⅱ 1 1 1 100 元 资源限制 300 台时 400 千克 250 千克问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利 最多？线性规划模型(Ⅰ、Ⅱ产品的产量分别为x1 , x2)： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0?§2.1线性规划问题的提出? LP模型三要素 - 决策变量- 约束条件（线性等式或线性不等 式） - 目标函数（线性函数，最大化或 最小化）§2.1线性规划问题的提出生产组织与决策问题例2. 某汽车工厂可生产大轿车和载重汽车，已 知生产每辆汽车所用的钢材均为 2 吨，该厂每 年供应的钢材为 1600 吨，生产能力为每 2.5 小 时生产一辆载重汽车，每 5 小时生产一辆大轿 车，工厂全年有效工时为2500小时；已知供应 给该厂大轿车用的座椅每年可装配 400 辆。据 市场调查，出售一辆大轿车可获利 4 千元，出 售一辆载重车可获利 3 千元。问在这些条件下， 如何安排生产使得工厂获利最大？分析：问题是如何安排生产使得工厂获利最大？项目 产品大轿车生产能力 5 (小时 ? 辆) 2.5 (小时 ? 辆) 2500 (小时 ? 年)钢材 2 (吨? 辆) 2 (吨? 辆) 1600 (吨)装配座椅 (辆 ? 年)400利润 (千元 ? 辆)4载重车提供量3设大轿车和载重车的产量分别为x1和x2（辆），则 解： 原材料的限制： 2 x1 ? 2 x2 ? 1600 工时的限制：大轿车座椅的限制： 非负限制：5 x1 ? 2.5 x2 ? 2500 x1 ? 400 x1 ? 0, x2 ? 0分析：问题是如何安排生产使得工厂获利最大？项目 产品 大轿车 载重车 提供量生产能力5 (小时 ? 辆) 2.5 (小时 ? 辆) 2500 (小时 ? 年)钢材 (吨 ) 2 2 1600装配座椅 (辆 ? 年 ) 400利润 (千元 ? 辆) 4 3目标：利润最大maxZ ? 4 x1 ? 3 x2§2.1线性规划问题的提出因此该问题的数学模型为：目标函数max Z ? 4 x1 ? 3 x2? 2 x1 ? 2 x2 ? 1600 ?5 x ? 2.5 x ? 2500 ? 1 2 ? ? x1 ? 400 ? ? x1 ? 0, x2 ? 0约 束 条 件§2.1线性规划问题的提出实际问题最优解 LP模型§2.1线性规划问题的提出? 建模过程 1. 理解要解决的问题，了解题的目标和条件； 2. 定义决策变量(x1 ，x2 ，… ，xn ), 每一组值表示一个方案； 3. 用决策变量的线性函数形式写出目标函数，确定最大化或 最小化目标； 4. 用一组决策变量的等式或不等式表示解决问题过程中必须 遵循的约束条件 ? 一般形式 目标函数： Max（Min）z = c1 x1 + c2 x2 + … + cn xn 约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0§2.2 图 解 法对于只有两个决策变量 的线性规划问题，可以在平 面直角坐标系上作图表示线 性规划问题的有关概念，并 求解。 下面通过例 1 详细讲解其 方法：设备 原料A 原料B 单位产 50元 100元 品获利 I 1 2 0 II 1 1 1 资源限制 300台时 400千克 250千克例1. 目标函数： Max z = 50x1 + 100x2 约束条件： x1 + x2 ≤ 300 (A) 2x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解： x1 = 50，x2 = 250 最优目标值 z = 27500§2.2 图 解 法(1) 分别取决策变量X1 , X2为坐标向量建立直角坐标系。 在直角坐标系里 , 图上任意一点的坐标代表了决策变量 的一组值, 例1的每个约束条件都代表一个半平面。x2X2≥0x2X1≥0X1=0X2=0x1x1§2.2 图 解 法（2）对每个不等式(约束条件)，先取其等式在坐标 系中作直线，然后确定不等式所决定的半平面。300 200 100 100 200 300 x1+x2≤300 x1+x2=300 400 300 200 100 2x1+x2≤400 100 200 300 2x1+x2=40 0§2.2 图 解 法 （ 3）把五个图合并成一个图，取各约束条件 的公共部分，如图2-1所示。x2=250x2 2x1+x2=400300 200x2=250100x2≤250x1+x2=300 x1 图2-1100 200 300x2=0x1=0（ 4 ）目标函数 z=50x1+100x2 ，当 z 取某一固定值时得到 一条直线，直线上的每一点都具有相同的目标函数值， 称之为“等值线”。平行移动等值线，当移动到 B点时， z在可行域内实现了最大化。A, B, C, D, E是可行域的顶 点，对有限个约束条件则其可行域的顶点也是有限的。x2 A z=+100x2 BCz=+100x2z=+100x2z=0=50x1+100x2D Ex1图2-2§2.2 图 解 法图解法的运算步骤1. 分别以 L.P. 模型中的 两个变量为横轴和竖轴 建立平面直角坐标系(例 如可以以例1中的x1为横 轴，以x2为竖轴)。0x2x1§2.2 图 解 法 2. 在所建立的平面坐标系中画出约束条件所 围 成 的 区 域 图 形 － － 可 行 ( 解 集 ) 域 （ the feasible region），并将其用阴影表示出来。例1. max Z = x1+3x2 s.t. ? x1+ x2≤6 ? ?-x1+2x2≤8 ? ? x ≥0, x ≥0 1 2-8x264可行域60x13. 画出目标函数的图形(通常可画出当目 标函数值为零时的(基准)目标函数图)，确 定目标函数平行移动的方向，并沿目标函 数直线的法向用小箭头标出。例1. max Z = x1+3x2 s.t.? x1+ x2≤6 ? ? -x1+2x2≤8 ? ? x ≥0, x ≥0 1 2-8 Z=x1+3x2= 064x2可行域06x1§2.2 图 解 法4．将（基准）目标函数直线沿所标示的方 向平行移动直至可行域的边界，若这时目 标函数的直线与可行域的边界点或边界线 重合，则其重合点或重合线段上的点即为 此L.P.问题的最优解,当重合部分为一点，则 该点的坐标即为原 L.P.的唯一解，当重合部 分为一条线段时，则该线段上的任一点的 坐标即为原 L.P. 的解，这时原 L.P. 问题有无 穷多个解; 否则，原L.P.问题无解。max Z = x1+ x2＝6 -x1+2x2＝8下方程解得x1 , x2 ： x1+ x2＝6 解得: x1 ＝4/3 x1+3x2 -x1+2x2＝8 x2＝14/3设点 P的坐标为 (x1 ,x2)，则可由以 §2.2 图 解 法6 4x2最优解目标函数基准线 Z=x1+3x2= 0 -8P可行域目标函数等值线06x1故最优解为：x1 ＝4/3 ， x2 ＝14/3最优值为： max Z = x1+3x2 ＝4/3 +3× 14/3=46/3max Z = x1+3x2 x1+ x2＝6 -x1+2x2＝8 目标函数基准线 Z=x1+3x2= 0 -86 4x2最优解P可行域目标函数等值线06x1§2.2 图 解 法例2. 求解L.P.问题：解：max Z = x1+x2 s.t. ? x1+ x2≤6 ? ? -x1+2x2≤8 ? ? x1 ≥0, x2≥0以x1为横轴，以x2为竖轴建立直角 坐标系，并根据题意画图。由图可知例 2 的目标函数在线段 PQ 上任一点处均取最 大值，原问题有无穷多个最优解。设点 P 的坐标为 ( x 1 , x2), 则可解得点P的坐标为(3/4, 14/3)。 故原问题的一个最优解为：x1＝4/3，x2＝14/3 max Z = x1＋x 2 Z = x1+3x2 ＝4/3 + 14/3=6 其最优值为： maxx1+ x2＝6 -x1+2x2＝86 4x2 P最优解目标函数基准线 Z=x1+x2= 0 -8可行域目标函数等值线0Q 6 x1§2.2 图 解 法 目标函数无上 界，无最优解 例3. max Z = x ＋x 1 2 x2 s.t. ? 2x1 - x2≥2 ? ? - x1+2x2≤8 ? ? x ≥0, x ≥0 1 24 Z=x1+x2= 0 -8目标函数等值线0 -21可行域x1例4.§2.2 图 解 法目标函数等值线min Z = x1＋x2 s.t. ? 2x1 - x2≥2 ? ? - x1+2x2≤8 ? ? x ≥0, x ≥0 1 2Z=x1+x2= 0 -8x24最优解0 -21可行域x1§2.2 图 解 法? 重要结论：C 如果线性规划有最优解，则一定有一个可行域的 顶点对应一个最优解； C 无穷多个最优解。如例 3，线段 PQ上的所有点都 代表了最优解； C 无界解。即可行域的范围延伸到无穷远，目标函 数值可以无穷大或无穷小，如例 4 。一般来说， 在实际问题中，这说明模型有错，忽略了一些必 要的约束条件； C 无可行解。若在例 1 的数学模型中再增加一个约 束条件 4x1+3x2≥1200 ，则可行域为空域，不存在 满足约束条件的解，当然也就不存在最优解了。§2.2 图 解 法练习. max Z = -x1+2x2 s.t. ? x1≤3 ? ? x1－x2 ≥ 0 ? ? x ≥0, x ≥0 1 2Z= -x1+2x2= 0解得P点坐标为： x1=3，x2 =3 最优值为： maxZ=3P最优解x2可行域3 0x1第三章 线性规划的应用§1 生产计划的问题； §2 套裁下料问题； §3 配料问题； §4 投资问题。§1生产计划的问题甲 乙 丙 限制 5 10 7
4 2 8 00例 1 ．某公司面临一个是外包 铸造工时 协作还是自行生产的问题。该 (小时/件) 机加工工时 公司生产甲、乙、丙三种产品， 都需要经过铸造、机加工和装 (小时/件) 装配工时 配三个车间。甲、乙两种产品 (小时/件) 的铸件可以外包协作，亦可以 自产铸件成 自行生产，但产品丙必须本厂 本(元/件) 外协铸件成 铸造才能保证质量。数据如表。 本(元/件) 问：公司为了获得最大利润， 机加工成本 甲、乙、丙三种产品各生产多 (元/件) 少件？甲、乙两种产品的铸造 装配成本 (元 / 件 ) 中，由本公司铸造和由外包协 产品售价 作各应多少件？ (元/件)35 2 3546 -1 2 3 223 18 16铸造工时(小时/件) 机加工工时(小时/件) 装配工时(小时/件) 自产铸件成本(元/件) 外协铸件成本(元/件) 机加工成本(元/件) 装配成本(元/件) 产品售价(元/件)甲 5 6 3 3 5 2 3 23乙 10 4 2 5 6 1 2 18丙 7 8 2 4 -3 2 16资源限制
10000解：设 x1, x2, x3 分别为三道工序都由本公司 加工的甲、乙、丙三种产品的件数，x4, x5 分别 为由外协铸造再由本公司加工和装配的甲、乙两 种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和甲 乙 丙 资源限制 5 10 7 8000 铸造工时(小时/件) 6 4 8 12000 机加工工时(小时/件) 3 2 2 10000 装配工时(小时/件) 3 5 4 自产铸件成本(元/件) 5 6 -外协铸件成本(元/件) 2 1 3 机加工成本(元/件) 3 2 2 装配成本(元/件) 23 18 16 产品售价(元/件) 产品甲全部自制的利润=23-(3+2+3)=15 产品甲铸造外协，其余自制的利润=23-(5+2+3)=13 产品乙全部自制的利润=18-(5+1+2)=10 产品乙铸造外协，其余自制的利润=18-(6+1+2)=9 产品丙的利润=16-(4+3+2)=7 可得到xi（i=1,2,3,4,5）的利润分别为15,10,7,13,9元.甲 乙 乙 丙丙 资源限制 资源限制 5 10 77 8000 铸造工时 (小时 10 8000 铸造工时(小时 /件)/件) 44
12000 机加工工时(小时 /件) /件) 机加工工时 (小时 22 10000 装配工时(小时 /件)/件) 3 22 10000 装配工时 (小时 55 自产铸件成本(元( /件 ) /件) 3 44 自产铸件成本 元 66 外协铸件成本(元( /件 ) /件) 5 -- -外协铸件成本 元 1 3 机加工成本(元/件) 2 1 3 机加工成本(元/件) 2 2 装配成本(元/件) 3 2 2 装配成本(元/件) 18 16 产品售价(元/件) 23 18 16 产品售价(元/件) 通过以上分析,可建立如下的数学模型: 目标函数： Max z=15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件： 5x1 + 10x2 + 7x3 ≤
+ 4x2 + 8x3 + 6x4 + 4x5 ≤
+ 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1, x2, x3, x4, x5 ≥ 0甲 5 6 3 3 5 2 3 23Excel中的求解§2套裁下料问题例 2. 某工厂要做 100 套钢架 , 每套用长为 2.9m, 2.1m, 1.5m 的圆钢各一根 。已知原料每根长 7.4m，问: 应如何下料，可使所用原料最省？ 解： 共可设计下列8种下料方案，见下表方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8 2.9 m 1 2 0 1 0 1 0 0 2.1 m 0 0 2 2 1 1 3 0 1.5 m 3 1 2 0 3 1 0 4 合计 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 剩余料头 0 0.1 0.2 0.3 0.8 0.9 1.1 1.42.9 m 2.1 m 1.5 m 合计 剩余料头方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4设 x1, …, x8 分别为上面 8 种方案下料的原材料根数。 这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + … + x8 约束条件： x1+2x2 + x4 + x6 ≥100 2x3+2x4 + x5 + x6 + 3x7 ≥100 3x1 + x2+2x3 +3x5+ x6 +4x8≥100 x1, x2, …, x8 ≥ 0§2套裁下料问题? 用 Excel 计算得出最优下料方案：按方案 1 下 料30根；按方案2下料10根；按方案4下料50根, 即: x1=30; x2=10; x3=0; x4=50; x5=x6=x7=x8=0； 只需90根原材料就可制造出100套钢架。 ? 注意：在建立此类型数学模型时，约束条件 用大于等于号比用等于号要好。因为有时在套 用一些下料方案时可能会多出一根某种规格的 圆钢，但它可能是最优方案。如果用等于号， 这一方案就不是可行解了。§3例 3 ． 某 工 产品 厂要用三种 名称 原料 1, 2, 3 甲 混合调配出 三种不同规 格的产品甲、 乙 乙、丙，数 丙 据如右表。 问：该厂应 原材 如何安排生 料名 1 产，使利润 收入为最大 ? 2配料问题规格要求单价 (元/kg) 50 35 25 单价 (元/kg) 65 25 35原材料1不少于50%， 原材料2不超过25% 原材料1不少于25%， 原材料2不超过50% 不限每天最多供应量 100 100 603产品名称 规格要求 单价（元/kg） 50 甲 原材料 1 不少于 50%，原材料 2 不超过 25% 35 乙 原材料 1 不少于 25%，原材料 2 不超过 50% 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价（元/kg） 65 25 35解：设 xij 表示第 i 种(甲、乙、丙)产品中原料j 的 含量。这样我们建立数学模型时，要考虑： 对甲: x11 , x12 , x13； x11≥0.5(x11+x12+x13) , x12≤0.25(x11+x12+x13)产品名称 规格要求 单价（元/kg） 50 甲 原材料 1 不少于 50%，原材料 2 不超过 25% 35 乙 原材料 1 不少于 25%，原材料 2 不超过 50% 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价（元/kg） 65 25 35对乙: x21 , x22 , x23； x21≥0.25(x21+x22+x23), x22≤0.5(x21+x22+x23)产品名称 规格要求 单价（元/kg） 50 甲 原材料 1 不少于 50%，原材料 2 不超过 25% 35 乙 原材料 1 不少于 25%，原材料 2 不超过 50% 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价（元/kg） 65 25 35对丙： x31，x32，x33；没限制，即无约束条件。 对于原料1： x11，x21，x31； (x11+x21+x31)≤100 对于原料2： x12，x22，x32； (x12+x22+x32)≤100 对于原料3： x13，x23，x33； (x13+x23+x33)≤60 约束条件： 规格要求 4 个；供应量限制 3 个。产品名称 规格要求 单价（元/kg） 50 甲 原材料 1 不少于 50%，原材料 2 不超过 25% 35 乙 原材料 1 不少于 25%，原材料 2 不超过 50% 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价（元/kg） 65 25 35目标：利润最大，利润 = 收入 - 原料支出, 故有: 目标函数: Max f =50(x11+x12+x13)+35(x21+x22+x23)+25(x31+x32+x33) - 65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33) = -15x11+25x12+15x13-30x21+10x22-40x31-10x33通过整理，得到以下模型： 目标函数： Max z =-15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件： s.t. 0.5 x11-0.5 x12 -0.5 x13 ≥ 0 (原材料1不少于50%) -0.25x11+0.75x12 -0.25x13≤0 (原材料2不超过25%) 0.75x21-0.25x22 -0.25x23 ≥0 (原材料1不少于25%) -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 (原材料2不超过50%) x11+ x21 + x31 ≤ 100 (供应量限制） x12+ x22 + x32 ≤ 100 (供应量限制） x13+ x23 + x33 ≤ 60 (供应量限制） xij ≥ 0, i = 1, 2, 3; j = 1, 2, 3思考题： ?如 果 实 际 问 题 的 情 况，目标函数或约束 条件不可用线性函数 描述将会延拓出什么 问题？ ?进 一 步 ， 当 实 际 问 题的条件是不确定的 或不清晰的，又将如 何分析和考虑？ 有兴趣可查阅和了解 非线性规划、模糊线 性规划等内容。练习1 学校准备为学生添加营养餐，每个学生每月至 少需要补充 60单位的碳水化合物，40单位的蛋 白质和35单位的脂肪。已知两种营养品每斤： A B 变量： x y 含量: 约束条件：碳水化合物 5 x+ 2 y≥60 蛋白质 3 x+ 2 y≥40 脂肪 5 x+ 1 y≥35 非负条件： x≥0, y≥0 单价 目标函数：min s= 1.5 x+ 0.7 y 问题：买A和B分别多少斤既满足学生营养需要 又省钱？§4 投资问题例 4．某部门现有资金 200万元，今后五年内考虑给 以下的项目投资。已知：项目A：从第一年到第五年 每年年初都可投资，当年末能收回本利110%；项目 B：从第一年到第四年每年年初都可投资，次年末能 收回本利 125% ，但规定每年最大投资额不能超过 30万元；项目C：需在第三年年初投资，第五年末能 收回本利 140% ，但规定最大投资额不能超过 80 万 元；项目D：需在第二年年初投资，第五年末能收回 本利155%，但规定最大投资额不能超过100万元。 据测定每万元每次投资的风险指数如下表，问： a） 应如何确定这些项目的每年投资额，使得第五年年末 拥有资金的本利金额为最大？b）应如何确定这些项 目的每年投资额，使得第五年年末拥有资金的本利在 330万元的基础上使得其投资总的风险系数为最小？项目 A B C D风险指数（次/万元） 1 3 4 5.5解： 1）确定决策变量：连续投资问题 设 xij ( i = 1～5，j = 1～4)表示第 i 年初投 资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金 额。这样我们建立如下的决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x242）约束条件：第一年：A当年末可收回投资，故第一年年初 应把全部资金投出去，于是 x11+ x12 = 200；第二年：B次年末才可收回投资，故第二年年 初有资金1.1 x11，于是 x21 + x22+ x24 = 1.1x11；第三年：年初有资金 1.1x21+ 1.25x12，于是x31 + x32+ x33 = 1.1x21+ 1.25x12第四年：年初有资金 1.1x31+ 1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22第五年：年初有资金 1.1x41+ 1.25x32，于是x51 = 1.1x41+ 1.25x32 B、C、D的投资限制： xi2 ≤ 30 ( i =1、2、3、4 )， x33 ≤ 80， x24 ≤ 1003）目标函数及模型： a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 ≤ 30 ( i =1、2、3、4 )， x33 ≤ 80， x24 ≤ 100 ， xij ≥ 0 ( i = 1, 2, 3, 4, 5；j = 1, 2, 3, 4, ）项目 A B C D风险指数（次/万元） 1 3 4 5.5b)所设变量与问题 a相同，目标函数为风险最小， 有:Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24b)在问题a的约束条件中加上“第五年末拥有资 金本利在330万元”的条件，于是模型如下： Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42) +4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 ≤ 30 ( i =1, 2, 3, 4 )，x33 ≤ 80，x24 ≤ 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330 xij ≥ 0 ( i = 1, 2, 3, 4 , 5；j = 1, 2, 3, 4 ）线性规划的高级应用? 数据包络分析(Data Envelopment Analysis ,DEA)：线性规划在测量有相同目 标和目的的工作单位相对效率中的一种应用。 例如，DEA用于同一连锁销售店中的单个快 餐店。银行用DEA做分行的绩效测量。线性规划的高级应用? 医院绩效评价 总医院、大学医院、县医院和州医院的管理者聚在一起讨 论以各自的医院帮助彼此改进绩效的方法。一个顾问建议 他们考虑采用DEA来测量每所医院相对于所有4所医院的绩 效。在讨论这种评价如何进行时，确定出下面3种输入测量 和4种输出测量： 输入测量 (1)全日制非医生人员的数目 (2)物资花费总数 (3)可用床日的数目 输出测量 (1)有医疗保险服务的病人日数目 (2)无医疗保险服务的病人日数目 (3)培训的护士数目 (4)培训的实习医生数目 这4所医院输入和输出的年测量结果如下表所示。数据包络分析4所医院年消耗资源（输入）输入测 量 医院4所医院提供的年服务（输出）输出测 量总医院医院总医院大学医 院县医院州医院 医疗保 险病人 日(1000) 非医疗 保险病 人日 (1000) 培训的 护士 48.14大学医 院 34.62县医院州医院36.7233.16全日制 非医生 人员物资花 费(1000 美元)285.3162.3275.7210.443.127.1145.9856.46123.8128.7348.5154.1253148175160可用床 日(1000)106.7264.21104.1104.04培训的 实习医 生41272384数据包络分析? DEA思路：首先使用一个线性规划模型，基于有相同目标的 所有运营单位的输入和输出，构建一个假定的合成单位， 在此是一家合成医院。对应于这4所医院的每个输出测量， 合成医院的输出由全部4所医院相应输出的加权平均计算得 到。应于每个输入测量，合成医院的输入由采用相同权重 的全部4所医院相应输入的加权平均计算得到。线性规划模 型中的约束条件要求合成医院的所有输出大于等于被评价 的县医院的输出。如果合成医院的输入能显示出少于县医 院的输入，那么就说明合成医院能利用较少的输入产出一 样或更加多的输出。在这种情况下，模型就说明合成医院 比县医院更有效率。因为合成医院是基于全部4所医院的， 所以当与同组内其他医院相比时，被评价医院被判定为是 相对低效的。数据包络分析? 为了确定在计算合成医院的输入和输出时每 家医院所占的权重，设决策变量为 --wg总医院输入和输出采用的权重 --wu大学医院输入和输出采用的权重 --wc县医院输入和输出采用的权重 --ws州医院输入和输出采用的权重数据包络分析约束条件： 权重之和为1:wg+wu+wc+ws=1 合成医院的输出大于等于县医院的输出 医疗保险病人日： 48.14wg+3.62wu+36.72wc+33.16ws&=36.72 非医疗保险病人日： 43.1wg+27.11wu+45.98wc+56.46ws&=45.98 培训的护士： 253wg+148wu+175wc+160ws&=175 培训的实习医生： 41wg+27wu+23wc+84ws&=23数据包络分析? 设县医院输入可用于合成医院的百分比为E ? 约束条件合成医院的输入小于等于合成医院的可用 资源可表示为： 非医生人员数目： 285.2wg+162.3wu+275.7wc+210.4ws&=275.7E 物资花费： 123.8wg+128.7wu+348.5wc+154.1ws&=348.5E 床日： 106.72wg+64.21wu+104.1wc+104.04ws&=104.04E 目标函数 Min E：最小化合成医院可用的输入资源数据包络分析? 决策规则如下： ? 如果E=1，合成医院需要与县医院一样多的 输入，没有证据表明县医院是低效的 ? 如果E&1，合成医院需要较少的输入就能得 到县医院的输出，合成医院是更有效的，因 此县医院可以被认为是相对低效的数据包络分析? DEA方法步骤： ? 1、定义决策变量或权重，用于确定合成运营单位 的输入和输出 ? 2、写出要求权重总和等于1的一个约束条件 ? 3、对于每个输出测量，写出一个要求合成运营单 位的输出大于等于第j个运营单位对于输出的约束 条件 ? 4、定义一个决策变量E，它确定第j个运营单位的 输入用于合成运营单位的比例 ? 5、对于每个输入测量，写出一个要求合成运营单 位的输入小于或等于合成运营单位可用资源的约束 条件 ? 6、写出目标函数，为minE作业评分细则? 数学模型5分：决策变量2分，目标函数1分， 约束条件2分 ? Excel求解4分：表格设计2分，规划求解设置 1分，求解结果1分 ? 求解结果说明1分第四章运 输 问 题? §1 运 输 模 型 ? §2 运输问题的计算机求解 ? §3 运输问题的应用 ? §4* 运输问题的表上作业法§1运 输 模 型例1、某公司从两个产地A1、A2将物品运往三 个销地 B1 、 B2 、 B3 ，各产地的产量、各销地 的销量和各产地运往各销地每件物品的运费 如下表所示，问：应如何调运可使总运输费 用最小？A1 A2 销量B1 6 6 150B2 4 5 150B3 6 5 200产量 200 300A1 A2 销量B1 6 6 150B2 4 5 150B3 6 5 200产量 200 300解： 产销平衡问题： 总产量 = 总销量设 xij 为从产地Ai运往销地Bj的运输量，得到 下列运输量表： B1 B2 B3 产量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 150 150 200 销量A1 A2 销量A1 A2 销量B1 6 6 150B1 x11 x21 150B2 4 5 150B2 x12 x22 150B3 6 5 200B3 x13 x23 200产量 200 300产量 200 300Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23A1 A2 销量A1 A2 销量B1 6 6 150B1 x11 x21 150B2 4 5 150B2 x12 x22 150B3 6 5 200B3 x13 x23 200产量 200 300产量 200 300产地A1运出的运输量等于其产量： x11+ x12 + x13 = 200 产地A2运出的运输量等于其产量： x21 + x22+ x23 = 300 运到销地B1的运输量等于其需求量： x11 + x21 = 150 运到销地B2的运输量等于其需求量： x12 + x22 = 150 运到销地B3的运输量等于其需求量： x13 + x23 = 200 运输量非负： xij≥ 0 (i=1,2；j=1,2,3)§1整理得：运 输 模 型Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150x12 + x22 = 150x13 + x23 = 200xij ≥ 0 ( i = 1、2；j = 1、2、3）§1运 输 模 型? 一般运输模型：产销平衡A1、 A2、…、 Am 表示某物资的m个 产地； B1、B2、…、Bn 表示某物质的n个 销地；ai 表示产地Ai的产量； bj 表示销地 Bj 的销量； cij 表示把物资从产地Ai运往销 地Bj的单位运价。 ? 设 xij 为从产地Ai运往销地Bj的运输量，得 到下列一般运输量问题的模型：§1销地运 输 模 型B2 … Bn 产量运输问题及其数学模型产地B1A1 A2a1?Am 销量 b1运价ma2?am b2 … bn?a ? ?bi ?1 i j?inj产销平衡§1销地运 输 模 型B2 c12 c22 … … … Bn c1n c2n 产量 a1 a2产 销 平 衡 表运输问题及其数学模型产地B1 c11 c21A1 A2?Am 销量?cm1 b1?cm2 b2 … …?cmnm i ?1?amn j?ibn ? a i ? ? b j求使总的运输费用最小的调运方案？§1min s ?n运 输 模 型运输问题线性规划模型?? cij xijj ?1 i ?1nm总费用最小产 地 Ai 发 量之和等 于其产量? ? ? xij ? ai ( i ? 1,2,? , m ) ?1 ? jm 销 地 Bj 收 ? 量之和等 ? ? xij ? b j ( j ? 1,2,? , n) 于其销量 ? i ?1 ? xij ? 0 ( i ? 1,2,? , j ? 1,2,? , n) ? 运量不能为负数 ?思考题： ?运输问题如何进行求解？ 要求： 对以上例子用 Excel的 线性规划工具进行计算。§2 运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三 个销地 B1 、 B2 、 B3 ，各产地的产量、各销地 的销量和各产地运往各销地每件物品的运费 如下表所示，问：应如何调运可使总运输费 用最小？A1 A2 销量B1 6 6 150B2 4 5 150B3 6 5 200产量 300 300 600 500A1 A2 销量B1 6 6 150B2 4 5 150B3 6 5 200产量 300 300 600 500解：增 加一个 虚设的 销地运 输费用 为0.B1 B2 B3 B4 A1 6 4 6 0 A2 6 5 5 0 销量 150 150 200 100产量 300 300 600 600§2 运输问题的计算机求解例 3 、某公司从两个产地 A1 、 A2 将物品运往三 个销地 B1、 B2、B3，各产地的产量、各销地的 销量和各产地运往各销地每件物品的运费如下 表所示，问：应如何调运可使总运输费用最小？A1 A2 销量B1 6 6 250B2 4 5 200B3 6 5 200产量 200 300 500 650A1 A2 销量B1 6 6 250B2 4 5 200B3 6 5 200产量 200 300 500 650解：增 加一个 虚设的 产地运 输费用 为0A1 A2 A3 销量B1 6 6 0 250B2 4 5 0 200B3 6 5 0 200产量 200 300 150 650 650思考题在例 3中，即某公司从两个产地 A1、A2将物品 运往三个销地B1、B2、B3，各产地的产量、各 销地的销量和各产地运往各销地每件物品的运 费如下表所示，如果增加条件：B3的需求不能 满足则需以高价（每单位10元）在本地购买， 问：应如何调运可使总费用最小？ B1 B2 B3 产量A1A2 销量66 25045 20065 200 650200300 500§3 运输问题的应用一、产销不平衡的运输问题 例4、石家庄北方研究院有一、二、三三个区。每 年分别需要用煤 3000 、 1000 、 2000 吨，由河北临 城、山西盂县两处煤矿负责供应，价格、质量相 同。供应能力分别为吨，运价为： 一区 二区 三区 产量 1.80 1.70 1.55 4000 山西盂县 1.60 1.50 1.75 1500 河北临城 00 需要量 由于需大于供，经院研究决定一区供应量可 减少 0--300 吨，二区必须满足需求量，三区供应 量不少于1500吨, 试求总费用为最低的调运方案。§3运输问题的应用应用Excel计算得：§3运输问题的应用生产 单位成 季 能力 本(万 度 (台) 元)二、生产与储存问题 例 6 、某厂按合同规定须于当 年每个季度末分别提供10、15、 25、20台同一规格的柴油机。 已知该厂各季度的生产能力及 生产每台柴油机的成本如右表。 如果生产出来的柴油机当季不 交货，每台每积压一个季度需 储存、维护等费用 0.15 万元。 试求在完成合同的情况下，使 该厂全年生产总费用为最小的 决策方案。12253510.811.134301011.011.3解：把第 i 季度生产的柴油机数目看作第 i 个生产 厂的产量；把第 j 季度交货的柴油机数目看作第 j 个 销售点的销量；成本加储存、维护等费用看作运费。 可构造下列产销不平衡问题: 季度 1 2 3 4 季度 1 10.80 10.95 11.10 11.25 2 M 11.10 11.25 11.40 3 M M 11.00 11.15 4 M M M 11.30 产量 25 35 30 10 100 70销量10152520设 xij为第i季度生产的第j季度交货的柴油机数目，则 交货: x11 =10 生产: x11+x12+x13+x14≤25 x12+x22 =15 x22+x23+x24≤35 x13+x23+x33 =25 x33+x34≤30 x14+x24+x34+x44=20 x44≤10 目标函数: Minf=10.8x11+10.95x12+11.1x13+11.25x14+ +11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44季度 1 2 3 4 季度 1 10.80 10.95 11.10 11.25 2 M 11.10 11.25 11.40 3 M M 11.00 11.15 4 M M M 11.30 销量 10 15 25 20产量 25 35 30 10 100 70§3 运输问题的应用? 应用Excel的求解结果§3 运输问题的应用三、转运问题： 在原运输问题上增加若干转运站。运输 方式有: 产地? 转运站、转运站? 销地、 产地? 产地、产地? 销地、销地? 转运站、 销地? 产地等。转运关系下的运输网络A1A2A1A2T1B1B2B1 B2没有转运关系的运输网络转运关系的运输网络例 7、腾飞电子仪器公司在大连和广州有两 个分厂生产同一种仪器，大连分厂每月生产 400台，广州分厂每月生产600台。该公司在 上海和天津有两个销售公司负责对南京、济 南、南昌、青岛四个城市的仪器供应。另外 因为大连距离青岛较近，公司同意大连分厂 向青岛直接供货，运输费用如图，单位是百 元。问应该如何调运仪器，可使总运输费用 最低？图中 1- 广州、 2- 大连、 3- 上海、 4- 天 津、5-南京、6-济南、7-南昌、8-青岛。应该如何调运仪器，可使总运输费用最低？图 中 1- 广州、 2- 大连、 3- 上海、 4- 天津、 5- 南京、 6-济南、7-南昌、8-青岛。广州上海南 京 济 南 南 昌大连天津青 岛运价表 上海 天津 广州 2 3 大连 3 1 0 M 上海 天津 M 0 销量 南京 济南 南昌 青岛 产量M M 2M M 6M M 3M 4 6300600 400 200 150 350运价表 上海 天津 南京 济南 南昌 青岛 产量 2 3 M M M M 600 广州 3 1 M M M 4 400 大连 0 M 2 6 3 6 1000 上海 M 0 4 4 6 5 1000 天津 销量 0 150 350 300§3 运输问题的应用? 应用Excel的求解结果整数规划§1 整数规划简介§2 整数规划的计算机求解§3 整数规划的应用 *§4 整数规划的分枝定界法整数规划?整数规划是一类要求变量取整数值的数学规划， 可分成线性和非线性两类。 ?整数线性规划(Integer Linear Programming， 简记为ILP)问题研究的是要求变量取整数值时， 在一组线性约束条件下一个线性函数最优问题， 是应用非常广泛的运筹学的一个重要分支。 应用实例：● 项目投资问题 ● 选址问题 ● 工作分配问题 ● 背包问题整数规划?根据变量的取值情况，整数线性规划又可以分 为纯整数规划（所有变量取整数），混合整数规 划（部分变量取整数）， 0-1 整数规划（变量只 取0或1）等。?求整数解的线性规划问题，不是用四舍五入法 或去尾法对线性规划的非整数解加以处理就能解 决的。整数线性规划一些基本算法的设计是以相 应线性规划的最优解为出发点而发展出来的。?整数规划是数学规划中一个较弱的分支，目前 有成熟的方法解线性整数规划问题，而非线性整 数规划问题，还没有好的办法。§1 整数规划简介例1. 某公司拟用集装箱托运甲、乙两种货物， 这两种货物每件的体积、重量、可获利润以及 托运所受限制如表所示。货物甲 乙 托运限制每件体积 (立方米) 195 273 1365每件重量 (百千克) 4 40 140每件利润 （百元） 2 3甲种货物至多托运 4 件，问两种货物各托运多 少件，可使获得利润最大。§1 整数规划简介货物甲 乙 托运限制 每件体积 (立方米) 195 273 1365 每件重量 (百千克) 4 40 140 每件利润 （百元） 2 3解：设x1 、 x2分别为甲、乙两种货物托运的件数，建 立模型。 目标函数： Max z = 2x1 +3x2 约束条件：s.t. 195 x1 + 273 x2 ≤ + 40 x2 ≤140 x1 ≤4 x1，x2 ≥0, 为整数。 如果去掉最后一个约束，就是一个线性规划问题.§1 整数规划的图解法6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8利用图解法，得到线性规划的最优解为x1=2.44, x2=3.26, 目标函数值为14.66。 由 图表可看出 , 可 行 域 中 的 整数 点 主 要 为 (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(4,1),(4,2)；整数规划 的最优解为x1=4, x2=2,目标函数值为14。§1 整数规划的分支定界法该算法的基本思路是：先不考虑整数限制，求出相应的线性 规划的最优解，若此解不符合整数要求，则去掉不包含整数 解的部分可行域，将可行域D分成D1和D2两部分（分枝） ， 然后分别求解这两部分可行域对应的线性规划，如果它们的 解仍不是整数解，则继续去掉不包含整数解的部分可行域， 将可行域D1或D2分成D3与D4两部分，再求解D3与D4对应 的线性规划，在计算中若已得到一个整数可行解X0，则以该 解的目标函数值Z0作为分枝的界限，如果某一线性规划的目 标值Z≤ Z0，就没有必要继续分枝，因为分枝（增加约束） 的结果所得的最优解只能比Z0 更差。反之若Z＞Z0 ，则该 线性规划分枝后，有可能产生比 Z0更好的整数解，一旦真 的产生了一个更好的整数解，则以这个更好的整数解目标值 作为新的界限，继续进行分枝，直至产生不出更好的整数解 为止。§1 整数规划的分支定界法去掉整数约束， 转化为线性规划分支：将一个线性规划分成 两个可行域互不重叠的线性规划求解每个分支的线性规划最优解否是否求出 整数最优解是该分支的求解结束， 最优值作为界限§1 整数规划的图解法用分枝定界法求解整数规划问题（用图解法计算）max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 ? 1 2 ? ?4 ? x1 ? ? x1 , x2 ? 0且全为整数记为（IP）解：首先去掉整数约束，变成一般线性规划问题max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 ? 1 2 ? ?4 ? x1 ? ? x1 , x2 ? 0记为（LP）§1 整数规划的图解法用图解法求（LP）的最 优解，如图所示。 x23⑶ x1 ? 4⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 ? 1 2 ? ?4 ? x1 ? ? x1 , x2 ? 03x1 ? 5x2 ? Zx1§1 整数规划的图解法x1＝18/11, x2 =40/11Z(0) =218/11≈(19.8) 即Z 也是（IP）最大值的上限。5x1 ? 6 x2 ? 30x23⑵⑴ x1 ? x2 ? ?2(18/11,40/11)⑶ x1 ? 4max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 ? 1 2 ? ?4 ? x1 ? ? x1 , x2 ? 03x1 ? 5x2 ? Zx1§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8§1 整数规划的图解法x1＝18/11, x2 =40/11Z(0) =218/11≈(19.8)即Z 也是（IP）最大值的上限。 对于x1＝18/11≈1.64， 取值x1 ≤1， x1 ≥2 对于x2 =40/11 ≈3.64， 取值x2 ≤3 ，x2 ≥4 先将（LP）划分为（LP1）和 （LP2）,取x1 ≤1, x1 ≥2x23⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2(18/11,40/11)⑶ x1 ? 43x1 ? 5x2 ? Zx1§1 整数规划的图解法先将（LP）划分为（LP1）和（LP2）,取x1 ≤1, x1 ≥2，有下式：max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP1) ? x1 ?4 ? x ?1 1 ? ? ? x1 , x2 ? 0max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP 2) ? x1 ?4 ? x ?2 1 ? ? ? x1 , x2 ? 0现在只要求出（LP1）和（LP2）的最优解即可。§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8x1≤1LP1 x1=？, x2=？ Z(1) ＝？x1≥2LP2 x1=？, x2=？ Z(2) ＝？§1 整数规划的图解法先求（LP1）,如图所示。max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP1) ? x1 ?4 ? x ?1 ? 1 ? ? x1 , x2 ? 0x23⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2A⑶ x1 ? 4113x1 ? 5x2 ? Zx1§1 整数规划的图解法先求（LP1）,如图所示。max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP1) ? x1 ?4 ? x ?1 ? 1 ? ? x1 , x2 ? 0x23⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 AB⑶ x1 ? 4此时B 在点取得最优解。 x1＝1, x2 =3, Z(1)＝16113x1 ? 5x2 ? Zx1§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=？, x2=？ Z(1) ＝？ x1≥2 LP2 x1=？, x2=？ Z(2) ＝？§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=1, x2=3 Z(1) ＝16 x1≥2 LP2 x1=？, x2=？ Z(2) ＝？§1 整数规划的图解法求（LP2） ,如图所示。max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP 2) ? x1 ?4 ? x ?2 ? 1 ? ? x1 , x2 ? 0x23⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 AB ⑶ x1 ? 4113x1 ? 5x2 ? Zx1§1 整数规划的图解法求（LP2） ,如图所示。max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP 2) ? x1 ?4 ? x ?2 ? 1 ? ? x1 , x2 ? 0x23⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 ABC ⑶ x1 ? 4在C 点取得最优解。1即x1＝2, x2 =10/3,Z(2) ＝56/3≈18.71 3x1 ? 5x2 ? Zx1§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8x1≤1 LP1 x1=1, x2=3 Z(1) ＝16 x1≥2 LP2 x1=？, x2=？ Z(2) ＝？§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8x1≤1 LP1 x1=1, x2=3 Z(1) ＝16 x1≥2 LP2 x1=2, x2=10/3 Z(2) ＝18.7找到整数解， 此枝停止计算§1 整数规划的图解法求（LP2） ,如图所示。max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP 2) ? x1 ?4 ? x ?2 ? 1 ? ? x1 , x2 ? 05x1 ? 6 x2 ? 30 ⑵x2⑴ x1 ? x2 ? ?2 A3BC ⑶ x1 ? 4在C 点取得最优解。 即x1＝2, x2 =10/3,1Z(2) ＝56/3≈18.71x1 ? 5x2 ? Z3x1∵Z2 &Z1＝16 ∴原问题可能有比（16）更大的最优解， 但 x2 不是整数，故利用 x2 ≤3 ， x2 ≥4 加入条件。§1 整数规划的图解法（LP）划分为（LP1）和（LP2）,x1 ≤1, x1 ≥2 max Z ? x1 ? 5 x2 max Z ? x1 ? 5 x2? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP1) ? x1 ?4 ? x ?1 1 ? ? ? x1 , x2 ? 0? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 1 2 ? ? ( LP 2) ? x1 ?4 ? x ?2 ? 1 ? ? x1 , x2 ? 0§1 整数规划的图解法对于LP2,加入条件： x2≤3, x2≥4 有下式： max Z ? x1 ? 5 x2 max Z ? x1 ? 5 x2? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? ?4 ? x1 ( LP 21) ? ?2 ? x1 ? x2 ?3 ? ? ? x1 , x2 ? 0? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? ?4 ? x1 ( LP 22) ? ?2 ? x1 ? x2 ?4 ? ? ? x1 , x2 ? 0只要求出（LP21）和（LP22）的最优解即可。§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=1, x2=3 Z(1) ＝16找到整数解， 此枝停止计算x1≥2 LP2 x1=2, x2=10/3 Z(2) ＝18.7 x2≤3 x2≥4LP21 x1=？, x2=？ Z(21) ＝？LP22 x1=？, x2=？ Z(22) ＝？§1 整数规划的图解法先求（LP21）,如图所示。 xmax Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? ?4 ? x1 ( LP 21) ? ?2 ? x1 ? x2 ?3 ? ? ? x1 , x2 ? 0⑵25x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 A3BC⑶ x1 ? 4113x1 ? 5x2 ? Zx1§1 整数规划的图解法先求（LP21）,如图所示。 xmax Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? ?4 ? x1 ( LP 21) ? ?2 ? x1 ? x2 ?3 ? ? ? x1 , x2 ? 0⑵25x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 A3BCD ⑶ x1 ? 41此时D 在点取得最优解。即 x1＝12/5=2.4, x2 =3,Z(21)＝87/5=17.413x1 ? 5x2 ? Zx1§1 整数规划的图解法求（LP22），如图所示。 x2 无可行解，不再分枝。max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? ?4 ? x ( LP 22) ? 1 ?2 ? x1 ? x2 ?4 ? ? ? x1 , x2 ? 0⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 A3BCD⑶ x1 ? 4113x1 ? 5x2 ? Zx1§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=1, x2=3 Z(1) ＝16找到整数解， 此枝停止计算x1≥2 LP2 x1=2, x2=10/3 Z(2) ＝18.7 x2≤3 x2≥4LP21 x1=？, x2=？ Z(21) ＝？LP22 x1=？, x2=？ Z(22) ＝？§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=1, x2=3 Z(1) ＝16找到整数解， 此枝停止计算x1≥2 LP2 x1=2, x2=10/3 Z(2) ＝18.7 x2≤3 x2≥4LP21 x1=2.4, x2=3 Z(21) ＝17.4LP22 无可 行解§1 整数规划的图解法（LP21）,如图所示， 在D点取 x2 得最优解。 即 x1＝12/5=2.4, x2 =3,⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 AZ(3)＝87/5=17.4x1＝2.4不是整数，可继续分枝。 即 x1≤2， x1 ≥33BCD⑶ x1 ? 4113x1 ? 5x2 ? Zx1§1 整数规划的图解法max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? ?4 ? x1 ( LP 21) ? ?2 ? x1 ? x2 ?3 ? ? ? x1 , x2 ? 0max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? ?4 ? x1 ( LP 22) ? ?2 ? x1 ? x2 ?4 ? ? ? x1 , x2 ? 0§1 整数规划的图解法在（LP21）的基础上继续分枝。加入条件x1≤2， x1 ≥3有下式：max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? x1 ?4 ? ( LP 211) ? x1 ?2 ? x ?3 ? 2 ? x1 ?2 ? ? x1 , x2 ? 0max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? x1 ?4 ? ( LP 212) ? x1 ?2 ? x ?3 ? 2 ? x1 ?3 ? ? x1 , x2 ? 0只要求出（LP211）和（LP212）的最优解即可。§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8x1≤1LP1 x1=1, x2=3 Z(1) ＝16找到整数解， 此枝停止计算x1≥2LP2 x1=2, x2=10/3 Z(2) ＝18.5x2≤3LP21 x1=2.4, x2=3 Z(21) ＝17.4 x1≥3 LP212 x1=？, x2=？ Z(212) ＝？x2≥4LP22 无可 行解 ＃x1≤2 LP211 x1=？, x2=？ Z(211) ＝？§1 整数规划的图解法先求（LP211）max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? x1 ?4 ? ( LP 211) ? x1 ?2 ? x ?3 ? 2 ? x1 ?2 ? ? x1 , x2 ? 05x1 ? 6 x2 ? 30 ⑵x23B⑴ x1 ? x2 ? ?2 A C D ⑶ x1 ? 4113x1 ? 5x2 ? Zx1§1 整数规划的图解法先求（LP211）max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ? ?5 x1 ? 6 x2 ? 30 ? x1 ?4 ? ( IP 211) ? x1 ?2 ? x ?3 ? 2 ? x1 ?2 ? ? x1 , x2 ? 0且为整数5x1 ? 6 x2 ? 30 ⑵x23 B⑴ x1 ? x2 ? ?2AC E D⑶ x1 ? 41如图所示，此时E 在点取得最优解 即 x1＝2, x2 =3, Z(211)＝1713x1 ? 5x2 ? Zx1§1 整数规划的图解法求（LP212）max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? x1 ?4 ? ( LP 212) ? x1 ?2 ? x ?3 ? 2 ? x1 ?3 ? ? x1 , x2 ? 0x23⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2 ABC ED ⑶ x1 ? 4113x1 ? 5x2 ? Zx1§1 整数规划的图解法求（LP212）max Z ? x1 ? 5 x2 ? x1 ? x2 ? ?2 ?5 x ? 6 x ? 30 2 ? 1 ? x1 ?4 ? ( LP 212) ? x1 ?2 ? x ?3 ? 2 ? x1 ?3 ? ? x1 , x2 ? 0x23⑵5x1 ? 6 x2 ? 30⑴ x1 ? x2 ? ?2ABC ED F ⑶ x1 ? 4如图所示。此时 F在点取 得最优解。 x1＝3, x2 =2.5, Z(212)＝31/2=15.5113x1 ? 5x2 ? Zx1§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=1, x2=3 Z(1) ＝16找到整数解， 此枝停止计算x1≥2 LP2 x1=2, x2=10/3 Z(2) ＝18.5 x2≤3 LP21 x1=2.4, x2=3 Z(21) ＝17.4 x1≥3 LP212 x1=3, x2=5/2 Z(212) ＝15.5 ＃ x2≥4 LP22 无可 行解 ＃x1≤2 LP211 x1=2, x2=3 Z(211) ＝17找到整数解， 此枝停止计算§1 整数规划的图解法LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=1, x2=3 Z(1) ＝16找到整数解， 此枝停止计算x1≥2 LP2 x1=2, x2=10/3 Z(2) ＝18.5 x2≤3 LP21 x1=2.4, x2=3 Z(21) ＝17.4 x1≥3 LP212 x1=3, x2=5/2 Z(212) ＝15.5 ＃ x2≥4 LP22 无可 行解 ＃找到 最优 解x1≤2 LP211 x1=2, x2=3 Z(211) ＝17找到整数解， 此枝停止计算至此，原问 题（IP）的最优 解为：LP x1=18/11, x2=40/11 Z(0) ＝19.8 x1≤1 LP1 x1=1, x2=3 Z(1) ＝16 ＃ x1≥2 LP2 x1=2, x2=10/3 Z(2) ＝18.5 x2≤3 LP21 x1=2.4, x2=3 Z(21) ＝17.4 x1≥3 x2≥4 LP22 无可 行解 ＃x1=2， x2 =3, Z* = Z(211) ＝17以上的求解过程 可以用一个树形 图表示如右：x1≤2LP211 x1=2, x2=3 Z(211) ＝17 ＃LP212 x1=3, x2=5/2 Z(212) ＝15.5 ＃练习：用分枝定界法求解整数规划问题 （图解法）m axZ ? x1 ? x 2 ?14x1 ? 9 x 2 ? 51 ? ? ? 6 x1 ? 3 x 2 ? 1 ? x , x ? 0且全为整数 ? 1 2LP x1=3/2, x2=10/3 Z(0) ＝29/6 x1≤1 LP1 x1=1, x2=7/3 Z(1) ＝10/3 x2≤2x1≥2 LP2 x1=2, x2=23/9 Z(2) ＝41/9 x2≥3 LP22 无可 行解 x1≥3 LP212 x1=3, x2=1 Z(212) ＝4 ＃ ＃LP21 x1=33/14, x2=2 Z(21) ＝61/14 x1≤2 LP211 x1=2, x2=2 Z(211) ＝4 ＃§2 整数规划的计算机求解? 利用Excel求解整数线性规划问题时，只需在约束 条件中添加整数约束的条件，如下图所示例1的数学模型利用Excel的求解结果为甲装4件，乙装2 件，最大的利润为14百元§3 整数规划的应用一、投资场所的选择 例2、京成畜产品公司计划在市区的东、西、南、北四区 建立销售门市部，拟议中有10个位置 Aj (j=1,2,3,…,10)可供选 择，考虑到各地区居民的消费水平及居民居住密集度，规定: 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。A1A2A3A4 80A5 70A6 90A7 80A8A9A10投资额 100 120 150140 160 18036 40 50 22 20 30 25 48 58 61 利润 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的， 预测情况见表所示 (单位：万元)。但投资总额不能超过720万 元，问应选择哪几个销售点，可使年利润为最大?A1 利润 36A2 40A3 50A4 80 22A5 70 20A6 90 30A7 80 25A8 48A9 58A10 61投资额 100 120 150140 160 180解：设：0--1变量 xi = 1 (Ai 点被选用)或 0 (Ai 点没被选用)。 这样我们可建立如下的数学模型： Max z=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤ 720x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 且xj 为0--1变量，i = 1, 2, 3, … ,10例 3 、解决某市消防站的布点问题，该城市有 6 个区， 每个区都可以建消防站。市政府希望设置的消防站 最少，但必须满足在城市的任何地区发生火警时， 消防车要在 15 分钟内赶到现场。据实地测定，各区 之间消防车行驶的时间如下表所示，请帮助该市制 定一个最省的计划。 1 2 3 4 5 6 1 0 10 16 28 27 20 2 10 0 24 32 17 10 3 16 24 0 12 27 21 4 28 32 12 0 15 25 5 27 17 27 15 0 14 6 20 10 21 25 14 0设 xi =1,0; 1－i 区建消防站，0－i 区不建消 防站，i=1,…6 min z = x1 + x2 + x3 + x4 + x5 + x6 s.t. x1 + x2 ≥1, x1 + x2 + x6 ≥1, x3 + x4 ≥1, 1 2 3 4 5 6 1 0 10 16 28 27 20 x3 + x4 + x5 ≥1 2 10 0 24 32 17 10 x4 + x5 + x6 ≥1, 3 16 24 0 12 27 21 x2 + x5 + x6 ≥1 4 28 32 12 0 15 25 xi = 0, 1; i=1,…6 5 27 17 27 15 0 146 20 10 21 25 14 0§3 整数规划的应用0/1背包问题背包可装入10单位体积物品。若背包中每件物 品至多只能装一个，怎样才能使背包装的物品价值 最高。物品 名称 体积 价值12平板电脑mp3226334 5照相机休闲食品 衣服65 554 6物品1 2 3 4名称平板电脑 mp3 照相机 休闲食品体积2 2 6 5价值6 3 5 45衣服56解：xi为是否带第 i 种物品 Max Z=6x1 + 3x2 +5x3+4x4 +6x52x1+2x2 +6x3 +5x4 +5x5 ? 10xi为0, 1动态规划简介在多阶段决策问题中，各个阶段采取的决策， 一般来说是与时间有关的，决策依赖于当前状态，又 随即引起状态的转移，一个决策序列就是在变化的状 态中产生出来的，故有“动态”的含义，称这种解决 多阶段决策最优化问题的方法为动态规划方法。动态规划简介动态规划是运筹学的一个分支。与其说动态规 划是一种算法，不如说是一种思维方法来得更贴切。 因为动态规划没有固定的框架，即便是应用到同一道 题上，也可以建立多种形式的求解算法。许多隐式图 上的算法，例如求单源最短路径的Dijkstra算法、广 度优先搜索算法，都渗透着动态规划的思想。 因此，动态规划不像深度或广度优先那样可以 提供一套模式，需要的时候，取来就可以使用；它必 须对具体问题进行具体分析处理，需要丰富的想象力 去建立模型，需要创造性的思想去求解。0/1背包问题的动态规划解法0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变 量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了 (x1, …, xi-1)，在决策xi时，问题处于下列两种状态之一：a.背包容量不足以装入物品i，则xi=0背包不增加价值；b.背包容量可以装入物品i，则xi=1背包的价值增加了vi，若xi=0 则背包不增加价值这两种情况下背包价值的最大者应该是对 xi决策后的背包价值。 令V(i, j)表示在前i(1≤i≤n)个物品中能够装入容量为 j（1≤j≤C） 的背包中的物品的最大值，则可以得到如下动态规划函数： V(i, 0)= V(0, j)=0 （式3）j ? wi ?V (i ? 1, j ) （式4） V (i, j ) ? ? V (i ? 1, j ), V (i ? 1, j ? wi ) ? vi } j ? wi ?max{式3表明：把前面i个物品装入容量为0的背包和把0个物品装入 容量为j的背包，得到的价值均为0。式4的第一个式子表明：如 果第i个物品的重量大于背包的容量，则装入前i个物品得到的 最大价值和装入前i-1个物品得到的最大价值是相同的，即物品 i不能装入背包；第二个式子表明：如果第i个物品的重量小于 背包的容量，则会有以下两种情况：（1）如果把第i个物品装 入背包，则背包中物品的价值等于把前i-1个物品装入容量为jwi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物 品没有装入背包，则背包中物品的价值就等于把前i-1个物品装 入容量为j的背包中所取得的价值。显然，取二者中价值较大者 作为把前i个物品装入容量为j的背包中的最优解。第一阶段，只装入前1个物品，确定在各种情况下的背包能够得 到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得 到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最 大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推， 如果V(n,C)&V(n-1,C)，表明第n个物品被装入背包，前n-1个物 品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背 包，前n-1个物品被装入容量为C的背包中。依此类推，直到确 定第1个物品是否被装入背包中为止。由此，得到如下函数：0 ? x