规划技术-线性规划.ppt

《规划技术-线性规划.ppt》由会员分享，可在线阅读，更多相关《规划技术-线性规划.ppt（166页珍藏版）》请在三一办公上搜索。

1、04年7月,管理运筹学讲义,1,第二讲规划技术线性规划,四川大学工商管理学院管理科学系 钟 胜 副教授Tel：84533811Email：,L I N E A R P R O G R A M M I N G,LP,04年7月,管理运筹学讲义,2,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 prob

2、lems.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月,管理运筹学讲义,3,线性规划(Linear Programmi

3、ng)是运筹学的重要组成部分，也是最基础的部分。,自1947年丹齐格()提出了求解线性规划的一般方法单纯形法以来，线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一个国家、一个地区，小到一个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。,04年7月,管理运筹学讲义,4,第一节线性规划的模型与图解法,第二节单纯形法,第三节对偶问题与灵敏度分析,第四节线性规划软件简介,第五节运输问题,第六节线性整数规划,第七节线性规划应用实例,04年7月,管理运筹

4、学讲义,5,See You!,04年7月,管理运筹学讲义,6,第一节线性规划的模型与图解法,1.1线性规划问题及其数学模型,1.2两变量问题的图解法,1.3线性规划模型的标准形式及解的概念,04年7月,管理运筹学讲义,7,1.1线性规划问题及其数学模型,线性规划问题的提出及主要概念,线性规划问题的数学模型,In this section,we introduce linear programming and define some important terms that are used to describe linear programming problems.,04年7月,管理运筹学

5、讲义,8,线性规划问题的提出及主要概念,在生产管理和经营活动中，组织常常必须对如何向不同的活动分配资源的问题做出决策，以便最好地达成组织的目标。,这样的问题通常有两类，一类是如何合理地使用有限的劳动力、设备、资金等资源，以最大化效益；另一类是为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分以使资源消耗最少。,04年7月,管理运筹学讲义,9,向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些活动。,由于所有活动都要求一定资源作支撑，而资源却是有限的，这

6、必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使资源达到最大的效用。,04年7月,管理运筹学讲义,10,显然，上述活动所引起的问题是一类有约束的最优化问题（Constrained Optimization）。,线性规划正是解决有约束的最优化问题的一种常用的方法，其涉及的主要概念包括：,决策变量（Decision Variables）:最优化问题的决策对象；,约束条件（Constraints）:对决策所能产生的结果的限制。,目标（Objective）:决策所希望达到的最优结果（最大或最小）；,04年7月,管理运筹学讲义,11,解决线性规划问题的过程通常分为四个步骤：,定

7、义问题和收集数据。必需向管理者咨询所要考虑问题涉及到的数据及确定研究的合理目标。,建立模型，用恰当的数学式表示问题。,求出问题的最优解。,进行敏感性分析，检查条件发生变化时可能发生的情况。,04年7月,管理运筹学讲义,12,案例1：潘得罗索工业公司的产品组合,潘得罗索工业公司是一家墨西哥公司，截止1998年，公司产销量占该国的四分之一。,与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品因厚度和所用木材的质量而有所不同。由于产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有很大的变化。这样，在某个月一个产品可能比另

8、一个产品赚取更大的利润，而在下一个月的情况则可能正好相反。,04年7月,管理运筹学讲义,13,所以，每个月管理层面临的关键问题是选择产品组合（Product Mix），以尽可能多地获取利润。,这一选择是很复杂的，因为它需要考虑当前生产产品必须的各种资源的可得数量。六项最重要的资源为：四种类型的原木（根据原木的质量区分）；生产胶合板的两项关键作业的生产能力（磨压作业和抛光作业）。,04年7月,管理运筹学讲义,14,从1980年开始，潘得罗索工业公司管理部门每个月使用线性规划决定下个月的产品组合。线性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得资源，然后求解模型，找

9、出可行并且最大的可能利润产品组合。,线性规划还给潘得罗索工业公司的管理层提供了其它一些有价值的信息，包括当前生产中某一特定资源的采购决策及其对利润的影响。例如，假设公司为生产某一特别赚钱的产品所需的某类原木只有少量供应，线性规划将表明如果赶紧购买该类原木会对产品组合以及利润产生多大的影响。,04年7月,管理运筹学讲义,15,采用线性规划后，潘得罗索工业公司的成绩是显著的。产品组合调整使公司总利润增加了20%，线性规划的其他贡献包括更好的原材料利用、更好的资本投资和更好的人员利用。,04年7月,管理运筹学讲义,16,案例2：航空业的成本控制,航空业在1983年和1984年发生了史无前例的行业竞争

10、，尽管如此，联合航空公司还是开通了48个新机场的服务，并且取得了很大的增长。1984年，它是唯一的一家在美国全部50个州开通服务的公司，1984年的收入比1983年增长了6个百分点，达到62亿美元，而同时成本的增长少于2%，因此营运利润提高，达到了5.64亿美元。,04年7月,管理运筹学讲义,17,在航空业，成本控制是关键。作为公司管理扩展的一部分，1982年联合航空公司的高层管理部门实施了一个成本控制项目，目标是根据消费者的需求进行工作排程，以改进航空订票处和机场工作人员的利用率。,那时，联航在其11个航班订票处有超过4000名机场销售代表和支持人员。在10个最大的机场，大约有1000名顾客

11、服务代表，有些是兼职的，每班28小时不等；大部分是全职的，每班810小时，有许多不同的上班时间。每个订票处都是全天24小时营业（通过电话订票），各个重要的机场也是如此。,04年7月,管理运筹学讲义,18,为了更有效地满足服务要求，在每个地点为所有员工进行工作排程，这是一个组合的梦魇。一旦一名雇员上了班，就会工作一个班次（210小时不等），只有就餐和每隔两个小时短暂的休息时间。那么，一周7天及一天24小时，每个班次需要多少雇员上班呢？如何排程？幸运的是，线性规划能解决这些组合的梦魇问题。,据估计，建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上节省了600万美元，得到

12、的其它好处包括改善客户服务以及降低雇员的工作负担。,04年7月,管理运筹学讲义,19,线性规划问题的数学模型,例1：一家玻璃制品公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工而成，然后进入储藏室冷却至室温。花瓶有大、小两种尺寸，但生产过程几乎相当，而且使用同一种材料。不论尺寸，每一个花瓶都需要20分钟的艺术加工，每周艺术加工工作时间为40小时；大、小花瓶每个需彩色玻璃2 OZ和1 OZ，每周可用的玻璃为160 OZ；另外，一个小花瓶占用2单位储存空间，大花瓶占用3个单位储存空间，一共有260个储存空间。大、小花瓶的利润贡献率分别为12元/个和10元/个。问应该怎样安

13、排生产，利润值最大。,04年7月,管理运筹学讲义,20,04年7月,管理运筹学讲义,21,分析建模：用B表示每周生产大花瓶的数量，S表示每周生产小花瓶的数量，则决策变量(Decision Variables)为B、S。,目标函数(Objective Function)：,材料约束(Constraint of material)：,时间约束(Constraint of time)：,储存约束(Constraint of inventory)：,非负约束(Sign restriction)：,04年7月,管理运筹学讲义,22,模型：,04年7月,管理运筹学讲义,23,由上可知，数学建模过程主要有四

14、个步骤：,确定决策变量；,确定目标函数；,确定约束条件；,确定非负约束。,04年7月,管理运筹学讲义,24,例2：某寻呼台每天需要话务员人数、值班时间以及工资情况如下表所示。每班话务员在轮班开始时报到，并连续工作9小时。问如何安排，使得既满足需求又使总支付工资最低，试建立数学模型。,04年7月,管理运筹学讲义,25,04年7月,管理运筹学讲义,26,分析建模：决策变量为从第 i 班开始工作的人数，设为 xi（i=1,2,3,4,5,6,7,8）。,目标函数：,04年7月,管理运筹学讲义,27,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,第班人数约束：,第班人

15、数约束：,第班人数约束：,非负约束：,04年7月,管理运筹学讲义,28,模型：,04年7月,管理运筹学讲义,29,例3：某集团有1000000元资金供投资，该集团有5个可供选择的投资项目，其中各种资料如下表：,该集团的目标为：投资风险最小，每年红利至少80000元，最低平均增长率14%，最低平均信用度6，请用线性规划方法描述该问题。,04年7月,管理运筹学讲义,30,分析建模：决策变量为各项目的投资数额，设为 xi（i=1,2,3,4,5）。,目标函数：,投资额约束：,红利约束：,增长额约束：,平均信用度约束：,非负约束：,04年7月,管理运筹学讲义,31,模型：,04年7月,管理运筹学讲义,

16、32,例4：某石油公司利用三种油料生产两种混合原料。每种油的成本和每天的可用量如表所示：,04年7月,管理运筹学讲义,33,两种混合原料中各种油料所占比例如下表所示：,原料售价为30元/L，原料售价为35元/L，该公司有一项长期合同，每天供应两种原料各10000L。试建立该问题的数学规划模型。,04年7月,管理运筹学讲义,34,分析建模：决策变量为加入到原料中的各种油料的量：,A 1为加入原料中的油料 A 的升数；,A 2为加入原料中的油料 A 的升数；,B 1为加入原料中的油料 B 的升数；,B 2为加入原料中的油料 B 的升数；,C 1为加入原料中的油料 C 的升数；,C 2为加入原料中的

17、油料 C 的升数。,04年7月,管理运筹学讲义,35,原料和原料的产量：,原料：ABC,原料：ABC,各种油料的使用量：,油料A：AA 2,油料B：BB 2,油料C：CC 2,04年7月,管理运筹学讲义,36,两种原料的销售收入：,30(ABC)35(ABC),三种油料的成本：,8(AA 2)10(BB 2)12(CC 2),目标函数为：,04年7月,管理运筹学讲义,37,三种可用油料的约束：,各种油料所占比例的约束：,04年7月,管理运筹学讲义,38,长期供货合同约束：,非负约束：,04年7月,管理运筹学讲义,39,模型：,04年7月,管理运筹学讲义,40,1.2两变量问题的图解法,对于只有

18、两个决策变量的线性规划问题，可以用作图法求解。,图解法不仅直观，而且可从中得到有关线性规划问题的许多重要结论，有助于理解线性规划一般解法的基本原理。,In this section,we learn how to solve graphically those linear programming problems that involve only two variables.,04年7月,管理运筹学讲义,41,图解法的过程介绍,规划问题求解的几种可能结果,图解法的启示,04年7月,管理运筹学讲义,42,例1：,一、图解法的过程介绍,04年7月,管理运筹学讲义,43,0,40,D,50,10

19、0,30,40,可行域(Feasible Region),04年7月,管理运筹学讲义,44,解方程组：,得最优解(Optimal Solution)：,04年7月,管理运筹学讲义,45,上述图解过程涉及的几个概念：,凸集(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 extr

20、eme 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月,管理运筹学讲义,46,例2：,04年7月,管理运筹学讲义,47,0,14,2,4,12,6,(无界)可行域(Unbounded Feasible Region),D,04年7月,管理运筹学讲义,48,解方程组：,得最优解(Optimal Solution)：,04年7月,管理运筹学讲义,49,用图解法求解线性规划，可能会出现以下四种情况：

21、,有唯一最优解have a unique optimal solution(如例1、例2)；,有无穷多最优解have an infinite number of optimal solutions(alternative or multiple optimal solutions)(如例3)；,二、规划问题求解的几种可能结果,04年7月,管理运筹学讲义,50,无界解(有可行解，但无有限最优解)unbounded(如例4)；,无可行解have no feasible solutions(如例5)。,04年7月,管理运筹学讲义,51,例3：,04年7月,管理运筹学讲义,52,例4：,04年7月,管

22、理运筹学讲义,53,例5：,04年7月,管理运筹学讲义,54,三、图解法的启示,线性规划问题可行域非空，则一定为凸集；,线性规划问题最优解存在，那么唯一最优解一定是可行域凸集的某个顶点（极点）；无穷最优解一定是可行域的某个边或某个面；,规划问题一般解题思路：先找出凸集的任一顶点，计算该点处目标函数值，与其他顶点的目标函数值比较，如果该点值最大，那么该点就是最优解或最优解之一；如果不是，那么就对目标函数值比该点大的另一点重复上述过程，直到找到最优解。,04年7月,管理运筹学讲义,55,例6：,04年7月,管理运筹学讲义,56,1.3线性规划模型的标准形式及解的概念,线性规划模型的标准形式,化非标

23、准形式为标准形式,有关解的概念,04年7月,管理运筹学讲义,57,对于一般线性规划模型，目标函数可以求最大，也可以求最小；约束条件可以是“”，也可以是“”或“=”型。因此，一般线性规划模型可表示为,一、线性规划模型的标准形式,04年7月,管理运筹学讲义,58,为论述方便，通常把最大化、等式约束型的线性规划称为线性规划的标准型(Standard Form)：,04年7月,管理运筹学讲义,59,线性规划的标准型还可写为“号简写式”：,04年7月,管理运筹学讲义,60,线性规划的标准型的“矩阵形式”为：,04年7月,管理运筹学讲义,61,线性规划的标准型的“向量形式”为：,04年7月,管理运筹学讲义

24、,62,一般地，我们还对标准型作如下假定：,矩阵A的秩rank(A)=m，0mn。即标准型中的约束方程彼此独立，没有多余方程，且约束方程个数小于变量的个数。,b0.若有bj0，则可对第j个约束方程两边同时乘以-1即可。,04年7月,管理运筹学讲义,63,二、化非标准形式为标准形式,从实际问题得到的线性规划模型往往是非标准形式的。,对于各种非标准型的线性规划都可以通过适当的方法变换为等价的标准型问题。,04年7月,管理运筹学讲义,64,若目标函数为求最小化：minZ=CX，则作Z=Z=CX，将目标函数化为求最大化：maxZ=CX；,若约束条件是“”型，则在该约束不等式左边加一个新变量(松弛变量(

25、slack variable)，将不等式化为等式；,若约束条件是“”型，则在该约束不等式左边减一个新变量(剩余变量(excess variable)，将不等式化为等式；,04年7月,管理运筹学讲义,65,若决策变量xk 无非负约束，即xk 可正可负，则作两个新变量：xk 0，xk0，令xk=xkxk，将原模型中xk均用（xkxk）替代，而在非负约束中增加xk 0，xk0；,若决策变量xk 0，则作新变量：xk=xk 0，于是xk=xk，将原模型中xk均用（xk）替代，而在非负约束中增加xk 0。,04年7月,管理运筹学讲义,66,例：,04年7月,管理运筹学讲义,67,例：,04年7月,管理运

26、筹学讲义,68,例：,04年7月,管理运筹学讲义,69,例：,04年7月,管理运筹学讲义,70,三、有关解的概念,若数学模型为：,式中：A=(aij)mn，nm，且r(A)=m。,04年7月,管理运筹学讲义,71,定义凡同时满足（2）式和（3）式的解X=(x1，x2，xn)T 称为线性规划问题的可行解，同时满足（1）式的可行解称为最优解。,定义设线性规划约束方程组的系数矩阵Amn的秩为m(nm)，则A中任一个m阶可逆阵B称为线性规划问题的一个基矩阵，简称一个基，若记B=(p1,p2,pm)，则称pj(j=1,2,m)为基B的一个基向量，而A中其余nm个列向量称为非基向量。,04年7月,管理运筹

27、学讲义,72,定义将（2）式写成向量形式：,则当A中确定了一个基B后，与基向量pj 相对应的决策变量xj 称为关于基B的一个基变量(basic variable)，与非基向量所对应的决策变量称为非基变量(nonbasic variable)。,显然关于基B的基变量有m个，非基变量有nm个。,04年7月,管理运筹学讲义,73,定义取A中一个基B=(pj1,pj2,pjm)，对应的基变量为xj1,xj2,xjm，令非基变量全为0，则得满足约束条件（2）的一个解X，称为是关于基B的一个基本解(basic solution)。,显然对应于A中每一个基B，都可找出一个基本解。而A中最多有Cmn个基，因此

28、线性规划问题最多只有Cmn个基本解。,定义若一个基本解X同时满足非负约束(3)，则称X为基本可行解(basic feasible solution)。,04年7月,管理运筹学讲义,74,例：求下列线性规划问题的所有基本解、基本可行解和最优解：,04年7月,管理运筹学讲义,75,第二节单纯形法(The Simplex Algorithm),2.1单纯形法原理,2.2单纯形法与单纯形表,2.3大M法,2.4解的几种情况,04年7月,管理运筹学讲义,76,2.1单纯形法原理,单纯形法是利用线性规划最优解在可行域角点上得到这一结论而设计的一种迭代算法：,它首先确定一个初始角点，用某种法则判别它是否最优

29、解。若不是，则设法寻找一个目标函数值更大的、新的、更好的角点。由于角点个数有限，因而经过有限次迭代后必定达到最优点。,04年7月,管理运筹学讲义,77,由上述分析可见，单纯形法需解决四个问题：,可行域的角点有何特征？,如何确定第一个角点？,如何判定一个角点是否最优？,如何从一个角点出发去寻找更好的角点？,04年7月,管理运筹学讲义,78,关于第一个问题，可以证明：线性规划可行域角点的坐标恰好是该线性规划的某一个基本可行解；角点与基本可行解是一一对应的。,于是单纯形法求解线性规划的步骤为：确定一个初始基本可行解；检验一个基本可行解是否最优；寻找一个更好的基本可行解。,关于后三个问题（即三个步骤）

30、的解决办法，我们将通过以下的原理推导加以说明。,04年7月,管理运筹学讲义,79,设线性规划的标准型为：,其中，不妨设B是一个可行基，系数矩阵A可分块为,04年7月,管理运筹学讲义,80,不失一般性，假定B=(P1,Pm)，对应于B的基变量XB=(x1,xm)T；N=(Pm+1,Pn)，对应的非基变量XN=(xm+1,xn)T；于是，X=(XB,XN)T；相应地，C=(CB,CN)。于是，线性规划可表示为,04年7月,管理运筹学讲义,81,进一步简化得：,对(2)式两边同时左乘B-1，得,代入(1)式，得,04年7月,管理运筹学讲义,82,令非基变量XN=0，若基变量XB0，则相应基本可行解为

31、,此时，目标函数值为,04年7月,管理运筹学讲义,83,若系数矩阵A中不含单位矩阵I，则可由以后介绍的大M法确定一个初始基本可行解。,单纯形法步骤1：确定一个初始基本可行解。,先化原线性规划问题为标准型，若其系数矩阵A中含单位矩阵I，则取初始基B0=I，由此初始基可得初始基本可行解,04年7月,管理运筹学讲义,84,由于CBB-1BCB=0，故有,04年7月,管理运筹学讲义,85,于是，当CBB-1NCN0时，对一切可行解,其目标函数值Z均满足：,04年7月,管理运筹学讲义,86,若条件满足，则该基本可行解为最优解；反之，只要有一个非基变量的检验数大于0，则该基本可行解不是最优解，需另寻更好的

32、基本可行解。,单纯形法步骤2：检验基本可行解的最优性。,对给定的可行基B，判别其对应基本可行解XB=B-1b，XN=0是否最优解，只需判定最优检验向量CNCBB-1N是否满足：,04年7月,管理运筹学讲义,87,基B的选择是在基B的基础上进行的。假设BP1,Pm，N=Pm+1,Pn，则新可行基B是从原非基阵N中选择一列Pk去代替原基B中的某一列Pl而得到的。,单纯形法步骤3：寻找更好的基本可行解。,若基B对应基本可行解不是最优解，则需寻求一个新的可行基B以获取更好的基本可行解。,下面我们不加证明地给出具体步骤。,04年7月,管理运筹学讲义,88,则选择相应的列Pk作为进基列；,首先，计算所有非

33、基变量检验数j，如果,然后，计算,则选择出基列为Pl。,04年7月,管理运筹学讲义,89,单纯形法步骤：,Step1：Convert the LP to standard form.,Step2：Obtain a bfs(if possible)from the standard form.,Step3：Determine whether the current bfs is optimal.,Step4：If the current bfs is not optimal,determine which nonbasic variable should become a basic varia

34、ble and which basic variable should become a nonbasic variable to find a new bfs with a better objective function value.,Step5：Find the new bfs with the better objective function value.Go to Step3.,04年7月,管理运筹学讲义,90,2.2单纯形法与单纯形表,例：用单纯形法求解线性规划：,04年7月,管理运筹学讲义,91,解：首先将线性规划化为标准型,04年7月,管理运筹学讲义,92,用单纯形表解线性

35、规划：,1/2,3/2,2,4/5,3/4,2,04年7月,管理运筹学讲义,93,于是，最优解为：,04年7月,管理运筹学讲义,94,2.3大M法(The Big M Method),例：用大M法求解线性规划：,04年7月,管理运筹学讲义,95,解：在第一个约束条件中引入松弛变量x4，在第二个约束条件中引入剩余变量x5和人工变量(artificial variable)x6，在第三个约束条件中引入人工变量x7，并化最小化问题为最大化问题，得线性规划标准型：,04年7月,管理运筹学讲义,96,用单纯形表解线性规划：,11,3/2,1,-,1,-,04年7月,管理运筹学讲义,97,4,-,-,04

36、年7月,管理运筹学讲义,98,2.4解的几种情况,唯一最优解,若单纯形终表中所有非基变量的检验数j0，则此线性规划只有唯一最优解。,无穷多最优解,若单纯形终表中所有非基变量的检验数j0，且某个非基变量xk之检验数k=0，则此线性规划有无穷多个最优解。,04年7月,管理运筹学讲义,99,例：求解线性规划：,04年7月,管理运筹学讲义,100,解：首先将线性规划化为标准型,04年7月,管理运筹学讲义,101,用单纯形表解线性规划：,6,10,6,2,04年7月,管理运筹学讲义,102,由上表知，线性规划有两个最优解：,则两个解的一切凸组合,均为线性规划的最优解。,04年7月,管理运筹学讲义,103

37、,无有限最优解,若单纯形表中某一非基变量的检验数j0，而表上与之对应列元素全小于或等于0，则此线性规划无有限最优解。,例：求解线性规划：,04年7月,管理运筹学讲义,104,解：首先将线性规划化为标准型,04年7月,管理运筹学讲义,105,单纯形表为：,由上表知，线性规划无有限最优解。,04年7月,管理运筹学讲义,106,退化解,若单纯形表中，最优解,的某个分量bk=0，则称此解为一个退化解。,04年7月,管理运筹学讲义,107,第三节对偶问题与灵敏度分析Duality and Sensitivity Analysis,3.1线性规划的对偶问题,3.2对偶解的经济解释,3.3灵敏度分析,04年

38、7月,管理运筹学讲义,108,3.1线性规划的对偶问题,随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随着与之配对的、两者有密切联系的另一个线性规划问题。我们将其中一个称为原问题，另一个称为对偶问题。,由对偶问题引伸出来的对偶解有着重要的经济意义，是经济学中重要的概念与工具之一。,04年7月,管理运筹学讲义,109,对偶问题的实例,线性规划对偶问题的基本性质,化原问题为对偶问题,04年7月,管理运筹学讲义,110,一、对偶问题的实例,例1：某家具厂木器车间生产木门与木窗两种产品，加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木

39、窗需要木工3小时，油漆工1小时。该车间每日可用木工总工时为120小时，油漆工总工时为50小时，问该车间应如何安排生产才能使每日收入最大？,04年7月,管理运筹学讲义,111,令该车间每日安排生产木门x1 扇，木窗x2 扇，则线性规划模型为：,解得：,04年7月,管理运筹学讲义,112,现在从另一角度来考虑该车间的生产问题：,假如有一个个体经营者，手中有一批木器家具生产订单，他想租借该木器车间完成他的订单，于是他必须考虑支付给该车间租用木工与油漆工每个工时的价格。此时他必须构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图从而愿意替他加工这批订单，又使自己所付的工时费用总数最少？,04年

40、7月,管理运筹学讲义,113,设w1 为付给木工每工时的价格，w2 为付给油漆工每工时的价格，则线性规划模型为：,解得：,04年7月,管理运筹学讲义,114,04年7月,管理运筹学讲义,115,04年7月,管理运筹学讲义,116,显然，线性规划LP1 和LP2 既有紧密联系，又有一定区别：它们都使用木器生产车间相同的数据，只是这些数据在模型中所处的位置不同，所要表达的含义也不同。,若称线性规划LP1 为原问题(Primal Problem)，则称线性规划LP2 为LP1 的对偶问题(Dual Problem)。,04年7月,管理运筹学讲义,117,04年7月,管理运筹学讲义,118,二、化原问

41、题为对偶问题,04年7月,管理运筹学讲义,119,例2：写出下面线性规划的对偶规划：,04年7月,管理运筹学讲义,120,解：令对偶规划的决策变量为y1、y2、y3，则原线性规划的对偶规划：,04年7月,管理运筹学讲义,121,例3：写出下面线性规划的对偶规划：,04年7月,管理运筹学讲义,122,解：令对偶规划的决策变量为y1、y2、y3，则原线性规划的对偶规划：,04年7月,管理运筹学讲义,123,三、线性规划对偶问题的基本性质,对称性：一个线性规划的对偶问题的对偶问题恰是原问题。,弱对偶性(Weak Duality)：假定是原规划()的任一可行解，是对偶规划()的任一可行解，则有CXYb

42、。,无界性：若原规划(对偶规划)为无界解，则其对偶规划(原规划)无可行解(逆命题不成立)。,04年7月,管理运筹学讲义,124,设X*是原规划的可行解，Y*是对偶规划的可行解。当CX*=Y*b时，X*、Y*皆为最优解。,强对偶性：原规划有最优解，则对偶规划也有最优解，且最优值相同。,互补松弛性：在线性规划的最优解中，若对应于某约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应的对偶变量一定为零。,04年7月,管理运筹学讲义,125,例4：已知线性规划,的对偶规划的最优解为,试用对偶问题的互补松弛性求出原规划的最优解。,04年7月,管理运筹学讲义,1

43、26,3.2对偶解的经济解释Economic Interpretation of the Dual Problem,由强对偶性可知，原规划有最优解，则对偶规划也有最优解，且最优值相同。于是最优值为,04年7月,管理运筹学讲义,127,由上式可得,这表明线性规划中第种资源增加一个单位时，总利润将增加yi*。这个概念在西方经济学中被称为资源的“影子价格”(shadow price)。,事实上，影子价格是在最优产品组合下，某种资源的边际产出或机会成本，表明在最优产品组合状态下，该资源的“潜在价值”。,04年7月,管理运筹学讲义,128,影子价格可由单纯形表确定,04年7月,管理运筹学讲义,129,用

44、单纯形表解线性规划：,30,25,20,50,04年7月,管理运筹学讲义,130,3.3灵敏度分析,资源向量的分量b i 变化的分析,价格系数cj变化的分析,主要分析：bi在什么范围内变化不影响最优解。,主要分析：cj在什么范围内变化不影响最优解。,04年7月,管理运筹学讲义,131,追加新变量的分析,约束矩阵变化的分析,主要分析：在原问题最优解已求出的情况下，增加新的决策变量会引起最优解怎样的变化。,主要分析：在原问题最优解已求出的情况下，基向量或非基向量变化将引起最优解怎样的变化。,04年7月,管理运筹学讲义,132,第四节线性规划软件简介,用LINDO软件解线性规划,用Excel软件解线

45、性规划,04年7月,管理运筹学讲义,133,例1：用软件求解线性规划：,04年7月,管理运筹学讲义,134,例2：用软件求解线性规划：,04年7月,管理运筹学讲义,135,例3：用软件求下列线性规划的对偶解，并进行灵敏度分析：,04年7月,管理运筹学讲义,136,第五节运输问题,运输问题(Transportation Problem)研究如何制定最合理的物资调运方案，使总运输费用最低。,04年7月,管理运筹学讲义,137,典型的运输问题可由下图描述：,04年7月,管理运筹学讲义,138,其中有个产地可以供应物资，用A i（i=1，2，m）表示。有个销地需要物资，用B j（j=1，2，n）表示。

46、,产地A i 的产量为ai，销地B j的销量为bj，从A i 到B j的单位运价为cij。,04年7月,管理运筹学讲义,139,产销平衡问题,产销不平衡问题,04年7月,管理运筹学讲义,140,一、产销平衡问题,在运输问题模型中，总产量等于总销量，即,时，称为产销平衡运输问题。,04年7月,管理运筹学讲义,141,在实际工作中，常用产销平衡表和单位运价表来描述这类问题。,04年7月,管理运筹学讲义,142,04年7月,管理运筹学讲义,143,在产销平衡条件下，运输问题的数学模型为：,04年7月,管理运筹学讲义,144,例1：某公司设有3个加工厂A1、A2、A3 和4个门市部B1、B2、B3、B

47、4。各加工厂的产量和各门市部的销量如表1所示。从各加工厂到各门市部的单位运价如表2所示。在满足门市部销售需求的情况下，如何进行调运使总的运输支出最少？,表1,04年7月,管理运筹学讲义,145,表2,04年7月,管理运筹学讲义,146,04年7月,管理运筹学讲义,147,解得：,即,04年7月,管理运筹学讲义,148,二、产销不平衡问题,例2：某采石联合公司负责供应B1、B2、B3三处修路工程所需的石子。预计三个工程所需的石子量为72、102、41车，联合公司有三个采石厂A1、A2、A3，分别能供应石子76、82、77车。各采石厂至各工程地点每车石子运费如下表，怎样安排调运总费用最低？,04年

48、7月,管理运筹学讲义,149,解：采石公司总供应能力为235车，而工程的总需求为215车，这是一个总供给大于总需求的产销不平衡问题。,04年7月,管理运筹学讲义,150,解得：,即,04年7月,管理运筹学讲义,151,例3：某采石联合公司负责供应B1、B2、B3三处修路工程所需的石子。预计三个工程所需的石子量为72、102、81车，联合公司有三个采石厂A1、A2、A3，分别能供应石子76、82、77车。各采石厂至各工程地点每车石子运费如下表，怎样安排调运总费用最低？,04年7月,管理运筹学讲义,152,解：现在采石公司总供应能力仍为235车，而工程的总需求变为255车，这是一个总供给小于总需求

49、的产销不平衡问题。,04年7月,管理运筹学讲义,153,解得：,即,04年7月,管理运筹学讲义,154,第六节线性整数规划,前面介绍的线性规划问题的决策变量均是连续的。,然而，在许多实际问题中，决策变量往往只能取整数。我们把限制部分决策变量或全部决策变量只能取整数的线性规划称为线性整数规划，简称整数规划（Integer Programming）或IP规划。,04年7月,管理运筹学讲义,155,整数规划的一般形式为：,04年7月,管理运筹学讲义,156,整数规划一般可分为三类：,纯整数规划：全部决策变量都限定取整数；,混合整数规划：部分决策变量限定取整数，其余决策变量取连续变量；,0-1整数规划

50、：不仅限定决策变量取整数，而且只能取0和1两个值。,04年7月,管理运筹学讲义,157,例1：某厂拟用集装箱托运甲、乙两种货物，每件货物的体积、重量、可获得的利润，以及托运所受限制如下表，问每集装箱中两种货物各装多少件，可使利润最大？,04年7月,管理运筹学讲义,158,解：设x1、x2 分别为甲、乙两种货物的托运件数，则该问题的数学模型为,04年7月,管理运筹学讲义,159,解得：,若无取整限制，其解为,04年7月,管理运筹学讲义,160,例2：(指派问题Assignment Problem)某市游泳队有4名运动员甲、乙、丙、丁，他们的100米自由泳、蛙泳、蝶泳、仰泳的成绩如下表所示，现要组