《整数规划(带答案)【课堂上课】》由会员分享，可在线阅读，更多相关《整数规划(带答案)【课堂上课】（75页珍藏版）》请在金锄头文库上搜索。
1、第八章第八章 整整 数数 规规 划划 运运运运 筹筹筹筹 学学学学1学习课堂第八章第八章 整数规划整数规划1整数规划的图解法整数规划的图解法2整数规划的计算机求解整数规划的计算机求解3整数规划的应用整数规划的应用4整数规划的分枝定界法整数规划的分枝定界法2学习课堂整整数数规规划划是是一一类类要要求求变变量量取取整整数数值值的的数数学学规规划划，可分成可分成线性线性和和非线性非线性两类。两类。求整数解的线性规划问题，求整数解的线性规划问题，应注意：应注意：不不是是用用四四舍舍五五入入法法和和去去尾尾法法对对线线性性规规划划的的非非整数解加以处理就能解决的。整数解加以处理就能解决的。整整数数线线性
2、性规规划划一一些些基基本本算算法法的的设设计计是是以以相相应应线性规划的最优解为出发点线性规划的最优解为出发点而发展出来的。而发展出来的。根根据据变变量量的的取取值值情情况况，整整数数线线性性规规划划又又可可以以分分为为纯纯整整数数规规划划（所所有有变变量量取取非非负负整整数数），混混合合整整数数规规划划（部部分分变变量量取取非非负负整整数数），0-1整整数数规规划划（变量只取（变量只取0或或1）等。）等。第八章第八章 整数规划整数规划3学习课堂整整数数规规划划是是数数学学规规划划中中一一个个较较弱弱的的分分支支，目目前前有有成成熟熟的的方方法法解解线线性性整整数数规规划划问问题题，而而非非线
3、线性性整整数规划问题，还没有好的办法。数规划问题，还没有好的办法。整整数数线线性性规规划划(Integer Linear Programming，简简记记为为ILP)问问题题研研究究的的是是要要求求变变量量取取整整数数值值时时，在在一一组组线线性性约约束束条条件件下下一一个个线线性性函函数数最最优优问问题题，是应用非常广泛的运筹学的一个重要分支。是应用非常广泛的运筹学的一个重要分支。 第八章第八章 整数规划整数规划4学习课堂1 1 整数规划的图解法整数规划的图解法例例1. 某某公公司司拟拟用用集集装装箱箱托托运运甲甲、乙乙两两种种货货物物，这这两两种种货货物物每每件件的的体体积积、重重量量、可
4、可获获利利润润以以及及托运所受限制如表所示。托运所受限制如表所示。甲甲种种货货物物至至多多托托运运4件件，问问两两种种货货物物各各托托运运多多少件，可使获得的利润最大。少件，可使获得的利润最大。货物货物每件体积每件体积(立方米立方米)每件重量每件重量(百千克百千克)每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制13651405学习课堂货物货物每件体积每件体积(立方米立方米)每件重量每件重量(百千克百千克)每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140解解：设设x1 、 x2分分别别为为甲甲、乙乙两两种种货货物物托托运
5、运的的件件数数，建建立模型。立模型。 目标函数：目标函数： Max z = 2x1 +3x2 约束条件：约束条件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0, 为整数为整数。如果去掉最后一个约束，就是一个线性规划问题如果去掉最后一个约束，就是一个线性规划问题.1 1 整数规划的图解法整数规划的图解法6学习课堂利利用用图图解解法法，得得到到线线性性规规划划的的最最优优解解为为x1=2.44, x2=3.26,目标函数值为目标函数值为14.66。由由图图表表可可看看出出, 整整数数规规划划的的最最优优解解（黄黄色色叉叉号号）为为x
6、1=4, x2=2,目标函数值为目标函数值为14。Max z = 2x1 +3x2195x1+273x2=13654 x1+40 x2 =1404231123x2x11 1 整数规划的图解法整数规划的图解法Max z = 2x1 +3x2 约束条件：约束条件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140x1 47学习课堂由由于于相相应应的的线线性性规规划划的的可可行行域域包包含含了了其其整整数数规规划划的的可可行行点点，则则对对于于整整数数规规划划，易易知知有以下性质：有以下性质：性性质质1：任任何何求求最最大大目目标标函函数数值值的的纯纯整整数数规规划
7、划或或混混合合整整数数规规划划的的最最大大目目标标函函数数值值小小于于或或等等于于相相应应的的线线性性规规划划的的最最大大目目标标函函数数值值；任任何何求求最最小小目目标标函函数数值值的的纯纯整整数数规规划划或或混混合合整整数数规规划划的的最最小小目目标标函函数数值值大大于于或或等等于于相应的线性规划的最小目标函数值。相应的线性规划的最小目标函数值。1 1 整数规划的图解法整数规划的图解法8学习课堂例例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1, x2, x3 0 , 均为整数均为整
8、数用用管管理理运运筹筹学学软软件件求解得：求解得： x1 = 5 x2 = 2 x3 = 2 2 2 整数规划的计算机求解整数规划的计算机求解纯整数规划问题纯整数规划问题9学习课堂10学习课堂例例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 - 3x2 + 2x3 3 x3 1 x1, x2, x3 0 x1，x3 为整数，为整数，x3 为为0-1变量变量用用管理运筹学管理运筹学软件求软件求解得解得: z = 16.25x1 = 4 x2 = 1.25 x3 = 1 11学习课堂12学习课堂3 3 整数规划的应用整数
9、规划的应用应用实例：应用实例： 投资投资场所的选择问题场所的选择问题 背包问题背包问题 固定成本固定成本问题问题 指派指派问题问题 分布系统设计分布系统设计 投资投资问题问题13学习课堂3 3 整数规划的应用整数规划的应用 一、投资场所的选择一、投资场所的选择 例例4、京成畜产品公司计划在市区的东、西、南、北四区、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有建立销售门市部，拟议中有10个位置个位置 Aj (j=1,2,3,10)可供选可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定择，考虑到各地区居民的消费水平及居民居住密集度，规定: 在东区由在东区由A1 ，
10、 A2 ，A3 三个点三个点至多至多选择选择两个两个； 在西区由在西区由A4 ， A5 两个点中两个点中至少至少选选一个一个； 在南区由在南区由A6 ， A7 两个点中两个点中至少至少选选一个一个； 在北区由在北区由A8 ， A9 ， A10 三个点中三个点中至少至少选选两个两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示预测情况见表所示 (单位：万元单位：万元)。但投资总额。但投资总额不能超过不能超过720万万元，问应选择哪几个销售点，可使年利润为最大元，问应选择哪几个销售点，可使年利润为最大?14学习
11、课堂解解：设设：0-1变变量量 xi = 1 (Ai 点点被被选选用用)或或 0 (Ai 点点没没被被选选用用)。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0 且且xi 为为0-1变量变量，i = 1, 2, 3, ,10在东区
12、由在东区由A1 ， A2 ，A3 三个点三个点至多至多选择选择两个两个；在西区由在西区由A4 ， A5 两个点中两个点中至少至少选选一个一个；在南区由在南区由A6 ， A7 两个点中两个点中至少至少选选一个一个；在北区由在北区由A8 ， A9 ， A10 三个点中三个点中至少至少选选两个两个15学习课堂补补充充例例、解解决决某某市市消消防防站站的的布布点点问问题题，该该城城市市有有6个个区区，每每个个区区都都可可以以建建消消防防站站。市市政政府府希希望望设设置置的的消消防防站站最最少少，但但必必须须满满足足在在城城市市的的任任何何地地区区发发生生火火警警时时，消消防防车车要要在在15分分钟钟内
13、内赶赶到到现现场场。据据实实地地测测定定，各各区区之之间间消消防防车车行行驶驶的的时时间间如如下下表表所所示示，请请帮帮助助该该市制定一个最省的计划。市制定一个最省的计划。 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 016学习课堂 设设 xi =1,0; 1i 区区建建消消防防站站，0i 区区不不建建消消防站，防站，i=1,6min z = x1 + x2 + x3 + x4 + x5 + x6约束方程
14、保证每个地区都有一个消防站在约束方程保证每个地区都有一个消防站在15分钟行程内。分钟行程内。将将6个地区的条件分别列出：个地区的条件分别列出：s.t. x1 + x2 1, x1 + x2 + x6 1 x3 + x4 1, x3 + x4 + x5 1 x4 + x5 + x6 1, x2 + x5 + x6 1 xi = 0, 1; i=1,6 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 017学习课
15、堂 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0第第2个地区建一个（地区个地区建一个（地区1、2、6都解决了）都解决了）第第4个地区建一个（地区个地区建一个（地区3、4、5都解决了）都解决了）18学习课堂二、二、背包问题背包问题（补充）（补充）背背包包可可装装入入8单单位位重重量量，10单单位位体体积积物物品品。若若背背包包中中每每件件物物品品至至多多只只能能装装一一个个，怎怎样样才才能能使使背背包包装
16、的物品价值最高。装的物品价值最高。物品物品 名称名称 重量重量 体积体积 价值价值 1 书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4 10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 19学习课堂解：解：xi为是否带第为是否带第 i 种物品种物品Max Z=20x1 + 30x2 +10x3+18x4 +15x55x1+3x2 +x3 +2x4 +4x5 82x1+x2 +4x3 +3x4 +5x5 10xi为为0, 1物品物品 名称名称 重量重量 体积体积 价值价值 1 书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4
17、10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 20学习课堂一般形式：一般形式：, 整整数数 xi为是否携带第为是否携带第i 种物品种物品ai为为i 物品单位重量，物品单位重量，b为最大负重为最大负重ci为为i 物品重要性估价物品重要性估价21学习课堂3 3 整数规划的应用整数规划的应用三、固定成本问题三、固定成本问题 例例5高高压压容容器器公公司司制制造造小小、中中、大大三三种种尺尺寸寸的的金金属属容容器器，所所用用资资源源为为金金属属板板、劳劳动动力力和和机机器器设设备备，制制造造一一个个容容器器所所需需的的各各种种资资源源的的数数量量如如表表所所示示。不不考考虑虑固
18、固定定费费用用，每每种种容容器器售售出出一一只只所所得得的的利利润润分分别别为为 4万万元元、5万万元元、6万万元元，可可使使用用的的金金属属板板有有500吨吨，劳劳动动力力有有300人人/月月，机机器器有有100台台/月月，此此外外不不管管每每种种容容器器制制造造的的数数量量是是多多少少，都都要要支支付付一一笔笔固固定定的的费费用用：小小号号是是l00万万元元，中中号号为为 150 万万元元，大大号号为为200万万元元。现现在在要要制制定定一一个个生生产产计计划划，使使获获得得的的利利润为最大。润为最大。22学习课堂解：这是一个整数规划的问题。解：这是一个整数规划的问题。 设设x1，x2，
19、x3 分分别别为为小小号号容容器器、中中号号容容器器和和大大号号容容器器的的生生产产数数量量。各各种种容容器器的的固固定定费费用用只只有有在在生生产产该该种种容容器器时时才才投投入入，若若不不生生产产则则没没有有这这部部分分费费用用，为为了了说说明明固固定定费费用用的的这这种种性性质质，设设 yi = 1(当当生生产产第第 i种种容容器器, 即即 xi 0 时时) 或或0（当当不不生生产产第第 i种种容容器器即即 xi = 0 时）。时）。 引引入入约约束束 xi M yi ，i =1，2，3，M充充分分大大，以保证当以保证当 yi = 0 时，时，xi = 0 。 3 3 整数规划的应用整数
20、规划的应用即：不投入固即：不投入固定费用，是不定费用，是不能投入生产的能投入生产的23学习课堂这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大充分大 xj 0 yj 为为0-1变量变量，i = 1,2,33 3 整数规划的应用整数规划的应用没有固定投入，就不生产没有固定投入，就不生产.yi =0，则，则xi=0. xi是
21、数量，是数量，M为一个充分大的数。为一个充分大的数。一个容器至少需要一个容器至少需要2个劳动个劳动力，共有力，共有300个劳动力，因个劳动力，因此容器数量不会超过此容器数量不会超过150.因因此当此当yi =1时，时，M可取可取150投入固定费用，投入固定费用，生产小号容器生产小号容器y1y2y324学习课堂三、指派问题三、指派问题 有有 n n 项项不不同同的的任任务务，恰恰好好 n n 个个人人可可分分别别承承担担这这些些任任务务，但但由由于于每每人人特特长长不不同同，完完成成各各项项任任务务的的效效率率等等情情况况也也不不同同。现现假假设设必必须须指指派派每每个个人人去去完完成成一一项项
22、任任务务，怎怎样样把把 n n 项项任任务务指指派派给给n n个个人人，使使得得完完成成 n n 项项任任务务的的总的效率最高总的效率最高，这就是，这就是指派问题。指派问题。 3 3 整数规划的应用整数规划的应用25学习课堂例例6 6有有四四个个工工人人，要要分分别别指指派派他他们们完完成成四四项项不不同同的的工工作作，每每人人做做各各项项工工作作所所消消耗耗的的时时间间如如下下表表所所示示，问问应应如如何何指指派派工工作作，才才能能使使总总的消耗时间为最少的消耗时间为最少。3 3 整数规划的应用整数规划的应用26学习课堂解：引入解：引入01变量变量 xij，并令并令 xij =1(当当指指派
23、派第第 i人人去去完完成成第第j项项工工作作时时)或或0(当当不不指指派派第第i人人去去完完成成第第j项项工工作作时时)这这可可以以表表示示为为一一个个0-1整数规划问题：整数规划问题：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x443 3 整数规划的应用整数规划的应用27学习课堂整数规划模型为：整数规划模型为：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32
24、+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x3
25、3+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 为为0-1变量变量，i,j = 1,2,3,43 3 整数规划的应用整数规划的应用每人只每人只能干一能干一项工作项工作一项工一项工作只能作只能由一个由一个人干人干28学习课堂对于有对于有m个人完成个人完成n项任务的一般指派问题，项任务的一般指派问题，设：设：m不一定等于不一定等于n，当当mn时，有的时，有的人没有任务。人没有任务。第第i个人完成的任务个人完成的任务且最多承担一项且最多承担一项第第j项工作正好有一项工作正好有一人承担人承担注意：当注意
26、：当m0yi=0时，当不利用第时，当不利用第i种设备生产时，此时相应种设备生产时，此时相应的的Xi=0目标函数为：目标函数为：Min Z=7x1+2x2+5x3+100y1+300y2+200y358学习课堂(1) 约束条件约束条件X1 800，X2 1200，X3 1400，X1+X2+X3=2000(改大于等于结果相同改大于等于结果相同)0.5X1+1.8X2+1.0X3 2000还得保证还得保证Yi=0时，时，Xi=0.(没有准备费就不启没有准备费就不启用该设备用该设备)，引入一个很大的，引入一个很大的MXi M Yi（i=1,2,3）Xi 0,（i=1,2,3）Yi（i=1,2,3）是
27、）是0-1变量变量59学习课堂（2）约束条件改为0.5X1+1.8X2+1.0X3 250060学习课堂（3）约束条件改为0.5X1+1.8X2+1.0X3 280061学习课堂（4）去掉电量的约束条件62学习课堂第第5题题5：二二63学习课堂500800700yi是是0-1变量，变量， yi=0，相当于该，相当于该库房不存在库房不存在需求量需求量上海上海y2，武汉，武汉y40,10,01,1最多最多2个库房个库房武汉和广州不能同时建武汉和广州不能同时建i=1,2,3,4北京北京上海上海广州广州武汉武汉华北华北华中华中华南华南264学习课堂第第6题：指派问题题：指派问题（1）引入引入01变量变
28、量 xij，并令并令 xij =1(当指派第当指派第i人去完成第人去完成第j项工作时项工作时) 0(当不指派第当不指派第i人去完成第人去完成第j项工作时项工作时)目标函数 Min Z= 20x11+ 19x12+ 20x13+ 28x14+18x21+ 24x22+ 27x23+ 20x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20x42+ 24x43+ 19x4465学习课堂 x11+ x12+ x13+ x14= 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作乙只能干一项工作) x31+ x32+
29、 x33+ x34= 1 (丙只能干一项工作丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干)66学习课堂（2）把目标函数改为求最大值即可，即：）把目标函数改为求最大值即可，即：Max Z= 20x11+ 19x12+ 2
30、0x13+ 28x14+18x21+ 24x22+ 27x23+ 20x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20x42+ 24x43+ 19x44约束条件不变约束条件不变67学习课堂（3）增加了一项工作增加了一项工作E，问应指派，问应指派四个人干四个人干哪四项工作哪四项工作，共有五项工作，则结果中肯定，共有五项工作，则结果中肯定有一项工作无人做。有一项工作无人做。 mn，人数少于任务数。此时，添加虚拟，人数少于任务数。此时，添加虚拟人数人数n-m=1个，该人是虚拟的，因此完成各个，该人是虚拟的，因此完成各项工作所需的时间都设为项工作所需的时间都设为0.
31、此时变为此时变为5个人完个人完成成5项工作的问题了。项工作的问题了。Min Z= 20x11+ 19x12+ 20x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20x24+ 20x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20x42+ 24x43+ 19x44 +16x45 + 0x51+ 0x52+ 0x53+ 0x54 +0x55甲乙丙甲乙丙丁每个丁每个人做第人做第5项工作项工作的时间的时间68学习课堂约束条件 x11+ x12+ x13+ x14 + x15 = 1 x21+ x22+ x23+ x24 + x2
32、5 = 1 x31+ x32+ x33+ x34 + x35 = 1 x41+ x42+ x43+ x44 + x45 = 1 x51+ x52+ x53+ x54 + x55 = 1 x11+ x21+ x31+ x41 + x51 =1 x12+ x22+ x32+ x42 + x52 =1 x13+ x23+ x33+ x43 + x53 = 1 x14+ x24+ x34+ x44 + x54 = 1 x15+ x25+ x35+ x45 + x55 = 1结果中安排第结果中安排第5个虚拟人去个虚拟人去做哪项工作，做哪项工作，表明实际中该表明实际中该项工作无人做项工作无人做69学习课堂
33、方法二：方法二：x11+ x12+ x13+ x14 + x15 = 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24 + x25 = 1 (乙只能干一项工作乙只能干一项工作)x31+ x32+ x33+ x34 + x35 = 1 (丙只能干一项工作丙只能干一项工作)x41+ x42+ x43+ x44 + x45 = 1 (丁只能干一项工作丁只能干一项工作)x11+ x21+ x31+ x41 1 ( A工作工作)x12+ x22+ x32+ x42 1 ( B工作工作)x13+ x23+ x33+ x43 1 ( C工作工作)x14+ x24+ x34+ x
34、44 1 ( D工作工作)x15+ x25+ x35+ x45 1 ( E工作工作)Min Z= 20x11+ 19x12+ 20x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20x24+ 20x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20x42+ 24x43+ 19x44 +16x45 用用普通线性规普通线性规划模块划模块求解求解70学习课堂（4）增加了一个人，问应指派哪四个人去）增加了一个人，问应指派哪四个人去干这四项工作，肯定有一个人没有工作做。干这四项工作，肯定有一个人没有工作做。目标函数目标函数 Min Z
35、= 20x11+ 19x12+ 20x13+ 28x14+ 18x21+ 24x22+ 27x23+ 20x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20x42+ 24x43+ 19x44 + 16x51+ 17x52+ 20x53+ 21x5471学习课堂方法一：虚设一个工作，每个人完成此项工方法一：虚设一个工作，每个人完成此项工作的时间设为作的时间设为0.x11+ x12+ x13+ x14 + x15 = 1 x21+ x22+ x23+ x24 + x25 = 1x31+ x32+ x33+ x34 + x35 = 1x41+ x42+ x43+ x
36、44 + x45 = 1x51+ x52+ x53+ x54 + x55 = 1x11+ x21+ x31+ x41 + x51 =1x12+ x22+ x32+ x42 + x52 =1x13+ x23+ x33+ x43 + x53 = 1x14+ x24+ x34+ x44 + x54 = 1x15+ x25+ x35+ x45 + x55 = 1Min Z= 20x11+ 19x12+ 20x13+ 28x14+0x15 + 18x21+24x22+27x23+ 20x24+ 0x25+ 26x31+16x32+15x33+ 18x34+ 0x35+ 17x41+ 20x42+ 24x
37、43+ 19x44 +0x45 + 16x51+ 17x52+20x53+ 21x54 +0x55用用指派问题指派问题求求解的结论解的结论72学习课堂方法二：方法二：x11+ x12+ x13+ x14 1 (甲至多干一项工作甲至多干一项工作) x21+ x22+ x23+ x24 1 (乙至多干一项工作乙至多干一项工作)x31+ x32+ x33+ x34 1 (丙至多干一项工作丙至多干一项工作)x41+ x42+ x43+ x44 1 (丁至多干一项工作丁至多干一项工作)x51+ x52+ x53+ x54 1 (戊至多干一项工作戊至多干一项工作)x11+ x21+ x31+ x41 +
38、x51 = 1 ( A工作只能一人干工作只能一人干)x12+ x22+ x32+ x42 + x52 = 1 ( B工作只能一人干工作只能一人干)x13+ x23+ x33+ x43 + x53 = 1 ( C工作只能一人干工作只能一人干)x14+ x24+ x34+ x44 + x54 = 1 ( D工作只能一人干工作只能一人干)用用普通线性规划普通线性规划模块模块求解的结论求解的结论松弛变量为松弛变量为0，对偶价格，对偶价格也为也为0，所以，所以不止一组最不止一组最优解优解73学习课堂第第7题题分城市讨论 起飞起飞到达到达1019:0010210:0010315:0010420:00105
39、22:00106 7:002*2x=4x3*3x=9x8*8x=64x13*13x=169x15*15x=225x10714:0019*19x=361x(次日)20*20x=400x(次日)25*25x=625x(次日)6*6x=36x8*8x=64x10818:0015*15x=225x(次日)16*16x=256x(次日)21*21x=441x(次日)2*2x=4x4*4x=16x10911:0022*22x=484x(次日)23*23x=529x(次日)4*4x=16x9*9x=81x11*11x=121x11019:0014*14x=196x(次日)15*15x=225x(次日)20*
40、20x=400x(次日)25*25x=625x(次日)3*3x=9x101102103104105106107108109110例：例：106航班航班7:00达到达到A，让，让102航班航班10:00起飞起飞对于城市对于城市A停留停留1小时费用为小时费用为x元元74学习课堂依此分析城市依此分析城市B，城市，城市C根据上一航班到达的时间与下一航班起飞时根据上一航班到达的时间与下一航班起飞时间的时间差，如果大于间的时间差，如果大于2小时，当天可起飞，小时，当天可起飞，否则，只能次日起飞。根据停留时间，计算否则，只能次日起飞。根据停留时间，计算出每一种情况的停留损失费，填入矩阵中即出每一种情况的停留损失费，填入矩阵中即可利用可利用“指派问题指派问题”求解。求解。最优值一定，最优解或许不唯一。最优值一定，最优解或许不唯一。75学习课堂
