运筹学胡运权第1章.ppt

《运筹学胡运权第1章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学(OperationsResearch)一、古代朴素的运筹学思想例如：田忌赛马二、运筹学的起源国外英文原名OperationsResearch简称“O.R.”直译为：运用研究或作业研究正式出现于1938年7月英国一份关于防空作战系统运行的研究报告中二战后运筹学的发展经历了三个阶段绪论国内1956年成立第一个运筹学小组1957年从“夫运筹策帷幄之中，决胜于千里之外”中摘取“运筹”二字，将O.R.正式翻译为“运筹学”三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供优化决策方案。研究对象：复杂系统的组织和管理参考《大英百科全书》、《辞海

2、》、《中国企业管理百科全书》等。四、运筹学研究的基本特点系统的整体优化多学科的配合模型方法的应用五、运筹学研究的基本步骤分析与表述问题建立数学模型对问题求解对模型和模型导出的解进行检验建立对解的有效控制方案的实施六、本课程的主要学习内容第一章线性规划及单纯形法第二章线性规划的对偶理论第三章运输问题第四章整数规划与分配问题第六章图与网络分析第一章线性规划及单纯形法LinearProgrammingandSimplexMethodxa此为无约束的极值问题§1.1一般线性规划问题的数学模型1-1问题的提出例1用一块边长为a的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？解：

3、如图设四个角上减去的小正方形边长为x，则容器体积为：时，容积最大例2常山机器厂生产I、II两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：如何安排生产才能使总的利润最大？单位产品消耗设备工时III设备工时限量（小时）设备A设备B设备C240205121615单位利润（元）23解：设计划期内两种产品的数量分别为x1，x2，则总利润为：maxz=2x1+3x22x1+2x2124x1165x215x10，x20简记为：s.t.（约束于：）z=2x1+3x2在满足限制条件下求z的最大值。此为

4、有约束极值问题1-2线性规划问题的数学模型原型模型数学模型提炼数学工具1、原型：现实世界中人们关心、研究的实际对象。模型：将某一部分信息简缩、提炼而构造的原型替代物。数学模型：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。3、规划问题数学模型的三要素（2）目标函数：问题要达到的目标要求，表示为决策变量的函数。用z=f(x1，x2，…，xn)表示。（1）决策变量：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用x1，x2，…，xn表示。（3）约束条件：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等

5、式或不等式。2、规划问题即求目标函数在若干约束条件下的最值。4、线性规划问题（LinearProgramming）的数学模型（2）一般形式：（1）条件：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为“L.P.”max(或min)z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（=，≥）b1a21x1+a22x2+…+a2nxn≤（=，≥）b2…am1x1+am2x2+…+amnxn≤（=，≥）bmx1,x2,…,xn≥0（3）其他形式：连加形式向量形式其中称为价值行向量；决策列向量系数列向量右端列向量矩阵形式其中称为价值行向量；决策列向量

6、右端列向量约束矩阵或系数矩阵1-3线性规划问题的标准形式1、标准形式或2、条件目标函数求极大值约束条件全是等式（线性方程组）决策变量全非负右端常数全非负3、标准化方法（1）若目标函数求极小值，即则令转化为（2）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。注意：松弛变量在目标函数中系数全为0。约束为≥不等式，减去松弛变量，化为等式约束条件；约束为≤不等式，加上松弛变量，化为等式约束条件。多退少补例：maxz=2x1+3x22x1+2x2124x1165x215x10，x20s.t.标准化（3）若决策变量xj≤0，则令（4）若决策变量xj取

7、值无限制，则令（5）若约束等式的右端常数bi≤0，则等式两边同时乘以“-1”。其中（“一分为二”）例：将下列线性规划模型化为标准形式。则问题化为标准形式：并引入松弛变量x4,x5,1-4线性规划问题的解已知线性规划的标准形式：或1、求解线性规划问题：从满足（2）、（3）的方程组中找出一个解使目标函数（1）达到最大值。2、可行解：所有可行解的集合。可行域：满足约束条件（2）、（3）的解。记做最优解：使目标函数达到最大值的可