文档库 最新最全的文档下载
当前位置:文档库 › 运筹学习题集

运筹学习题集

习题一

1.1 用图解法求解下列线性规划问题,并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。
(1) min z =6x1+4x2 (2) max z =4x1+8x2
st. 2x1+ x2≥1 st. 2x1+2x2≤10
3x1+ 4x2≥1.5 -x1+ x2≥8
x1, x2≥0 x1, x2≥0
(3) max z = x1+ x2 (4) max z =3x1-2x2
st. 8x1+6x2≥24 st. x1+x2≤1
4x1+6x2≥-12 2x1+2x2≥4
2x2≥4 x1, x2≥0
x1, x2≥0
(5) max z =3x1+9x2 (6) max z =3x1+4x2
st. x1+3x2≤22 st. -x1+2x2≤8
-x1+ x2≤4 x1+2x2≤12
x2≤6 2x1+ x2≤16
2x1-5x2≤0 x1, x2≥0
x1, x2≥0
1.2. 在下列线性规划问题中,找出所有基本解,指出哪些是基本可行解并分别代入目标函数,比较找出最优解。
(1) max z =3x1+5x2 (2) min z =4x1+12x2+18x3
st. x1 + x3 =4 st. x1 +3x3- x4 =3
2x2 + x4 =12 2x2+2x3 - x5=5
3x1+ 2x2 + x5 =18 xj ≥0 (j=1,…,5)
xj ≥0 (j=1,…,5)
1.3. 分别用图解法和单纯形法求解下列线性规划问题,并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。
(1) max z =10x1+5x2
st. 3x1+4x2≤9
5x1+2x2≤8
x1, x2≥0
(2) max z =100x1+200x2
st. x1+ x2≤500
x1 ≤200
2x1+6x2≤1200
x1, x2≥0
1.4. 分别用大M法和两阶段法求解下列线性规划问题,并指出问题的解属于哪一类:
(1) max z =4x1+5x2+ x3 (2) max z =2x1+ x2+ x3
st. 3x1+2x2+ x3≥18 st. 4x1+2x2+2x3≥4
2x1+ x2 ≤4 2x1+4x2 ≤20
x1+ x2- x3=5 4x1+8x2+2x3≤16
xj ≥0 (j=1,2,3) xj ≥0 (j=1,2,3)
(3) max z = x1+ x2 (4) max z =x1+2x2+3x3-x4
st. 8x1+6x2≥24 st. x1+2x2+3x3=15
4x1+6x2≥-12 2x1+ x2+5x3=20
2x2≥4 x1+2x2+ x3+ x4=10
x1, x2≥0 xj ≥0 (j=1,…,4)
(5) max z =4x1+6x2 (6) max z =5x1+3x2+6x3
st. 2x1+4x2 ≤180 st. x1+2x2+ x3≤18
3x1+2x2 ≤150 2x1+ x2+3x3≤16
x1+ x2=57 x1+ x2+ x3=10
x2≥22 x1, x2≥0,x3无约束
x1, x2≥0

1.5 线性规划问题max z=CX,AX=b,X≥0,如X*是该问题的最优解,又λ>0为某一常数,分别讨论下列情况时最优解的变化:
(1) 目标函数变为max z=λCX;
(2) 目标函数变为max

z=(C+λ)X;
(3) 目标函数变为max z= X,约束条件变为AX=λb。
1.6 下表中给出某求极大化问题的单纯形表,问表中a1, a2, c1, c2, d为何值时以及表中变量属于哪一种类型时有:
(1) 表中解为唯一最优解;
(2) 表中解为无穷多最优解之一;
(3) 表中解为退化的可行解;
(4) 下一步迭代将以x1替换基变量x5 ;
(5) 该线性规划问题具有无界解;
(6) 该线性规划问题无可行解。
x1 x2 x3 x4 x5
x3 d 4 a1 1 0 0
x4 2 -1 -5 0 1 0
x5 3 a2 -3 0 0 1
cj -zj c1 c2 0 0 0

1.7 战斗机是一种重要的作战工具,但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外,需抽一部分用于培训驾驶员。已知每年生产的战斗机数量为aj(j=1,…,n),又每架战斗机每年能培训出k名驾驶员,问应如何分配每年生产出来的战斗机,使在n年内生产出来的战斗机为空防作出最大贡献?

1.8. 某石油管道公司希望知道,在下图所示的管道网络中可以流过的最大流量是多少及怎样输送,弧上数字是容量限制。请建立此问题的线性规划模型,不必求解。
2 5 4
10
3 11
1 4 3 6
5
6 8 7
3 5
1.9. 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下:
班 次 时 间 所需人数
1 6:00-10:00 60
2 10:00-14:00 70
3 14:00-18:00 60
4 18:00-22:00 50
5 22:00-2:00 20
6 2:00-6:00 30
设司机和乘务人员分别在各时间区段一开始时上班,并连续工作八小时,问该公交线路至少配备多少名司机和乘务人员。列出此问题的线性规划模型。

1.10 某班有男生30人,女生20人,周日去植树。根据经验,一天男生平均每人挖坑20个,或栽树30棵,或给25棵树浇水;女生平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多?请建立此问题的线性规划模型,不必求解。

1.11.某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加工费及售价如下表所示。
问该厂每月应生产这三种牌号糖果各多少千克,使该厂获利最大?试建立此问题的线性规划的数学模型。
甲 乙 丙 原料成本(元/千克) 每月限量(千克)
A

≥60% ≥15% 2.00 2000
B 1.50 2500
C ≤20% ≤60% ≤50% 1.00 1200
加工费(元/千克) 0.50 0.40 0.30
售 价 3.40 2.85 2.25

1.12. 某商店制定7-12月进货售货计划,已知商店仓库容量不得超过500件,6月底已存货200件,以后每月初进货一次,假设各月份此商品买进售出单价如下表所示,问各月进货售货各多少,才能使总收入最多?请建立此问题的线性规划模型,不必求解。
月 份 7 8 9 10 11 12
买进单价 28 24 25 27 23 23
售出单价 29 24 26 28 22 25

1.13 .某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日,春夏季4000人日,如劳动力本身用不了时可外出干活,春夏季收入为2.1元/人日,秋冬季收入为1.8元/人日。该农场种植三种作物:大豆、玉米、小麦,并饲养奶牛和鸡。种作物时不需要专门投资,而饲养动物时每头奶牛投资400元,每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草,并占用人工秋冬季为100人日,春夏季为50人日,年净收入400元/每头奶牛。养鸡时不占土地,需人工为每只鸡秋冬季需0.6人日,春夏季为0.3人日,年净收人为2元/每只鸡。农场现有鸡舍允许最多养3000只鸡,牛栏允许最多养32头奶牛。三种作物每年需要的人工及收人情况如下表所示。


大豆 玉米 麦子
秋冬季需人日数 20 35 10
春夏季需人日数 50 75 40
年净收入(元/公顷) 175 300 120
试决定该农场的经营方案,使年净收人为最大。(建立线性规划模型,不需求解)

习题二

2.1 写出下列线性规划问题的对偶问题
(1) max z =10x1+ x2+2x3 (2) max z =2x1+ x2+3x3+ x4
st. x1+ x2+2 x3≤10 st. x1+ x2+ x3 + x4 ≤5
4x1+ x2+ x3≤20 2x1- x2+3x3 =-4
xj ≥0 (j=1,2,3) x1 - x3+ x4≥1
x1,x3≥0,x2,x4无约束
(3) min z =3x1+2 x2-3x3+4x4 (4) min z =-5 x1-6x2-7x3
st. x1-2x2+3x3+4x4≤3 st. -x1+5x2-3x3 ≥15
x2+3x3+4x4≥-5 -5x1-6x2+10x3 ≤20
2x1-3x2-7x3 -4x4=2= x1- x2- x3=-5
x1≥0,x4≤0,x2,,x3 无约束 x1≤0, x2≥0,x3 无约束

2.2 已知线性规划问题max z=CX,AX=b,X≥0。分别说明发生下列情况时,其对偶问题的解的变化:
(1)问题的第k个约束条件乘上常数λ(λ≠0);
(2)将第k个约束条件乘上常数λ(λ≠0)后加到第r个约束条件上;
(3)目标函数改变为max z=λCX(λ≠0);
(4)模型中全部x1用3 代换。
2.3

已知线性规划问题 min z=8x1+6x2+3x3+6x4
st. x1+2x2 + x4≥3
3x1+ x2+ x3+ x4≥6
x3 + x4=2
x1 + x3 ≥2
xj≥0(j=1,2,3,4)
(1) 写出其对偶问题;
(2) 已知原问题最优解为x*=(1,1,2,0),试根据对偶理论,直接求出对偶问题的最优解。

2.4 已知线性规划问题 min z=2x1+x2+5x3+6x4 对偶变量
st. 2x1 +x3+ x4≤8 y1
2x1+2x2+x3+2x4≤12 y2
xj≥0(j=1,2,3,4)
其对偶问题的最优解y1*=4;y2*=1,试根据对偶问题的性质,求出原问题的最优解。

2.5 考虑线性规划问题 max z=2x1+4x2+3x3
st. 3x1+4 x2+2x3≤60
2x1+ x2+2x3≤40
x1+3x2+2x3≤80
xj≥0 (j=1,2,3)
(1)写出其对偶问题
(2)用单纯形法求解原问题,列出每步迭代计算得到的原问题的解与互补的对偶问题的解;
(3)用对偶单纯形法求解其对偶问题,并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解;
(4)比较(2)和(3)计算结果。

2.6 已知线性规划问题 max z=10x1+5x2
st. 3x1+4x2≤9
5x1+2x2≤8
xj≥0(j=1,2)
用单纯形法求得最终表如下表所示:
x1 x2 x3 x4 b
x2 0 1


x1 1 0 —

1
?j=cj-Zj 0 0 —


试用灵敏度分析的方法分别判断:
(1)目标函数系数c1或c2分别在什么范围内变动,上述最优解不变;
(2)约束条件右端项b1,b2,当一个保持不变时,另一个在什么范围内变化,上述最优基保持不变;
(3)问题的目标函数变为max z =12x1+4x2时上述最优解的变化;
(4)约束条件右端项由 变为 时上述最优解的变化。
2.7 线性规划问题如下: max z=—5x1+5x2+13x3
st. —x1+x2+3x3≤20 ①
12x1+4x2+10x3≤90 ②
xj≥0 (j=1,2,3)
先用单纯形法求解,然后分析下列各种条件下,最优解分别有什么变化?
(1) 约束条件①的右端常数由20变为30;
(2) 约束条件②的右端常数由90变为70;
(3) 目标函数中x3的系数由13变为8;
(4) x1的系数列向量由(—1,12)T变为(0,5)T;
(5) 增加一个约束条件③:2x1+3x2+5x3≤50;
(6) 将原约束条件②改变为:10x1+5x2+10x3≤100。

2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下:
cj 基变量 50 40 10 60 S
x1 x2 x3 x4
a c 0 1
1 6
b d 1 0
2 4
?j=cj-Zj 0 0 e f g
(1)给出a,b,c,d,e,f,g的值或表达式;
(2)指出原问题是求目标函数的最大值还是最小值;
(3)用a+?a,b+?b分别代替a和b,仍然保持上表是最优单纯形表,求?a,?b满足的范围。

2.9 某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人,每月白坯纸供应量为30000千

克。已知工人的劳动生产率为:每人每月可生产原稿纸30捆,或日记本30打,或练习本30箱。已知原材料消耗为:每捆原稿纸用白坯纸 千克,每打日记本用白坯纸 千克,每箱练习本用白坯纸 千克。又知每生产一捆原稿纸可获利2元,生产一打日记本获利3元,生产一箱练习本获利1元。试确定:
(1)现有生产条件下获利最大的方案;
(2)如白坯纸的供应数量不变,当工人数不足时可招收临时工,临时工工资支出为每人每月40元,则该厂要不要招收临时工?如要的话,招多少临时工最合适?

2.10 某厂生产甲、乙两种产品,需要A、B两种原料,生产消耗等参数如下表(表中的消耗系数为千克/件)。
产品原料 甲 乙 可用量(千克) 原料成本(元/千克)
A 2 4 160 1.0
B 3 2 180 2.0
销售价(元) 13 16
(1)请构造数学模型使该厂利润最大,并求解。
(2)原料A、B的影子价格各为多少。
(3)现有新产品丙,每件消耗3千克原料A和4千克原料B,问该产品的销售价格至少为多少时才值得投产。
(4)工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产?在保持原问题最优基的不变的情况下,最多应购入多少?可增加多少利润?





习题三

3.1 求解下表所示的运输问题,分别用最小元素法、西北角法和伏格尔法给出初始基可行解:
B1 B2 B3 B4 供应量
A1 (10) (6) (7) (12) 4
A2 (16) (10) (5) (9) 9
A3 (5) (4) (10) (10) 5
需要量 5 3 4 6 18

3.2由产地A1,A2发向销地B1,B2的单位费用如下表,产地允许存贮,销地允许缺货,存贮和缺货的单位运费也列入表中。求最优调运方案,使总费用最省。
B1 B2 供应量 存贮费/件
A1 8 5 400 3
A2 6 9 300 4
需要量 200 350
缺货费/件 2 5

3.3 对如下表的运输问题:
A B 供应量
X 100(6) (4) 100
Y 30(5) 50(8) 80
Z (2) 60(7) 60
需要量 130 110 240
(1)若要总运费最少,该方案是否为最优方案?
(2)若产地Z的供应量改为100,求最优方案。

3.4 某利润最大的运输问题,其单位利润如下表所示:
B1 B2 B3 B4 供应量
A1 (6) (7) (5) (8) 8
A2 (4) (5) (10) (8) 9
A3 (2) (9) (7) (3) 7
需要量 8 6 5 5 24
(1)求最优运输方案,该最优方案有何特征?
(2)当A1的供应量和B3的需求量各增加2时,结果又怎样?

3.5 某玩具公司分别生产三种新型玩具,每月可供量分别为1000、2000、2000件,它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500件,由于经营方面原因,各商店销售不同玩具的盈利额不同,见下表。又知丙百货商店要求至少供应C玩具1000件

,而拒绝进A玩具。求满足上述条件下使总盈利额最大的供销分配方案。




甲 乙 丙 可供量
A 5 4 - 1000
B 16 8 9 2000
C 12 10 11 2000

3.6 目前,城市大学能存贮200个文件在硬盘上,100个文件在计算机存贮器上,300个文件在磁带上。用户想存贮300个字处理文件,100个源程序文件,100个数据文件。每月,一个典型的字处理文件被访问8次,一个典型的源程序文件被访问4次,一个典型的数据文件被访问2次。当某文件被访问时,重新找到该文件所需的时间取决于文件类型和存贮介质,如下表。
时 间(分钟) 处理文件 源程序文件 数据文件
硬盘 5 4 4
存贮器 2 1 1
磁带 10 8 6
如果目标是极小化每月用户访问所需文件所花的时间,请构造一个运输问题的模型来决定文件应该怎么存放并求解。

3.7 已知下列五名运动员各种姿势的游泳成绩(各为50米)如表5-2:试用运输问题的方法来决定如何从中选拔一个参加200混合泳的接力队,使预期比赛成绩为最好。
赵 钱 张 王 周
仰 泳 37.7 32.9 33.8 37.0 35.4
蛙 泳 43.4 33.1 42.2 34.7 41.8
蝶 泳 33.3 28.5 38.9 30.4 33.6
自由泳 29.2 26.4 29.6 28.5 31.1

3.8 求总运费最小的运输问题,其中某一步的运输图如下表。
B1 B2 B3 供应量
A1 3(3) (5) (7) 3
A2 2(4) 4(2) (4) 6
A3 (5) 1(6) 5(3) d
需要量 a b c e

(1)写出a,b,c,d,e的值,并求出最优运输方案;
(2)A3到B1的单位运费满足什么条件时,表中运输方案为最优方案。

3.9 某一实际的运输问题可以叙述如下:有n个地区需要某种物资,需要量分别为bj(j=1,…,n)。这些物资均由某公司分设在m个地区的工厂供应,各工厂的产量分别为ai(i=1,…,m),已知从i地区的工厂至第j个需求地区的单位物资的运价为cij,又 = ,试阐述其对偶问题并解释对偶变量的经济意义。

3.10. 为确保飞行安全,飞机上的发动机每半年必须强迫更换进行大修。某维修厂估计某种型号战斗机从下一个半年算起的今后三年内每半年发动机的更换需要量分别为:100,70,80,120,150,140。更换发动机时可以换上新的,也可以用经过大修的旧的发动机。已知每台新发动机的购置费为10万元,而旧发动机的维修有两种方式:快修,每台2万元,半年交货(即本期拆下来送修的下批即可用上);慢修,每台1万元,但需一年交货(即本期拆下来送修的需下下批才能用上)。设该厂新接受该项发动机更换维修任务,又知这种型号战斗机三年后将退役,退

役后这种发动机将报废。问在今后三年的每半年内,该厂为满足维修需要各新购、送去快修和慢修的发动机数各是多少,使总的维修费用为最省?(将此问题归结为运输问题,只列出产销平衡表与单位运价表,不求数值解。)

3.11 甲、乙两个煤矿分别生产煤500万吨,供应A、B、C三个电厂发电需要,各电厂用量分别为300、300、400万吨。已知煤矿之间、煤矿与电厂之间以及各电厂之间相互距离(单位:公里)如下列三个表所示。又煤可以直接运达,也可经转运抵达,试确定从煤矿到各电厂间煤的最优调运方案(最小总吨公里数)。

从 到 甲 乙 从 到 A B C 从 到 A B C
甲 0 120 甲 150 120 80 A 0 70 100
乙 100 0 乙 60 160 40 B 50 0 120
C 100 150 0


习题四

4.1 分别用图解法和单纯形法求解下述目标规划问题
(1) min z =p1( + )+p2
st. -x1+ x2+ d-1- d+1=1
-0.5x1+ x2+ d-2-d+2=2
3x1+3x2+ d-3- d+3=50
x1,x2≥0;d-i,d+i≥0(i =1,2,3)
(2) min z =p1(2 +3 )+p2 +p3
st. x1+ x2+d-1-d+1 =10
x1 +d-2-d+2 =4
5x1+3x2+d-3-d+3 =56
x1+ x2+d-4-d+4 =12
x1,x2≥0;d-i,d+i ≥0(i =1,…,4)
4.2 考虑下述目标规划问题
min z =p1(d+1+d+2)+2p2d-4+p2d-3+p3d-1
st. x1 +d-1-d+1=20
x2+d-2-d+2=35
-5x1+3x2+d-3-d+3=220
x1-x2+d-4-d+4=60
x1,x2≥0;d-i,d+i ≥0(i =1,…,4)
(1)求满意解;
(2)当第二个约束右端项由35改为75时,求解的变化;
(3)若增加一个新的目标约束:-4x1+x2+d-5-d+5=8,该目标要求尽量达到目标值,并列为第一优先级考虑,求解的变化;
(4)若增加一个新的变量x3,其系数列向量为(0,1,1,-1)T,则满意解如何变化?

4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律,该台每天允许广播12小时,其中商业节目用以赢利,每小时可收入250美元,新闻节目每小时需支出40美元,音乐节目每播一小时费用为17.50美元。法律规定,正常情况下商业节目只能占广播时间的20%,每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排?优先级如下:
P1:满足法律规定要求;
P2:每天的纯收入最大。
试建立该问题的目标规划模型。

4.4 某企业生产两种产品,产品Ⅰ售出后每件可获利10元,产品Ⅱ售出后每件可获利8元。生产每件产品Ⅰ需3小时的装配时间,每件产品Ⅱ需2小时装配时间。可用的装配时间共计为每周120小时,但允许加班。在加班时间内

生产两种产品时,每件的获利分别降低1元。加班时间限定每周不超过40小时,企业希望总获利最大。试凭自己的经验确定优先结构,并建立该问题的目标规划模型。

4.5 某厂生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工厂每周最大加工能力的数据如下:
A B 每周最大加工能力
I 4 6 150
II 3 2 70
利润(元/台) 300 450
工厂经营目标的期望值及优先级如下:
P1:每周总利润不得低于10000元;
P2:因合同要求,A型机每周至少生产10台:B型机每周至少生产15台;
P3:由于条件限制且希望充分利用工厂的生产能力,工序I的每周生产时间必须恰好为150小时,工序II的每周生产时间可适当超过其最大加工能力(允许加班)。试建立此问题的目标规划模型



习题五

5.1 试将下述非线性的0-1规划问题转换为线性的0-1规划问题
max z =x12+x2x3-x33
st. -2x1+3x2+x3 ≤3
xj=0或1(j=1,2,3)

5.2 某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使总的钻探费用为最小。若10个井位的代号为s1,s2,…,s10,相应的钻探费用为c1,c2,…,c10,并且井位选择上要满足下列限制条件:
(1) 或选择s1和s7,或选择钻探s8;
(2) 选择了s3或s4就不能选s5,或反过来也一样;
(3) 在s5,s6,s7,s8中最多只能选两个。
试建立此问题的整数规划模型。

5.3 用分枝定界法求解下列整数规划问题
(1) max z =x1+x2
st. x1+ x2 ≤
-2x1 +x2 ≤
x1,x2≥0且为整数
(2) max z =2x1+3x2
st. 5x1+7x2≤35
4x1+9x2≤36
x1,x2≥0且为整数

5.4 用割平面法求解下列整数规划问题
(1) max z =7x1+9x2
st. -x1+3 x2 ≤6
7x1 + x2 ≤35
x1,x2≥0且为整数
(2) min z =4x1+5x2
st. 3x1+2x2≥7
x1+4x2≥5
3x1+ x2≥2
x1, x2≥0且为整数

5.5 用隐枚举法求解0-1整数规划问题
max z = 3x1+2x2-5x3-2x4+3x5
st. x1+ x2 + x3+2x4+ x5≤ 4
7x1 +3x3-4x4+3x5≤ 8
11x1-6x2 +3x4-3x5≥ 3
xj =0或1(j=1,…,5)

5.6 请用解0-1整数规划的隐枚举法求解下面的两维0-1背包问题:
max f = 2x1+2x2+3x3
s.t. x1+2x2+2x3≤4
2x1+x2+3x3≤5
xj=0或1,j=1,2,3




5.7 用匈牙利法求解如下效率矩阵的指派问题
7 9 10 12
13 12 16 17
15 16 14 15
11 12 15 16

5.8 分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数,故规定其中有一个人可兼完成两项任务,其余三人每人完成一项。试确定总花费时间为最少的指派方案。
人 任务 A B C D E

25 29 31 42 37
乙 39 38 26 20 33
丙 34 27 28 40 32
丁 24 42 36 23 45

5.9 已知下列五人各种姿势的游泳成绩(各为50米),试问如何进行指派,从中选拔一个参加200米混合泳的接力队,使预期比赛成绩为最好。
赵 钱 张 王 周
仰 泳 37.7 32.9 33.8 37.0 35.4
蛙 泳 43.4 33.1 42.2 34.7 41.8
蝶 泳 33.3 28.5 38.9 30.4 33.6
自由泳 29.2 26.4 29.6 28.5 31.1
5.10. 运筹学中著名的旅行商贩(货郎担)问题可以叙述如下:某旅行商贩从某一城市出发,到其它几个城市去推销商品,规定每个城市均须到达而且只到达一次,然后回到原出发城市。已知城市i和j之间的距离为dij,问该商贩应选择一条什么样的路线顺序旅行,使总的旅程为最短。试对此问题建立整数规划模型。

5.11. 有三个不同的产品要在三台机床上加工,每个产品必须首先在机床1上加工,然后依次在机床2,3上加工。在每台机床上加工三个产品的顺序应保持一样,假定用tij表示在第j机床上加工第i个产品的时间,问应如何安排,使三个产品总的加工周期为最短。试建立此问题的整数规划模型。













习题参考答案
第一章 线性规划及单纯形法
1.1
(1)解:
第一,求可行解集合。令两个约束条件为等式,得到两条直线,在第一象限划出满足两个不等式的区域,其交集就是可行集或称为可行域,如图1-1所示,交集为(1/2, 0)。
第二,绘制目标函数图形。将目标函数的系数组成一个坐标点(6,4),过原点O作一条矢量指向点(6,4),矢量的长度不限,矢量的斜率保持4比6,再作一条与矢量垂直的直线,这条直线就是目标函数图形,目标函数图形的位置任意,如果通过原点则目标函数值Z=0,如图1-2所示。
第三,求最优解。图1-2的矢量方向是目标函数增加的方向或称梯度方向,在求最小值时将目标函数图形沿梯度方向的反方向平行移动,(在求最大值时将目标函数图形沿梯度方向平行移动)直到可行域的边界,停止移动,其交点对应的坐标就是最优解,如图1-3所示。最优解x=(1/2, 0),目标函数的最小值Z=3。



(2)无可行解;[求解方法与(1)类似]
(3)无界解;
(4)无可行解;
(5)无穷多最优解 z*=66
(6)唯一最优解 z*=92/3,x1=20/3,x2=3/8
1.2
(1)解:由题目可知,其系数矩阵为

因 线性独立,故有
令非基变量 得 →
得到一个基可行解 , 。
线性独立,故有
令非基变量 得 →
得到一个基本解,但非可行解 , 。
同理可以求出
,得基本可行解 。
,得基本可行解 。
,得基本可行解 。
,得基本可行解 。
,得基本

非可行解 。
,得基本非可行解 。
(1)、(2)答案如下表所示,其中打三角符号的是基本可行解,打星号的为最优解:
x1 x2 x3 x4 x5 z x1 x2 x3 x4 x5
△ 0 0 4 12 18 0 0 0 0 -3 -5
△ 4 0 0 12 6 12 3 0 0 0 -5
6 0 -2 12 0 18 0 0 1 0 -3
△ 4 3 0 6 0 27 -9/2 0 5/2 0 0
△ 0 6 4 0 6 30 0 5/2 0 -3 0
*△ 2 6 2 0 0 36 0 3/2 1 0 0 △*
4 6 0 0 -6 42 3 5/2 0 0 0 △
0 9 4 -6 0 45 0 0 5/2 9/2 0 △
1.3
(1)解:单纯形法
首先,将问题化为标准型。加松弛变量x3,x4,得

其次,列出初始单纯形表,计算最优值。
CB XB 10 5 0 0 b
X1 X2 X3 X4
0 X3 3 4 1 0 9
0 X4 5 2 0 1 8
σj 10 5 0 0
0 X3 0 14/5 1 -3/5 21/5
10 X1 1 2/5 0 1/5 8/5
σj 0 1 0 -2
5 X2 1 1 5/14 -3/14 3/2
10 X1 0 0 -1/7 2/7 1
σj 0 0 -5/14 -25/14
(表一)
由单纯形表一得最优解为
图解法:









(2)略
1.4
(1) 解:大M法
首先将数学模型化为标准形式

式中x4,x5为松弛变量,x5可作为一个基变量,第一、三约束分别加入人工变量x6 x7,目标函数中加入-Mx6-Mx7一项,得到大M单纯形法数学模型

由单纯形表计算:


CB XB 4 5 1 0 0 -M -M b
X1 X2 X3 X4 X5 X6 X7
-M X6 3 2 1 -1 0 1 0 18
0 X5 2 1 0 0 1 0 0 4
-M X7 1 1 -1 0 0 0 1 5
σj 4+4M 5+3M 1 -M 0 0 0
-M X6 -1 0 1 -1 -2 1 0 10
5 X2 2 1 0 0 1 0 0 4
-M X7 -1 0 -1 0 0 0 1 1
σj 4-2M 0 1 -M -2M 0 0
1 X3 -1 0 1 -1 -2 0 10
0 X2 2 1 0 0 1 0 4
-M X7 -2 0 0 -1 -2 1 11
σj 5-2M 0 0 1-M 2-2M 0
表1.4-1.1
在迭代过程中,人工变量一旦出基后不会在进基,所以当人工变量X6出基后,对应第六列的系数可以不再计算,以减少计算量。
当用大M单纯形法计算得到最优解并且存在人工变量大于零时,则表明原线性规划无可行解。
两阶段单纯形法
首先,化标准形同大M法,第一、三约束分别加入人工变量x6 x7后,构造第一阶段问题

用单纯形法求解,得到第一阶段问题的计算表1.4-1.2,
CB XB 0 0 0 0 0 1 1 b
X1 X2 X3 X4 X5 X6 X7
1 X6 3 2 1 -1 0 1 0 18
0 X5 2 1 0 0 1 0 0 4
1 X7 1 1 -1 0 0 0 1 5
σj -4 -3 0 1 0 0 0
1 X6 0 1/2 1 -1 -3/2 1 0 12
0 X1 1 1/2 0 0 1/2 0 0 2
1 X7 0 1/2 -1 0 -1/2 0 1 3
σj 0 -1 0 1 2 0 0
1 X6 -1 0 1 -1 -2 1 0 10
0 X2 2 1 0 0 2 0 0 4
1 X7 -1 0 -1 0 -1 0 1 1
σj 2 0 0 1 3 0 0
表1.4-1.2
在第一阶段的最优解中人工变量不为零,则原问题无可行解。
注:在第二阶段计算时,初始表中的检验数不能引用第一阶段最优表的检验数,必须换成原问题的检验数。
(2) 无穷多最优解,如X1=(4,0,0);X2=(0,0,8)
(3) 无界解

(4) 唯一最优解 X*=(5/2,5/2,5/2,0)
(5) 唯一最优解 X*=(24,33)
(6) 唯一最优解 X*=(14,0,-4)
1.5
(4) X*仍为最优解,max z=λCX;
(5) 除C为常数向量外,一般X*不再是该问题的最优解;
(6) 最优解变为λX*,目标函数值不变。
1.6
(7) d≥0,c1<0, c2<0
(8) d≥0,c1≤0, c2≤0,但c1,c2中至少一个为零
(9) d=0或d>0,而c1>0且d/4=3/a2
(10) c1>0,d/4>3/a2
(11) c2>0,a1≤0
(12) x5为人工变量,且c1≤0, c2≤0
1.7
解:设xj表示第j年生产出来分配用于作战的战斗机数;yj为第j年已培训出来的驾驶员;(aj-xj)为第j年用于培训驾驶员的战斗机数;zj为第j年用于培训驾驶员的战斗机总数。则模型为
max z = nx1+(n-1)x2+…+2xn-1+xn
s.t. zj=zj-1+(aj-xj)
yj=yj-1+k(aj-xj)
x1+x2+…+xj≤yj
xj,yj,zj≥0 (j=1,2, …,n)
1.8
提示:设出每个管道上的实际流量,则发点发出的流量等于收点收到的流量,中间点则流入等于流出,再考虑容量限制条件即可。目标函数为发出流量最大。
设xij=从点i到点j的流量
max z=x12+x13
st. x12=x23+x24+x25
x13+x23=x34+x35
x24+x34+x54=x46
x25+x35=x54+x56 以上为流量平衡条件
x12+x13=x46+x56 始点=收点
x12≤10,x13≤6,x23≤4,x24≤5,x25≤3,x34≤5,x35≤8,x46≤11,x54≤3,x56≤7
xij≥0,对所有i,j
1.9
提示:设每个区段上班的人数分别为x1,x2,…,x6即可
1.10
解:设男生中挖坑、栽树、浇水的人数分别为x11 、x12 、x13,女生中挖坑、栽树、浇水的人数分别为x21 、x22 、x23 ,S为植树棵树。由题意,模型为:
max S=20 x11+10 x21
s.t. x11 +x12 +x13 =30
x21 +x22 +x23 =20
20 x11+10 x21 =30 x12+20 x22=25 x13+15 x23
Xij≥0 i=1,2;j=1,2,3
1.11
解:设各生产x1,x2,x3
max z = 1.2 x1+1.175x2+0.7x3
s.t. 0.6x1+0.15x2 ≤2000
0.2x1+0.25x2+0.5x3≤2500
0.2x1+ 0.6x2+0.5x3≤1200
x1,x2,x3≥0
1.12
解:设7-12月各月初进货数量为xi件,而各月售货数量为yi件,i=1,2,…,6,S为总收入,则问题的模型为:
max S=29y1+24y2+26y3+28y4+22y5+25y6-(28x1+24x2+25x3+27x4+23x5+23x6)
st. y1≤200+x1≤500
y2≤200+x1-y1+x2≤500
y3≤200+x1-y1+x2-y2+x3≤500
y4≤200+x1-y1+x2-y2+x3-y3+x4≤500
y5≤200+x1-y1+x2-y2+x3-y3+x4-y4+x5≤500
y2≤200+x1-y1+x2-y2+x3-y3+x4-y4+x5-y5+x6≤500
xi≥0,yi≥0 i=1,2,…,6 整数
1.13
解:用x1,x2,x3分别代表大豆、玉米、麦子的种植面积(hm2,公顷);x4,x5分别代表奶牛和鸡的饲养数;x6,x7分别代表秋冬和春夏季多余的劳动力(人日),则有


第二

章 对偶理论和灵敏度分析
2.1 对偶问题为
(1) (2)
(3) (4)
2.2
(1)因为对偶变量Y=CBB-1,第k个约束条件乘上λ(λ≠0),即B-1的k列将为变化前的1/λ,由此对偶问题变化后的解(y’1, y’2, …, y’k,…y’m)=(y1, y2, …, (1/λ)yk,…ym)
(2)与前类似,y’r= ,y’i= yi(i≠r)
(3)y’i=λyi(i=1,2, …,m)
(4)yi(i=1,2, …,m)不变
2.3
(1) 对偶问题为

(2) 由互补松弛性—— ( 分别为松弛变量和最优解)可得 ,从而可知,

又由对偶性质的最优性—— 可得

四方程联立即可求得对偶问题的最优解:
Y*=(2,2,1,0)
2.4
解:
其对偶问题为
min w=8y1+12y2
2y1+2y2 ≥2 (1)
2y2 ≥1 (2)
y1+y2 ≥5 (3)
y1+2y2 ≥6 (4)
y1, y2 ≥0
将y1*,y2* 代入约束条件,得(1)与(2)为严格不等式,由互补松弛性YsX*=0得x1*=x2*=0;又因为y1, y2≥0,由互补松弛性 Y*Xs=0,得Xs1=Xs2=0,即 原问题约束条件应取等号,故
x3+x4=8 解之得 x3=4
x3+2x4=12 x4=4
所以原问题最优解为X*=(0, 0, 4, 4)T,目标函数最优值为 Z*=44。
2.5
(1) 略
(2) 原问题的解 互补的对偶问题的解
第一步(0,0,0,60,40,80) (0,0,0,-2,-4,-3)
第二步(0,15,0,0,25,35) (1,0,0,1,0,-1)
第三步(0,20/3,50/3,0,0,80/3) (5/6,2/3,0,11/6,0,0)
(3) 对偶问题的解 对偶问题互补的对偶问题的解
第一步(0,0,0,-2,-4,-3) (0,0,0,60,40,80)
第二步(1,0,0,1,0,-1) (0,15,0,0,25,35)
第三步((5/6,2/3,0,11/6,0,0) (0,20/3,50/3,0,0,80/3)
(4) 比较(2)和(3)计算结果发现,对偶单纯形法实质上是将单纯形法应用于对偶问题的求解,又对偶问题的对偶即原问题,因此两者计算结果完全相同。
2.6
(1)15/4≤c1≤50,4/5≤c2≤40/3
(2)24/5≤b1≤16,9/2≤b2≤15
(3)X*=(8/5,0,21/5,0)
(4)X*=(11/3,0,0,2/3)
2.8
(1)a=40,b=50,c=x2,d=x1,e=-22.5,f=-80,g=s-440
(2)最大值
(3)2?a+?b>= -90, ?a+2?b>= -80
2.9
(1)x1,x2,x3代表原稿纸、日记本和练习本月产量,建模求解最终单纯形表如下: x1 x2 x3 x4 x5
x2 2000 0 1 7/3 1/10 -10
x1 1000 1 0 -4/3 -1/10 40
cj-zj 0 0 -10/3 -1/10 -50
(2)临时工影子价格高于市场价格,故应招收。招200人最合适。
2.10
(1) s=13x1-(2x1*1.0+3x1*2.0)+16x2-(4x2*1.0+2x2*2.0)
=5x1+8x2
max z=5

x1+8x2
s.t. 2x1+4x2≤160
3x1+2x2≤180
x1,x2≥0
X*= (50,15) max z=370元
(2)影子价格: A :7/4 B:1/2
(3)CBB-1p-(-c3+11)≥0 CB=73/4=18.25
(4)b’ = (160+a,180), B-1 b =((3/8)a +15,50-a/4) ≥0
得到-40≤a ≤200 a=200 增加利润350元
X1 X2 X3 X4
X2 15+(3/8)a 0 1 3/8 -1/4
X1 50- a/4 1 0 -1/4 1/2
s -370- 7a/4 0 0 -7/4 -1/2

第三章 运输问题
3.1
解:
表3.1-1
B1 B2 B3 B4 供应量
A1 (10) (6) (7) (12) 4
A2 (16) (10) (5) (9) 9
A3 (5) (4) (10) (10) 5
需要量 5 3 4 6 18
西北角法是优先从运价表的西北角的变量赋值,当行或列分配完毕后,再在表中余下部分的西北角赋值,以此类推,直到右下角元素分配完毕。
表3.1-1西北角元素是x11, x11=min{a1, b1}= min{4, 5}= 4,将4填
在C11的左侧,表示A1供应4单位给B2。同时将第一行划去,表示A1的产量全部运出,得表3.1-2。在表3.1-2中,西北角元素是x21,x21= min{9, 5-4}=1,同时降第一列划去,表示B1已满足需要,得到表3.1-3。依次向右下角安排运量,结果如表3.1-4所示。
表3.1-2
B1 B2 B3 B4 供应量
A1 4 (10) (6) (7) (12) 4
A2 (16) (10) (5) (9) 9
A3 (5) (4) (10) (10) 5
需要量 5 3 4 6 18
表3.1-3
B1 B2 B3 B4 供应量
A1 4 (10) (6) (7) (12) 4
A2 1 (16) (10) (5) (9) 9
A3 (5) (4) (10) (10) 5
需要量 5 3 4 6 18
表3.1-4
B1 B2 B3 B4 供应量
A1 4 (10) (6) (7) (12) 4
A2 1 (16) 3(10) 4(5) 1(9) 9
A3 (5) (4) (10) 5(10) 5
需要量 5 3 4 6 18
最小元素法的思想是就近优先运送,即最小运价cij对应的变量xij优先赋值xij=min{ai, bj},然后在剩下的运价中取最小运价对应的变量赋值并满足约束,依次下去,直到最后得到一个初始基本可行解。
表3.1-1中最小元素是C32,令x32=min{a3, b2}= min{5, 3}= 3,同时将第二列划去,得到表3.1-5。在表3.1-5中,最小元素为C23,C31,任意选取其一,这里选C31,令x31= min{5-3, 5}=2,同时将第三行划去,得表3.1-6。依次进行下去,其结果见表3.1-7。
表3.1-5
B1 B2 B3 B4 供应量
A1 (10) (6) (7) (12) 4
A2 (16) (10) (5) (9) 9
A3 (5) 3(4) (10) (10) 5
需要量 5 3 4 6 18
表3.1-6
B1 B2 B3 B4 供应量
A1 (10) (6) (7) (12) 4
A2 (16) (10) (5) (9) 9
A3 (5) 3(4) (10) (10) 5
需要量 5 3 4 6 18
表3.1-7
B1 B2 B3 B4 供应量
A1 3 (10) (6) (7) 1(12) 4
A2 (16) (10) 4(5) 5(9) 9
A3 2 (5) 3(4) (10) (10) 5
需要量 5 3 4 6 18
伏格尔法是最小元素法的改进,考虑到产地到销地的最小运价和此小运价之间的差额,如果差额很大,就选最小运价处险调运,否

则会增加总运费。
在表3.1-1中求行差额 和列差额 。计算公式为

若同时将第三行与第一列划去,最后即变量个数比小于3+4-1=6个,因而应再x32,x33,x34和x11,x12中任意选一个变量作为即变量,运量为零,这里选x11,如表3.1-8所示。
求第二个基变量仍然是求差额,因为第三行和第一列已满足,所以只求u1,u2和v2,v3,v4即可,结果见表3.1-9。此时,有两个最大差额u2,v2,任选一个即可,这里选v2.第二列最小运价为c12,故x12=min{4,3}=3.同
时将第二列划去。这样依次下去,其结果见表3.1-10。
表3.1-8
B1 B2 B3 B4 供应量 ui
A1 0 (10) (6) (7) (12) 4 1
A2 (16) (10) (5) (9) 9 4
A3 5 (5) (4) (10) (10) 5 1
需要量 5 3 4 6 18
vj 【5】 2 2 1
表3.1-9
B1 B2 B3 B4 供应量 ui
A1 0 (10) (6) (7) (12) 4 1
A2 (16) (10) (5) (9) 9 4
A3 5 (5) (4) (10) (10) 5 —
需要量 5 3 4 6 18
vj — 【4】 2 3
表3.1-10
B1 B2 B3 B4 供应量
A1 0 (10) 3(6) 1(7) (12) 4
A2 (16) (10) 3(5) 6(9) 9
A3 5 (5) (4) (10) (10) 5
需要量 5 3 4 6 18

3.4
(1)
B1 B2 B3 B4 供应量
A1 8(6) (7) 0(5) (8) 8
A2 (4) (5) 4(10) 5(8) 9
A3 (2) 6(9) 1(7) (3) 7
需要量 8 6 5 5 24
(2)
B1 B2 B3 B4 供应量
A1 8(6) (7) 2(5) (8) 8+2
A2 (4) (5) 4(10) 5(8) 9
A3 (2) 6(9) 1(7) (3) 7
需要量 8 6 5+2 5 24
3.5
甲 乙 丙 丁 可供量
A 500 500 1000
B 1500 500 2000
C 500 1500 2000
销售量 1500 1500 1500 500
3.6
存贮能力大,即产大于销,虚拟一个销地,所需存取时间为0,文件数为100,最优解为:x11=200, x21=100, x31=0 ,x32=100, x33=100, x34=100 最优值为:(200×5+100×2)×8+100×8×4+100×6×2=14000
3.7
解:用伏格尔法初始解:28.5+29.6+34.7+35.4=128.2
赵 钱 张 王 周
仰 泳 37.7 32.9 33.8 37.0 35.4(1)
蛙 泳 43.4 33.1 42.2 34.7(1) 41.8
蝶 泳 33.3(0) 28.5(1) 38.9 30.4 33.6
自由泳 29.2(0) 26.4 29.6(1) 28.5 31.1
泳 0(1) 0 0 0 0(0)

赵 钱 张 王 周
仰 泳 37.7 32.9 33.8(2) 37.0 35.4(1)
蛙 泳 43.4 33.1 42.2 34.7(1) 41.8
蝶 泳 33.3(0) 28.5(1) 38.9 30.4 33.6
自由泳 29.2(0) 26.4 29.6(1) 28.5 31.1
泳 0(1) 0 0 0 0(0)

赵 钱 张 王 周
仰 泳 37.7 32.9 33.8(1) 37.0 35.4(0)
蛙 泳 43.4 33.1 42.2 34.7(1) 41.8
蝶 泳 33.3(0) 28.5(1) 38.9 30.4 33.6
自由泳 29.2(1) 26.4 29.6(0) 28.5 31.1
泳 0(0) 0 0 0 0(1)

赵 钱 张 王 周
仰 泳 37.7 32.9 [33.8] 37.0 35.4
蛙 泳 43.4 33.1 42.2 [34.7] 41.8
蝶 泳 33.3 [28.5] 38.9 30.4 33.6
自由泳 [29.2] 26.4 29.6 28.5 31.1
最优解:29.2+28.5+

33.8+34.7=126.2
3.8
(1)a=5,b=5,c=5,d=6,e=15 最优解略
(2)c31≥8
3.9
数学模型为:
min z =
s.t ≤ai (i=1,2,…,m)
≥bj (j=1,2,…,n)
xij≥0
上面第一个约束条件可以改写为- ≥-ai,则对偶问题为:
max z’ = -
s.t vj ≤ui +cij (i=1,2,…,m j=1,2,…,n)
ui, vj≥0
对偶变量ui的经济意义为在i产地单位物资的价格,vj的经济意义为在j销地单位物资的价格。对偶问题的经济意义为:如该公司欲自己将该种物资运至各地销售,其差价不能超过两地之间的运价(否则买主将在i地购买自己运至j地),在此条件下,希望获利为最大。
3.10
用xj表示每期(半年一期)的新购数,yij表示第i期更换下来送去修理用于第j期的发动机数。显然当j>i+1时,应一律送慢修,cij为相应的修理费。每期的需要数bj为已知,而每期的供应量分别由新购与大修送回来的满足。如第1期拆卸下来的发动机送去快修的可用于第2期需要,送去慢修的可用于第3期及以后各期的需要。因此每期更换下来的发动机数也相当于供应量,由此列出这个问题用运输问题求解时的产销平衡表与单位运价表为:
1 2 3 4 5 6 库存 供应量
新 购 10 10 10 10 10 10 0 660
第1期送修的 M 2 1 1 1 1 0 100
第2期送修的 M M 2 1 1 1 0 70
第3期送修的 M M M 2 1 1 0 80
第4期送修的 M M M M 2 1 0 120
第5期送修的 M M M M M 2 0 150
需 求 量 100 70 80 120 150 140 520

3.11.
解:转运问题,最优解如下表
甲 乙 A B C 产 量
甲 1000 500 1500
乙 900 300 300 1500
A 1000 1000
B 1000 1000
C 100 900 1000
销 量 1000 1000 1300 1300 1400

第四章 目标规划
4.1分别用图解法和单纯形法求解下述目标规划问题
(1)满意解为X1=(50/3,0)’,X2=(88/9,62/9)’间线段
(2)满意解为X=(4,6)’
4.2.
(1)满意解X=(0,35)’,d-1=20,d-3=115,d-4=95,其余d-i=d+i=0
(2)满意解X=(0,220/3)’,d-1=20,d-2=5/3,d-4=400/3,其余d-i=d+i=0
(3)满意解X=(0,35)’,d-1=20,d-3=115,d-4=95,d-5=27,其余d-i=d+i=0
(4)满意解不变
4.3
设安排商业节目x1小时,新闻x2小时,音乐x3小时,模型为:
min z = p1(d-1+ d-2+d+3) + p2d-4
s.t x1 + x2 + x3 + d-1 = 12

x1 + d-2= 2.4
x2 - d+3 = 1
250x1 - 40x2 – 17.5x3 + d-4 - d+4= 600
x1, x2, x3, d-1 ,d-2 ,d+3 ,d-4 , d+4 ≥0
4.4 略
4.5
设A、B型机的产量分别为x1,x2台,模型为:

第五章 整数规划
5.1
解:令y= 1,当x2=x3=1时
0,否则
故有x2x3=y,又x12,x33分别与x1,x3等价,因此原模型可转换为
max z = x1+ y- x3
st. -2x1+3x2+ x3 ≤ 3
y ≤ x2
y ≤ x3
x2+ x3 ≤ y+1
xj = 0或1(j=1,2,3);y= 0或1
5.2
min z =
s.t = 5
x1 + x8 = 1 x3 + x5 ≤ 1
x7 + x8 = 1 x4 + x5 ≤ 1
x5 + x6 + x7 + x8 ≤ 2
xj= 1,选择钻探sj井位
0,否则
5.3
(1)最优解x1=2,x2=2或x1=3,x2=1;z=4
(2)最优解x1=4,x2=2;z=14
5.4
(1)最优解x1=4,x2=3;z=55
(2)最优解x1=2,x2=1;z=13
5.5
最优解x1=x2=1,x3=x4=x5=0;z=5
5.6
最优解(1, 0, 1)和(0, 1, 1)。Z=5.
5.7
最优解为x13=x22=x34=x41=1,最优值为48


5.8
虚拟一人戊,完成各项工作时间取甲乙丙丁中最小者,构造下表
人 任务 A B C D E
甲 25 29 31 42 37
乙 39 38 26 20 33
丙 34 27 28 40 32
丁 24 42 36 23 45
戊 24 27 26 20 32
最优分配方案:甲-B,乙-D和C,丙-E,丁-A;总计需要131小时
5.9 此问题是一个非平衡的纸牌问题,通过虚设一泳姿,而设运动员的游泳成绩为零,化为平衡指派问题。
5.10
解:设xij= 1,商贩从i直接去j
0, 否则 整数规划模型为:
min z = dijxij
s.t xij = 1 (j=1,2, …,n)
xij = 1 (i=1,2, …,n)
ui – uj+n xij≤n-1
ui 为连续变量(i=1,2, …,n),也可取整数值
i,j=1,2, …,n,i≠j
5.11
解:设xij表示第i种产品在j机床上开始加工的时刻,模型为
min z = max ﹛x13+t13,x23+t23,x33+t33﹜
s.t xij+tij≤ti,j+1 (i=1,2,3;j=1,2)加工顺序约束
xij+tij-xi+1,j≤M σi
xi+1,j+ti+1,j-xij≤M(1-σi) 互斥性约束
i=1,2; j=1,2,3; σi =0或1
xij ≥0



相关文档