规划技术线性规划课件

《规划技术线性规划课件》由会员分享，可在线阅读，更多相关《规划技术线性规划课件（166页珍藏版）》请在金锄头文库上搜索。

1、第二讲第二讲规划技术规划技术线性规划线性规划管理科学系管理科学系 钟钟 胜胜 副教授副教授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.

2、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 Prog

3、ramming)是运筹学的重是运筹学的重要组成部分，也是最基础的部分。要组成部分，也是最基础的部分。自自1947年丹齐格年丹齐格(G.B.Dantzig)提出了求解线提出了求解线性规划的一般方法单纯形法以来，线性规划在性规划的一般方法单纯形法以来，线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性规划的应用领域题的规模及运算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军更加广泛。无论工业、农业、商业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一事、经济计划和管理决策等领域都有应

4、用。大到一个国家、一个地区，小到一个企业、一个车间、一个国家、一个地区，小到一个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。个班组都有运用线性规划后提高经济效益的例子。04年7月3规划技术线性规划课件第一节线性规划的模型与图解法第一节线性规划的模型与图解法第二节单纯形法第二节单纯形法第三节对偶问题与灵敏度分析第三节对偶问题与灵敏度分析第四节线性规划软件简介第四节线性规划软件简介第五节运输问题第五节运输问题第六节线性整数规划第六节线性整数规划第七节线性规划应用实例第七节线性规划应用实例04年7月4规划技术线性规划课件See You!04年7月5规划技术线性规划课件第一节线性规划

5、的模型与图解法第一节线性规划的模型与图解法 1.1线性规划问题及其数学模型线性规划问题及其数学模型 1.2两变量问题的图解法两变量问题的图解法 1.3线性规划模型的标准形式及解的概念线性规划模型的标准形式及解的概念04年7月6规划技术线性规划课件 1.1线性规划问题及其数学模型线性规划问题及其数学模型 1.1.1线性规划问题的提出及主要概念线性规划问题的提出及主要概念 1.1.2线性规划问题的数学模型线性规划问题的数学模型 In this section,we introduce linear programming and define some important terms that a

6、re used to describe linear programming problems.04年7月7规划技术线性规划课件 1.1.1线性规划问题的提出及主要概念线性规划问题的提出及主要概念在生产管理和经营活动中，组织常常必须对如在生产管理和经营活动中，组织常常必须对如何向不同的活动分配资源的问题做出决策，以便最何向不同的活动分配资源的问题做出决策，以便最好地达成组织的目标。好地达成组织的目标。这样的问题通常有两类，这样的问题通常有两类，一类一类是如何合理地使是如何合理地使用有限的劳动力、设备、资金等资源，以最大化效用有限的劳动力、设备、资金等资源，以最大化效益；益；另一类另一类是为了达

7、到一定的目标，应如何组织生是为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分产，或合理安排工艺流程，或调整产品的成分以使资源消耗最少。以使资源消耗最少。04年7月8规划技术线性规划课件向不同的活动分配的资源可以是资金、不同的向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些媒体做广告、金融活动、进行资金投资或其他一些活动。活动。由于所有活动都要求一定资源作支撑，而

8、资源由于所有活动都要求一定资源作支撑，而资源却是有限的，这必然导致活动间的冲突与矛盾。这却是有限的，这必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使就需要管理者利用一些科学的方法进行协调，以使资源达到最大的效用。资源达到最大的效用。04年7月9规划技术线性规划课件显然，上述活动所引起的问题是一类显然，上述活动所引起的问题是一类有约束的有约束的最优化问题最优化问题（Constrained Optimization）。）。线性规划线性规划正是解决有约束的最优化问题的一种正是解决有约束的最优化问题的一种常用的方法，其涉及的常用的方法，其涉及的主要概念主要概念包括：包括：

9、决策变量（决策变量（Decision Variables）:最优化问题最优化问题的决策对象；的决策对象； 约束条件（约束条件（Constraints）:对决策所能产生的对决策所能产生的结果的限制。结果的限制。 目标（目标（Objective）:决策所希望达到的最优结决策所希望达到的最优结果（最大或最小）；果（最大或最小）；04年7月10规划技术线性规划课件解决线性规划问题的过程通常分为四个步骤：解决线性规划问题的过程通常分为四个步骤： 定义问题和收集数据。定义问题和收集数据。必需向管理者咨询所要必需向管理者咨询所要考虑问题涉及到的数据及确定研究的合理目标。考虑问题涉及到的数据及确定研究的合理目

10、标。 建立模型，用恰当的数学式表示问题。建立模型，用恰当的数学式表示问题。 求出问题的最优解。求出问题的最优解。 进行敏感性分析，检查条件发生变化时可能发进行敏感性分析，检查条件发生变化时可能发生的情况。生的情况。04年7月11规划技术线性规划课件案例案例1：潘得罗索工业公司的产品组合潘得罗索工业公司的产品组合 潘得罗索工业公司是一家墨西哥公司，截止潘得罗索工业公司是一家墨西哥公司，截止1998年，公司产销量占该国的四分之一。年，公司产销量占该国的四分之一。 与其他胶合板生产厂商一样，潘得罗索工业公与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品因厚度和所用木材的质量而有所不同。司的许多产

11、品因厚度和所用木材的质量而有所不同。由于产品在一个竞争的环境中进行销售，产品的价由于产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有化。结果导致每项产品对公司整体利润的贡献也有很大的变化。这样，在某个月一个产品可能比另一很大的变化。这样，在某个月一个产品可能比另一个产品赚取更大的利润，而在下一个月的情况则可个产品赚取更大的利润，而在下一个月的情况则可能正好相反。能正好相反。04年7月12规划技术线性规划课件 所以，每个月管理层面临的所以，每个月管理层面临的关键问题关键问题

12、是选择产是选择产品组合（品组合（Product Mix），以尽可能多地获取利润。），以尽可能多地获取利润。 这一选择是很复杂的，因为它需要考虑当前生这一选择是很复杂的，因为它需要考虑当前生产产品必须的产产品必须的各种资源的可得数量各种资源的可得数量。六项最重要的。六项最重要的资源为：资源为： 四种类型的原木（根据原木的质量区分）；四种类型的原木（根据原木的质量区分）； 生产胶合板的两项关键作业的生产能力（磨压作业生产胶合板的两项关键作业的生产能力（磨压作业和抛光作业）。和抛光作业）。04年7月13规划技术线性规划课件从从1980年开始，潘得罗索工业公司管理部门每年开始，潘得罗索工业公司管理部门

13、每个月使用个月使用线性规划线性规划决定下个月的产品组合。线性规决定下个月的产品组合。线性规划的数学模型考虑了这一决策的所有相关限制条件，划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得资源，然后求解模包括生产产品所需的有限的可得资源，然后求解模型，找出型，找出可行并且最大的可能利润产品组合可行并且最大的可能利润产品组合。 线性规划还给潘得罗索工业公司的管理层提供线性规划还给潘得罗索工业公司的管理层提供了其它一些有价值的信息，包括了其它一些有价值的信息，包括当前生产中某一特当前生产中某一特定资源的采购决策及其对利润的影响定资源的采购决策及其对利润的影响。例如，假设。例如

14、，假设公司为生产某一特别赚钱的产品所需的某类原木只公司为生产某一特别赚钱的产品所需的某类原木只有少量供应，线性规划将表明如果赶紧购买该类原有少量供应，线性规划将表明如果赶紧购买该类原木会对产品组合以及利润产生多大的影响。木会对产品组合以及利润产生多大的影响。04年7月14规划技术线性规划课件采用线性规划后，潘得罗索工业公司的成绩是采用线性规划后，潘得罗索工业公司的成绩是显著的。产品组合调整使公司总利润增加了显著的。产品组合调整使公司总利润增加了20%，线性规划的其他贡献包括更好的原材料利用、更好线性规划的其他贡献包括更好的原材料利用、更好的资本投资和更好的人员利用。的资本投资和更好的人员利用。

15、04年7月15规划技术线性规划课件案例案例2：航空业的成本控制航空业的成本控制 航空业在航空业在1983年和年和1984年发生了史无前例的行年发生了史无前例的行业竞争，尽管如此，联合航空公司还是开通了业竞争，尽管如此，联合航空公司还是开通了48个个新机场的服务，并且取得了很大的增长。新机场的服务，并且取得了很大的增长。1984年，年，它是唯一的一家在美国全部它是唯一的一家在美国全部50个州开通服务的公司，个州开通服务的公司，1984年的收入比年的收入比1983年增长了年增长了6个百分点，达到个百分点，达到62亿亿美元，而同时成本的增长少于美元，而同时成本的增长少于2%，因此营运利润提，因此营运

16、利润提高，达到了高，达到了5.64亿美元。亿美元。04年7月16规划技术线性规划课件 在航空业，在航空业，成本控制是关键成本控制是关键。作为公司管理扩。作为公司管理扩展的一部分，展的一部分，1982年联合航空公司的高层管理部门年联合航空公司的高层管理部门实施了一个成本控制项目，实施了一个成本控制项目，目标目标是根据消费者的需是根据消费者的需求进行求进行工作排程工作排程，以，以改进航空订票处和机场工作人改进航空订票处和机场工作人员的利用率员的利用率。 那时，联航在其那时，联航在其11个航班订票处有超过个航班订票处有超过4000名名机场销售代表和支持人员。在机场销售代表和支持人员。在10个最大的机

17、场，大个最大的机场，大约有约有1000名顾客服务代表，有些是兼职的，每班名顾客服务代表，有些是兼职的，每班28小时不等；大部分是全职的，每班小时不等；大部分是全职的，每班810小时，有许小时，有许多不同的上班时间。每个订票处都是全天多不同的上班时间。每个订票处都是全天24小时营小时营业（通过电话订票），各个重要的机场也是如此。业（通过电话订票），各个重要的机场也是如此。04年7月17规划技术线性规划课件 为了更有效地满足服务要求，在每个地点为所为了更有效地满足服务要求，在每个地点为所有员工进行工作排程，这是一个组合的梦魇。一旦有员工进行工作排程，这是一个组合的梦魇。一旦一名雇员上了班，就会工作

18、一个班次（一名雇员上了班，就会工作一个班次（210小时不小时不等），只有就餐和每隔两个小时短暂的休息时间。等），只有就餐和每隔两个小时短暂的休息时间。那么，一周那么，一周7天及一天天及一天24小时，每个班次需要多少雇小时，每个班次需要多少雇员上班呢？如何排程？幸运的是，线性规划能解决员上班呢？如何排程？幸运的是，线性规划能解决这些组合的梦魇问题。这些组合的梦魇问题。 据估计，建立在线性规划基础上的计算机规划据估计，建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上系统每年为联合航空公司在直接薪酬和津贴成本上节省了节省了600万美元，得到的其它好处包括改善客户服万美元，

19、得到的其它好处包括改善客户服务以及降低雇员的工作负担。务以及降低雇员的工作负担。04年7月18规划技术线性规划课件 1.1.2线性规划问题的数学模型线性规划问题的数学模型例例1：一家玻璃制品公司生产带有花样图案的一家玻璃制品公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工而成，然后进入储藏室冷却至室温。花瓶液态加工而成，然后进入储藏室冷却至室温。花瓶有大、小两种尺寸，但生产过程几乎相当，而且使有大、小两种尺寸，但生产过程几乎相当，而且使用同一种材料。不论尺寸，每一个花瓶都需要用同一种材料。不论尺寸，每一个花瓶都需要20分分钟

20、的艺术加工，每周艺术加工工作时间为钟的艺术加工，每周艺术加工工作时间为40小时；小时；大、小花瓶每个需彩色玻璃大、小花瓶每个需彩色玻璃2 OZ和和1 OZ，每周可用，每周可用的玻璃为的玻璃为160 OZ；另外，一个小花瓶占用；另外，一个小花瓶占用2单位储存单位储存空间，大花瓶占用空间，大花瓶占用3个单位储存空间，一共有个单位储存空间，一共有260个个储存空间。大、小花瓶的利润贡献率分别为储存空间。大、小花瓶的利润贡献率分别为12元元/个个和和10元元/个。问应该怎样安排生产，利润值最大。个。问应该怎样安排生产，利润值最大。04年7月19规划技术线性规划课件花瓶种类占用材料（OZ）艺术加工（小时

21、）储存空间（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)：非负约束非负约

22、束(Sign restriction) ：04年7月21规划技术线性规划课件模型模型：04年7月22规划技术线性规划课件由上可知，数学建模过程主要有四个步骤：由上可知，数学建模过程主要有四个步骤：确定决策变量；确定决策变量；确定目标函数；确定目标函数；确定约束条件；确定约束条件；确定非负约束。确定非负约束。04年7月23规划技术线性规划课件例例2：某寻呼台每天需要话务员人数、值班时某寻呼台每天需要话务员人数、值班时间以及工资情况如下表所示。每班话务员在轮班开间以及工资情况如下表所示。每班话务员在轮班开始时报到，并连续工作始时报到，并连续工作9小时。问如何安排，使得既小时。问如何安排，使得既满足

23、需求又使总支付工资最低，试建立数学模型。满足需求又使总支付工资最低，试建立数学模型。04年7月24规划技术线性规划课件时 间最少人数每人工资0366036460698559121050121513481518154518211350212485604年7月25规划技术线性规划课件分析建模分析建模：决策变量为从第决策变量为从第 i 班开始工作的人班开始工作的人数，设为数，设为 xi（i =1,2,3,4,5,6,7,8）。）。目标函数目标函数：04年7月26规划技术线性规划课件第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数

24、约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：非负约束：非负约束：04年7月27规划技术线性规划课件模型模型：04年7月28规划技术线性规划课件例例3：某集团有某集团有1000000元资金供投资，该集团元资金供投资，该集团有有5个可供选择的投资项目，其中各种资料如下表：个可供选择的投资项目，其中各种资料如下表：投资项目风险(%) 红利(%) 增长(%)信用度110510112681783187141041262245410710该集团的目标为：投资风险最小，每年红利至该集团的目标为：投资风险最小，每年红利至少少80000元，最低平均增长

25、率元，最低平均增长率14%，最低平均信用度，最低平均信用度6，请用线性规划方法描述该问题。，请用线性规划方法描述该问题。04年7月29规划技术线性规划课件分析建模分析建模：决策变量为各项目的投资数额，设决策变量为各项目的投资数额，设为为 xi（i =1,2,3,4,5）。）。目标函数目标函数：投资额约束：投资额约束：红利约束：红利约束：增长额约束：增长额约束：平均信用度约束：平均信用度约束：非负约束：非负约束：04年7月30规划技术线性规划课件模型模型：04年7月31规划技术线性规划课件例例4：某石油公司利用三种油料生产两种混合某石油公司利用三种油料生产两种混合原料。每种油的成本和每天的可用量

26、如表所示：原料。每种油的成本和每天的可用量如表所示：油成本，元/L可用量，LA810000B1015000C122000004年7月32规划技术线性规划课件两种混合原料中各种油料所占比例如下表所示：两种混合原料中各种油料所占比例如下表所示：混合原料油料A油料B油料C1最多占25%最少占30% 最多占40%2最少占20%最多占50% 最少占30%原料售价为原料售价为30元元/L，原料售价为，原料售价为35元元/L，该公，该公司有一项长期合同，每天供应两种原料各司有一项长期合同，每天供应两种原料各10000L。试建立该问题的数学规划模型。试建立该问题的数学规划模型。04年7月33规划技术线性规划课

27、件分析建模分析建模：决策变量为加入到原料中的各种决策变量为加入到原料中的各种油料的量：油料的量：A 1为加入原料中的油料为加入原料中的油料 A 的升数；的升数；A 2为加入原料中的油料为加入原料中的油料 A 的升数；的升数；B 1为加入原料中的油料为加入原料中的油料 B 的升数；的升数；B 2为加入原料中的油料为加入原料中的油料 B 的升数；的升数；C 1为加入原料中的油料为加入原料中的油料 C 的升数；的升数；C 2为加入原料中的油料为加入原料中的油料 C 的升数。的升数。04年7月34规划技术线性规划课件原料和原料的产量：原料和原料的产量：原料：原料：ABC原料：原料：ABC各种油料的使用

28、量：各种油料的使用量：油料油料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规划技术线性规划

29、课件 1.2两变量问题的图解法两变量问题的图解法对于只有对于只有两个决策变量两个决策变量的线性规划问题，可以的线性规划问题，可以用作图法求解。用作图法求解。图解法不仅直观，而且可从中得到有关线性规图解法不仅直观，而且可从中得到有关线性规划问题的许多重要结论，有助于理解线性规划一般划问题的许多重要结论，有助于理解线性规划一般解法的基本原理。解法的基本原理。In this section, we learn how to solve graphically those linear programming problems that involve only two variables.04年7月

30、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

31、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：0

32、4年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(alt

33、ernative 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规划技术线性规划课件三、图解法的启示三、图解法的启示 线性规划问题可行域非空线

34、性规划问题可行域非空，则一定为凸集；则一定为凸集； 线性规划问题最优解存在，那么唯一最优解一定线性规划问题最优解存在，那么唯一最优解一定是可行域凸集的某个顶点（极点）；无穷最优解一是可行域凸集的某个顶点（极点）；无穷最优解一定是可行域的某个边或某个面；定是可行域的某个边或某个面； 规划问题规划问题一般解题思路一般解题思路：先找出凸集的任一顶点，：先找出凸集的任一顶点，计算该点处目标函数值，与其他顶点的目标函数值计算该点处目标函数值，与其他顶点的目标函数值比较，如果该点值最大，那么该点就是最优解或最比较，如果该点值最大，那么该点就是最优解或最优解之一；如果不是，那么就对目标函数值比该点优解之一；

35、如果不是，那么就对目标函数值比该点大的另一点重复上述过程，直到找到最优解。大的另一点重复上述过程，直到找到最优解。04年7月54规划技术线性规划课件例例6：04年7月55规划技术线性规划课件 1.3线性规划模型的标准形式及解的概念线性规划模型的标准形式及解的概念线性规划模型的标准形式线性规划模型的标准形式化非标准形式为标准形式化非标准形式为标准形式有关解的概念有关解的概念04年7月56规划技术线性规划课件 对于一般线性规划模型，目标函数可以求最大，对于一般线性规划模型，目标函数可以求最大，也可以求最小；约束条件可以是也可以求最小；约束条件可以是“”，也可以是，也可以是“”或或“=”型。因此，一

36、般线性规划模型可表示型。因此，一般线性规划模型可表示为为一、线性规划模型的标准形式一、线性规划模型的标准形式04年7月57规划技术线性规划课件 为论述方便，通常把为论述方便，通常把最大化、等式约束型最大化、等式约束型的线的线性规划称为线性规划的性规划称为线性规划的标准型标准型(Standard Form)：04年7月58规划技术线性规划课件 线性规划的标准型还可写为线性规划的标准型还可写为“ 号简写式号简写式”： 04年7月59规划技术线性规划课件 线性规划的标准型的线性规划的标准型的“矩阵形式矩阵形式”为为： 04年7月60规划技术线性规划课件 线性规划的标准型的线性规划的标准型的“向量向量

37、形式形式”为为： 04年7月61规划技术线性规划课件 一般地一般地，我们还对标准型作如下假定：我们还对标准型作如下假定： 矩阵矩阵A的秩的秩rank(A)=m，0mn。即标准型中。即标准型中的约束方程彼此独立，没有多余方程，且约束方程的约束方程彼此独立，没有多余方程，且约束方程个数小于变量的个数。个数小于变量的个数。 b0. .若有若有bj0 ，而，而表上与之对应列元素全小于或等于表上与之对应列元素全小于或等于0，则此线性规划，则此线性规划无有限最优解。无有限最优解。 例例：求解线性规划：求解线性规划：04年7月103规划技术线性规划课件 解：首先将线性规划化为标准型解：首先将线性规划化为标准

38、型04年7月104规划技术线性规划课件 单纯形表为：单纯形表为：CBXBB-1b2x12x20x30x40x31-11100x44-1201检验数检验数j=cj-CBB-1Pj2200 由上表知，线性规划无有限由上表知，线性规划无有限最优解。最优解。04年7月105规划技术线性规划课件退化解退化解若单纯形表中，若单纯形表中，最优解最优解的某个分量的某个分量bk=0，则称此解为一个退化解。，则称此解为一个退化解。04年7月106规划技术线性规划课件第三节对偶问题与灵敏度分析第三节对偶问题与灵敏度分析Duality and Sensitivity Analysis 3.1线性规划的对偶问题线性规划

39、的对偶问题 3.2对偶解的经济解释对偶解的经济解释 3.3灵敏度分析灵敏度分析04年7月107规划技术线性规划课件 3.1线性规划的对偶问题线性规划的对偶问题 随着线性规划应用的逐步深入，人们发现一个随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随着与之配对的、两者有密切线性规划问题往往伴随着与之配对的、两者有密切联系的另一个线性规划问题。我们将其中一个称为联系的另一个线性规划问题。我们将其中一个称为原问题，另一个称为对偶问题。原问题，另一个称为对偶问题。 由对偶问题引伸出来的对偶解有着重要的经济由对偶问题引伸出来的对偶解有着重要的经济意义，是经济学中重要的概念与工具之一。意义，是

40、经济学中重要的概念与工具之一。04年7月108规划技术线性规划课件对偶问题的实例对偶问题的实例线性规划对偶问题的基本性质线性规划对偶问题的基本性质化原问题为对偶问题化原问题为对偶问题04年7月109规划技术线性规划课件一、对偶问题的实例一、对偶问题的实例 例例1：某家具厂木器车间生产木门与木窗两种某家具厂木器车间生产木门与木窗两种产品，加工木门收入为产品，加工木门收入为56元元/扇，加工木窗收入为扇，加工木窗收入为30元元/扇。生产一扇木门需要木工扇。生产一扇木门需要木工4小时，油漆工小时，油漆工2小时；小时；生产一扇木窗需要木工生产一扇木窗需要木工3小时，油漆工小时，油漆工1小时。该车小时。

41、该车间每日可用木工总工时为间每日可用木工总工时为120小时，油漆工总工时为小时，油漆工总工时为50小时，问该车间应如何安排生产才能使每日收入小时，问该车间应如何安排生产才能使每日收入最大？最大？04年7月110规划技术线性规划课件 令该车间每日安排生产木门令该车间每日安排生产木门x1 扇，木窗扇，木窗x2 扇，扇，则线性规划模型为：则线性规划模型为：解得：解得：04年7月111规划技术线性规划课件 现在从另一角度来考虑该车间的生产问题：现在从另一角度来考虑该车间的生产问题： 假如有一个个体经营者，手中有一批木器家具假如有一个个体经营者，手中有一批木器家具生产订单，他想租借该木器车间完成他的订单

42、，于生产订单，他想租借该木器车间完成他的订单，于是他必须考虑支付给该车间租用木工与油漆工每个是他必须考虑支付给该车间租用木工与油漆工每个工时的价格。此时他必须构造一个数学模型来研究工时的价格。此时他必须构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图从而愿意如何定价才能既使木器车间觉得有利可图从而愿意替他加工这批订单，又使自己所付的工时费用总数替他加工这批订单，又使自己所付的工时费用总数最少？最少？04年7月112规划技术线性规划课件 设设w1 为付给木工每工时的价格，为付给木工每工时的价格，w2 为付给油漆为付给油漆工每工时的价格，则线性规划模型为：工每工时的价格，则线性规划模型为

43、：解得：解得：04年7月113规划技术线性规划课件04年7月114规划技术线性规划课件04年7月115规划技术线性规划课件 显然，线性规划显然，线性规划LP1 和和LP2 既有紧密联系，又有既有紧密联系，又有一定区别：它们都使用木器生产车间相同的数据，一定区别：它们都使用木器生产车间相同的数据，只是这些数据在模型中所处的位置不同，所要表达只是这些数据在模型中所处的位置不同，所要表达的含义也不同。的含义也不同。 若称线性规划若称线性规划LP1 为为原问题原问题(Primal Problem)，则，则称线性规划称线性规划LP2 为为LP1 的的对偶问题对偶问题(Dual Problem)。04年7

44、月116规划技术线性规划课件04年7月117规划技术线性规划课件二、化原问题为对偶问题二、化原问题为对偶问题原问题对偶问题目标函数形式max目标函数形式min变量n个变量约束n个约束变量 0约束 变量 0约束 无正负限制约束=约束m个约束变量m个变量约束 变量 0约束 变量0 约束=无正负限制约束方程右端项目标函数中的价值函数目标函数中的价值系数约束方程的右端项04年7月118规划技术线性规划课件 例例2：写出下面线性规划的对偶规划：写出下面线性规划的对偶规划：04年7月119规划技术线性规划课件 解：解：令对偶规划的决策变量为令对偶规划的决策变量为y1、y2、y3，则原，则原线性规划的对偶规

45、划：线性规划的对偶规划：04年7月120规划技术线性规划课件 例例3：写出下面线性规划的对偶规划：写出下面线性规划的对偶规划：04年7月121规划技术线性规划课件 解：解：令对偶规划的决策变量为令对偶规划的决策变量为y1、y2、y3，则原，则原线性规划的对偶规划：线性规划的对偶规划：04年7月122规划技术线性规划课件三、线性规划对偶问题的基本性质三、线性规划对偶问题的基本性质 对称性：对称性：一个线性规划的对偶问题的对偶问题一个线性规划的对偶问题的对偶问题恰是原问题。恰是原问题。 弱对偶性弱对偶性(Weak Duality)：假定假定是原规划是原规划()的任的任一可行解，是对偶规划一可行解，

46、是对偶规划()的任一可行解，的任一可行解，则有则有CXYb。 无界性：无界性：若若原规划原规划(对偶规划对偶规划)为无界解，则其为无界解，则其对偶规划对偶规划(原规划原规划)无可行解无可行解(逆命题不成立逆命题不成立)。04年7月123规划技术线性规划课件 设设X*是原规划的可行解，是原规划的可行解，Y*是对偶规划的可是对偶规划的可行解。当行解。当CX*=Y*b时，时，X*、Y*皆为最优解。皆为最优解。 强对偶性：强对偶性：原规划有最优解，则原规划有最优解，则对偶规划也有对偶规划也有最优解，且最优值相同最优解，且最优值相同。 互补松弛互补松弛性：性：在线性规划的最优解中，若对应在线性规划的最优

47、解中，若对应于某约束条件的对偶变量值为非零，则该约束条件于某约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等取严格等式；另一方面，如果约束条件取严格不等式，则其对应的对偶变量一定为零。式，则其对应的对偶变量一定为零。04年7月124规划技术线性规划课件 例例4：已知线性规划已知线性规划的对偶规划的最优解为的对偶规划的最优解为试用对偶问题的互补松弛性求出原规划的最优解。试用对偶问题的互补松弛性求出原规划的最优解。04年7月125规划技术线性规划课件 3.2对偶解的经济解释对偶解的经济解释Economic Interpretation of the Dual P

48、roblem 由由强对偶性强对偶性可知，原规划可知，原规划有最优解，则有最优解，则对偶规对偶规划也有最优解，且最优值相同划也有最优解，且最优值相同。于是最优值为。于是最优值为04年7月126规划技术线性规划课件 由上式可得由上式可得这表明线性规划中第种资源增加一个单位时，总这表明线性规划中第种资源增加一个单位时，总利润将增加利润将增加yi*。这个概念在西方经济学中被称为资。这个概念在西方经济学中被称为资源的源的“影子价格影子价格”(shadow price)。事实上，影子价格是事实上，影子价格是在最优产品组合在最优产品组合下，某种下，某种资源的资源的边际产出边际产出或或机会成本机会成本，表明在

49、最优产品组合，表明在最优产品组合状态下，该资源的状态下，该资源的“潜在价值潜在价值”。04年7月127规划技术线性规划课件影子价格可由单纯形表确定影子价格可由单纯形表确定04年7月128规划技术线性规划课件 用单纯形表解线性规划：用单纯形表解线性规划：CBXBB-1b56x130x20x30x40x312043100x4502101检验数检验数j=cj-CBB-1Pj56300030250x320011-256x12511/201/2检验数检验数j=cj-CBB-1Pj020-28205030x220011-256x11510-1/23/2检验数检验数j=cj-CBB-1Pj00-2-2404

50、年7月129规划技术线性规划课件 3.3灵敏度分析灵敏度分析资源向量的分量资源向量的分量b i 变化的分析变化的分析价格系数价格系数cj变化的分析变化的分析主要分析：主要分析：bi在什么范围内变化不影响最优解。在什么范围内变化不影响最优解。主要分析：主要分析：cj在什么范围内变化不影响最优解。在什么范围内变化不影响最优解。04年7月130规划技术线性规划课件追加新变量追加新变量的分析的分析约束矩阵变化约束矩阵变化的分析的分析主要分析：主要分析：在原问题最优解已求出的情况下，在原问题最优解已求出的情况下，增加新的决策变量会引起最优解怎样的变化。增加新的决策变量会引起最优解怎样的变化。主要分析：主

51、要分析：在原问题最优解已求出的情况下，在原问题最优解已求出的情况下，基向量或非基向量变化将引起最优解怎样的变化。基向量或非基向量变化将引起最优解怎样的变化。04年7月131规划技术线性规划课件第四节线性规划软件简介第四节线性规划软件简介用用LINDO软件解线性规划软件解线性规划用用Excel软件解线性规划软件解线性规划04年7月132规划技术线性规划课件 例例1：用软件求解线性规划：用软件求解线性规划：04年7月133规划技术线性规划课件 例例2：用软件求解线性规划：用软件求解线性规划：04年7月134规划技术线性规划课件 例例3：用软件求下列线性规划的对偶解，并进用软件求下列线性规划的对偶解

52、，并进行灵敏度分析：行灵敏度分析：04年7月135规划技术线性规划课件第五节运输问题第五节运输问题 运输问题运输问题(Transportation Problem)研究研究如何制定最合理的物资调运方案如何制定最合理的物资调运方案，使总运输，使总运输费用最低。费用最低。04年7月136规划技术线性规划课件 典型的运输问题可由下图描述：典型的运输问题可由下图描述：04年7月137规划技术线性规划课件 其中有个产地可以供应物资，用其中有个产地可以供应物资，用A i（i=1，2，m）表示。有个销地需要物）表示。有个销地需要物资，用资，用B j（j=1，2，n）表示。）表示。 产地产地A i 的产量为的

53、产量为ai ，销地销地B j的销量为的销量为bj ，从，从A i 到到B j的单位运价为的单位运价为cij 。04年7月138规划技术线性规划课件产销平衡问题产销平衡问题产销不平衡问题产销不平衡问题04年7月139规划技术线性规划课件一、产销平衡问题一、产销平衡问题在运输问题模型中，总产量等于总销量，在运输问题模型中，总产量等于总销量，即即时，称为时，称为产销平衡运输问题产销平衡运输问题。04年7月140规划技术线性规划课件 在实际工作中，常用在实际工作中，常用产销平衡表产销平衡表和和单位单位运价表运价表来描述这类问题。来描述这类问题。2n产量x11x12x1na2x21x22x2na2 mx

54、m1xm2xmnam销量bb2bnai=bj 04年7月141规划技术线性规划课件2nc11c12c1n2c21c22c2n mcm1cm2cmn04年7月142规划技术线性规划课件 在产销平衡条件下，运输问题的数学模型为：在产销平衡条件下，运输问题的数学模型为：04年7月143规划技术线性规划课件 例例1：某公司设有某公司设有3个加工厂个加工厂A1、A2、A3 和和4个个门市部门市部B1、B2、B3、B4。各加工厂的产量和各门市。各加工厂的产量和各门市部的销量如表部的销量如表1所示。从各加工厂到各门市部的单位所示。从各加工厂到各门市部的单位运价如表运价如表2所示。在满足门市部销售需求的情况下

55、，所示。在满足门市部销售需求的情况下，如何进行调运使总的运输支出最少？如何进行调运使总的运输支出最少？B1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量365620表表104年7月144规划技术线性规划课件表表2单位运价B1B2B3B4A1311310A21928A37410504年7月145规划技术线性规划课件04年7月146规划技术线性规划课件 解得：解得：B1B2B3B4产量A120507A210034A306039销量365620 即即04年7月147规划技术线性规划课件二、产销不平衡问题二、产销不平衡问题 例例2：某采石

56、联合公司负责供应某采石联合公司负责供应B1、B2、B3三三处修路工程所需的石子。预计三个工程所需的石子处修路工程所需的石子。预计三个工程所需的石子量为量为72、102、41车，联合公司有三个采石厂车，联合公司有三个采石厂A1、A2、A3，分别能供应石子，分别能供应石子76、82、77车。各采石厂至各车。各采石厂至各工程地点每车石子运费如下表，怎样安排调运总费工程地点每车石子运费如下表，怎样安排调运总费用最低？用最低？运价B1B2B3A1488A2162416A38162404年7月148规划技术线性规划课件 解：解：采石公司总供应能力为采石公司总供应能力为235车，而工程的总车，而工程的总需求

57、为需求为215车，这是一个总供给大于总需求的产销不车，这是一个总供给大于总需求的产销不平衡问题。平衡问题。04年7月149规划技术线性规划课件 解得：解得：B1B2B3产量A1076076A20214182A3725077销量7210241 即即04年7月150规划技术线性规划课件 例例3：某采石联合公司负责供应某采石联合公司负责供应B1、B2、B3三三处修路工程所需的石子。预计三个工程所需的石子处修路工程所需的石子。预计三个工程所需的石子量为量为72、102、81车，联合公司有三个采石厂车，联合公司有三个采石厂A1、A2、A3，分别能供应石子，分别能供应石子76、82、77车。各采石厂至各车

58、。各采石厂至各工程地点每车石子运费如下表，怎样安排调运总费工程地点每车石子运费如下表，怎样安排调运总费用最低？用最低？运价B1B2B3A1488A2162416A38162404年7月151规划技术线性规划课件 解：解：现在采石公司总供应能力仍为现在采石公司总供应能力仍为235车，而工车，而工程的总需求变为程的总需求变为255车，这是一个总供给小于总需求车，这是一个总供给小于总需求的产销不平衡问题。的产销不平衡问题。04年7月152规划技术线性规划课件 解得：解得：B1B2B3产量A1076076A2018182A3725077销量7210281 即即04年7月153规划技术线性规划课件第六节

59、线性整数规划第六节线性整数规划 前面介绍的线性规划问题的决策变量均前面介绍的线性规划问题的决策变量均是连续的。是连续的。 然而，在许多实际问题中，决策变量往然而，在许多实际问题中，决策变量往往只能取整数。我们把限制部分决策变量或往只能取整数。我们把限制部分决策变量或全部决策变量只能取整数的线性规划称为全部决策变量只能取整数的线性规划称为线线性整数规划性整数规划，简称，简称整数规划整数规划（Integer Programming）或）或IP规划规划。04年7月154规划技术线性规划课件 整数规划的一般形式为：整数规划的一般形式为：04年7月155规划技术线性规划课件 整数规划一般可分为三类：整数

60、规划一般可分为三类： 纯整数规划纯整数规划：全部决策变量都限定取整：全部决策变量都限定取整数；数； 混合整数规划混合整数规划：部分决策变量限定取整：部分决策变量限定取整数，其余决策变量取连续变量；数，其余决策变量取连续变量； 0-1整数规划整数规划：不仅限定决策变量取：不仅限定决策变量取整数，而且只能取整数，而且只能取0和和1两个值。两个值。04年7月156规划技术线性规划课件 例例1：某厂拟用集装箱托运甲、乙两种某厂拟用集装箱托运甲、乙两种货物，每件货物的体积、重量、可获得的利货物，每件货物的体积、重量、可获得的利润，以及托运所受限制如下表，问每集装箱润，以及托运所受限制如下表，问每集装箱中

61、两种货物各装多少件，可使利润最大？中两种货物各装多少件，可使利润最大？货物(件)体积(m3)重量(百斤)利润(百元)甲5220乙4510托运限制24m3/箱13百斤/箱04年7月157规划技术线性规划课件 解：解：设设x1、x2 分别为甲、乙两种货物的托运件数，分别为甲、乙两种货物的托运件数，则该问题的数学模型为则该问题的数学模型为04年7月158规划技术线性规划课件 解得：解得：若无取整限制，其解为若无取整限制，其解为04年7月159规划技术线性规划课件 例例2：(指派问题指派问题Assignment Problem)某市游泳队有某市游泳队有4名运动员甲、乙、丙、丁，他名运动员甲、乙、丙、丁

62、，他们的们的100米自由泳、蛙泳、蝶泳、仰泳的成绩米自由泳、蛙泳、蝶泳、仰泳的成绩如下表所示，现要组成一个混合泳接力队，如下表所示，现要组成一个混合泳接力队，问应如何指派，才能使总成绩最好？问应如何指派，才能使总成绩最好？自由泳蛙泳蝶泳仰泳甲565746163乙63696571丙571776367丁559761636204年7月160规划技术线性规划课件 解：解：该问题的数学模型为该问题的数学模型为04年7月161规划技术线性规划课件 解得：解得： 即即04年7月162规划技术线性规划课件 例例3：(指派问题指派问题)有有4种机械分别安装在种机械分别安装在4个工地，它们再个工地，它们再4个工地的工作效率不同个工地的工作效率不同（如下表），问应如何指派安排，才能使（如下表），问应如何指派安排，才能使4台台机械发挥的总效率最大？机械发挥的总效率最大？机械工地1工地2工地3工地4甲30254032乙32353036丙35403427丁2843323804年7月163规划技术线性规划课件 解：解：该问题的数学模型为该问题的数学模型为04年7月164规划技术线性规划课件 解得：解得： 即即04年7月165规划技术线性规划课件第七节线性规划应用实例第七节线性规划应用实例布利斯烟草公司布利斯烟草公司广告战略广告战略投资战略投资战略04年7月166规划技术线性规划课件