规划技术-线性规划.ppt

第二讲第二讲规划技术规划技术线性规划线性规划四川大学工商管理学院四川大学工商管理学院管理科学系管理科学系 钟钟 胜胜 副教授副教授Tel：84533811Email：L I N E A R P R O G R A M M I N G04年7月1管理运筹学讲义 Linear programming(LP)is a tool for solving optimization problems.In 1947,George Dantzig developed an efficient method,the simplex algorithm,for solving linear programming problems.Since the development of the simplex algorithm,LP has been used to solve optimization problems in industries as diverse as banking,education,forestry,petroleum,and trucking.In a survey of Fortune 500 firms,85%of those responding said that they had used LP.04年7月2管理运筹学讲义线性规划线性规划(Linear Programming)是运筹学的重是运筹学的重要组成部分，也是最基础的部分。要组成部分，也是最基础的部分。自自1947年丹齐格年丹齐格()提出了求解线性规划的一般提出了求解线性规划的一般方法单纯形法以来，线性规划在理论上趋向成方法单纯形法以来，线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及运熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性规划的应用领域更加广泛。无算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军事、经济计划论工业、农业、商业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一个国家、一个和管理决策等领域都有应用。大到一个国家、一个地区，小到一个企业、一个车间、一个班组都有运地区，小到一个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。用线性规划后提高经济效益的例子。04年7月3管理运筹学讲义第一节线性规划的模型与图解法第一节线性规划的模型与图解法第二节单纯形法第二节单纯形法第三节对偶问题与灵敏度分析第三节对偶问题与灵敏度分析第四节线性规划软件简介第四节线性规划软件简介第五节运输问题第五节运输问题第六节线性整数规划第六节线性整数规划第七节线性规划应用实例第七节线性规划应用实例04年7月4管理运筹学讲义See You!04年7月5管理运筹学讲义第一节线性规划的模型与图解法第一节线性规划的模型与图解法 线性规划问题及其数学模型线性规划问题及其数学模型 两变量问题的图解法两变量问题的图解法 线性规划模型的标准形式及解的概念线性规划模型的标准形式及解的概念04年7月6管理运筹学讲义 线性规划问题及其数学模型线性规划问题及其数学模型 线性规划问题的提出及主要概念线性规划问题的提出及主要概念 线性规划问题的数学模型线性规划问题的数学模型 In this section,we introduce linear programming and define some important terms that are used to describe linear programming problems.04年7月7管理运筹学讲义 线性规划问题的提出及主要概念线性规划问题的提出及主要概念在生产管理和经营活动中，组织常常必须对如在生产管理和经营活动中，组织常常必须对如何向不同的活动分配资源的问题做出决策，以便最何向不同的活动分配资源的问题做出决策，以便最好地达成组织的目标。好地达成组织的目标。这样的问题通常有两类，这样的问题通常有两类，一类一类是如何合理地使是如何合理地使用有限的劳动力、设备、资金等资源，以最大化效用有限的劳动力、设备、资金等资源，以最大化效益；益；另一类另一类是为了达到一定的目标，应如何组织生是为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分产，或合理安排工艺流程，或调整产品的成分以使资源消耗最少。以使资源消耗最少。04年7月8管理运筹学讲义向不同的活动分配的资源可以是资金、不同的向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些媒体做广告、金融活动、进行资金投资或其他一些活动。活动。由于所有活动都要求一定资源作支撑，而资源由于所有活动都要求一定资源作支撑，而资源却是有限的，这必然导致活动间的冲突与矛盾。这却是有限的，这必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使就需要管理者利用一些科学的方法进行协调，以使资源达到最大的效用。资源达到最大的效用。04年7月9管理运筹学讲义显然，上述活动所引起的问题是一类显然，上述活动所引起的问题是一类有约束的有约束的最优化问题最优化问题（Constrained Optimization）。）。线性规划线性规划正是解决有约束的最优化问题的一种正是解决有约束的最优化问题的一种常用的方法，其涉及的常用的方法，其涉及的主要概念主要概念包括：包括：决策变量（决策变量（Decision Variables）:最优化问题最优化问题的决策对象；的决策对象；约束条件（约束条件（Constraints）:对决策所能产生的对决策所能产生的结果的限制。结果的限制。目标（目标（Objective）:决策所希望达到的最优结决策所希望达到的最优结果（最大或最小）；果（最大或最小）；04年7月10管理运筹学讲义解决线性规划问题的过程通常分为四个步骤：解决线性规划问题的过程通常分为四个步骤：定义问题和收集数据。定义问题和收集数据。必需向管理者咨询所要必需向管理者咨询所要考虑问题涉及到的数据及确定研究的合理目标。考虑问题涉及到的数据及确定研究的合理目标。建立模型，用恰当的数学式表示问题。建立模型，用恰当的数学式表示问题。求出问题的最优解。求出问题的最优解。进行敏感性分析，检查条件发生变化时可能发进行敏感性分析，检查条件发生变化时可能发生的情况。生的情况。04年7月11管理运筹学讲义案例案例1：潘得罗索工业公司的产品组合潘得罗索工业公司的产品组合 潘得罗索工业公司是一家墨西哥公司，截止潘得罗索工业公司是一家墨西哥公司，截止1998年，公司产销量占该国的四分之一。年，公司产销量占该国的四分之一。与其他胶合板生产厂商一样，潘得罗索工业公与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品因厚度和所用木材的质量而有所不同。司的许多产品因厚度和所用木材的质量而有所不同。由于产品在一个竞争的环境中进行销售，产品的价由于产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有化。结果导致每项产品对公司整体利润的贡献也有很大的变化。这样，在某个月一个产品可能比另一很大的变化。这样，在某个月一个产品可能比另一个产品赚取更大的利润，而在下一个月的情况则可个产品赚取更大的利润，而在下一个月的情况则可能正好相反。能正好相反。04年7月12管理运筹学讲义 所以，每个月管理层面临的所以，每个月管理层面临的关键问题关键问题是选择产是选择产品组合（品组合（Product Mix），以尽可能多地获取利润。），以尽可能多地获取利润。这一选择是很复杂的，因为它需要考虑当前生这一选择是很复杂的，因为它需要考虑当前生产产品必须的产产品必须的各种资源的可得数量各种资源的可得数量。六项最重要的。六项最重要的资源为：资源为：四种类型的原木（根据原木的质量区分）；四种类型的原木（根据原木的质量区分）；生产胶合板的两项关键作业的生产能力（磨压作业生产胶合板的两项关键作业的生产能力（磨压作业和抛光作业）。和抛光作业）。04年7月13管理运筹学讲义从从1980年开始，潘得罗索工业公司管理部门每年开始，潘得罗索工业公司管理部门每个月使用个月使用线性规划线性规划决定下个月的产品组合。线性规决定下个月的产品组合。线性规划的数学模型考虑了这一决策的所有相关限制条件，划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得资源，然后求解模包括生产产品所需的有限的可得资源，然后求解模型，找出型，找出可行并且最大的可能利润产品组合可行并且最大的可能利润产品组合。线性规划还给潘得罗索工业公司的管理层提供线性规划还给潘得罗索工业公司的管理层提供了其它一些有价值的信息，包括了其它一些有价值的信息，包括当前生产中某一特当前生产中某一特定资源的采购决策及其对利润的影响定资源的采购决策及其对利润的影响。例如，假设。例如，假设公司为生产某一特别赚钱的产品所需的某类原木只公司为生产某一特别赚钱的产品所需的某类原木只有少量供应，线性规划将表明如果赶紧购买该类原有少量供应，线性规划将表明如果赶紧购买该类原木会对产品组合以及利润产生多大的影响。木会对产品组合以及利润产生多大的影响。04年7月14管理运筹学讲义采用线性规划后，潘得罗索工业公司的成绩是采用线性规划后，潘得罗索工业公司的成绩是显著的。产品组合调整使公司总利润增加了显著的。产品组合调整使公司总利润增加了20%，线性规划的其他贡献包括更好的原材料利用、更好线性规划的其他贡献包括更好的原材料利用、更好的资本投资和更好的人员利用。的资本投资和更好的人员利用。04年7月15管理运筹学讲义案例案例2：航空业的成本控制航空业的成本控制 航空业在航空业在1983年和年和1984年发生了史无前例的行年发生了史无前例的行业竞争，尽管如此，联合航空公司还是开通了业竞争，尽管如此，联合航空公司还是开通了48个个新机场的服务，并且取得了很大的增长。新机场的服务，并且取得了很大的增长。1984年，年，它是唯一的一家在美国全部它是唯一的一家在美国全部50个州开通服务的公司，个州开通服务的公司，1984年的收入比年的收入比1983年增长了年增长了6个百分点，达到个百分点，达到62亿亿美元，而同时成本的增长少于美元，而同时成本的增长少于2%，因此营运利润提，因此营运利润提高，达到了亿美元。高，达到了亿美元。04年7月16管理运筹学讲义 在航空业，在航空业，成本控制是关键成本控制是关键。作为公司管理扩。作为公司管理扩展的一部分，展的一部分，1982年联合航空公司的高层管理部门年联合航空公司的高层管理部门实施了一个成本控制项目，实施了一个成本控制项目，目标目标是根据消费者的需是根据消费者的需求进行求进行工作排程工作排程，以，以改进航空订票处和机场工作人改进航空订票处和机场工作人员的利用率员的利用率。那时，联航在其那时，联航在其11个航班订票处有超过个航班订票处有超过4000名名机场销售代表和支持人员。在机场销售代表和支持人员。在10个最大的机场，大个最大的机场，大约有约有1000名顾客服务代表，有些是兼职的，每班名顾客服务代表，有些是兼职的，每班28小时不等；大部分是全职的，每班小时不等；大部分是全职的，每班810小时，有许小时，有许多不同的上班时间。每个订票处都是全天多不同的上班时间。每个订票处都是全天24小时营小时营业（通过电话订票），各个重要的机场也是如此。业（通过电话订票），各个重要的机场也是如此。04年7月17管理运筹学讲义 为了更有效地满足服务要求，在每个地点为所为了更有效地满足服务要求，在每个地点为所有员工进行工作排程，这是一个组合的梦魇。一旦有员工进行工作排程，这是一个组合的梦魇。一旦一名雇员上了班，就会工作一个班次（一名雇员上了班，就会工作一个班次（210小时不小时不等），只有就餐和每隔两个小时短暂的休息时间。等），只有就餐和每隔两个小时短暂的休息时间。那么，一周那么，一周7天及一天天及一天24小时，每个班次需要多少雇小时，每个班次需要多少雇员上班呢？如何排程？幸运的是，线性规划能解决员上班呢？如何排程？幸运的是，线性规划能解决这些组合的梦魇问题。这些组合的梦魇问题。据估计，建立在线性规划基础上的计算机规划据估计，建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上系统每年为联合航空公司在直接薪酬和津贴成本上节省了节省了600万美元，得到的其它好处包括改善客户服万美元，得到的其它好处包括改善客户服务以及降低雇员的工作负担。务以及降低雇员的工作负担。04年7月18管理运筹学讲义 线性规划问题的数学模型线性规划问题的数学模型例例1：一家玻璃制品公司生产带有花样图案的一家玻璃制品公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工而成，然后进入储藏室冷却至室温。花瓶液态加工而成，然后进入储藏室冷却至室温。花瓶有大、小两种尺寸，但生产过程几乎相当，而且使有大、小两种尺寸，但生产过程几乎相当，而且使用同一种材料。不论尺寸，每一个花瓶都需要用同一种材料。不论尺寸，每一个花瓶都需要20分分钟的艺术加工，每周艺术加工工作时间为钟的艺术加工，每周艺术加工工作时间为40小时；小时；大、小花瓶每个需彩色玻璃大、小花瓶每个需彩色玻璃2 OZ和和1 OZ，每周可用，每周可用的玻璃为的玻璃为160 OZ；另外，一个小花瓶占用；另外，一个小花瓶占用2单位储存单位储存空间，大花瓶占用空间，大花瓶占用3个单位储存空间，一共有个单位储存空间，一共有260个个储存空间。大、小花瓶的利润贡献率分别为储存空间。大、小花瓶的利润贡献率分别为12元元/个个和和10元元/个。问应该怎样安排生产，利润值最大。个。问应该怎样安排生产，利润值最大。04年7月19管理运筹学讲义花瓶种类占用材料（OZ）艺术加工（小时）储存空间（1单位）利润值（元）大花瓶21/3312小花瓶11/3210每周可用能力1604026004年7月20管理运筹学讲义分析建模分析建模：用用B表示每周生产大花瓶的数量，表示每周生产大花瓶的数量，S表示每周生产小花瓶的数量，则决策变量表示每周生产小花瓶的数量，则决策变量(Decision Variables)为为B、S。目标函数目标函数(Objective Function)：材料约束材料约束(Constraint of material)：时间约束时间约束(Constraint of time)：储存约束储存约束(Constraint of inventory)：非负约束非负约束(Sign restriction)：04年7月21管理运筹学讲义模型模型：04年7月22管理运筹学讲义由上可知，数学建模过程主要有四个步骤：由上可知，数学建模过程主要有四个步骤：确定决策变量；确定决策变量；确定目标函数；确定目标函数；确定约束条件；确定约束条件；确定非负约束。确定非负约束。04年7月23管理运筹学讲义例例2：某寻呼台每天需要话务员人数、值班时某寻呼台每天需要话务员人数、值班时间以及工资情况如下表所示。每班话务员在轮班开间以及工资情况如下表所示。每班话务员在轮班开始时报到，并连续工作始时报到，并连续工作9小时。问如何安排，使得既小时。问如何安排，使得既满足需求又使总支付工资最低，试建立数学模型。满足需求又使总支付工资最低，试建立数学模型。04年7月24管理运筹学讲义时 间最少人数每人工资0366036460698559121050121513481518154518211350212485604年7月25管理运筹学讲义分析建模分析建模：决策变量为从第决策变量为从第 i 班开始工作的人班开始工作的人数，设为数，设为 xi（i=1,2,3,4,5,6,7,8）。）。目标函数目标函数：04年7月26管理运筹学讲义第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：非负约束：非负约束：04年7月27管理运筹学讲义模型模型：04年7月28管理运筹学讲义例例3：某集团有某集团有1000000元资金供投资，该集团元资金供投资，该集团有有5个可供选择的投资项目，其中各种资料如下表：个可供选择的投资项目，其中各种资料如下表：投资项目风险(%)红利(%)增长(%)信用度110510112681783187141041262245410710该集团的目标为：投资风险最小，每年红利至该集团的目标为：投资风险最小，每年红利至少少80000元，最低平均增长率元，最低平均增长率14%，最低平均信用度，最低平均信用度6，请用线性规划方法描述该问题。，请用线性规划方法描述该问题。04年7月29管理运筹学讲义分析建模分析建模：决策变量为各项目的投资数额，设决策变量为各项目的投资数额，设为为 xi（i=1,2,3,4,5）。）。目标函数目标函数：投资额约束：投资额约束：红利约束：红利约束：增长额约束：增长额约束：平均信用度约束：平均信用度约束：非负约束：非负约束：04年7月30管理运筹学讲义模型模型：04年7月31管理运筹学讲义例例4：某石油公司利用三种油料生产两种混合某石油公司利用三种油料生产两种混合原料。每种油的成本和每天的可用量如表所示：原料。每种油的成本和每天的可用量如表所示：油成本，元/L可用量，LA810000B1015000C122000004年7月32管理运筹学讲义两种混合原料中各种油料所占比例如下表所示：两种混合原料中各种油料所占比例如下表所示：混合原料油料A油料B油料C1最多占25%最少占30%最多占40%2最少占20%最多占50%最少占30%原料售价为原料售价为30元元/L，原料售价为，原料售价为35元元/L，该公，该公司有一项长期合同，每天供应两种原料各司有一项长期合同，每天供应两种原料各10000L。试建立该问题的数学规划模型。试建立该问题的数学规划模型。04年7月33管理运筹学讲义分析建模分析建模：决策变量为加入到原料中的各种决策变量为加入到原料中的各种油料的量：油料的量：A 1为加入原料中的油料为加入原料中的油料 A 的升数；的升数；A 2为加入原料中的油料为加入原料中的油料 A 的升数；的升数；B 1为加入原料中的油料为加入原料中的油料 B 的升数；的升数；B 2为加入原料中的油料为加入原料中的油料 B 的升数；的升数；C 1为加入原料中的油料为加入原料中的油料 C 的升数；的升数；C 2为加入原料中的油料为加入原料中的油料 C 的升数。的升数。04年7月34管理运筹学讲义原料和原料的产量：原料和原料的产量：原料：原料：ABC原料：原料：ABC各种油料的使用量：各种油料的使用量：油料油料A：AA 2 2油料油料B：BB 2 2油料油料C：CC 2 204年7月35管理运筹学讲义两种原料的销售收入：两种原料的销售收入：30(ABC)35(ABC)三种油料的成本：三种油料的成本：8(AA 2 2)10(BB 2 2)12(CC 2 2)目标函数为：目标函数为：04年7月36管理运筹学讲义三种可用油料的约束：三种可用油料的约束：各种油料所占比例的约束：各种油料所占比例的约束：04年7月37管理运筹学讲义长期供货合同约束：长期供货合同约束：非负约束：非负约束：04年7月38管理运筹学讲义模型模型：04年7月39管理运筹学讲义 两变量问题的图解法两变量问题的图解法对于只有对于只有两个决策变量两个决策变量的线性规划问题，可以的线性规划问题，可以用作图法求解。用作图法求解。图解法不仅直观，而且可从中得到有关线性规图解法不仅直观，而且可从中得到有关线性规划问题的许多重要结论，有助于理解线性规划一般划问题的许多重要结论，有助于理解线性规划一般解法的基本原理。解法的基本原理。In this section,we learn how to solve graphically those linear programming problems that involve only two variables.04年7月40管理运筹学讲义图解法的过程介绍图解法的过程介绍规划问题求解的几种可能结果规划问题求解的几种可能结果图解法的启示图解法的启示04年7月41管理运筹学讲义例例1：一、图解法的过程介绍一、图解法的过程介绍04年7月42管理运筹学讲义040D501003040可行域可行域(Feasible Region)04年7月43管理运筹学讲义解方程组：解方程组：得最优解得最优解(Optimal Solution)：04年7月44管理运筹学讲义上述图解过程涉及的上述图解过程涉及的几个概念几个概念：凸集凸集(Convex Sets)A set of points S is a convex set if the line segment joining any pair of points in S is wholly contained in S.极点极点(Extreme Point)For any convex set S,a point P in S is an extreme point if each line segment that lies completely in S and contains the point P has P as an endpoint of the line segment.04年7月45管理运筹学讲义例例2：04年7月46管理运筹学讲义01424126(无界无界)可行域可行域(Unbounded Feasible Region)D04年7月47管理运筹学讲义解方程组：解方程组：得最优解得最优解(Optimal Solution)：04年7月48管理运筹学讲义用图解法求解线性规划，可能会出现以下四种用图解法求解线性规划，可能会出现以下四种情况：情况：有唯一最优解有唯一最优解have a unique optimal solution(如如例例1、例例2)；有无穷多最优解有无穷多最优解have an infinite number of optimal solutions(alternative or multiple optimal solutions)(如如例例3)；二、规划问题求解的几种可能结果二、规划问题求解的几种可能结果04年7月49管理运筹学讲义 无界解无界解(有可行解，但无有限最优解有可行解，但无有限最优解)unbounded(如如例例4)；无可行解无可行解have no feasible solutions(如如例例5)。04年7月50管理运筹学讲义例例3：04年7月51管理运筹学讲义例例4：04年7月52管理运筹学讲义例例5：04年7月53管理运筹学讲义三、图解法的启示三、图解法的启示 线性规划问题可行域非空线性规划问题可行域非空，则一定为凸集；则一定为凸集；线性规划问题最优解存在，那么唯一最优解一定线性规划问题最优解存在，那么唯一最优解一定是可行域凸集的某个顶点（极点）；无穷最优解一是可行域凸集的某个顶点（极点）；无穷最优解一定是可行域的某个边或某个面；定是可行域的某个边或某个面；规划问题规划问题一般解题思路一般解题思路：先找出凸集的任一顶点，：先找出凸集的任一顶点，计算该点处目标函数值，与其他顶点的目标函数值计算该点处目标函数值，与其他顶点的目标函数值比较，如果该点值最大，那么该点就是最优解或最比较，如果该点值最大，那么该点就是最优解或最优解之一；如果不是，那么就对目标函数值比该点优解之一；如果不是，那么就对目标函数值比该点大的另一点重复上述过程，直到找到最优解。大的另一点重复上述过程，直到找到最优解。04年7月54管理运筹学讲义例例6：04年7月55管理运筹学讲义 线性规划模型的标准形式及解的概念线性规划模型的标准形式及解的概念线性规划模型的标准形式线性规划模型的标准形式化非标准形式为标准形式化非标准形式为标准形式有关解的概念有关解的概念04年7月56管理运筹学讲义 对于一般线性规划模型，目标函数可以求最大，对于一般线性规划模型，目标函数可以求最大，也可以求最小；约束条件可以是也可以求最小；约束条件可以是“”，也可以是，也可以是“”或或“=”型。因此，一般线性规划模型可表示型。因此，一般线性规划模型可表示为为一、线性规划模型的标准形式一、线性规划模型的标准形式04年7月57管理运筹学讲义 为论述方便，通常把为论述方便，通常把最大化、等式约束型最大化、等式约束型的线的线性规划称为线性规划的性规划称为线性规划的标准型标准型(Standard Form)：04年7月58管理运筹学讲义 线性规划的标准型还可写为线性规划的标准型还可写为“号简写式号简写式”：04年7月59管理运筹学讲义 线性规划的标准型的线性规划的标准型的“矩阵形式矩阵形式”为为：04年7月60管理运筹学讲义 线性规划的标准型的线性规划的标准型的“向量向量形式形式”为为：04年7月61管理运筹学讲义 一般地一般地，我们还对标准型作如下假定：我们还对标准型作如下假定：矩阵矩阵A的秩的秩rank(A)=m，0mn。即标准型中。即标准型中的约束方程彼此独立，没有多余方程，且约束方程的约束方程彼此独立，没有多余方程，且约束方程个数小于变量的个数。个数小于变量的个数。b0.若有若有bj0，而，而表上与之对应列元素全小于或等于表上与之对应列元素全小于或等于0，则此线性规划，则此线性规划无有限最优解。无有限最优解。例例：求解线性规划：求解线性规划：04年7月103管理运筹学讲义 解：首先将线性规划化为标准型解：首先将线性规划化为标准型04年7月104管理运筹学讲义 单纯形表为：单纯形表为：CBXBB-1b2x12x20 x30 x40 x31-11100 x44-1201检验数检验数j=cj-CBB-1Pj2200 由上表知，线性规划无有限由上表知，线性规划无有限最优解。最优解。04年7月105管理运筹学讲义退化解退化解若单纯形表中，若单纯形表中，最优解最优解的某个分量的某个分量bk=0，则称此解为一个退化解。，则称此解为一个退化解。04年7月106管理运筹学讲义第三节对偶问题与灵敏度分析第三节对偶问题与灵敏度分析Duality and Sensitivity Analysis 线性规划的对偶问题线性规划的对偶问题 对偶解的经济解释对偶解的经济解释 灵敏度分析灵敏度分析04年7月107管理运筹学讲义 线性规划的对偶问题线性规划的对偶问题 随着线性规划应用的逐步深入，人们发现一个随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随着与之配对的、两者有密切线性规划问题往往伴随着与之配对的、两者有密切联系的另一个线性规划问题。我们将其中一个称为联系的另一个线性规划问题。我们将其中一个称为原问题，另一个称为对偶问题。原问题，另一个称为对偶问题。由对偶问题引伸出来的对偶解有着重要的经济由对偶问题引伸出来的对偶解有着重要的经济意义，是经济学中重要的概念与工具之一。意义，是经济学中重要的概念与工具之一。04年7月108管理运筹学讲义对偶问题的实例对偶问题的实例线性规划对偶问题的基本性质线性规划对偶问题的基本性质化原问题为对偶问题化原问题为对偶问题04年7月109管理运筹学讲义一、对偶问题的实例一、对偶问题的实例 例例1：某家具厂木器车间生产木门与木窗两种某家具厂木器车间生产木门与木窗两种产品，加工木门收入为产品，加工木门收入为56元元/扇，加工木窗收入为扇，加工木窗收入为30元元/扇。生产一扇木门需要木工扇。生产一扇木门需要木工4小时，油漆工小时，油漆工2小时；小时；生产一扇木窗需要木工生产一扇木窗需要木工3小时，油漆工小时，油漆工1小时。该车小时。该车间每日可用木工总工时为间每日可用木工总工时为120小时，油漆工总工时为小时，油漆工总工时为50小时，问该车间应如何安排生产才能使每日收入小时，问该车间应如何安排生产才能使每日收入最大？最大？04年7月110管理运筹学讲义 令该车间每日安排生产木门令该车间每日安排生产木门x1 扇，木窗扇，木窗x2 扇，扇，则线性规划模型为：则线性规划模型为：解得：解得：04年7月111管理运筹学讲义 现在从另一角度来考虑该车间的生产问题：现在从另一角度来考虑该车间的生产问题：假如有一个个体经营者，手中有一批木器家具假如有一个个体经营者，手中有一批木器家具生产订单，他想租借该木器车间完成他的订单，于生产订单，他想租借该木器车间完成他的订单，于是他必须考虑支付给该车间租用木工与油漆工每个是他必须考虑支付给该车间租用木工与油漆工每个工时的价格。此时他必须构造一个数学模型来研究工时的价格。此时他必须构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图从而愿意如何定价才能既使木器车间觉得有利可图从而愿意替他加工这批订单，又使自己所付的工时费用总数替他加工这批订单，又使自己所付的工时费用总数最少？最少？04年7月112管理运筹学讲义 设设w1 为付给木工每工时的价格，为付给木工每工时的价格，w2 为付给油漆为付给油漆工每工时的价格，则线性规划模型为：工每工时的价格，则线性规划模型为：解得：解得：04年7月113管理运筹学讲义04年7月114管理运筹学讲义04年7月115管理运筹学讲义 显然，线性规划显然，线性规划LP1 和和LP2 既有紧密联系，又有既有紧密联系，又有一定区别：它们都使用木器生产车间相同的数据，一定区别：它们都使用木器生产车间相同的数据，只是这些数据在模型中所处的位置不同，所要表达只是这些数据在模型中所处的位置不同，所要表达的含义也不同。的含义也不同。若称线性规划若称线性规划LP1 为为原问题原问题(Primal Problem)，则，则称线性规划称线性规划LP2 为为LP1 的的对偶问题对偶问题(Dual Problem)。04年7月116管理运筹学讲义04年7月117管理运筹学讲义二、化原问题为对偶问题二、化原问题为对偶问题原问题对偶问题目标函数形式max目标函数形式min变量n个变量约束n个约束变量 0约束 变量 0约束 无正负限制约束=约束m个约束变量m个变量约束 变量 0约束 变量0 约束=无正负限制约束方程右端项目标函数中的价值函数目标函数中的价值系数约束方程的右端项04年7月118管理运筹学讲义 例例2：写出下面线性规划的对偶规划：写出下面线性规划的对偶规划：04年7月119管理运筹学讲义 解：解：令对偶规划的决策变量为令对偶规划的决策变量为y1、y2、y3，则原，则原线性规划的对偶规划：线性规划的对偶规划：04年7月120管理运筹学讲义 例例3：写出下面线性规划的对偶规划：写出下面线性规划的对偶规划：04年7月121管理运筹学讲义 解：解：令对偶规划的决策变量为令对偶规划的决策变量为y1、y2、y3，则原，则原线性规划的对偶规划：线性规划的对偶规划：04年7月122管理运筹学讲义三、线性规划对偶问题的基本性质三、线性规划对偶问题的基本性质 对称性：对称性：一个线性规划的对偶问题的对偶问题一个线性规划的对偶问题的对偶问题恰是原问题。恰是原问题。弱对偶性弱对偶性(Weak Duality)：假定假定是原规划是原规划()的任的任一可行解，是对偶规划一可行解，是对偶规划()的任一可行解，的任一可行解，则有则有CXYb。无界性：无界性：若若原规划原规划(对偶规划对偶规划)为无界解，则其为无界解，则其对偶规划对偶规划(原规划原规划)无可行解无可行解(逆命题不成立逆命题不成立)。04年7月123管理运筹学讲义 设设X*是原规划的可行解，是原规划的可行解，Y*是对偶规划的可是对偶规划的可行解。当行解。当CX*=Y*b时，时，X*、Y*皆为最优解。皆为最优解。强对偶性：强对偶性：原规划有最优解，则原规划有最优解，则对偶规划也有对偶规划也有最优解，且最优值相同最优解，且最优值相同。互补松弛互补松弛性：性：在线性规划的最优解中，若对应在线性规划的最优解中，若对应于某约束条件的对偶变量值为非零，则该约束条件于某约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等取严格等式；另一方面，如果约束条件取严格不等式，则其对应的对偶变量一定为零。式，则其对应的对偶变量一定为零。04年7月124管理运筹学讲义 例例4：已知线性规划已知线性规划的对偶规划的最优解为的对偶规划的最优解为试用对偶问题的互补松弛性求出原规划的最优解。试用对偶问题的互补松弛性求出原规划的最优解。04年7月125管理运筹学讲义 对偶解的经济解释对偶解的经济解释Economic Interpretation of the Dual Problem 由由强对偶性强对偶性可知，原规划可知，原规划有最优解，则有最优解，则对偶规对偶规划也有最优解，且最优值相同划也有最优解，且最优值相同。于是最优值为。于是最优值为04年7月126管理运筹学讲义 由上式可得由上式可得这表明线性规划中第种资源增加一个单位时，总这表明线性规划中第种资源增加一个单位时，总利润将增加利润将增加yi*。这个概念在西方经济学中被称为资。这个概念在西方经济学中被称为资源的源的“影子价格影子价格”(shadow price)。事实上，影子价格是事实上，影子价格是在最优产品组合在最优产品组合下，某种下，某种资源的资源的边际产出边际产出或或机会成本机会成本，表明在最优产品组合，表明在最优产品组合状态下，该资源的状态下，该资源的“潜在价值潜在价值”。04年7月127管理运筹学讲义影子价格可由单纯形表确定影子价格可由单纯形表确定04年7月128管理运筹学讲义 用单纯形表解线性规划：用单纯形表解线性规划：CBXBB-1b56x130 x20 x30 x40 x312043100 x4502101检验数检验数j=cj-CBB-1Pj56300030250 x320011-256x12511/201/2检验数检验数j=cj-CBB-1Pj020-28205030 x220011-256x11510-1/23/2检验数检验数j=cj-CBB-1Pj00-2-2404年7月129管理运筹学讲义 灵敏度分析灵敏度分析资源向量的分量资源向量的分量b i 变化的分析变化的分析价格系数价格系数cj变化的分析变化的分析主要分析：主要分析：bi在什么范围内变化不影响最优解。在什么范围内变化不影响最优解。主要分析：主要分析：cj在什么范围内变化不影响最优解。在什么范围内变化不影响最优解。04年7月130管理运筹学讲义追加新变量追加新变量的分析的分析约束矩阵变化约束矩阵变化的分析的分析主要分析：主要分析：在原问题最优解已求出的情况下，在原问题最优解已求出的情况下，增加新的决策变量会引起最优解怎样的变化。增加新的决策变量会引起最优解怎样的变化。主要分析：主要分析：在原问题最优解已求出的情况下，在原问题最优解已求出的情况下，基向量或非基向量变化将引起最优解怎样的变化。基向量或非基向量变化将引起最优解怎样的变化。04年7月131管理运筹学讲义第四节线性规划软件简介第四节线性规划软件简介用用LINDO软件解线性规划软件解线性规划用用Excel软件解线性规划软件解线性规划04年7月132管理运筹学讲义 例例1：用软件求解线性规划：用软件求解线性规划：04年7月133管理运筹学讲义 例例2：用软件求解线性规划：用软件求解线性规划：04年7月134管理运筹学讲义 例例3：用软件求下列线性规划的对偶解，并进用软件求下列线性规划的对偶解，并进行灵敏度分析：行灵敏度分析：04年7月135管理运筹学讲义第五节运输问题第五节运输问题 运输问题运输问题(Transportation Problem)研究研究如何制定最