《浙江大学管理学院杜红duhongcmazjueducn讲解材料》由会员分享，可在线阅读，更多相关《浙江大学管理学院杜红duhongcmazjueducn讲解材料（118页珍藏版）》请在金锄头文库上搜索。
1、浙江大学管理学院 杜 红 ,管理科学方法（复习版）,狭义的管理科学：数理方法制定管理决策 Management Science = Operations research (MS=OR) 决策制定（主体、环境、过程） 定量分析（数学、概率、统计） 运筹方法（问题、建模、解决）,第一章 管理科学简介,第一章 管理科学简介,定性分析的方法 德尔菲方法 小组讨论 定量模型的运用 运筹模型,管理科学的方法论,第一章 管理科学简介,运筹方法解决典型管理问题,第三章 线性规划模型,线性规划问题模型的一般形式： 目标函数： 约束条件：,第三章 线性规划模型,线性规划问题的基本要求 目标函数和约束条件必须是线
2、性函数； 线性表达：相加性、比例性 决策变量的连续分布； 不限于整数，可以是小数，但不能四舍五入 目标函数的单一性； 多目标是要设法简化成单目标 模型必须是确定型的； 所有参数a、b、c都应是确定值 决策变量的非负性,第三章 线性规划模型,两个变量的线性规划问题的几何解释,Max z = X1+3X2 s.t. X1+ X26 -X1+2X28 X1 , X20,z=0,z=3,z=6,z=9,z=12,z=15.3,0 1 2 3 4 5 6,-8 -7 -6 -5 -4 -3 -2 -1,6 5 4 3 2 1,x1,x2,目标函数等值线 Z = X1+3X2,可行域,(4/3,14/3)
3、,例：求解以下线性规划问题,第三章 线性规划模型,对偶问题与影子价格 定义： 设以下线性规划问题 MAX Z = CTX s.t. AXb X0 为原始问题，则称以下问题 MIN W = bTY s.t. ATYC Y0 为原始问题的对偶问题，最优值Y为影子价格,第三章 线性规划模型,对偶问题与原始问题的关系,对偶问题的性质 对偶问题的对偶是原问题。 若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等(Z*=W*)，最优解满足CX*=Y*b。 若X*,Y*分别是原问题和对偶问题的可行解，则 X*,Y*为最优解的充分必要条件是Y*XL=0和YSX*=0。,第三章 线性规划模型,
4、原问题标准型： Max Z= CX AX + XL= b X,XL0,对偶问题标准型： Min W= Yb YA - YS= C Y,YS0,第三章 线性规划模型,原问题和对偶问题的互补松松弛关系：,第三章 线性规划模型,对偶问题求解举例： 对以下线性规划问题： MIN Z2X1X22X3 s.t. X1X2X34 X1X2KX36 X10，X2 0，X3 无约束 已知其最优解为 X1* =5 , X2* = 0 , X3* =1。 写出其对偶问题并求其最优解和 K 的值。,写出对偶问题： MAX W = 4Y1+6Y2 s.t. -Y1-Y2 2 Y1+Y2-1 Y1-KY2=2 Y20,根
5、据对偶性质： 4Y1+6Y2 = -12 -Y1-Y2 =2 Y1-KY2=2 Y1*=0,Y2*=-2,K=1,第三章 线性规划模型,对偶问题解影子价格 根据对偶问题的性质有： Z* = W* = bi yi* 两边对bi求偏导数得到： Z* = yi* (i= 1,2, ,m) bi 即 yi* 表示每增加一个单位 bi 后 Z* 的增量,第三章 线性规划模型,线性规划模型的应用 生产计划问题（教材P42,实例3.1,例3-6) 项目投资问题（教材P43,实例3.2,例3-7) 配料配套问题（教材P44,实例3.3,作业) 合理下料问题（例3-8) 运输调运问题（线性规划问题扩展） 任务指
6、派问题（线性规划问题扩展）,第四章 线性规划的扩展,整数线性规划(Integer Linear Programming, ILP) 问题定义： 决策变量是整数的线性规划 所有变量都取整数的规划称为纯整数规划 部分变量取整数的规划称为混合整数规划 整数规划与线性规划的关系 线性规划问题 整数规划问题,第四章 线性规划的扩展,整数规划与线性规划解的差异,X2,X1,A,B,线性规划解：A （2.6，3.8）, Z=17.8,整数规划解： B （5，3 ）, Z=17.0,第四章 线性规划的扩展,0-1规划 一些变量的取值被限定为0或1。是整数规划的特例。 0-1规划的一般模型： s.t. Xj =
7、 0,1 j=1,2,n （X=0,1 等价于 X1, X0 且取整数。） 0-1规划问题求解：思路与LP、IP问题一致。 教材P8183 实例4.7、实例4.8,考虑固定成本的最小生产费用问题 某工厂有三种设备均可生产同一产品，第j种设备运行的固定成本为dj，运行的单位变动成本为cj，则生产成本与产量xj的关系为： j=1,2,3 如何使设备运行的总成本最小？,第四章 线性规划的扩展,引入01变量 yj ， 令 建立以下模型： 这里M是一个很大的正数。 当yj=0时，xj=0，即第j种设备不运行，相应的运行成本 djyj+cjxj=0 当yj1时，0 xjM，实际上对xj没有限制，运行成本为
8、 dj+cjxj 这是一个混合0-1规划问题,第四章 线性规划的扩展,互斥约束的处理：如：f(x) a (a0) 当问题需要同时考虑一对分段约束时，如何将其同时出现在模型中（非线性变成线性）： 如： f(x)-30 (1) ; f(x)0 (2) 通过引入一个01整数变量 y 和一个充分大的正实数M, 可化为： f(x)+3My (3) f(x) M(1-y) (4) 当y=0时，(3)=(1), (4)自然成立，不起作用 当y=1时，(4)=(2),(3)为：3M+f(x),当M很大时也自然成立，因此也不起作用。 （3）和（4）可同时进入模型约束。,第四章 线性规划的扩展,多中选一的处理：
9、模型希望在下列n个约束中，只能有一个约束有效： fi (x) 0 (i=1,2,n) （1） 引入n个01整数变量yi ,(i=1,2,n),可将上式改写为： fi (x) M(1- yi) (i=1,2,n), (2) (3) M为任意大的正数。 (2) : 当yi1 时 ，(2)=(1) ; yi 0 时，自然满足 (3) : 保证了yi 有且只有一个取值为1，其余为0。,第四章 线性规划的扩展,多中选一的处理： 模型希望在下列n个约束中，只能有一个约束有效： fi (x) 0 (i=1,2,n) （1） 引入n个01整数变量yi ,(i=1,2,n),可将上式改写为： fi (x) M(
10、1- yi) (i=1,2,n), (2) (3) M为任意大的正数。 (2) : 当yi1 时 ，(2)=(1) ; yi 0 时，自然满足 (3) : 保证了yi 有且只有一个取值为1，其余为0。,第四章 线性规划的扩展,多中选一的处理： 模型希望在下列2个约束中，只能有一个约束有效： 3X1+4X2 5，4X3-2X2 3 引入2个01整数变量yi ,(i=1,2),可将上式改写为： （Y=1时不采用，Y0时采用） 3X1+4X2 5 + MY1 4X3-2X2 3 +MY2 Y1+Y2=1 M为任意大的正数。,第四章 线性规划的扩展,第四章 线性规划的扩展,指派问题 n项任务（B1,B
11、2,Bn)由n个人 (A1,A2,An) 去完成，每项任务交给一人，每人只有一项任务。第i个人Ai去做第j项任务Bj的工作效率（如工时、成本或价值等）为Cij。问如何安排人员使总工作效率最好？ 设Xij表示Ai完成Bj工作，并令 1 当指派Ai去完成Bj工作 Xij = 0 当不指派Ai去完成Bj工作,第四章 线性规划的扩展,指派问题数学模型的标准型 MIN Z = （Cij0) （i= 1,2,n) (j= 1,2,n) Xij 皆为 0 或 1 由 Cij 组成的方阵 C = ( Cij )nn 称为效率矩阵,第四章 线性规划的扩展,指派问题标准型的求解匈牙利法 指派问题有以下性质： 若从
12、效率矩阵C的任何一行（列）各元素中分别减去一个常数K（K可正可负）得到新矩阵D,则以D为效率矩阵的指派问题与原问题有相同的解，但最优值比原问题最优值小K。 用匈牙利法求解的条件： MIN、i=j 、Cij0,第四章 线性规划的扩展,匈牙利法的主要步骤： 第一步：变换效率矩阵，使在各行各列都出现零元素。 1、从矩阵C的每行元素减去该行的最小元素； 2、再从所得矩阵的每列中减去该列最小元素。 第二步：以最少数目的水平线和垂直线划去所有的零元素。如果所用的直线等于行或列数，则结束指派。否则继续。 第三步：找到没有被划去的最小的元素，所有没有被划中的元素减去这一最小值。而被划中两次的元素（该元素行列都
13、被划中）则要加上这一最小值。再返回到第一步。 第四步：最后根据零元素的位置，确定最优分配方案。,练习题：建立线性规划模型,练习题1：建立线性规划模型,确定决策变量： X1，X2，X3为每月买进的商品量 Y1，Y2，Y3为每月卖出的商品量 确定目标函数： MAX Z=3.31Y1+3.25Y2+2.95Y3 -2.85X1-3.05X2-2.90X3 确定约束条件： 买进的商品当月到货下月卖出，每月卖出的量应小于月初时的库存量 在买卖时间没有严格要求的情况下，先卖再买总是有利的，因此每月最大库存量为月初库存减去卖出再加上买进的量,练习题1：建立线性规划模型,月初库存量 买进 卖出 一月 1000
14、 X1 Y1 二月 1000Y1+X1 X2 Y2 三月 1000Y1+X1-Y2+X2 X3 Y3 因此： Y1 1000 Y2 1000Y1+X1 Y3 1000Y1+X1-Y2+X2 每月库存容量最多为5000，三月末为2000 ： 一月： 1000Y1+X1 5000 二月： 1000Y1+X1-Y2+X2 5000 三月： 1000Y1+X1-Y2+X2-Y3+X2 = 2000,练习题1：建立线性规划模型,每月进货的资金应小于拥有的资金和卖出商品的收入之和：（先卖再买） 一月：2.85 X1 20000 + 3.10 Y1 二月：3.05 X2 20000 + 3.10 Y1 -2.85X1+3.25Y2 三月：2.90 X3 20000 + 3.10 Y1 -2.85X1+3.25Y2 -3.05X2+2.95Y3 X1,X2,X3,Y1,Y2,Y3非负整数,练习题2：建立线性规划模型,练习题2：建立线性规划模型,决策变量确定：（是否投资需要决策） X11，X12，X21，X31 均为01变量 约束条件确定： 第一种产品
