第三章线性规划的典型应用

1、线性规划的典型应用内容内容生产组织与计划问题生产组织与计划问题运输问题运输问题指派问题指派问题下料问题下料问题生产组织与计划问题生产组织与计划问题例题例题某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：该厂每周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5

2、 51 11515已知该厂生产每吨甲、乙药品的利已知该厂生产每吨甲、乙药品的利润分别为润分别为5 5万元和万元和2 2万元。但根据市万元。但根据市场需求调查的结果，甲药品每周的场需求调查的结果，甲药品每周的产量不应超过产量不应超过4 4吨。问该厂应如何安吨。问该厂应如何安排两种药品的产量才能使每周获得排两种药品的产量才能使每周获得的利润最大？的利润最大？121212112maxZ=5x +2x30 x20 x1605xx15. .x4x0,x0st一般描述一般描述数学模型数学模型112211112211211222221122max. . .0(1,., )nnnnnnmmmnnmjZstjn

3、C x C xC xa xa xa xba xa xa xba xa xa xbx求解方法求解方法理论上的一般求解方法：理论上的一般求解方法： 二变量：图解法二变量：图解法 三变量以上：单纯形法三变量以上：单纯形法使用软件：使用软件：MatlabMatlab、lingolingo（lindolindo）运输问题2321341运输问题网络图运输问题网络图a2=27a3=19b1=22b2=13b3=12b4=13a1=14供应量供应地运价需求量需求地675384275910614+27+19= 22+13+12+13供需平衡问题运输问题的一般描述运输问题的一般描述产需平横产需平横11111212

4、111211211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx供供应应地地约约束束需需求求地地约约束束11mnijijab供不应求供不应求11111212111211211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx供供应应地地约约束束需需求求地地约约束束11mnijijab供过于求供过于求111112121112

5、11211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx供供应应地地约约束束需需求求地地约约束束11mnijijab转运问题及图示转运问题及图示所谓转运问题所谓转运问题(Transhipment Problem)实质上是运输问实质上是运输问题的一种，其区别就在于不是将工厂生产出的产品直接题的一种，其区别就在于不是将工厂生产出的产品直接送的顾客手中，而是要经过某些中间环节，如仓库、配送的顾客手中，而是要经过某些中间环节，如仓库、配送中心等送中心等.图图7-2

6、表示的（即有一个中间环节）的转运问表示的（即有一个中间环节）的转运问题题. 数学模型数学模型(1)(1)(2)(2)1111(1)1(1)(2)11min Z= ; , 1,2,(), 1,2, ,(s.t. mllnijijjkjkijjklijijmnijjkikc xcxxaimxxjl运出量应不大于生产量运入(2)1(1)(2) , 1,2,() 0,0, 1,2,1,2, ,1,2,.ljkkjijjkxbknxxim jl kn量应等于运出量运入量应等于需求量(1)ijx(2)jkx(1)ijc(2)ijc运输问题的求解运输问题的求解 模型也是线性规划模型，可用单纯形法； 模型的系

7、数矩阵是矩阵维数较大、涉及变量较多，系数矩阵是 稀疏矩阵，因此可以考虑更好的算法； 一般方法：表上作业法； 大体步骤： 先给一个初始方案（最小元素法、西北角法、沃格尔法） 判断最优性（闭回路法、对偶变量法） 如果不是，对该方案进行修改，再判断，直到方案最优。指派问题指派问题指派问题描述描述指派问题也称分配问题，主要研究人指派问题也称分配问题，主要研究人和工作（任务）间如何匹配，以使所和工作（任务）间如何匹配，以使所有工作完成的效率实现最优化。形式有工作完成的效率实现最优化。形式上，指派问题给定了一系列所要完成上，指派问题给定了一系列所要完成的工作以及一系列完成工作的人员，的工作以及一系列完成工

8、作的人员，所需要解决的问题就是要确定出指派所需要解决的问题就是要确定出指派哪个人去完成哪项工作。哪个人去完成哪项工作。在现实生活中，经常会遇到指派人员做某在现实生活中，经常会遇到指派人员做某项工作（任务）的情况项工作（任务）的情况指派问题的假设（平衡指派）指派问题的假设（平衡指派） 人的数量和工作的数量相等；人的数量和工作的数量相等； 每个人只能完成一项工作；每个人只能完成一项工作； 每项工作只能由一个人来完成；每项工作只能由一个人来完成； 每个人和每项工作的组合都会有一个每个人和每项工作的组合都会有一个 相关的成本（单位成本）；相关的成本（单位成本）；由于每人的由于每人的 知识、能力、经验等

9、不同，故各人完成知识、能力、经验等不同，故各人完成 不同任务所需的时间（或其它资源）不不同任务所需的时间（或其它资源）不 同；同； 目标是要确定如何指派能使总成本最小目标是要确定如何指派能使总成本最小111212122212nnnnnnxxxxxxXxxx 111212122212nnnnnnccccccCccc 设设xij为第为第i个人做第个人做第j项工作，取值项工作，取值0 0或或1 1 cij为第为第i个人完成第个人完成第j项工作所需要的成本项工作所需要的成本指派问题的数学模型 设设xij为第为第i个人做第个人做第j项工作，项工作， cij为第为第i个人完成第个人完成第j项工作所需要的成

10、本项工作所需要的成本 平衡指派问题的数学模型为平衡指派问题的数学模型为1111 ()Min z1 (1,2,)s.t. 1 (1,2,)01 ( ,1,2,) nnijijijnijjnijiijijc xxinxjnxi jn LLL(第 人只能做一项工作)(第 项工作只能一人做)非负 或需要说明的是需要说明的是指派问题实际上是一种特殊的运输问题。指派问题实际上是一种特殊的运输问题。其中出发地是人，目的地是工作。只不过其中出发地是人，目的地是工作。只不过，每一个出发地的供应量都为，每一个出发地的供应量都为1 1（因为每（因为每个人都要完成一项工作），每一个目的地个人都要完成一项工作），每一个

11、目的地的需求量都为的需求量都为1 1（因为每项工作都要完成（因为每项工作都要完成）。由于运输问题有）。由于运输问题有“整数解性质整数解性质”，因，因此，没有必要加上所有决策变量都是此，没有必要加上所有决策变量都是0-10-1变量的约束变量的约束. .求解按照一般的线性规划编程求解即可。求解按照一般的线性规划编程求解即可。指派问题是一种特殊的LP问题，是一种特殊的运输问题。11111212111211211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx区别：

12、变量取区别：变量取0 0或或1 1；整数规划介绍整数规划介绍在许多实际问题中，决策变量必须为整数。例如当决在许多实际问题中，决策变量必须为整数。例如当决策变量是分配的人数、购买的设备数、投入的车辆数、策变量是分配的人数、购买的设备数、投入的车辆数、是否投资等的时候，它们一般必须为非负整数才有意义。是否投资等的时候，它们一般必须为非负整数才有意义。在这种情况下，常需要应用整数规划进行优化。在这种情况下，常需要应用整数规划进行优化。整数规划（整数规划（Integer ProgrammingInteger Programming，简称，简称IPIP），是要），是要求全部或部分决策变量为整数的规划。整

13、数规划分为线求全部或部分决策变量为整数的规划。整数规划分为线性整数规划和非线性整数规划。在此只介绍线性整数规性整数规划和非线性整数规划。在此只介绍线性整数规划，简称为整数规划。划，简称为整数规划。整数规划分为两大类：一般整数规划与整数规划分为两大类：一般整数规划与0-10-1整数规划整数规划（Binary Integer ProgrammingBinary Integer Programming，简称，简称BIPBIP）。）。整数规划与一般规划相比，其可行解不是连续的，而整数规划与一般规划相比，其可行解不是连续的，而是离散的是离散的。整数规划举例整数规划举例某航空公司是一家使用小型飞机经营短途

14、航线的小型区域性企某航空公司是一家使用小型飞机经营短途航线的小型区域性企业。该公司已经经营得不错，其管理层决定拓展其经营领域。业。该公司已经经营得不错，其管理层决定拓展其经营领域。 管理层面临的基本问题是：是采购更多的小型飞机来开辟一管理层面临的基本问题是：是采购更多的小型飞机来开辟一些新的短途航线，还是开始通过为一些跨地区航线购买大型的些新的短途航线，还是开始通过为一些跨地区航线购买大型的飞机来进军全国市场（或双管齐下）？哪一种战略最有可能获飞机来进军全国市场（或双管齐下）？哪一种战略最有可能获得最高收益？得最高收益？ 下表提供了购买每一种飞机的年净利润期望（包括资本回收下表提供了购买每一种

15、飞机的年净利润期望（包括资本回收成本）；给出了每架飞机的采购成本，以及可用于飞机采购的成本）；给出了每架飞机的采购成本，以及可用于飞机采购的总可用资金总可用资金1 1亿元；并表明了管理层希望小型飞机的采购不超过亿元；并表明了管理层希望小型飞机的采购不超过两架。两架。需要的决策是：小型飞机和大型飞机各需要采购多少才能够获需要的决策是：小型飞机和大型飞机各需要采购多少才能够获得最大的年总净利润？得最大的年总净利润？小型飞机小型飞机大型飞机大型飞机可获得的总资金可获得的总资金每架飞机年利润每架飞机年利润100100万元万元500500万元万元1 1亿元亿元每架飞机采购成本每架飞机采购成本500500

16、万元万元50005000万元万元最多购买数量最多购买数量2 2没有限制没有限制数学模型数学模型设小型飞机与大型飞机的购买数量分别为设小型飞机与大型飞机的购买数量分别为x1、x2( (架架) )1212112Max z100500500500010000s.t.2,0 xxxxxx x且为整数由于离散问题比连续问题更难以处理，整数规划要比一般线性规由于离散问题比连续问题更难以处理，整数规划要比一般线性规划难解得多，而且至今尚无一种像求解线性规划那样较成熟的算划难解得多，而且至今尚无一种像求解线性规划那样较成熟的算法。目前常用的基本算法有分支定界法、割平面法等。法。目前常用的基本算法有分支定界法、

17、割平面法等。对于指派问题（对于指派问题（0-10-1规划），目前认为最简洁的方法规划），目前认为最简洁的方法匈牙利法。匈牙利法。各种变形的指派问题建模各种变形的指派问题建模有些人并不能进行某项工作有些人并不能进行某项工作任务比人多任务比人多( (人少事多人少事多););人比任务多（人多事少）；人比任务多（人多事少）；某人可以同时被指派给多个任务（一人可做几件事）某人可以同时被指派给多个任务（一人可做几件事）某事可以由多人共同完成（一事可由多人完成）某事可以由多人共同完成（一事可由多人完成） 目标是与指派有关的总利润最大而不是使总成本最小目标是与指派有关的总利润最大而不是使总成本最小各种变形的指

18、派问题建模各种变形的指派问题建模（1 1）有些人并不能进行某项工作）有些人并不能进行某项工作 如果第如果第i i个人不能干第个人不能干第j j项工作，则项工作，则x xijij0 0；（2 2）人少事多人少事多(m(m(人数人数)n)n)n（工作数）（工作数）) )p 填上一些虚拟的事，填上一些虚拟的事，n+1n+1，i+2i+2，m;m;p p 模型模型01,ijcinm ，1111 ()Min z1 (1,2,)s.t. 1 (1,2,)0 ( ,1,2,) ijijijijjijimjmmimijc xxixjxi jmmmLLL(第 人只能做一项工作)(第 项工作只能一人做)非负 一人

19、可以做多事一人可以做多事5家建筑公司承建家建筑公司承建5项工程的指派问题，为了保证工程项工程的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司质量，经研究决定，舍弃建筑公司 A4和和A5，而让技，而让技术力量较强的建筑公司术力量较强的建筑公司A1，A2和和A3来承建。根据实际来承建。根据实际情况，可以允许每家建筑公司承建一项或两项工程。情况，可以允许每家建筑公司承建一项或两项工程。求使总费用最少的指派方案。求使总费用最少的指派方案。4871512791714106912871A2A3A1B2B3B4B5B4871512487151279171410791714106912876912871B2B3B4B5B1A1A2A2A3A3A487151204871512079171410079171410069128706912870C1A1A2A2A3A3A1B2B3B4B5B6B1112161