资源预览内容
第1页 / 共118页
第2页 / 共118页
第3页 / 共118页
第4页 / 共118页
第5页 / 共118页
第6页 / 共118页
第7页 / 共118页
第8页 / 共118页
第9页 / 共118页
第10页 / 共118页
亲,该文档总共118页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
浙江大学管理学院 杜 红 ,管理科学方法(复习版),狭义的管理科学:数理方法制定管理决策 Management Science = Operations research (MS=OR) 决策制定(主体、环境、过程) 定量分析(数学、概率、统计) 运筹方法(问题、建模、解决),第一章 管理科学简介,第一章 管理科学简介,定性分析的方法 德尔菲方法 小组讨论 定量模型的运用 运筹模型,管理科学的方法论,第一章 管理科学简介,运筹方法解决典型管理问题,第三章 线性规划模型,线性规划问题模型的一般形式: 目标函数: 约束条件:,第三章 线性规划模型,线性规划问题的基本要求 目标函数和约束条件必须是线性函数; 线性表达:相加性、比例性 决策变量的连续分布; 不限于整数,可以是小数,但不能四舍五入 目标函数的单一性; 多目标是要设法简化成单目标 模型必须是确定型的; 所有参数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),例:求解以下线性规划问题,第三章 线性规划模型,对偶问题与影子价格 定义: 设以下线性规划问题 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。,第三章 线性规划模型,原问题标准型: 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,根据对偶性质: 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) 运输调运问题(线性规划问题扩展) 任务指派问题(线性规划问题扩展),第四章 线性规划的扩展,整数线性规划(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 = 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没有限制,运行成本为 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)可同时进入模型约束。,第四章 线性规划的扩展,多中选一的处理: 模型希望在下列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(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,B2,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 称为效率矩阵,第四章 线性规划的扩展,指派问题标准型的求解匈牙利法 指派问题有以下性质: 若从效率矩阵C的任何一行(列)各元素中分别减去一个常数K(K可正可负)得到新矩阵D,则以D为效率矩阵的指派问题与原问题有相同的解,但最优值比原问题最优值小K。 用匈牙利法求解的条件: MIN、i=j 、Cij0,第四章 线性规划的扩展,匈牙利法的主要步骤: 第一步:变换效率矩阵,使在各行各列都出现零元素。 1、从矩阵C的每行元素减去该行的最小元素; 2、再从所得矩阵的每列中减去该列最小元素。 第二步:以最少数目的水平线和垂直线划去所有的零元素。如果所用的直线等于行或列数,则结束指派。否则继续。 第三步:找到没有被划去的最小的元素,所有没有被划中的元素减去这一最小值。而被划中两次的元素(该元素行列都被划中)则要加上这一最小值。再返回到第一步。 第四步:最后根据零元素的位置,确定最优分配方案。,练习题:建立线性规划模型,练习题1:建立线性规划模型,确定决策变量: X1,X2,X3为每月买进的商品量 Y1,Y2,Y3为每月卖出的商品量 确定目标函数: MAX Z=3.31Y1+3.25Y2+2.95Y3 -2.85X1-3.05X2-2.90X3 确定约束条件: 买进的商品当月到货下月卖出,每月卖出的量应小于月初时的库存量 在买卖时间没有严格要求的情况下,先卖再买总是有利的,因此每月最大库存量为月初库存减去卖出再加上买进的量,练习题1:建立线性规划模型,月初库存量 买进 卖出 一月 1000 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变量 约束条件确定: 第一种产品
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号