LINGO求解优化问题.doc

首 页

一、Lingo简介
1. 目标函数
一个函数解析式，你希望求它的最大或最小值
max=函数解析式； 或 min=函数解析式；
例 max=3*b+2*c^2;
min=b^(1/3)-c*k；
Lingo的语句以 ; 号结束。
2. 运算
加(+)，减(-)，乘(*)，除(/)，乘方(x^a)
3. 变量
用字母或字母数字的组合表示
例 a，b，cc1，x1。
Lingo的变量缺省值为非负数。
4. 限制条件
一组等式或不等式。
Lingo的>，<与>=，<=等价。
示例程序1
min=3*x1+5*x2; !x1,x2是非负变量;
3*x1+2*x2>=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结束。
示例程序2
sets:
mat/1..4/: x; !mat是组的类型名,x数组名;
endsets

min=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;
endsets
data:
a=400 200 150 500;
enddata
data语句是以data开头，enddata结尾。
示例程序3
sets:
l/1..4/: x, a;
endsets

data:
a=7 2 3 9; !a(1)=7, a(2)=2, a(3)=3, a(4)=9;
enddata

max=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;
endsets

data:
a= 3.3 4.6 2.7 7.1 10.3;
enddata

max=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)的语句);
示例程序5
sets:
r/1..5/: a, b;
endsets
data:
a= 3.3 4.6 2.7 7.1 10.3;
enddata
max=@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;
endsets
data:
need=4000 2000 3000 10000;
enddata

min=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为整数数组，10≤y(i)≤500;

sets语句还可以定义矩阵
m×n矩阵就是m行，n列的数。
x=2 3 4 5 6
7 8 9 2 3
4 7 8 2 1;
x 是一3×5的矩阵，x(1, 2)调用第一行第二列的数3。
例 定义4×5矩阵。
Sets:
r/1..4/;
c/1..5/;
m(r,c): x; !r为行数，c为列数，m为4×5矩阵的类型名，x为矩阵名;
endsets
data语句用于矩阵
data:
x=2 5 6 7
5 6 3 1
8 7 9 10;
enddata
@sum语句用于矩阵
@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)为整数。
示例程序7
sets:
r/1..3/: s;
c/1..4/: pr, pd;
m(r,c): x; !定义一3×4矩阵;
endsets

data:
s = 750 250 400;
pr = 2 3 4 5;
x = 15 10 6 2
1 6 10 14
5 8 13 9;
enddata

max=@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)/16<s(1);
x(2,1)*pd(1)/16+x(2,2)*pd(2)/16+x(2,3)*pd(3)/16+x(2,4)*pd(4)/16<s(2);
x(3,1)*pd(1)/16+x(3,2)*pd(2)/16+x(3,3)*pd(3)/16+x(3,4)*pd(4)/16<s(3);
x(4,1)*pd(1)/16+x(4,2)*pd(2)/16+x(4,3)*pd(3)/16+x(4,4)*pd(4)/16<s(4);
示例程序8（@bin语句）
sets:
l/1..4/;
m(l,l): a,x;
endsets

data:
a=54 54 51 53
51 57 52 52
50 53 54 56
56 54 55 53;
enddata

min=@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;
endsets
data:
a=54 54 51 53
51 57 52 52
50 53 54 56
56 54 55 53;
enddata
min=@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 盎司脂肪。
四种食品的营养成分如下表：

卡路里
巧克力(盎司)
糖(盎司)
脂肪(盎司)
价格
果仁巧克力(块)
400
3
2
2
50
巧克力冰淇淋(杯)
200
2
2
4
20
可乐(瓶)
150
0
4
1
30
奶酪(块)
500
0
4
5
80
最低需求
500
6
10
8

试列出一份最节俭的食谱
［讲评］
问：选择哪些变量?
答：果仁巧克力x1块，巧克力冰淇淋x2杯，可乐x3瓶，奶酪x4块。
问：该问题的目标是什么？
答：食谱中饮食的成本最低：
min 50x1+20x2+30x3+80x4
问：限制条件？
答：满足每天的最低需求。
卡路里： 400x1+200x2+150x3+500x4≥500
巧克力： 3x1+2x2≥6
糖： 2x1+2x2+4x3+4x4≥10
脂肪： 2x1+4x2+x3+5x4≥8
［讨论］
如果巧克力冰淇淋的价格变为原来的两倍，食谱将如何改动？
练习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)

休息
休息

上班人数
17
13
15
19
14
16
11
［讨论］
假设邮局可要求员工加一天班，已知员工正常工作日薪为$50，加班工作日薪为$62。试定一最省钱的人事安排计划.
练习3.1 银行雇员
Gotham City National Bank 每周一至周五的9:00~17:00营业。银行对信贷员的需求量如下表:
时间段
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
信贷员需求量
4
3
4
6
5
6
8
8
银行雇用两种信贷员：全职信贷员（工作时间：9:00~17:00，除去11:00~12:00或12:00~13: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须满足什么条件？
a
b
a
a
a
c
c

答1：2a+b<120 及 2a+2c<90
答2：也可以是2a+b<90 及 2a+2c<120。
问：试试看哪种情况体积大？
［讨论］
在体积最大的前提下，哪种情况铁皮利用率大？
练习5.1 选点
如图，P, Q到河岸的距离分别为10, 8，试选一点R，使得R到河岸的距离及RP, RQ的和最小。
P
R
Q
河岸
←6→

6. 生产安排
某工厂在计划内拟生产I, II两种产品，已知生产单位产品所需的设备台时及A, B两种原材料的消耗如下表：

I
II
总量
设备(台时)
3
4
36
原材料A(kg)
0
2
12
原材料B(kg)
1
0
8
该工厂生产一件产品I可获利3百元，生产一件产品II可获利5百元。
应如何安排生产？
若该工厂决定不生产，而将上述资源出租，问总租金应为多少？
［讲评］
问：问题（2）是相对于问题（1）的影子价格问题，运行问题（1）的lingo求解后，在solution report 中的 dual cost 栏中显示。我们不妨假设，原材料A的单价为a百元/公斤，原材料B的单价为b百元/公斤，设备费为c百元/台时。因为3台时设备和1公斤原料B可生产一件产品I，等价于可获利3百元，所以，3*c+b>3，同理，4*c+2*a>5。但是作为承租方希望总租金最少：min=36*c+12*a+8*b。
［讨论］
若增加1公斤原材料Ａ，总获利增加多少？若市场上有x公斤的原材料出售，你愿以何种价格收购？
7. 组建混合泳接力队
Doc Councilman 正组建一支400米混合泳（自由泳，仰泳，蝶泳，蛙泳）接力队，有四位泳将，GARY HALL，MARK SPITZ，JIM MONTGOMERY，CHET JASTREMSKI，他们四项游泳项目成绩如下表， Doc Councilman应如何安排四位泳将的接力项目？
单位:秒
自由泳
蛙泳
蝶泳
仰泳
GARY HALL
54
54
51
53
MARK SPITZ
51
57
52
52
JIM MONTGOMERY
50
53
54
56
CHET JASTREMSKI
56
54
55
53
［讲评］
问：问题的目标是什么？
答：接力赛成绩最好
问：限制条件是什么？
答：每人只能参加一项，每项都须有人参加。
问：如何表示这种限制条件？
答：设置一个4×4的选择矩阵（每个元素只能是1或0），矩阵每行每列的和均为1
问：如何表示接力赛成绩？
答：设的矩阵与成绩矩阵点乘（对应元素相乘）后对所有元素求和
8. 工作指派
四项工作指派给五个员工（每项工作只能由一人单独完成），每人完成各项工作耗时如下表，如何指派使得完成四项工作总耗时最少？

工作1
工作2
工作3
工作4
员工1
22
18
30
18
员工2
18
-
27
22
员工3
26
20
28
28
员工4
16
22
-
14
员工5
21
-
25
28
（注: 横线表该员工不宜完成该项工作）
［讲评］
问：碰到横线怎么办？
答：设成很大的数
问：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.37
p(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)变为
( 1－g(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)变为
(1－g(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
公司1
4000
5000
-
-
公司2
-
4000
-
4000
公司3
3000
-
2000
-
公司4
-
-
4000
5000
(a) 假设每位竟标者至多可分配到一条线路，问委员会将如何招标？
(b) 假设每位竟标者至多可分配到两条线路，问委员会将如何招标？
11. 运输和生产方案
福特在L.A. 和 Detroit生产汽车，在Atlanta有一仓库，供应点为Houston 和 Tampa；城市间每辆汽车运输费用见下表。 L.A.的生产能力为1100辆， Detroit的生产能力为2900辆。Houston汽车需求量为2400辆，Tampa汽车需求量为1500辆。

L.A
DETROIT
ATLANTA
HOUSTON
TAMPA
L.A.（工厂）
0
140
100
90
225
DETROIT（工厂）
145
0
111
110
119
ATLANTA（仓库）
105
115
0
113
78
HOUSTON（供应点）
89
109
121
0
-
TAMPA（供应点）
210
117
82
-
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. 化肥调拨方案
设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价（万元/万吨）如下表所示。试求出总的运费最省的化肥调拨方案。
需求地区
化肥厂
I
II
III
IV
产量(万吨)
A
16
13
22
17
50
B
14
13
19
15
60
C
19
20
23
禁止
50
最低需求(万吨)
30
70
0
10

最高需求(万吨)
50
70
30
不限

［讲评］
问：地区IV最高需求为不限，是不是无限大的意思？
答1：是的
答2：不是，地区IV最多可得到（50+50+60）（总产量）-（70+30）（其它地区最小需求）＝60
13. 物资运输
某航运公司承担6个港口城市A, B, C, D, E, F的四条固定航线的物资运输任务。已知各条航线的起点，终点城市及每天航班数见下表：
航线
起点城市
终点城市
每天航班数
1
E
D
3
2
B
C
2
3
A
F
1
4
D
B
1
假定各条航线使用相同型号的船只，由各城市间的航程天数见下表：
到
从
A
B
C
D
E
F
A
0
1
2
14
7
7
B
1
0
3
13
8
8
C
2
3
0
15
5
5
D
14
13
15
0
17
20
E
7
8
5
17
0
3
F
7
8
5
20
3
0
又知每条船只每次装卸货物的时间各需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。下表列出各航线的日收益与航班次数的关系。

航班次数
1
2
3
4
5
6
NEW YORK
$80
$150
$210
$250
$270
$280
LOS ANGELES
$100
$195
$275
$325
$300
$250
MIAMI
$90
$180
$265
$310
$350
$320
试帮该公司确定航线和相应的航班次数。
［讲评］
问：如果，NEW YORK飞3个航班，LOS ANGELES飞2个航班，MIAMI只能飞1个航班了，如何用数据表示这种安排（有利于收益的计算，及限制条件的表示）？
答：上述安排对应于下表：

航班次数
1
2
3
4
5
6
NEW YORK
0
0
1
0
0
0
LOS ANGELES
0
1
0
0
0
0
MIAMI
1
0
0
0
0
0
1表示选择，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。
试问如何安排各个时期的生产与库存，才能在满足市场需要的条件下，使总成本最小。
时期
1
2
3
4
需求(单位)
2
3
2
4
［讲评］
问：如何处理生产固定成本？
答：设计一个生产判断变量数组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的最大网速。
1
2
3
4
5
6
2
3
1
3
2
7
7
6

［讲评］
问：节点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 )
带宽
10
8
2
7
5
10
4
单位成本
4
1
6
1
2
3
2
19. 工序安排
某项研制新产品的各个工序，工序所需时间及相应费用，工序极限时间及相应费用，以及工序之间的相互关系如表：
工序代号
正常情况
采取措施后
缩短一天工期代价
紧后工序
正常时间(天)
直接费用
极限时间(天)
直接费用
a
60
10000
60
10000
--
b,c,d,e
b
45
4500
30
6300
120
l
c
10
2800
5
4300
300
f
d
20
7000
10
11000
400
g,h
e
40
10000
35
12500
500
h
f
18
3600
10
5440
230
l
g
30
9000
20
12500
350
k
h
15
3750
10
5750
400
l
k
25
6250
15
9150
290
l
l
35
12000
35
12000
--
l
研制过程中每天间接费用为400元。
(1) 试作出流程图，并求出正常情况最早完工时间
［讲评］
问：我们通常用
i
j
x

来表示工序x。
1
2
3
4
5
8
7
6
c
e
d
b
f
0
h
g
k
l
a

工序( 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. 邮递员投递路线
如下图所示，节点间的线段表示某小区的弄堂，线段旁的数字表示弄堂的长度。邮局在其中某个节点，请设计邮递员投递路线。
5
5
9
4
3
4
4
3
4
6
4
2
1
2
3
4
5
6
7
8
9

［讲评］
问：问题的目标是什么？
答：邮递员投递线路最短。
问：邮递员投递线路的长度是否等于所有弄堂的长度和？
答：不是，每条弄堂仅过一遍，未必可行？
问：为什么？
答1：左图中的弄堂，无论邮局在哪个节点，邮递员都得跑两趟。
右图中的每条弄堂，无论邮局在哪个节点，邮递员都只须跑一次。
1
1
2
3
2

问：有没有规律？
答1：问题跟邮局的位置无关，因为邮递员的投递路线是封闭的。
答2：每个节点进出的次数应该相等。
［讨论］
如果邮递员数目是2个或2个以上又将如何?
练习20.1 邮递员投递路线
如下图所示，节点间的线段表示某区的街道，街道都是单行道，线段旁的数字表示街道的长度。邮局在其中某个节点，请设计邮递员投递路线。
2
3
1
4
3
2
5
2
1
4
2
1
2
3
4
5
6
7

问：该问题和问模型20有哪些异同？
答：大同小异，只不过街道是单向的。
21. 航班空姐配备
Braneast 航空公司须为每天飞行于New York 和 Chicago的航班配备空姐。每位空姐住在New York或Chicago。每天每位空姐须飞一班New York-Chicago和一班Chicago-New York，空姐飞两航班的间隙（滞留时间）至少为1小时，Braneast 航空公司想减少空姐们的滞留时间，应如何配备？Braneast 航空公司每天的航班见下表：
航班:
1
2
3
4
5
6
7
飞-CHICAGO:
6
9
12
15
17
19
20
达-NEWYORK:
10
13
16
19
21
23
24
航班:
1
2
3
4
5
6
7
飞-NEWYORK:
7
8
10
12
14
16
18
达-CHICAGO:
9
10
12
14
16