管理运筹学教案1_绪论及线性规划模型【企业经营管理推荐】

1、赵 鹏 徐 彬 ：51687005办公地点：8711邮箱2022-3-20管理运筹学课程组21 运筹学的由来一、绪论 2022-3-20管理运筹学课程组32022-3-20管理运筹学课程组42022-3-20管理运筹学课程组5重要事件: 古代朴素的运筹思想 1917年爱尔朗的排队论公式。 1939年英国成立第一个运筹学工作小组，从事防空预警系统的研制（研究如何合理运用雷达），使原先平均击落一架敌机要发2万发炮弹改善为只要发4千发炮弹。 1939年前苏联的康托洛维奇提出类似线性规划模型， 1960年最佳资源利用的经济计算,获诺贝尔奖。 1942年美国成立运筹学工作小组,研究战斗行动效能,行动方式

2、。 1947年美国数学家，提出线性规划模型及单纯形算法 战争结束，Mores和Kimball合著第一部专著“运筹学的方法”。 战后，运筹学的应用领域从军事扩展到其它各领域。2022-3-20管理运筹学课程组6学会组织 1948年英国成立运筹学学会 1952年美国成立运筹学学会 1956年法国成立运筹学学会 1959年英、美、法成立运筹学联合会 我国50年代引入运筹学，1982年加入世界运筹学联合会(1956年时曾使用“运用学”，57年定名为“运筹学”)2022-3-20管理运筹学课程组72 运筹学的性质和内容 由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供

3、解答，为该系统的总目标服务的学科。钱学森 运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、资金等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”英国运筹学会 运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。近代运筹学工作者1.运筹学的定义 “运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。” 与2022-3-20管理运筹学课程组82.特点(1)运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行

4、业、部门之限制；(2)运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；(3)它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。 2022-3-20管理运筹学课程组9 规划论线性规划、目标规划、非线性规划、 整数规划、动态规划、组合规划等 图与网络 存储论 排队论 对策论 决策论 仿真 马尔科夫过程 可靠性 多目标规划 2022-3-20管理运筹学课程组103

5、 运筹学的工作步骤1. 提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；2. 建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来； 3. 求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；4. 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；5. 解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。2022-3-20管理运筹学课程组114 本课程的要求本课程的授课对象是管

6、理科学与工程类及交通运输类专业本科生，属管理类专业技术基础必修课。 学生通过学习该课程，应了解管理运筹学对优化决策问题进行定量研究的特点，理解线性规划、整数规划、动态规划、图与网络、排队论等分支的基本优化原理，掌握其中常用的模型和算法，具有一定的建模能力。 先修课程主要为线性代数和概率统计，学生对它们的掌握程度直接影响本课程的学习，所以要求学生课前要做必要的复习。 学习方法：理解、掌握基本理论和方法的基础上，适当作些习题。 参考书：其他版本的管理运筹学 二. 线性规划 (LP )( Linear Programming)本部分是课程的最重要部分2022-3-20管理运筹学课程组13本本节节重重

7、点点：线线性性规规划划模模型型的的特特点点线线性性规规划划解解的的存存在在情情况况线线性性规规划划标标准准型型线线性性规规划划解解的的基基本本概概念念（特特别别是是基基解解和和基基可可行行解解）1 线性规划问题及其数学模型第一章 线性规划与单纯形法2022-3-20管理运筹学课程组141.1 问题的提出 例1某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和A、B两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？2022-3-20管理运筹学课程组15设设 x1、x2分别表示计划期内产品分别表示计划期内产品、的产量，、的产量， 建立数学模型：建立数学模型

8、： 设备台时设备台时 约束条件约束条件 s.t. x1 + 2x2 8 原材料原材料 A (Subject to) 4 x1 16 原材料原材料 B 4 x2 12 产品产量产品产量 x1，x2 0 可利用资源 设备 原材料 A 原材料 B140204 8 台时 16kg 12kg 利润23 ？元利润最大 目标函数 max z = 2x1+ 3x22022-3-20管理运筹学课程组16例2: 某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表404524332231 A B C单位产品利润单位产品橡胶量单位产品钢消耗量产品已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各

9、多少使总利润最大？解：设x1，x2， x3分别为A、B、C日产量，则有 约束条件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30称x1，x2 ，x30为决策变量 目标函数： max z=40 x1+45x2 +24x32022-3-20管理运筹学课程组172万m31.4万m32022-3-20管理运筹学课程组18 设设 x1、x2 分别为第一、第二化工厂每天处理的工业污水量。分别为第一、第二化工厂每天处理的工业污水量。约束条件：约束条件： 第一化工厂到第二化工厂之间的污水含量要不大于第一化工厂到第二化工厂之间的污水含量要不大于 0. .

10、2 2% % (2 -(2 - x1) / 500 2 / 1000 流经第二化工厂后，河流中的污水含量仍不大于流经第二化工厂后，河流中的污水含量仍不大于 0. .2 2% %0.0. 8(2 -8(2 - x1) + ( (1. .4-4- x2) / 700 2 / 1000 污水处理量限制污水处理量限制 x1 2，x2 1. .4 4，x1 0，x2 0目标函数：目标函数： 要求两厂用于处理工业污水的费用最小要求两厂用于处理工业污水的费用最小 min z = 1000 x1+800 x22万m31.4万m32022-3-20管理运筹学课程组192022-3-20管理运筹学课程组20202

11、2-3-20管理运筹学课程组21 线线性性规规划划模模型型的的一一般般形形式式为为： max(min) z =c1x1 + c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn ( = , ) b1 a21x1 + a22x2 + a2nxn ( = , ) b2 ( (1 1.2 2) ) am1x1 + am2x2 + amnxn ( = , ) bm x1，x2，xn 0 (1.3) 求求解解线线性性规规划划问问题题的的任任务务是是：在在满满足足(1.2)、(1.3) 的的所所有有(x1，x2，xn)（可可行行解解）中中求求出出使使(1.1)达达到到最

12、最大大(小小)z 值值的的决决策策变变量量值值(x1*，x2*，xn*)（最最优优解解） 。2022-3-20管理运筹学课程组22例例 1 max max z z = 2 = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 2022-3-20管理运筹学课程组23max max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q24.向着目标函数的优化方向平移等值线，直至得到

13、等值线与可行域的最后交点，这种点就对应最优解。 2022-3-20管理运筹学课程组24线性规划问题解的存在情况：(1)存在唯一最优解max max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例12022-3-20管理运筹学课程组25（2）有无穷多最优解 若将例1目标函数变为 max z = 2x1+ 4x2，则问题变得存在无穷多最优解。如图max max z z = 2 = 2x1+ 4x2s.t. x1 + 2 x

14、2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q22022-3-20管理运筹学课程组26（3）有无界解( 无有限最优解或无最优解 ) z（4）无可行解（可行域为空集）注意：没有存在有限多个解的情况可行域有界时必有最优解，无界时不一定无最优解2022-3-20管理运筹学课程组27 用图解法求下面问题的解m ma ax x z z = = 2 2x1+ 2x2 s.t. x1 - x2 -1 -0.5x1 + x2 2 x1，x2 0 1m ma ax x z z = = x1+ x2 s.

15、t. x1 - x2 0 3x1 - x2 -3 x1，x2 0 2无界不可行2022-3-20管理运筹学课程组2813 线性规划问题的标准形式 为了求解LP问题，必须统一其模型，本课程选用标准型式为max z =c1x1 + c2x2 + cnxn (1.1)s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = bm x1，x2，xn 0 (1.3)其中bi 0，（i =1，2，m）一般m 0。2022-3-20管理运筹学课程组29标准型的简写形式:max z =c1x

16、1 + c2x2 + cnxn (1.1)s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = bm x1，x2，xn 0 (1.3) njjjxczmax1 njijijbxa1 m1,2,.,i n,.,jxj210 用求和符号表示2022-3-20管理运筹学课程组30用矩阵描述为： max z =CX AX = b X 0= (P1，P2，Pn)；a11 a12 a1na21 a22 a2n am1 am2 amnA=称 A 为约束条件的m n 阶系数矩阵，一般A的

17、秩为m。0 =0002022-3-20管理运筹学课程组31用向量表示： n,jxbxPCXzmaxjnjjj101 其其中中: : )c ,c ,c(Cn21 X=x1x2xnPj =a1ja2jamjb=b1b2bm向 量 Pj 对 应 的 决 策 变 量 为 xj 。2022-3-20管理运筹学课程组32b1b2 bm (p1,p2, ,pn)Pjxj=b a11 a12 a1n a21 a22 a2n am1 am2 amnx1x2 xn=xj0 j=1,nx1x2 xnMax z=x1x2 xn (c1 , c2, ,cn )=cjxj=CX=aijxj =bi i=1,mAX = b

18、 X 0 b2022-3-20管理运筹学课程组33 将一般形式化为标准型式将一般形式化为标准型式将目标函数最小化变为求目标函数最大化将目标函数最小化变为求目标函数最大化 min z = CX max z = -C= -CX，其中，其中 z = =- - z ；将将不不等等式式约约束束变变为为等等式式约约束束 njnjimiimjijijijxbxxabxa110 ( 松松弛弛变变量量 ) 011 imnjnjiimjijijijxbxxabxa（剩剩余余变变量量 ）将将负负约约束束、无无符符号号约约束束变变量量变变为为非非负负约约束束变变量量 xj 0 xj = =- - xj ， xj 0

19、xj 为为无无符符号号约约束束变变量量 xj = xj - - xj , , xj 0, xj 0 2022-3-20管理运筹学课程组34 x1 + 2 x2 84 x1 16 4 x2 12x1，x2 0 max z = 2x1+ 3x2 + 0 x3 + 0 x4+ 0 x5标准型：例3将例1的数学模型化为标准型。 max z = 2x1+ 3x2 所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有利润，在目标函数中其系数应为零；即c3 ，c4 ，c5 = 0。 x1+ 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 + x5 =12 x1，x2，x3，x4，x5 02022-3-20管理运筹学课程组35 x1 + x2 + x3 7 x1 x2 + x3 23 x1+ x2 +2 x3 = 5x1，x2 0，x3为无符号约束例4将下述线性规划问题化为标准型 min z = x1 +2x2 3x3解：用x4 - x5 替换x3 ，令z = -z x1 +