《管理运筹学第2章线性规划与单纯形法》由会员分享，可在线阅读，更多相关《管理运筹学第2章线性规划与单纯形法（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、某部门现有资金200万元，今后五年内考虑以下的 项目投资，已知项目A：第一年到第五年年初都可投资， 当年末能收回本利110%。已知项目B：第一年到第四 年年初都可投资，次年末能收回本利125%，但规定每 年最大投资额不能超过30万元。项目C：第三年初需要 投资，到第五年末能回收本利140%，但规定最大投资 额不超过
