《数据、模型与决策_(第二版)》第三章：线性规划

第二篇 规划和优化模型,第三章 线性规划,数据、模型与决策 (第二版),第三章 线性规划,第三章 线性规划,数据、模型与决策 (第二版),学习目的,线性规划是运筹学的一个重要分支。通过对本章的学习要求： 能够掌握线性规划问题中的主要概念 能够掌握线性规划问题中的线性规划的标准形式 能够掌握线性规划问题的求解方法图解法及单纯形法 理解线性规划问题解的概念和基本定理 了解线性规划问题的敏感性分析以及善于建立线性规划模型来解决一些实际问题。,第三章 线性规划,数据、模型与决策 (第二版),第三章 线性规划,3.1 线性规划问题概述 3.2 线性规划问题的图解法 3.3 单纯形法 3.4 对偶问题 3.5 敏感性分析,第三章 线性规划,数据、模型与决策 (第二版),3.1 线性规划问题概述,3.1.1 线性规划问题中的主要概念 3.1.2 线性规划问题的数学模型,第三章 线性规划,数据、模型与决策 (第二版),3.1.1 线性规划问题中的主要概念,目标（objective）: 所要达到的最优结果（最大或最小）。 约束条件（constraints）：对所能产生结果的限制。 线性规划：一种解决带有约束条件的最优化问题的方法。 解决线性规划问题的步骤 定义问题和收集数据。 建立模型，用恰当的数学式子表示问题 求出问题的最优解 进行敏感性分析，检查条件发生变化是会发生的情况。,第三章 线性规划,数据、模型与决策 (第二版),确定潘得罗索工业公司的产品组合,潘得罗索工业公司是一家墨西哥公司，截至在1998年的销售，公司生产了全国胶合板产量的四分之一，与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品根据厚度和所用木材的质量而有所不同。因为产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有很大的变动。 从1980年开始，潘得罗索工业公司管理部门每个月使用线性规划指导下个月的产品组合决策。线性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得数量。然后对模型求解，找出可行并且最大可能利润（largest possible profit）的产品组合。 采用线性规划后，潘得罗索工业公司的成绩是显著的。改进的产品组合使公司的总利润增加了20%，线性规划得其他贡献包括更好的原材料利用，更好的资本投资，和更好的人员利用。,第三章 线性规划,数据、模型与决策 (第二版),航空业的成本控制,那时，联行在其11个航班订票处，有超过4，000名的机场销售代表和支持人员。在十个最大的机场大约有一千名顾客服务代表，有些时兼职的，每班2到8个小时不等，大部分是全职的，每班8现实或10小时，有许多个不同的上班时间。每个订票处都有一天24小时营业（通过电话订票。然而，每个地点提供所需水平服务的雇员数量在一天24小时种的变化很大，或许美国半个小时就会有很大的变化。 为了更有效率的满足服务要求，在每个地点为所有工作人员设计动作排成，是一个组合的梦魇。一旦一名雇员上了班，就会工作一个班次，只有就餐和每个两个小时的短暂的休息时间，给定24小时的一天中每半个小时各的服务所需的最小雇员数，在七天一周中，24小时一天中每个班次需要多少雇员并且合适上班呢？ 幸运的是，线性规划能解决这些组合梦魇问题。据有形估计，建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上节省了600万美元，得到的其他好处包括改善客户服务以及降低雇员的工作负担。,第三章 线性规划,数据、模型与决策 (第二版),线性规划问题的数学模型,一家玻璃产品生产公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工而成，然后进入储藏室冷却至室温，花瓶有大和小两种尺寸，但是生产过程几乎相当，而且使用同一种材料。不论尺寸，每一个花瓶都需要20分钟的艺术加工，每周艺术加工工作时间为40小时；大小花瓶每个个需彩色玻璃2 OZ和1 OZ。每周可用的玻璃为160 OZ。另外，一个小花瓶占用2单位储存空间，大花瓶占用3个单位储存空间，一共有260个单位储存空间。大小花瓶的利润贡献率分别为12元/个和10元/个。问应该怎样安排生产，才能使利润值最大。,第三章 线性规划,数据、模型与决策 (第二版),线性规划问题的数学模型,B表示大花瓶每周生产的数量，S表示小花瓶每周生产的数量。,第三章 线性规划,数据、模型与决策 (第二版),约束条件 2B+S160 1/3B+1/3S40 3B+2S260 B0, S0 目标函数： max z =12B+10S,第三章 线性规划,数据、模型与决策 (第二版),数学模型表述如下 目标函数 max z =12B+10S 材料约束 2B+S160 时间约束 1/3B+1/3S40 储存约束 3B+2S260 非负约束 B0, S0,第三章 线性规划,数据、模型与决策 (第二版),数学建模四个步骤： 决策变量 确定目标函数 确定约束条件 确定非负约束,第三章 线性规划,数据、模型与决策 (第二版),实例分析： A集团有1,000,000元的资金可供投资，该集团有五个可供选择的投资项目，其中各种资料如下：,第三章 线性规划,数据、模型与决策 (第二版),A集团的目标为：投资风险最小，每年红利至少是80,000元，最低平均增长率14%，最低平均信用度为6，请用线性规划方法描述该问题。,第三章 线性规划,数据、模型与决策 (第二版),决策变量为个项目的投资数额，设为xi ( i =1,2,3,4,5) 目标函数： min z = ( 0.1x1 + 0.06x2 +0.18x3 + 0.12x4+ 0.04x5 ),第三章 线性规划,数据、模型与决策 (第二版),约束条件： 各项目投资总和为1,000,000元 x1 + x2 + x3 + x4+ x5 = 1,000,000 所得红利最少为80,000元 0.05 x1 + 0.08 x2 + 0.07 x3 + 0.06 x4+ 0.1 x5 80,000 增加额不低于140,000元 1x1 + 0.17 x2 + 0.14 x3 + 0.22 x4+0.7 x5140,000 平均信用度不低于6 (11 x1 + 8 x2 + 10 x3 + 4 x4+10 x5)/56 非负约束 xi 0 ( i =1,2,3,4,5),第三章 线性规划,数据、模型与决策 (第二版),实例分析： 某石油公司利用三种有生产两种混合原料。每种油的成本和每天的可用量如下表所示：,第三章 线性规划,数据、模型与决策 (第二版),燃料1售价为30元/升，燃料2 售价为35元/升，该公司有一向长期合同，每天供应两种原料，各10，000升。请建立该问题的数学规划模型。 解题过程： 决策变量为加入到两种燃料种的各种油的量： A1为原料1中加入A种油的升数。 A2为原料2中加入A种油的升数。 B1为燃料1中加入B种油的升数。 B2为燃料2中加入B种油的升数。 C1为燃料1中加入C种油的升数。 C2为燃料2中加入C种油的升数。,第三章 线性规划,数据、模型与决策 (第二版),燃料1和燃料2 的产量为： 燃料1：A1+B1+C1 燃料2：A2+B2+C2 各种油的使用量： A种油= A1+A2 B种油= B1+ B2 C种油= C1+ C2 目标是取得最大化的利润，两种燃料的销售收入为： 30(A1+ B1+ C1)+35(A2+ B2+ C2),第三章 线性规划,数据、模型与决策 (第二版),而三种油的成本为： 8(A1+A2)+10(B1+ B2)+12(C1+ C2 ) 利润是销售收入和成本之差，作为目标函数可以表示如下： max z =22A1+27 A2 +20 B1+25B2+18 C1+23 C2 三种可用的原料油的约束为： A1+A210,000 B1+ B215,000 C1+ C220,000,第三章 线性规划,数据、模型与决策 (第二版),各种原料油所占比例的六个约束： A10.25(A1+B1+C1) B10.3(A1+B1+C1) C10.4(A1+B1+C1) A20.2(A2+B2+C2) B20.5(A2+B2+C2) C20.3(A2+B2+C2) 长期供货合同约束： A1+B1+C110,000 A2+B2+C210,000 非负约束： Ai，Bi，Ci0 (i=1,2),第三章 线性规划,数据、模型与决策 (第二版),第三章 线性规划,3.1 线性规划问题概述 3.2 线性规划问题的图解法 3.3 单纯形法 3.4 对偶问题 3.5 敏感性分析,第三章 线性规划,数据、模型与决策 (第二版),3.2线性规划问题的图解法,3.2.1 图解法的过程介绍 3.2.2 规划问题求解的几种可能结果 3.2.3 图解法延伸,第三章 线性规划,数据、模型与决策 (第二版),3.2.1 图解法的过程介绍,花瓶问题 目标函数 max z =12B+10S 材料约束 2B+S160 （1） 时间约束 1/3B+1/3S40 （2） 储存约束 3B+2S260 （3） 非负约束 B0, S0,第三章 线性规划,数据、模型与决策 (第二版),直线把图分为两部分，直线上方的点都不符合约束条件， 而直线上和直线下方的点都满足约束条件。,第三章 线性规划,数据、模型与决策 (第二版),最优解为： B=20, S=100 将B和S值代入目标函数中得： Z=1220+10100=1240 所以最大利润值是1240。,第三章 线性规划,数据、模型与决策 (第二版),图解法的步骤： 其中一个变量作为横坐标轴，另一个变量作为纵坐标轴，画出平面直角坐标系，并适当选取单位坐标长度，由于变量是非负的，因此，画出坐标系的第一象限即可。 出各约束条件在坐标轴上对应的直线，找出可行域（常用阴影区域标识）。 图标目标函数，z是一个待求的目标函数值。目标函数常用一组平行虚线表示，离坐标原点越远的虚线表示的目标函数值越大。 确定最优解。因为最优解是可行域中使目标函数值达到最优的点，当目标函数直线由原点开始向右上方移动时，z值开始增大，一直移到目标函数直线与可行域相切时为止，切点就是最优解的点。,第三章 线性规划,数据、模型与决策 (第二版),3.2.2规划问题求解的几种可能结果,无穷多最优解 无界解 无解或者无可行解,第三章 线性规划,数据、模型与决策 (第二版),3.2.3图解法延伸,图解法的解体方法和几何判断对于求解一般的线性规划问题有很大启发： 1、性规划问题的解的情况有以下几种：唯一最优解；无穷多最优解；无界解；无可行解。 2、线性规划问题有解，那么可行域是凸集。 3、规划问题优解存在，那么唯一最优解一定是可行域凸集的某个顶点；无穷最优解一定是可行域的某个边或某个面。 4、规划问题的一般解体思路：先找出凸集的任一顶点，计算该点处目标函数值，与周围相邻顶点处的目标函数值相比较，如果该点值最大，那么该点就是最优解或者最优解之一；如果不是，那么就对目标函数值比该点大的另一点重复此过程，直到找出最优解。,第三章 线性规划,数据、模型与决策 (第二版),实例分析： 某工厂生产A,B两种产品，分别经过三道工序，已知建立的模型如下所示，可行域为凸多边形OACDB, 试以图解法求解最优生产方案。 目标函数 max z =20A+30B 工序一约束 2A+B40 工序二约束 A+2B40 工序三约束 A+B25 非负约束 A0, B0,第三章 线性规划,数据、模型与决策 (第二版),第三章 线性规划,数据、模型与决策 (第二版),A+2B=40 工序二约束 A+B=25 工序三约束 联立以上方程，可以求得最优解 A=10, B=15 代入目标函数，求得最大目标函数值为20*10+30*15=650。,第三章 线性规划,数据、模型与决策 (第二版),第三章 线性规划,3.1 线性规划问题概述 3.2 线性规划问题的图解法 3.3 单纯形法 3.4 对偶问题 3.5 敏感性分析,第三章 线性规划,数据、模型与决策 (第二版),3.3 单纯形法,3.3.1 线性规划问题的标准形式 3.3.2 线性规划问题解的概念和基本定理 3.3.3 单纯形法解题步骤,第三章 线性规划,数据、模型与决策 (第二版),3.3.1线性规划问题的标准形式,规定线性规划问题的一般形式： 目标函数 约束条件 （i =1,m） 非负约束 0 ( j =1,n),第三章 线性规划,数据、模型与决策 (第二版),转化为标准形式方法： 如果模型的目标函数为极小值： ，那么令z=-z , 。 如果右端项bi小于零，等式两端同时乘以-1 。 约束条件一般情况下是不等式。例如：x1+x26, 令x3=6-x1-x2 ，x3 0，将约束条件转化为x1+x2+x3=6 ，x3称作松弛变量。如果有x1+x26 ,令x4=6-x1-x2 , x40，约束条件转化为x1+x2-x4=6，x4称作剩余变量。 变量取值可能无约束。决策变量可以大于或等于零，也可以小于零。此时令xj=xj-xj, xj0, xj0, 将其代入线性规划模型。 决策变量小于等于零, 即xj0。令xj=-xj , 将xj代入线性规划模型。,第三章 线性规划,数据、模型与决策 (第二版),3.3.2线性规划问题解的概念和基本定理,目标函数 约束条件 （i =1,m） 非负约束 xj 0 ( j =1,n),第三章 线性规划,数据、模型与决策 (第二版),可行解：满足约束条件的解为可行解，全部可行解的集合为可行域。 最优解：使目标函数值达到最大的可行解为最优解。 定理一 ： 若线性规划问题存在可行解，则问题的可行域为凸集。 定理二 ： 线性规划问题的基可行解对应于线性规划问题可行域的顶点。 定理三 ：若线性规划问题有最优解，一定存在一个基可行解是最优解。,第三章 线性规划,数据、模型与决策 (第二版),3.3.3单纯形法解题步骤,已知模型如下： 目标函数 max z =20A+30B 工序一约束 2A+B40 工序二约束 A+2B40 工序三约束 A+B25 非负约束 A0, B0,第三章 线性规划,数据、模型与决策 (第二版),，引入三个松弛变量：C、D、E 原问题转变为如下形式： max z =20A+30B+0C+0D+0E 2A+B+C=40 A+2B+D=40 A+B+E=25 A0, B0,C0,D0,E0,第三章 线性规划,数据、模型与决策 (第二版),约束条件的系数矩阵为： U=(P1 ,P2 ,P3 ,P4 ,P5) = P3= ，P4= ，P5= 三个向量是线性无关的 这些向量构成基矩阵：V=(P3, P4, P5 ) =,第三章 线性规划,数据、模型与决策 (第二版),对应于V的变量为基变量，他们分别为： C=40-2A-B D=40-A-2B E=25-A-B 将上述基变量代入目标函数中，得到： Z=20A+30B+0 当还未生产时，A=B=0，资源未被利用。取C=40 ,D=40 ,E=25，利润值还未产生， 得到初始基本可行解：X(0) =(0，0，40，40，25)。,第三章 线性规划,数据、模型与决策 (第二版),B的取值满足： C=40-2A-B0 D=40-A-2B0 E=25-A-B0 因为A=0,所以有： C=40-B0 D=40-2B0 E=25-B0 B的取值要求满足上述三式，因此B为: B=min 40/1 ,40/2 ,25/1 =20,第三章 线性规划,数据、模型与决策 (第二版),现在知道，A=0 ,B=20 ,将其代入三个约束条件中， 2A+B+C=40 A+2B+D=40 A+B+E=25 得到一组新的解：X(1)=(0，20，20，0，5) 将上面三式变形，得到下式： C+B=40-3/2A (1) 2B=40-A-D (2) E+B=25-A (3),第三章 线性规划,数据、模型与决策 (第二版),将其进行转化，(1)-1/2*(2)，(2)/2，(3)-(2)/2，上述三式又变为： C=20-3/2A (4) B=20-1/2A-1/2D (5) E=5-1/2A+1/2D (6) 将上述三式代入目标函数式中， Z=600+5A-15D V=(C, B, E) =,第三章 线性规划,数据、模型与决策 (第二版),根据(4)、(5)、(6)式可以得到新的约束方程的系数矩阵： U= 从目标表达式Z=600+5A-15D上看，A的系数式正值，说明增加A的产量仍然可以提高利润，A的取值满足： C=20-3/2A0 B=20-1/2A-1/2D0 E=5-1/2A+1/2D0,第三章 线性规划,数据、模型与决策 (第二版),由于D=0，可得： C=20-3/2A0 B=20-1/2A0 E=5-1/2A0 A要求满足上述三式，因此 A=min 20/1.5, 20/0.5, 5/0.5=10 A变为基变量，而E变为非基变量，将A=10, E=0代入三个约束条件中： 2A+B+C=40 A+2B+D=40 A+B+E=25 通过求解可得：B=15, C=5, D=0,第三章 线性规划,数据、模型与决策 (第二版),新的基本可行解为： X(2)=(10，15，5，0，0)。 用A置换E，得到： C+3/2A=20 B+1/2A=20-1/2D 1/2A=5+1/2D-E 经变形得到下面三个新的式子： C=5-3/2D+3E B=15-D+E A=10+D-2E,第三章 线性规划,数据、模型与决策 (第二版),将上述三式带入目标函数 Z=650-10D-10E 从上式可以看出，D、E系数皆为负，如果这些变量值增加，将导致目标函数值的减少。因此最佳生产方案为： X(2)=(10，15，5，0，0) 最大利润值为：Z=650,第三章 线性规划,数据、模型与决策 (第二版),例 Keku公司一直开始从事汽车零配件的设计、生产，最近公司设计了两种新型改良产品(产品I和II)。根据以往新产品上市的经验和市场行情，Keku公司预计每生产一件产品I可获利2元，每生产一件产品II可获利3元。公司准备利用现有的生产资源，在计划期内安排生产I、II两种新产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。,第三章 线性规划,数据、模型与决策 (第二版),站在Keku公司的立场想知道如何安排生产才能获利最多？ 用单纯形法对它进行求解。,第三章 线性规划,数据、模型与决策 (第二版),分别设 、 表示在计划期内产品I、II的产量，建立该问题的数学模型为：,第三章 线性规划,数据、模型与决策 (第二版),将其转换为标准型为： （4） （5）,第三章 线性规划,数据、模型与决策 (第二版),确定初始可行基和基可行解 由式（5）可得 ， 和 对应的系数列向量线性无关，因此，取可行基： 则 ， 和 为基变量， ， 为非基变量。 将基变量和目标函数用非基变量表示为： （6） （7） 当非基变量 ， 时，得到基可行解 ，此时， ，即Keku公司未生产任何产品，其利润为0。,第三章 线性规划,数据、模型与决策 (第二版),确定换入变量 在目标函数式（6）中，非基变量 ， 的系数都是正数，因此，不管以谁作为换入变量都能使目标函数值增大，其经济意义为安排生产任一种产品都可以增加Keku公司的利润。我们选择系数较大的 作为换入变量。 确定换出变量 选择 作为换入变量后，必须从 ， 和 中确定一个换出变量。 解 （令 ），得到 解 （令 ），得到 为保证所有变量的非负性，故 ，此时， 为换出变量。这种确定换出变量的规则称为 规则。,第三章 线性规划,数据、模型与决策 (第二版),重复上述过程，可得最优解 结论： Keku公司应生产4件产品I和2件产品II，共可获得利润14元。,第三章 线性规划,数据、模型与决策 (第二版),第三章 线性规划,3.1 线性规划问题概述 3.2 线性规划问题的图解法 3.3 单纯形法 3.4 对偶问题 3.5 敏感性分析,第三章 线性规划,数据、模型与决策 (第二版),3.4 对偶问题,3.4.1 原问题与对偶问题的关系 3.4.2 举例说明,第三章 线性规划,数据、模型与决策 (第二版),3.4.1 原问题与对偶问题的关系,求原问题的对偶问题的步骤： （1）如约束条件中有“ ”的情况，将其转换成“ ”，使得所有约束条件全部变成“ ”或“=”的形式。 （2）如果原问题的目标函数是“ ”的形式，则 对偶问题的目标函数是“ ”的形式。 原问题的 n个变量对应于对偶问题中 n个约束条件。具体地， 若变量 的取值“ 0”，则对偶问题中第 i个约束条件为“ ”的不等式； 若变量 的取值“ 0”，则对偶问题中第 个约束条件为“ ”的不等式； 若变量 无约束，则对偶问题中第i 个约束条件为等式。 原问题的 m个约束条件对应于对偶问题中 m个变量。具体来讲， 若第i 个约束条件是“ ”的不等式，则变量 的取值“ 0”； 若第i 个约束条件为等式，则变量 无约束。,第三章 线性规划,数据、模型与决策 (第二版),（3）如果原问题的目标函数是“ ”的形式，则 对偶问题的目标函数是“ ”的形式。 原问题的 n个变量对应于对偶问题中n 个约束条件。具体地， 若变量 的取值“ 0”，则对偶问题中第 i个约束条件为“ ”的不等式；