LINGO求解优化问题.doc

首 页一、Lingo简介1. 目标函数一个函数解析式，你希望求它的最大或最小值 max=函数解析式； 或 min=函数解析式；例max=3*b+2*c2; min=b(1/3)-c*k；Lingo的语句以 ; 号结束。2. 运算加(+)，减(-)，乘(*)，除(/)，乘方(xa)3. 变量用字母或字母数字的组合表示 例a，b，cc1，x1。Lingo的变量缺省值为非负数。4. 限制条件一组等式或不等式。Lingo的，=，=36;3*x1+5*x2=45;Lingo的注释语句用!开头用;结束。5. 变量类型变量类型说 明bin( 变量名) ;限制该变量为0或1。bnd( a,变量名, b);限制该变量介于a，b之间。free(变量名);允许该变量为负数。gin( 变量名);限制该变量为整数。二、Lingo高级sets语句连续六个月的产量，可以用x1,x2,x3,x4,x5,x6表示, 但十二个月的产量用同样的方法表示就显繁琐。Lingo可以通过sets语句设置数组功能使问题变得简单。例 定义数组x, 有x(1),x(2),x(3),x(4)x(12)个成员，用以表示十二个月的产量。sets:r/1.12/:x; !r是组的类型名,x数组名;endsets;sets语句以sets开头，endsets结束。示例程序2sets:mat/1.4/: x; !mat是组的类型名,x数组名;endsetsmin=50*x(1)+20*x(2)+30*x(3)+80*x(4);400*x(1)+200*x(2)+150*x(3)+500*x(4)=500;3*x(1)+2*x(2)=6;2*x(1)+2*x(2)+4*x(3)+4*x(4)=10;2*x(1)+4*x(2)+x(3)+5*x(4)=8;data语句有时，我们要用到常数数组，比如在400*x(1)+200*x(2)+150*x(3)+500*x(4)=500中，x(1), x(2), x(3), x(4)的系数分别为400, 200, 150, 500，此时,可用data语句。例 定义数组a, 其中a(1)=400，a(2)=200，a(3)=150，a(4)=500。sets:l/1.4/: a,x;endsetsdata: a=400 200 150 500;enddatadata语句是以data开头，enddata结尾。示例程序3sets:l/1.4/: x, a;endsetsdata:a=7 2 3 9; !a(1)=7, a(2)=2, a(3)=3, a(4)=9;enddatamax=x(1)*a(3)+x(2)*a(1)+x(3)*a(4)+x(4)*a(2);x(1)+x(4)-x(2)-x(3)a(1);x(4)+2*x(2)a(4);x(1)+x(3)a(1);Lingo含有一些针对数组的命令，方便了数组的使用。for循环语句:for(数组类型名(i): 循环的语句);示例程序4（gin语句）sets:r/1.5/: a, b;endsetsdata:a= 3.3 4.6 2.7 7.1 10.3;enddatamax=a(1)*b(1)-a(2)*b(2)+a(3)*b(3)-a(4)*b(4);for(r(i): b(i) a(i);!等价于b(1)a(1)；b(2)a(2)；b(3)a(3)；b(4)a(4);for(r(i): gin(b(i); !b为整数数组;!等价于gin(b(1)；gin(b(2)；gin(b(3)；gin(b(4);sum语句sum(数组类型名(i): 含数组名(i)的语句);示例程序5sets: r/1.5/: a, b;endsetsdata: a= 3.3 4.6 2.7 7.1 10.3;enddatamax=sum(r(i):b(i)+sum(r(i):b(i)/a(i) +sum(r(i):b(i)*a(i); !等价于max=b(1)+b(2)+b(3)+b(4)+b(1)/a(1)+b(2)/a(2)+b(3)/a(3)+b(4)/a(4);for(r(i): b(i) a(i);for(r(i): gin(b(i);示例程序6（bnd语句）sets:m/1.4/: x, need, g, y;endsetsdata:need=4000 2000 3000 10000;enddatamin=30000*sum(m(i): x(i)+30*sum(m(i): g(i);g(1)=600+y(1)*(x(2)+x(3)+x(4)-need(1);g(2)=g(1)+y(2)*(sum(m(i): x(i)-x(2)-need(2); ! sum(m(i):x(i)-x(2)等价于x(1)+x(3)+x(4);g(3)=g(2)+y(3)*(sum(m(i): x(i)-x(3)-need(3);g(4)=g(3)+y(4)*(sum(m(i): x(i)-x(4)-need(4);gin(y(1);for(m(i): gin( x(i); bnd(10, y(i), 500) ); !x为整数数组，10y(i)500;sets语句还可以定义矩阵mn矩阵就是m行，n列的数。x=2 3 4 5 6 7 8 9 2 3 4 7 8 2 1;x 是一35的矩阵，x(1, 2)调用第一行第二列的数3。例 定义45矩阵。Sets:r/1.4/;c/1.5/;m(r,c): x; !r为行数，c为列数，m为45矩阵的类型名，x为矩阵名;endsetsdata语句用于矩阵data:x=2 5 6 7 5 6 3 1 8 7 9 10;enddatasum语句用于矩阵sum(m(i,j): x(i,j); !对x的全部元素求和;sum(m(1,j): x(1,j)40; !对x的第一行求和;sum(m(i,3): x(i,3)40; !对x的第三列求和;for(r(i): sum(m(i,j):x(i,j)50); !对x的每一行求和;for(c(j):sum(m(i,j):x(i,j)50); !对x的每一列求和;for循环语句可用于矩阵for(m(i,j): gin(x(i,j);表示所有的x(i,j)为整数。示例程序7sets: r/1.3/: s; c/1.4/: pr, pd; m(r,c): x; !定义一34矩阵;endsetsdata:s = 750 250 400;pr = 2 3 4 5;x = 15 10 6 2 1 6 10 14 5 8 13 9;enddatamax=sum(c(i): pr(i) *pd(i);for( r(i): sum(c(j): x(i,j)*pd(j)/16) =s(i);! for( r(i): sum(m(i,j):x(i,j)*pd(j)/16) =s(i)等价于:x(1,1)*pd(1)/16+x(1,2)*pd(2)/16+x(1,3)*pd(3)/16+x(1,4)*pd(4)/16s(1);x(2,1)*pd(1)/16+x(2,2)*pd(2)/16+x(2,3)*pd(3)/16+x(2,4)*pd(4)/16s(2);x(3,1)*pd(1)/16+x(3,2)*pd(2)/16+x(3,3)*pd(3)/16+x(3,4)*pd(4)/16s(3);x(4,1)*pd(1)/16+x(4,2)*pd(2)/16+x(4,3)*pd(3)/16+x(4,4)*pd(4)/16s(4);示例程序8（bin语句）sets: l/1.4/; m(l,l): a,x;endsetsdata:a=54 54 51 53 51 57 52 52 50 53 54 56 56 54 55 53;enddatamin=sum( m(i,j): a(i,j)*x(i,j) );for(l(i): sum(l(j): x(i,j)=1;sum(l(j): x(j,i)=1);! sum(l(j):x(i,j)=1,每一行的和为1；sum(l(j):x(j,i)=1,每一列的和为1;for( m(i,j): bin(x(i,j) ); !x元素取值为0或1;sets:l/1.4/;m(l,l):a,x;endsetsdata:a=54 54 51 53 51 57 52 52 50 53 54 56 56 54 55 53;enddatamin=sum(m(i,j):a(i,j)*x(i,j);for(l(i):sum(l(j):x(i,j)=1;sum(l(j):x(j,i)=1);! sum(l(j):x(i,j)=1,每一行的和为1；sum(l(j):x(j,i)=1,每一列的和为1;for(m(i,j):bin(x(i,j);三、优化问题Lingo 是较好的最优化建模工具，Lingo模型由两部分组成：(一) 目标（objective）： 最优化目标。(二) 限制条件（constraint）。1. 我的食谱由四种食品组成： 果仁巧克力（50 美分/块）； 巧克力冰淇淋（20美分/杯）； 可乐（30美分/瓶）； 奶酪（80美分块）。我每天的营养最低需求: 500 卡路里，6 盎司巧克力，10 盎司糖，8 盎司脂肪。四种食品的营养成分如下表：卡路里巧克力(盎司)糖(盎司)脂肪(盎司)价格果仁巧克力(块)40032250巧克力冰淇淋(杯)20022420可乐(瓶)15004130奶酪(块)50004580最低需求5006108试列出一份最节俭的食谱讲评问：选择哪些变量?答：果仁巧克力x1块，巧克力冰淇淋x2杯，可乐x3瓶，奶酪x4块。问：该问题的目标是什么？答：食谱中饮食的成本最低：min 50x1+20x2+30x3+80x4问：限制条件？答：满足每天的最低需求。卡路里：400x1+200x2+150x3+500x4500巧克力：3x1+2x26糖：2x1+2x2+4x3+4x410脂肪：2x1+4x2+x3+5x48讨论如果巧克力冰淇淋的价格变为原来的两倍，食谱将如何改动？练习1.1 生产两种糖果生产两种糖果：软糖和硬糖。糖果仅由糖、坚果和巧克力制成。现有100盎司糖，20盎司坚果，30盎司巧克力。软糖须含有至少20%的坚果；硬糖须含有至少10%的坚果和10%的巧克力。一盎司的软糖售价为25美分，一盎司的硬糖售价为20美分。试安排生产计划。练习1.2 生产三种产品某公司生产 A, B, C 三种产品，售价：A为$10，B为$56，C为$100。生产一单位A，需1小时的劳力；生产一单位 B，需2小时的劳力加上2单位的A；生产一单位 C，需3小时的劳力加上1单位的B。现有40小时的劳力，试安排生产计划。2. 生产一种电子产品某公司生产一种电子产品。已知明年四季度的需求（须按时交货）：第一季度为4000件；第二季度为2000件；第三季度为3000件；第四季度为10000件。公司员工每年有一个季度休假，每个员工年薪为$30,000，每个员工每季度最多可生产500件产品。每个季度末公司须为每件存货付存储费$30。公司现有600件产品，如何安排明年的生产？讲评问：该问题的目标是什么？答：员工年薪与存储费总和最低。问：限制条件？答：每季度初的库存与该季度生产量的和须满足该季度的需求。问：如何表示员工总数？答1：各季度上班的员工x(1)，x(2)，x(3)，x(4)的总和答2：答1的总和是员工总数的3倍，因为每个员工工作3个季度。问：如何表示存储费？答：设计每季度末的库存变量。问：如何表示每季度的产量？答：设计每季度每个员工的实际产量变量。讨论若每个季度上班员工数目相同，员工年薪与存储费总和将如何变化？练习2.1 产品生产任务某公司须完成如下交货任务：一季度为30件；二季度为20件；三季度为40件。每季度正常上班时间至多可生产27件，单位成本为$40，加班时间的单位生产成本为$60。产品不合格率为20%，每季度剩下的合格产品（在存货时）中有10%被破坏，单位存货费为$15。已知现有20件合格产品，如何安排3个季度的生产？3. 邮局雇员某邮局每天需一定数量的全职员工：星期一17名，星期二13名，星期三15名，星期四19名，星期五14名，星期六16名，星期日11名。全职员工连续工作5天后休息2天。邮局须雇用多少全职员工?讲评问：问题中如何设置变量？答：该问题跟模型2有点相似，将员工分为7种，分别为星期一开始上班（休假结束），星期二开始上班，星期日上班，对应人数分别为x(1), x(2), , x(7)，这样星期一来上班的人数为：x(1)+x(4)+x(5)+x(6)+x(7)。一二三四五六日x(1)休息休息x(2)休息休息x(3)休息休息x(4)休息休息x(5)休息休息x(6)休息休息x(7)休息休息上班人数17131519141611讨论假设邮局可要求员工加一天班，已知员工正常工作日薪为$50，加班工作日薪为$62。试定一最省钱的人事安排计划.练习3.1 银行雇员Gotham City National Bank 每周一至周五的9:0017:00营业。银行对信贷员的需求量如下表: 时间段9-1010-1111-1212-1313-1414-1515-1616-17信贷员需求量43465688银行雇用两种信贷员：全职信贷员（工作时间：9:0017:00，除去11:0012:00或12:0013:00的中餐时间），时薪为$8（含中餐时间）；兼职信贷员，工作时间为连续3小时，时薪为$5。试定一最省钱的信贷员雇用计划。每天兼职信贷员总数不超过5个。4. 买卖谷子Alexis Cornby 靠买卖谷子为生。年初，他有50吨谷子和$10000，每月初他可以以下价格买进谷子：一月为$300，二月为$350，三月为$400，四月为$500。每月末他可以以下价格卖出谷子：一月为$350，二月为$450，三月为$350，四月为$550。Alexis 的谷子存放于它的仓库内（仓库容量为100吨）。他买谷子时须付现金。试设计买卖计划。讨论若买谷子的钱可延期一个月付款，买卖计划将发生何种变化？5. 最大长方体体积有一块长为120厘米，宽为90厘米的矩形薄铁皮材料，现要剪一个长方体的展开图，做一个长方体模型。求长方体体积的最大值。讲评问：设a,b,c分别是长方体的长，宽，高，a,b,c须满足什么条件？abaaacc答1：2a+b120 及 2a+2c90答2：也可以是2a+b90 及 2a+2c3，同理，4*c+2*a5。但是作为承租方希望总租金最少：min=36*c+12*a+8*b。讨论若增加1公斤原材料，总获利增加多少？若市场上有x公斤的原材料出售，你愿以何种价格收购？7. 组建混合泳接力队Doc Councilman 正组建一支400米混合泳（自由泳，仰泳，蝶泳，蛙泳）接力队，有四位泳将，GARY HALL，MARK SPITZ，JIM MONTGOMERY，CHET JASTREMSKI，他们四项游泳项目成绩如下表， Doc Councilman应如何安排四位泳将的接力项目？单位:秒自由泳蛙泳蝶泳仰泳GARY HALL54545153MARK SPITZ51575252JIM MONTGOMERY50535456CHET JASTREMSKI56545553讲评问：问题的目标是什么？答：接力赛成绩最好问：限制条件是什么？答：每人只能参加一项，每项都须有人参加。问：如何表示这种限制条件？答：设置一个44的选择矩阵（每个元素只能是1或0），矩阵每行每列的和均为1问：如何表示接力赛成绩？答：设的矩阵与成绩矩阵点乘（对应元素相乘）后对所有元素求和8. 工作指派四项工作指派给五个员工（每项工作只能由一人单独完成），每人完成各项工作耗时如下表，如何指派使得完成四项工作总耗时最少？工作1工作2工作3工作4员工122183018员工218-2722员工326202828员工41622-14员工521-2528（注: 横线表该员工不宜完成该项工作）讲评问：碰到横线怎么办？答：设成很大的数问：5个人4项工作如何表示？答：每列的和为1（工作须有人做），每行的和小于或等于1（有机会不做）9. 森林砍伐已知森林具有6年的生长期，我们把森林中的树木按照高度分为6类：第1类树木的高度为 0, h1 ，它是树木的幼苗，其经济价值为p(1)=0；第k类树木的高度为 h(k-1), h(k) ，每一棵经济价值为p(k)；第6类树木的高度为 h(5), ，经济价值为p(6)。设每年对森林砍伐一次，且为了维持每年都有稳定的收获，只能砍伐部分树木，留下的树木和补种的幼苗，经过一年的生长期后，应该与上一次砍伐前的高度状态一致。再假设在一年的生长期内树木最多只能生长一个高度级，即第k类的树木可能进入k+1类（比例为g(k)），也可能停留在k类中。设g(1)=0.28, g(2)=0.32, g(3)=0.25, g(4)=0.23, g(5)=0.37p(2)=50元, p(3)=100元, p(4)=150元, p(5)=200元, p(6)=250元。求出对其进行最优采伐的策略。讲评问：如何描述砍伐前后森林高度状态的变化？答：设森林的总面积为1，6类高度树木分别为x(1), x(2), x(3), x(4), x(5), x(6)，被砍掉的面积分别为y(1), y(2), y(3), y(4), y(5), y(6)。 x(1)先变为x(1)-y(1)，由于补种树苗的原因，x(1)变为x(1)-y(1)+(y(1)+y(2)+y(3)+y(4)+y(5)+y(6)最后由于树木生长原因，x(1)变为( 1g(1) )( x(1)-y(1)+( y(1)+y(2)+y(3)+y(4)+y(5)+y(6) ) )x(2) 先变为x(2)-y(2)，后由于树木生长原因x(2)变为(1g(2)( x(2)-y(2) )+ g1(x(1)y(1)+(y(1)+y(2)+y(3)+y(4)+y(5)+y(6)同理，x(3)=(1-g(3)(x(3)-y(3)+g2*(x(2)-y(2)x(6)=(x(6)-y(6)+g5*(x(5)-y(5)讨论修改p2, p3, p4, p5, p6, g1, g2, g3, g4, g5的值，看看砍伐策略的变化情况。10. 公交线路招标Chicago教育委员会为该城市的四条学生公交线路招标。四家公司做出如下竟标：线路1线路2线路3线路4公司140005000-公司2-4000-4000公司33000-2000-公司4-40005000(a) 假设每位竟标者至多可分配到一条线路，问委员会将如何招标？(b) 假设每位竟标者至多可分配到两条线路，问委员会将如何招标？11. 运输和生产方案福特在L.A. 和 Detroit生产汽车，在Atlanta有一仓库，供应点为Houston 和 Tampa；城市间每辆汽车运输费用见下表。 L.A.的生产能力为1100辆， Detroit的生产能力为2900辆。Houston汽车需求量为2400辆，Tampa汽车需求量为1500辆。L.ADETROITATLANTAHOUSTONTAMPAL.A.（工厂）014010090225DETROIT（工厂）1450111110119ATLANTA（仓库）105115011378HOUSTON（供应点）891091210-TAMPA（供应点）21011782-0如何确定运输和生产方案，才能满足Houston 和 Tempa的需求且费用最低。讲评问：这个问题是否很简单？答1：这是一个从L.A. 和 Detroit到Houston 和 Tampa城市间的汽车运输问题，仓库Atlanta完全多余答2：仓库Atlanta可降低运费，例如，从L.A. 经过Atlanta到达Tampa比从L.A. 直接到达Tampa便宜问：这是运输问题中的转运问题，任何一个地点都可以输入也可以输出。生产点（L.A. 和 Detroit），仓库（Atlanta），需求点（Houston 和 Tampa）的输入和输出须满足什么条件？答：生产点：输入减输出等于产量；仓库：输入等于输出；需求点：输出减输入等于需求量。12. 化肥调拨方案设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价（万元/万吨）如下表所示。试求出总的运费最省的化肥调拨方案。 需求地区化肥厂IIIIIIIV产量(万吨)A1613221750B1413191560C192023禁止50最低需求(万吨)3070010最高需求(万吨)507030不限讲评问：地区IV最高需求为不限，是不是无限大的意思？答1：是的答2：不是，地区IV最多可得到（50+50+60）（总产量）-（70+30）（其它地区最小需求）6013. 物资运输某航运公司承担6个港口城市A, B, C, D, E, F的四条固定航线的物资运输任务。已知各条航线的起点，终点城市及每天航班数见下表：航线起点城市终点城市每天航班数1ED32BC23AF14DB1假定各条航线使用相同型号的船只，由各城市间的航程天数见下表：到从ABCDEFA0121477B1031388C23015557851703F7852030又知每条船只每次装卸货物的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货要求。讲评问：若城市x（起点），y（终点）间航程为4天，每条船只每次装卸货物的时间各需1天，空船从空船从y到x只需2天，每天航班数为5，应配备多少条船？答1：5条答2：若一天发出5条船，第二天便没船可发，应备5(4+2)30条答3：6天过后，离开x的船还没回来，应备5(4+2+2)40条问：该题中4条航线需多少船？答1：3(17+2)+2(3+2)+(7+2)+(13+2)=91答2：91条不够，城市E处的船只够19天（51条），E每天需3条空船。同理， A和 B每天均需1条船；而C, D, F处每天分别多出2 , 2, 1条船。答3：这这正好是一个C, D, F到E, A, B的运输问题。14. 确定航线和航班Indianapolis航空公司计划每天从Indianapolis飞6个航班，计划目的地为： New York, Los Angeles, 或 Miami。下表列出各航线的日收益与航班次数的关系。航班次数123456NEW YORK$80$150$210$250$270$280LOS ANGELES$100$195$275$325$300$250MIAMI$90$180$265$310$350$320试帮该公司确定航线和相应的航班次数。讲评问：如果，NEW YORK飞3个航班，LOS ANGELES飞2个航班，MIAMI只能飞1个航班了，如何用数据表示这种安排（有利于收益的计算，及限制条件的表示）？答：上述安排对应于下表：航班次数123456NEW YORK001000LOS ANGELES010000MIAMI1000001表示选择，0表示不选。正好可以设计一个选择矩阵（3行6列）。15. 安排机器生产某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的年产量函数为：y=8x（x为投入生产的机器台数），年完好率为0.7；机器在低负荷下生产的年产量函数为：y=5x（x为投入生产的机器台数），年完好率为0.9。假定开始生产时完好的机器数量为1000台，试问每年如何安排机器在高、低负荷下的生产，使在五年内生产的产品总产量最高。 讨论如果5年末完好机器数必须为500台，又将如何？16. 生产与库存某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如表所示。假定该厂生产每批产品的固定成本为3（千元），若不生产为0；每单位产品成本为1（千元）；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期末未售出的产品每单位需存储费0.5（千元）。还假定在第一个时期的初始储存量为0，第四个时期之末的库存量也为0。试问如何安排各个时期的生产与库存，才能在满足市场需要的条件下，使总成本最小。时期1234需求(单位)2324讲评问：如何处理生产固定成本？答：设计一个生产判断变量数组x，若生产则x(i)为1，不生产则x(i)为0问：如何表示每个时期的产量？答：设计一个产量数组y，x(i)*y(i) 则为第i时期的产量。17. 宽带网速下图为一网络，节点1到节点2的宽带带宽为6兆，节点1到节点3的宽带带宽为2兆，节点2到节点4的宽带带宽为3兆，节点4到节点6的宽带带宽为2兆，求节点1到节点6的最大网速。12345623132776讲评问：节点1到节点6的最大网速受什么限制？答1：受节点1输出宽带带宽的限制。答2：还受中间节点2，3，4，5输入和输出宽带带宽的限制。答3：中间节点的输入等于输出。问：如何表示节点1到节点6的最大网速？答：节点1的输出或节点6的输入。讨论若想提高节点1到节点6的最大网速x兆，如何实现？18. 网络传输费用问题 在网络传输过程中有时得考虑费用问题，下表中的单位成本是指流经该宽带单位流量的费用，考虑从节点1 到节点 5的最小费用最大流。宽带( 1, 2 )( 1, 3 )( 2, 4 )( 2, 5 )( 3, 2 )( 3, 4 )( 4, 5 )带宽108275104单位成本416123219. 工序安排某项研制新产品的各个工序，工序所需时间及相应费用，工序极限时间及相应费用，以及工序之间的相互关系如表：工序代号正常情况采取措施后缩短一天工期代价紧后工序正常时间(天)直接费用极限时间(天)直接费用a60100006010000-b,c,d,eb454500306300120lc10280054300300fd2070001011000400g,he40100003512500500hf183600105440230lg3090002012500350kh153750105750400lk256250159150290ll35120003512000-l研制过程中每天间接费用为400元。(1) 试作出流程图，并求出正常情况最早完工时间讲评问：我们通常用ijx来表示工序x。12345876cedbf0hgkla工序( 3, 6 )是虚拟工序，仅用来表示h须在d结束后才能开始。我们通常在各节点处摆放一个记时器，定t(1)=0，t(2)为以节点2为起点的工序中最早开始动工的时刻，t(3)为以节点3为起点的工序中最早开始动工的时刻，t(8)为完工时间。请问，t(5)，t(7)间需满足什么关系？答：t(5) - t(7)大于工序f所需时间。问：正常情况最早完工时间怎么表示？答：就是t(8)的最小值求最短工期下的最低费用。求最低费用下的最短工期。20. 邮递员投递路线如下图所示，节点间的线段表示某小区的弄堂，线段旁的数字表示弄堂的长度。邮局在其中某个节点，请设计邮递员投递路线。559434434642123456789讲评问：问题的目标是什么？答：邮递员投递线路最短。问：邮递员投递线路的长度是否等于所有弄堂的长度和？答：不是，每条弄堂仅过一遍，未必可行？问：为什么？答1：左图中的弄堂，无论邮局在哪个节点，邮递员都得跑两趟。右图中的每条弄堂，无论邮局在哪个节点，邮递员都只须跑一次。11232问：有没有规律？答1：问题跟邮局的位置无关，因为邮递员的投递路线是封闭的。答2：每个节点进出的次数应该相等。讨论如果邮递员数目是2个或2个以上又将如何? 练习20.1 邮递员投递路线如下图所示，节点间的线段表示某区的街道，街道都是单行道，线段旁的数字表示街道的长度。邮局在其中某个节点，请设计邮递员投递路线。231432521421234567问：该问题和问模型20有哪些异同？答：大同小异，只不过街道是单向的。21. 航班空姐配备Braneast 航空公司须为每天飞行于New York 和 Chicago的航班配备空姐。每位空姐住在New York或Chicago。每天每位空姐须飞一班New York-Chicago和一班Chicago-New York，空姐飞两航班的间隙（滞留时间）至少为1小时，Braneast 航空公司想减少空姐们的滞留时间，应如何配备？Braneast 航空公司每天的航班见下表：航班:1234567飞-CHICAGO:691215171920达-NEWYORK:10131619212324航班:1234567飞-NEWYORK:781012141618达-CHICAGO:9101214161820讲评问：该问题的目标是什么？答：空姐们的滞留时间总和最少。问：该问题的限制条件是什么？答：飞离CHICAGO的空姐须飞NEWYORK到CHICAGO的航班回来。飞离NEWYORK的空姐须飞CHICAGO到NEWYORK的航班回来。每个航班须配备空姐？22. 部门搬迁方案伦敦一家大公司计划将公司的一些部门搬出伦敦，以节约诸如房租人事等方面的费用，当然部门间的通信费用必将增加。公司由五个部门组成，A, B, C, D, 和 E，考虑搬迁的地址为Bristol和Brighton。每个城市至多安置3个部门。各部门搬迁后每年能节约的费用（千镑）如下表：ABCDEBristol101510205Brighton1020151515各部门间每年的通信量（千单位）如下表：ABCDEA1.01.5B1.41.2C2.0D0.7各部门间的通信单价（镑每年每单位）BristolBrightonLondonBristol51413Brighton1459London13910讲评问：如何表示部门搬迁方案？答：每一种方案都对应下表ABCDEBristol01100Brighton00010London10001上表表示以下方案：A, E留守London，B, C迁至Bristol，D迁至Brighton，所以我们可以用1个35的矩阵x表示搬迁方案。问：如何表示搬迁至London的收益？答：无收益，用0表示。问：如何计算通信费用？答：用55矩阵qq（在lingo中，qq允许只有6个元素）表部门间的通信量。33矩阵cc表地区间的通信单价。地区k, l间的总通信费用：就是x(k, i)x(l, j)qq(i, j)cc(k, l)23. 求流水线的最小循环时间一条流水线上有三个工作台，每个工序须在工作台上完成。现有A，B，C，D，E，F，G，H，I，J等10个工序，相互关系如下图，各工序耗时如下表。求流水线的最小循环时间。GABCHIJEFD耗时表工序ABCDEFGHIJ时间451195015121212128讲评问：流水线的最小循环时间是由什么时间决定的？答：由工作时间最长的工作台决定问：工序间的先后承接关系对工序在工作台上的安排有何限制？答：排在后面的工序不能先于前面的工序完成，也就是说，排在后面的工序所在的工作台不能先于前面的工序所在的工作台问：如何表示这种限制？答：工序A, B, C, E, E, F, G, H, I, J可用1，2，3，4，5，6，7，8，9，10来表示工作台按先后顺序可用1，2，3表示，每种安排对应于下表：工序ABCDEFGHIJ工作台11110000000工作台20000111000工作台30000000111工序安排就可用310的矩阵b表示每列和为1，工序I所在工作台号可用b(j, i)j表示四、优化问题解答1. 我的食谱（LP）min 50x1+20x2+30x3+80x4400x1+200x2+150x3+500x4500（保证卡路里需求）3x1+2x26（保证巧克力的需求）2x1+2x2+4x3+4x410（保证糖的需求）2x1+4x2+x3+5x48（保证脂肪的需求） x1, x2, x3, x40sets:mat/1.4/: x; ! x(1)果仁巧克力, x(2)巧克力冰淇淋, x(3)可乐, x(4)奶酪的数量;endsetsmin=50*x(1)+20*x(2)+30*x(3)+80*x(4); !50 20 30 80单价;400*x(1)+200*x(2)+150*x(3)+500*x(4)=500; !保证卡路里需求;3*x(1)+2*x(2)=6; !保证巧克力的需求;2*x(1)+2*x(2)+4*x(3)+4*x(4)=10; !保证糖的需求;2*x(1)+4*x(2)+x(3)+5*x(4)=8; !保证脂肪的需求;巧克力冰淇淋的价格变为原来的两倍： 修改目标函数，将巧克力冰淇淋的价格由原来的20改为40。练习1.1 生产两种糖果（LP）解法1糖(盎司) 坚果(盎司)巧克力(盎司)售价软糖（盎司）20%25硬糖（盎司）10%10%20限量1002030问：选择哪些变量?答：软糖中含：糖x11盎司，坚果x12盎司，巧克力x13盎司。 硬糖中含：糖x21盎司，坚果x22盎司，巧克力x23盎司。问：该问题的目标是什么？答：软糖和硬糖的总售价最高：max 25(x11+x12+x13)+20(x21+x22+x23)问：限制条件？答：糖：x11+x21100坚果：x12+x2220 x120.2(x11+x12+x13)x220.1(x21+x22+x23)巧克力：x13+x2330 x230.1(x21+x22+x23)max 25(x11+x12+x13)+20(x21+x22+x23)x11+x21100x12+x2220x120.2(x11+x12+x13)x220.1(x21+x22+x23)x13+x2330x230.1(x21+x22+x23)xij0, i=1,2, j=1,2,3sets:r/1.2/;c/1.3/;m(r,c): x;endsetsmax=25*(x(1,1)+x(1,2)+x(1,3)+20*(x(2,1)+x(2,2)+x(2,3) ;x(1,1)+x(2,1)=100 ;x(1,2)+x(2,2)=0.2*(x(1,1)+x(1,2)+x(1,3) ;x(2,2)=0.1*(x(2,1)+x(2,2)+x(2,3) ;x(1,3)+x(2,3)=0.1*(x(2,1)+x(2,2)+x(2,3);解法2max 25x1+20x2x1+x2100+20+30