运筹学习题集二.docx

运筹学习题集二

习题一

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≥0x3无约束
x1, x2≥0

1.5 线性规划问题max z＝CXAX＝bX≥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
x1x3≥0x2x4无约束
(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≥0x4≤0x2x3 无约束 x1≤0 x2≥0x3 无约束

2.2 已知线性规划问题max z＝CXAX=bX≥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*＝（1120）试根据对偶理论直接求出对偶问题的最优解。

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）约束条件右端项b1b2当一个保持不变时另一个在什么范围内变化上述最优基保持不变；
（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的系数列向量由（—112）T变为（05）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）给出abcdefg的值或表达式；
（2）指出原问题是求目标函数的最大值还是最小值；
（3）用a+?ab+?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由产地A1A2发向销地B1B2的单位费用如下表产地允许存贮销地允许缺货存贮和缺货的单位运费也列入表中。求最优调运方案使总费用最省。
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. 为确保飞行安全飞机上的发动机每半年必须强迫更换进行大修。某维修估计某种型号战斗机从下一个半年算起的今后三年内每半年发动机的更换需要量分别为：1007080120150140。更换发动机时可以换上新的也可以用经过大修的旧的发动机。已知每台新发动机的购置费为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 ＝1（ ＋ ）＋2
st. －x1＋ x2＋ d－1－ d＋1＝1
－0.5x1＋ x2＋ d－2－d＋2＝2
3x1＋3x2＋ d－3－ d＋3＝50
x1x2≥0；d－id＋i≥0（i =123）
（2） min z ＝1（2 ＋3 ）＋2 ＋3
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
x1x2≥0；d－id＋i ≥0（i =1…4）
4.2 考虑下述目标规划问题
min z ＝1（d＋1＋d＋2）＋22d－4＋2d－3＋3d－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
x1x2≥0；d－id＋i ≥0（i =1…4）
（1）求满意解；
（2）当第二个约束右端项由35改为75时求解的变化；
（3）若增加一个新的目标约束：－4x1＋x2＋d－5－d＋5＝8该目标要求尽量达到目标值并列为第一优先级考虑求解的变化；
（4）若增加一个新的变量x3其系数列向量为（011－1）T则满意解如何变化？

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

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
工经营目标的期望值及优先级如下：
1：每周总利润不得低于10000；
2：因合同要求A型机每周至少生产10台：B型机每周至少生产15台；
3：由于条件限制且希望充分利用工的生产能力工序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个井位的代号为s1s2…s10相应的钻探费用为c1c2…c10并且井位选择上要满足下列限制条件：
（1） 或选择s1和s7或选择钻探s8；
（2） 选择了s3或s4就不能选s5或反过来也一样；
（3） 在s5s6s7s8中最多只能选两个。
试建立此问题的整数规划模型。

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

5.4 用割平面法求解下列整数规划问题
(1) max z ＝7x1＋9x2
st. －x1＋3 x2 ≤6
7x1 ＋ x2 ≤35
x1x2≥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或1j=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上加工然后依次在机床23上加工。在每台机床上加工三个产品的顺序应保持一样假定用tij表示在第j机床上加工第i个产品的时间问应如何安排使三个产品总的加工周期为最短。试建立此问题的整数规划模型。

习题参考
第一章 线性规划及单纯形法
1.1
（1）解：
第一求可行解集合。令两个约束条件为等式得到两条直线在第一象限划出满足两个不等式的区域其交集就是可行集或称为可行域如图1-1所示交集为（1/2, 0）。
第二绘制目标函数图形。将目标函数的系数组成一个坐标点（64）过原点O作一条矢量指向点（64）矢量的长度不限矢量的斜率保持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)解：单纯形法
首先将问题化为标准型。加松弛变量x3x4得

其次列出初始单纯形表计算最优值。
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法
首先将数学模型化为标准形式

式中x4x5为松弛变量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