管理运筹学第2章线性规划与单纯形法.ppt
《管理运筹学第2章线性规划与单纯形法.ppt》由会员分享,可在线阅读,更多相关《管理运筹学第2章线性规划与单纯形法.ppt(120页珍藏版)》请在三一文库上搜索。
1、第二章 线性规划与单纯形法,主讲教师:马越峰,第二章 线性规划与单纯形法,2.1线性规划问题与数学模型 2.2图解法 2.3线性规划的应用 2.4单纯形法基本原理及计算步骤 2.5单纯形法的进一步讨论 2.6线性规划的对偶问题,2.1 线形规划(Linear Programming)问题及其数学模型,【引例】某工厂在计划期内要安排甲乙两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,以及资源的限制如下表所示:,问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多?,设生产甲产品x1个,生产乙产品x2个,目标函数 max Z= 50 x1+100x2,约 束 条 件,x1+
2、x2 300,2x1+x2 400,x2 250,x10,x2 0,线性规划模型,1.适用条件: (1)优化条件:问题目标最大化、最小化的要求; (2)约束条件:问题目标受一系列条件的限制; (3)选择条件:实现目标存在多种备选方案; (4)非负条件的选择:根据问题的实际意义决定是否非负。 2. 构建线性规划模型的步骤 (1)科学选择决策变量 (2)明确目标要求 (3)根据实际问题的背景材料,找出所有的约束条件 (4)确定是否增加决策变量的非负条件,线性规划模型表示形式,决策变量;,目标函数系数、价值系数或费用系数;,右端项或资源常数;,称为约束系数或技术系数。,(1)一般形式:,(2)集合形
3、式:,(3)向量形式:,(4)矩阵形式:,【例】 将线性规划模型一般表达式化为矩阵形式。,解:,设:,例1.目标函数: Max z = 50 x1 + 100 x2 约束条件: s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最优解: x1 = 50, x2 = 250 最优目标值 z = 27500,2 图 解 法,对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。 下面通过例1详细讲解其方法:,步骤:,(1)分别取决策变量X1 , X2 为坐标向量建立
4、直角坐标系。在直角坐标系里,图上任意一点的坐标代表了决策变量的一组值,例1的每个约束条件都代表一个半平面。,(2)对每个不等式(约束条件),先取其等式在坐标系中作直线,然后确定不等式所决定的半平面。,(3)把五个图合并成一个图,取各约束条件的公共部分,如图2-1所示。,(4)目标函数z=50x1+100x2,当z取某一固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到B点时,z在可行域内实现了最大化。A,B,C,D,E是可行域的顶点,对有限个约束条件则其可行域的顶点也是有限的。,解的几种可能结果,唯一最优解解 无穷多个最优解 无界解(可行域无
5、界,常为模型遗漏了某些必要的约束条件) 无可行解(可行域为空集,约束条件自相矛盾,资源满足不了人们的需求),可行解:满足LP问题所有约束条件的解 最优解:满足目标要求的可行解,四种结局:,无界解,无可行解:可行域为空集,增加的约束条件,线性规划标准形式,线性规划标准模型的一般表达式:,非标准形式标准化方法:,1.目标函数,2.约束条件为不等式:,引进松驰变量xs:,引进剩余变量xs:,4.决策变量为自由变量:,5.约束右端项为负:,两端乘-1:,0,3.约束条件为不等式:,引入松驰变量(含义是资源的剩余量) 【引例】中引入 s1, s2, s3 模型化为 目标函数:Max z = 50 x1
6、+ 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件:s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 对于最优解 x1 =50 x2 = 250 , s1 = 0 s2 =50 s3 = 0 说明:生产50单位产品和250单位产品将消耗完所有 可能的设备台时数及原料B,但对原料A则还剩余50千克。,【例】将线性规划模型转化为标准式,解:,无约束,(4)在第一、第三约束左端加上松弛变量x4,x60 ,在第二约束左端减去剩余变量x50,习题,1.用图解法求解下列L
7、P问题 (1)minZ= 6x1+4x2 (2)maxZ= 3x1-2x2 2x1+x2 1 x1+x2 1 3x1+4x2 3 2x1+2x2 4 x1,x2 0 x1,x2 0,2 、对下面LP问题 (1)用图解法求解 (2)写出此问题的标准形式 (3)求剩余变量的值 minZ=11x1+8x2 s.t. 10x1+2x2 20 3x1+3x2 18 4x1+9x2 36 x1,x2 0,图解法的灵敏度分析,1、目标函数中的系数Ci的灵敏度分析 分析Ci在什么范围内变化,原最优解不变 C1=50 C2=100,E,A,D,C,B,F,直线BC 的斜截式为:x2= -x1 +300 斜率为-
8、1 直线BF 的斜截式为:x2= 0x1 +250 斜率为0 目标函数Z=c1x1+c2x2的斜截式为: x= -c1/c2x1 +z/c2 斜率为-c1/c2 所以,当-1 -c/c0时,顶点B仍然是最优解 假设c2 不变,则有-1 -c1/100 0,解之得0 c1100,,,练习:计算C在什么范围内变化时顶 点B 仍然是最优解,2、约束条件右边b系数的灵敏度分析,b变化时通常引起可行域的变化从而引起最优解的变化。设例1中的设备台时增加了10个台时数,则约束变为:x1+x2310 代入求得新的最优解为x1=60,x2=250 Z=5060+100250=28000 比原来最大的利润2750
9、0增加了500元,可知每增加一个台时的设备可多获利润500/10=50元,在约束条件右边常量每增加一个单位而使最 优目标函数得到改进的量称为这个约束条件的 对偶价格,练习:将原料A增加10千克计算最优解和最优值,某一约束条件的对偶价格仅仅在某一 范围内有效,总 结,当约束条件右边常数增加一个单位时: (1)如果对偶价格大于零,则最优目标函数值得到改进,即求最大值时变得更大;求最小值时变得更小 (2)如果对偶价格小于零,则最优目标函数值变坏,即求最大值时变得小了;求最小值时变得大了 (3)如果对偶价格等于零,则最优目标函数值不变,练习:某公司目前正生产甲乙两种产品,产量分别为 30个和120个,
10、公司经理希望了解是否通过改变 这两种产品的数量而提高公司的利润.公司制造 每个产品所需的加工工时和各个车间的加工能 力如下表:,(1)假设生产的全部产品都能销售出去,用图解法确定 最优产品组合 (2)在上面求得的最优产品组合中,那些车间的能力还 有剩余,剩余多少?是剩余变量还是松弛变量? (3)各车间的能力分别增加一个加工工时数给公司带 来多少额外的利润. (4)当产品甲的利润不变时,产品乙的利润在什么范围 内变化时此最优解不变?当产品乙的利润不变时, 产品甲的利润在什么范围内变化时最优解不变. (5)当产品甲的利润从500降为450元,而产品乙的利润 从400元增加为430元时,原来产品组合
11、是否依然是 最优产品组合.,2.3 LP的应用,一.人力资源分配问题 例1.某昼夜服务的公交线路每天各时间段所需司机和乘务人员数如下:,设司机和乘务人员分别在各时段一开始时上班, 并连续工作8小时,问该公交线路怎样安排人员, 既能满足工作需要又配备最少司机和乘务人员。,设xi表示第i班次开始上班的人员,s.t.,minZ= X1 + X2 + X3 + X4+X5 + X6 X1+X6 60 X1+X2 70 X2+X3 60 X3+X4 50 X4+X5 20 X5+X630 X1,X2,X3,X4,X5,X6 0,最优解 : x=50 x=20 x=50 x=0 x=20 x=10 最优目
12、标函数值 Z=150,【练习】某中型百货商场对售货人员的需求统计如下表,并规定售货员每周工作5天且连续休息2天,问如何安排 人员的作息既满足工作需要又使配备人员最少?,解:设x1为星期一开始休息的人数,x2为星期二开始休息的人数, x7为星期日开始休息的人数,目标函数:minZ=x1+x2+x3+x4+x5+x6+x7,x1+x2+x3+x4+x528 x2+x3+x4+x5+x615 x3+x4+x5+x6+x724 x4+x5+x6+x7 + x125 x5+x6+x7 + x1+x219 x6+x7 + x1+x2+x3 31 x7 +x1+x2+x3+x428 xi 0,最优解: x1
13、 =12 x2 =0 x3 =11 x4 =5 x5 =0 x6 =8 x7 =0 目标函数最小值为:36,二 生产计划问题,例2、某公司生产甲,乙,丙三种产品,这三种产品都要经过铸造,机加工和装配三个车间。甲乙两种产品的铸件可以外包协作也可自行生产,但丙产品必须本厂铸造才能保证质量。有关情况见下表;公司中可利用的总工时为铸造8000小时机加工12000小时和装配10000小时。公司为了获得最大利润,甲,乙,丙三种产品各生产多少件,甲乙两种产品的铸造应多少由本公司完成?多少由外包协作?,解:设x1,x2,x3分别为三道工序都由本公司加工的 甲,乙,丙三种产品的件数,设x4,x5分别为由外 协铸
14、造再由本公司机加工和装配的甲乙两种产品的 件数。 计算每件产品的利润分别如下: 产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协,其余自制的利润=23-(5+2+3)=13 产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸造外协,其余自制的利润=18-(6+1+2)=9 产品丙的利润 =16-(4+3+2)=7,目标函数:max Z= 15X1 +10X2+ 7X3 +13 X4+9X5,5X1 + 10X2 + 7X3 8000 6 X1 + 4X2 + 8X3 +6 X4+4X5 12000 3X1 + 2X2 +2 X3 + 3X4+2X5 10000 X1
15、 ,X2 , X3,X4,X5 0,三 套裁下料问题,例3、某工厂要做100套钢架,每套用29m、21m和15m的原钢各一根。已知原料每根长74m,问应如何下料,可使所用原料最省。,设按各方案下料的原材料根数分别为 X1 , X2 ,X3 , X4,X5 。,目标函数:min Z= X1 + X2 + X3 + X4+X5,约束条件: X1 +2X2 + X4100 2 X3 + 2X4 +X5 100 3X1 + X2 + 2X3 +3X5 100 X1 , X2 ,X3 ,X4,X5 0,最优解X1 =30 X2 =10 X3 =0 X4=50 X5 =0 Z=90,四 、投资问题,例4、
16、某部门现有资金200万元,今后五年内考虑以下的 项目投资,已知项目A:第一年到第五年年初都可投资, 当年末能收回本利110%。已知项目B:第一年到第四 年年初都可投资,次年末能收回本利125%,但规定每 年最大投资额不能超过30万元。项目C:第三年初需要 投资,到第五年末能回收本利140%,但规定最大投资 额不超过80万元。项目D:第二年初需要投资,到第五 年末能回收本利155%,但规定最大投资额不超过100万 元。问:应如何确定这些项目的每年投资,使得第五年 末拥有资金的本利和金额最大?,这是一个连续投资的问题,设:X i j=第i年初投资j项 目的金额,见表:,目标函数: maxz=11X
17、 5A125 X 4B 140X 3C155 X 2D X 1A X 1B=200, X 2A X 2B X 2D = 11X 1A , X 3A X 3B X 3C = 11 X 2A 125X 1B , X 4A X 4B = 11 X 3A 125 X 2B , X 5A = 11X 4A 125 X 3B , X i B 30 (i= 1,2,3,4) , X 3C 80 , X 2D 100 , X i j0 ,,五、配料问题,例5:某工厂要用三种原料1、2、3混合调配出三种 不同规格的产品甲、乙、丙,数据如右表。问: 该厂应如何安排生产,使利润收入为最大?,解:设 xij 表示第
18、i 种(甲、乙、丙)产品中原料 j 的含量。这样我们建立数学模型时,要考虑: 对于甲: x11,x12,x13; 对于乙: x21,x22,x23; 对于丙: x31,x32,x33; 对于原料1: x11,x21,x31; 对于原料2: x12,x22,x32; 对于原料3: x13,x23,x33; 目标函数: 利润最大,利润 = 收入 - 原料支出 约束条件: 规格要求 4 个; 供应量限制 3 个,利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量,故有 目标函数 Max 50(x11+x12+x13)+35(x21+x22+x23)+25(x31
19、+x32+x33)-65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33) = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件: 从第1个表中有: x110.5(x11+x12+x13) x120.25(x11+x12+x13) x210.25(x21+x22+x23) x220.5(x21+x22+x23),从第2个表中,生产甲乙丙的原材料不能超过原 材料的供应限额,故有 (x11+x21+x31)100 (x12+x22+x32)100 (x13+x23+x33)60,习题,1、某锅炉制造厂要制造一种新
20、锅炉10台,每台锅炉需要不同长度的锅炉钢管数量如下:,库存的原材料的长度只有5500mm一种规格,问 如何下料才能使总的用料根数最少?,2.、前进电器厂生产A,B,C三种产品有关资料如下表:,问:在资源及市场允许的条件下如何安排生产获利最大,3.某公司在今后四个月内需租用仓库堆放物资 已知各个月所需的仓库面积数字如下表:,表2,表1,仓库的租借费用,当租借合同期限越长时,享受的折扣优惠也越大,具体数字如表2,租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要在任何一个月初办理租借合同,且每次办理可签一份也可同时签若干份租用面积和租借期限不同的合同.求一个所付的租
21、借费为最小的租借方案.,设xij(i=1,2,3,4)(j=1, 4-i+1)为第i个月初签定的租 借期为j个月的合同的租界面积,minZ=2800x11+4500x12+6000x13+7300x14+2800x21+ 4500x22+6000x23+ 2800x31+4500x32+2800x41 x11+x12+x13+x1415 s.t x12+x13+x14 +x21+x22+x2310 x13+x14 +x22+x23+x31+x32 20 x14+x23+x32+x4115 xij 0,4、某公司从两个产地A1,A2将货物运往三个销地B1,B2 B3,各产地的产量及各销地的销量和
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理 运筹学 线性规划 单纯
链接地址:https://www.31doc.com/p-2115655.html