下载文档原格式
运筹学讲稿一、运筹学的简史运筹学的早期工作及其历史可追溯到1914年，当时兰彻斯特（Lanchester）提出了军事运筹学的战斗方程；1917年，丹麦工程师埃尔朗（Erlang）在哥本哈根电话公司研究电话通信系统时，提出了排对论的一些著名公式；20世纪20年代初提出了存储论的最优批量公式.1947年美国数学家丹西格（G..B.Danting）在解决美国空军军事规划问题时，提出了线性规划及单纯形法.早在1939年，前苏联学者康托洛维奇（JT.B.KaHTopobny）在解决工业生产组织和计划问题时，已提出了类似线性规划模型，并给出了“解乘数法”的求解法.可惜当时未被重视.运筹学作为一门科学诞生于20世纪30年代末期，通常认为运筹学的活动是第二次世界大战早期从军事部门开始的.当时，英国为了研究“如何最好的运用空军及新发明的雷达保卫国家”，成立了一个由各方面的专家组成的交叉学科小组，即最早的运筹小组.进行“作战研究”（Operational,research），后来中文译名为“运筹学”.（我国在1956年用过运用学的名词，到1957年正式定名为运筹学）.第二次世界大战期间，英、美军队中的运筹学小组研究诸如护航舰队保护商对的编队问题；当船队遭受德国潜艇的攻击时，如何使船队损失最小的问题，反潜深水炸弹的合理起爆深度问题；稀有资源在军队中的分配问题等.第二次世界大战后，特别是运筹学在军事上的显著成功，引起了人们的广泛的关注，运筹学很快深入到工业、商业、政府部门等，并得到了迅速发展.在20世纪50年代中期，钱学森、许国志等老教授全面介绍运筹学，并结合我国特点在国内推广应用.1957年，我国在建筑业和纺织业中首先应用运筹学；从1958年开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用.在解决邮递员合理投递线路时，管梅谷教授提出了国外称之为“中国邮路问题”的解法；从20世纪60年代起，运筹学在钢铁和石油部门开始得到了比较全面、深入的应用.从1965年起，统筹学法在建筑业和大型设备维修计划等方面的应用取得了可喜的进展；1970年在全国大部分省、市和部门推广优选法；70年代中期，最优化方法在工程设计界受到了广泛的重视，并在许多方面取得成果；排队论开始应用于矿山、港口、电信及计算机等方面；图论用于线路布置、计算机设计、化学物品的存放等；70年代后期,存储论在应用汽车工业等方面获得成功.在此期间，以华罗庚教授为首的一大批数学家加入到运筹学的研究队伍，使运筹学的很多分支很快跟上当时的国际水平.运筹学是一门应用科学，至今还没有统一且确切的定义. 参见：程理民《运筹学模型与方法教程》 钱颂迪主编《运筹学》，清华大学出版二、引例例1 某工厂生产甲、乙两种产品，生产每件产品需要原材料、能源消耗、劳动力及所获利如下表所示：现有库存原材料1400千克；能源消耗总额不超过2400百元；全厂劳动满员为2000人，试安排生产任务（生产甲、乙产品各多少件），使获得利润最大，并求出最大利润. [模型建立]设安排生产甲产品x 件，乙产品y 件，相应的利润为S ,则此问题的数学模型为：maxS=5x+6y s.t. 2x+3y ≦1400x+6y ≦2400 (1) 4x+2y ≦2000 x ≥0,y ≥0,x,y ∈Z这是一个整数线性规划问题.例2 某工厂有100台机器，拟分四期使用，在每一期中有生产任务1A ，2A 两种.设第k 个周期初有完好的机器k x 台，根据经验，若周期初把k u 、k x -k u 台机器分别投入任务1A ，2A ，则周期末分别有k u /3、k x -k u /10台机器作废（k=1，2，3，4），如果在一个生产周期中每一台机器执行任务1A 可收益10千元，执行任务2A 可收益7千元，问怎样分配机器使收益最大？试建立数学模型.[数学模型的建立] 按题设，k x ，k u （k=1、2、3、4）受约束于(subject to 简记为 s.t.）1+k x =32k u +109(k x -k u ),0≤k u ≤k x 且1x =100 第K 个周期收益10k u +7（k x -k u ），因此四个周期的总收益为 V=∑=41k （10k u +7（k x -k u ）），于是问题的数学模型为：Max V=∑=41k （10k u +7(k x -k u ））s.t. 1+k x =32k u +109(k x -k u ) (2) 0≤k u ≤k x 且1x =100 ， k=1,2,3,4 这是一个分步决策，且为线性规划问题.例3 某投资者有5亿元，想取其中的一部分对项目1A ，2A 进行投资，设投资i x 亿元项目i A ,从历史资料来分析，投资于项目1A 和2A 分别有预期的年收益20%和16%.同时，与项目1A 和2A 有关的总的风险损失为2212221)(2x x x x +++ (记为Q) .试设计使预期的总收益R 最大而风险损失Q 尽可能的小的投资方案. [数学模型]此问题的数学模型为： Max R=0.21x +0.162x Min Q=2212221)(2x x x x +++ (3)s.t 21x x +≦5, 21,x x ≧0注意到：Min Q=Max(-Q),若投资者根据总收益与风险损失对自己的重要程度确定权系数，希望f=0.8R+0.2(-Q)最大，则数学模型为Max f=0.8(0.21x +0.162x )-0.2[2212221)(2x x x x +++] s.t 21x x +≦5, 21,x x ≧0 (4)三、数学模型的基本概念及解法1、概念① 在上面的数学模型（1）--（4）中，都是求函数的极值问题，象这样的在等式或不等式约束条件下求一元或多元函数的极值问题，称为数学规划问题.这个需要求极值的函数称为目标函数.数学规划问题中的自变量称为决策变量.② 在数学规划中，目标函数和约束条件中的函数式都是线性的，就称它为线性规划问题.否则就称非线性规划问题（至少有一个非线性的）. 如（1）（2）是线性规划；（4）是非线性规划.③ 早在1939年前苏联数学家康托洛维奇（JT.B.KaHTopobny ）和美国的希奇柯克（F.Litchcock ）等人就在生产组织管理和制定交通运输方案方面首先研究了和运用了线性规划方法.1947年，美国数学家丹西格（G..B.Danting ）提出了单纯行法，给出了求线性规划的上实用方法.④ 对于例3，数学规划（3）：在此数学规划问题中目标函数有多个，就称它为多目标规划问题.例如，全国大学生数学建模竞赛题96年A 题、98年A 题、98年B 题、03年B 题等都是多目标函数规划问题.⑤ 另外，目标函数，约束条件，出现“最多约能”；“约不能超过”.这种模糊概念、若至少出现一个，则就称相应的规划为模糊（数学）规划问题.⑥ 又如在(4)中，数学规划问题中，目标函数为二次函数，且约束条件中的函数式子是线性的，则称它为二次规划. ⑦线性规划的一般形式为∑==nj j j x c Z 1mins.t.()()()n j x b a x a b x a x a j m mn m n n,2,1.01111111=≥≥≤+≥≤++其中j i ij c b a ,,均为已知常数.矩阵表示:()0..min ≥≥≤=X b b AX t s CX Z 或⑧标准形式(矩阵)为..min ≥≤=X b AX t s CX Z (松弛度量,剩余度量)⑨线性规划问题中满足约束条件的解称为可行解,其全体称为可行域,使目标函数达到最小值(最大值)的可行解称为最优解,最优解对应的目标函数值勤称为最优值. 最优解为0X ,最优值为0CX . 2.重要结论 ① 若线性规划问题⑸存在可行域,则可行域为凸集.②若线性规划问题可行域有界，则最优解在可行域的顶点达到.3．数学规划的解法； ①． 解线性规划的单纯形法，（解法一）. ②．解法二 lindo 数学软件.Lindo ()()⎪⎪⎩⎪⎪⎨⎧.2.30,,50,100,200,,解线性非线性整数规划解线性整数规划个约束个变量解非线性规划个约束个变量二次规划线性规划Lingo lingo Gind lindo安装 A ：>install ↓ C: > . ；(表示进入状态) 例如 求 y x Z 32max +=s.t. 0.12531034≥≤+≤+y x y x y x.32max y x +? S T (或S.T 或Subject to) ? 1034<+y x ? 1253<+y x ? END : 运行 Go③． 图解法（线性规划）求例的数学模型.可行域为由；y x y x l by x l y x l 组成的凸五边形区域及.0,0.200024:,2400:,140032:321===+=+=+ 直线。
《运筹学》教案授课专业：信息管理、工程管理任课教师：黄健南通大学商学院2007．2教案用纸第 1 次课 3 学时上次课复习：无一、本次课题（或教材章节题目）：绪论1、运筹学的性质和特点2、运筹学的模型与工作步骤3、运筹学的应用与展望教学要求： 1、了解运筹学的性质和特点、运筹学的应用与展望2、运筹学的模型与工作步骤重点：运筹学工作步骤难点：无教学手段及教具：讲授讲授内容：1、运筹学的性质和特点2、运筹学的模型与工作步骤3、运筹学的应用与展望课后作业无同济大学出版社：运筹学教程参考资料高等教育出版社：管理运筹学注：本页为每次课教案首页教案用纸第 2 次课 3 学时上次课复习：运筹学的学科性质和发展概况运筹学的模型与工作步骤本次课题（或教材章节题目）：二、线性规划与目标规划第一章线性规划及单纯形法1、线性规划问题及其数学模型教学要求：1、通过实际问题引入线性规划模型，初步掌握建立线性规划模型的方法；2、通过图解法直观地理解线性规划解的状态和线性规划的基本性质；3、熟练掌握线性规划问题的标准化方法；4、理解基、基解，基可行解的概念。
重点：线性规划问题及其数学模型、标准形式难点：线性规划问题及其数学模型、线性规划问题解的概念教学手段及教具：讲授讲授内容：1、线性规划模型的建立2、线性规划问题的图解法3、线性规划问题的标准形式4、线性规划问题解的概念课后作业P44： 1.1、1.2、1.3、1.10同济大学出版社：运筹学教程参考资料高等教育出版社：管理运筹学注：本页为每次课教案首页教案用纸第 3 次课 3 学时上次课复习：1、线性规划模型的建立2、线性规划问题的图解法3、线性规划问题的标准形式4、线性规划问题解的概念本次课题（或教材章节题目）：2、线性规划问题的几何意义3、单纯形法4、单纯形法的计算步骤教学要求：1、了解线性规划问题的几何意义和基本性质2、理解单纯形法的理论基础，熟练掌握可行条件和优化条件；3、熟练掌握单纯形法的计算步骤重点：可行条件与优化条件。
《运筹学》教学大纲一、基本信息课程代码：2060241课程学分：3面向专业：物流管理课程性质：院级必修课开课院系：商学院物流管理系使用教材：教材《运筹学教程（第5版），胡运权，清华大学出版社，2018年》参考书目《运筹学习题集（第5版），胡运权，清华大学出版社，2019年》《管理运筹学（第2版），茹少峰，北京交通大学出版社，2017年》《运筹学（第3版），熊伟，机械工业出版社，2016年》《线性代数（第6版），同济大学数学系，高教出版社，2014年》《运筹学（第4版），运筹学教材组编写，清华大学出版社，2012年》先修课程：《高等数学（1）2100012（5）；高等数学（2）2100014（4）》二、课程简介运筹学是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具；它是抽象的数学理论和丰富多彩的实践相结合的“桥梁”；它为学生未来从事生产社会实践和应用科学研究的工作人员提供了完整的数学方法和广阔的应用领域。
通过课程学习，培养学生的逻辑思维能力、定量分析能力，使学生系统掌握运筹学的基本理论与方法，能够针对实际问题运用所学的知识建立运筹学的数学模型，并能够求解常用的运筹学数学模型，进而给出可行性解决方案。
同时，引导学生运用运筹学方法分析和解决在生产社会实践、企业运作管理以及规划等过程中面临的问题，启发学生将运筹学的理论方法与各自的专业知识结合起来，也为进一步学习其他专业课程提供必要的基础。
三、选课建议学习该课程前学生应该具有一定的高等数学及线性代数基础，同时对管理和经济学知识有所了解。
本课程适合商学院经管类专业，建议学生在第四至第七学期期间安排开设。
四、课程与专业毕业要求的关联性六、课程内容（一）第1单元绪论1.教学内容：1.1运筹学释义与发展简史1.2运筹学研究的基本特征与基方法1.3运筹学主要分支简介1.4运筹学与管理科学1.5运筹学算法与应用软件简介2.知识要求：2.1理论课时2①理解运筹学研究的基本特征。
运筹学课程讲义第一部分 线性规划 第一章 线性规划的基本性质 1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50元/个，椅子售价30元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4小时，油漆工2小时。
生产一个椅子需要木工3小时，油漆工1小时。
该厂每月可用木工工时为120小时，油漆工工时为50小时。
问该厂如何组织生产才能使每月的销售收入最大？213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m 、2.1m 、1.5m 的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m 。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型 1. 繁写形式 2. 缩写形式 3. 向量形式 4. 矩阵形式三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量x k 是自由变量，如何化为非负变量？4. 若原模型中变量x j 有上下界，如何化为非负变量？⎪⎪⎩⎪⎪⎨⎧≥≤-=--≤+--≥-+----=无约束321321321321321,0,052010651535765max x x x x x x x x x x x x x x x z 令'''3'3''3'331'1,0,,,Z Z x x x x x x x =-≥-=-=⎪⎪⎩⎪⎪⎨⎧≥-=+-++=+-+-=+-+-+--+-++-=0,,,,,,,5201010651533507765min 7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'x x x x x x x x x x x x x x x x x x x x x x x x Mx Mx x x x x x z 1. 2图解法该法简单直观，平面作图适于求解二维问题。
《运筹学》教案（本教案适用于32课时的班级）第一章线性规划与单纯形法1、教学计划第 1 次课 2 学时第 2 次课 2 学时第 3 次课 2 学时2、课件1.1线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。
例1：某工厂要安排生产Ⅰ、Ⅱ两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。
问应如何安排生产计划使工厂获利最多？解：设生产产品Ⅰ、Ⅱ的数量分别为1x 和2x 。
首先，我们的目标是要获得最大利润，即2132max x x z +=其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即8221≤+x x原材料约束：生产所用的两种原材料A 、B 不得超过所用有的原材料总数，即1641≤x1242≤x非负约束：生产的产品数必然为非负的，即0,21≥x x由此可得该问题的数学规划模型：⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0,1241648232max 21212121x x x x x x x x z总结：线性规划的一般建模步骤如下： （1）确定决策变量确定决策变量就是将问题中的未知量用变量来表示，如例1中的1x 和2x 。
确定决策变量是建立数学规划模型的关键所在。
（2）确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。
（3）确定约束条件将现实的约束用数学公式表示出来。
线性规划数学模型的特点（1）有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最小化。
（2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。
（3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函数最大或最小），从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是最优化问题。
《运筹学》课程教案2019-2020（ 1 ）学期授课教师： xxx授课专业：物流管理授课班级： xxxxx周学时： 3授课周数： 16xxxxxxxxxxx系第 一 章 教案教学目的和要求 教学目的：让学生对运筹学的基本概念有一个大致的了解 教学要求：要求学生能够课前预习教材内容 教学重 点难点教学重点：线性规划的图解法 教学难点：线性规划的标准形式教学内容第一章 线性规划的基本概念1.1线性规划问题及其数学模型1.1.1问题的提出1.1.2线性规划的一般数学模型 1.2线性规划的图解法1.2.1图解法的基本步骤适用于求解两个变量的线性规划问题 例4 利用例1说明图解法的主要步骤。
例1的数学模型为s.t.线性规划图解法的基本步骤：（1）建立以x 1,x 2为坐标轴的直角坐标系，画出线性规划 问题的可行域。
（2）求目标函数 Z=C 1x 1+C 2x 2 的梯度▽Z =（c 1,c 2）。
（3）任取等值线 C 1x 1+C 2x 2=Z 0, 沿梯度▽Z 正方向平移, （若是极小化问题，则沿负梯度方向-▽Z 平移）， 求等直线将离未离可行域时与可行域的交点。
121212112maxZ 5x 2x 30x 2 0x 160 5x x 15 x 4x 0, x 0=++≤⎧⎪+≤⎪⎨≤⎪⎪≥≥⎩第 二 章 教案教学目的和要求 使学生对于单纯形法有一定的了解，并且能够解决简单的关于单纯形法的问题。
教学重 点难点教学重点：单纯形法的一般原理 教学难点：表格单纯形法教学内容第二章 单纯形法2.1单纯形法的一般原理Dantzig 的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。
其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。
单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。
（2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。
《运筹学》教案（2014 年2 月）授课班级：2010级农林经济管理教材：《运筹学》，熊伟，机械工业出版社学分：4学分学时：64学时教学过程1.运筹学与线性规划基本概念（10分钟）2.应用模型举例（60分钟）生产计划问题、人员安排问题、合理用料问题、配料问题、投资问题教学过程3•线性规划的一般模型（10分钟）4.课堂练习（10分钟）5.课堂小结（5分钟）6.布置作业教学过程教学过程 1. 引例:（P41）两个模型的对应关系：（20分钟） 2. 线性规划的规范形式（10分钟） 3. 对偶模型（5分钟）4. 对称型对偶关系的一般形式（5分钟）5. 对称型对偶关系的一般形式（三个特点）（10分钟）非对称型对偶关系 对于非对称型且具有对偶关系的两个PL 问题，总结得出:定理：互为对偶的两个PL 问题，如果原问题中第k 个约束条件 是等式，则它的对偶规划中的第k 个变量无非负限制，反之亦然.线性规划的原始问题和对偶问题的对应关系可归纳为下表5. 6. 课堂小结，布置作业教学过程【性质1】（对称性）对偶问题的对偶是原问题。
（5分钟）【性质2】（弱对偶性）设F、r分别为LP（max）与DP （min）的可行解，则CX°<Y°b（10分钟）由性质2可得到下面几个推论：推论1：的任一可行解的目标值是（龙）的最优值下界；（龙）任一可行解的目标是（2乃的最优值的上界；推论2:在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解；推论3:若原问题可行且另一个问题不可行，则原问题具有无界解。
【性质3］（最优性）设F与尸分别是（2P）与（莎）的可行解，则F、尸是JLP）与（矿）的最优解当且仅当C X0 =卩呢（10分钟）【性质4】（对偶性）若互为对偶的两个问题其中一个有优解，则另一个也有最优解，且最优值相同。
（20分钟）教学过程由性质4还可推出另一结论：若（2P）与（矿）都有可行解，则两者都有最优解；若一个问题无最优解，则另一问题也无最优解。
