运筹学习题集二_运筹学习题集第二章

2020-02-28 其他范文下载本文

运筹学习题集二由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“运筹学习题集第二章”。

运筹学习题集二

习题一

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

x5 x3

0 x4

－1

－5

0 x5

－3

0cj －zj

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

1.8.某石油管道公司希望知道在下图所示的管道络中可以流过的最大流量是多少及怎样输送弧上数字是容量限制。请建立此问题的线性规划模型不必求解。210 15 631.9.某昼夜服务的公交线每天各时间区段内所需司机和乘务人员数如下：

班次时间所需人数

6:00-10:00

10:00-14:00

14:00-18:00

18:00-22:00

22:00-2:006

2:00-6:00设司机和乘务人员分别在各时间区段一开始时上班并连续工作八小时问该公交线至少配备多少名司机和乘务人员。列出此问题的线性规划模型。

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件以后每月初进货一次假设各月份此商品买进售出单价如下表所示问各月进货售货各多少才能使总收入最多？请建立此问题的线性规划模型不必求解。

月份买进单价

23售出单价

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

试决定该农场的经营方案使年净收人为最大。(建立线性规划模型不需求解)习题二

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）

－ 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

＋ 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 —?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 B 3 2 180 1.0 2.0

销售价（）13 16

（1）请构造数学模型使该利润最大并求解。（2）原料A、B的影子各为多少。（3）现有新产品丙每件消耗3千克原料A和4千克原料B问该产品的销售至少为多少时才值得投产。

（4）工可在市场上买到原料A。工是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下最多应购入多少？可增加多少利润？

习题三

3.1 求解下表所示的运输问题分别用最小素法、西北角法和伏格尔法给出初始基可行解： B1 B2 B3 B4 量 A1（10）A2（16）（6）（7）（12）（10）

（5）（9）9（10）A3（5）（4）（10）需要量 5 3 4 6 18 3.2由产地A1A2发向销地B1B2的单位费用如下表产地允许存贮销地允许缺货存贮和缺货的单位运费也列入表中。求最优调运方案使总费用最省。

B1 B2 量存贮费/件 A1 8 5 400 A2 6 9 300 需要量 200 3 4 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玩具。求满足上述条件下使总盈利额最大的销分配方案。

甲乙丙可量

－

1000 B

2000 C

2000

3.6 目前城市大学能存贮200个文件在硬盘上100个文件在计算机存贮器上300个文件在磁带上。用户想存贮300个字处理文件100个源程序文件100个数据文件。每月一个典型的字处理文件被访问8次一个典型的源程序文件被访问4次一个典型的数据文件被访问2次。当某文件被访问时重新找到该文件所需的时间取决于文件类型和存贮介质如下表。

时间（分钟）处理文件源程序文件数据文件硬盘存贮器磁带如果目标是极小化每月用户访问所需文件所花的时间请构造一个运输问题的模型来决定文件应该怎么存放并求解。

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 自由泳

3.8 求总运费最小的运输问题其中某一步的运输图如下表。29.2 26.4 29.6 28.5 31.1 B1 B2 B3 量 A1 3（3）A2 2（4）（5）（7）3 4（2）

（4）6

d A3（5）1（6）需要量

5（3）

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.为确保飞行安全飞机上的发动机每半年必须强迫更换进行大修。某维修估计某种型号战斗机从下一个半年算起的今后三年内每半年发动机的更换需要量分别为：***0。更换发动机时可以换上新的也可以用经过大修的旧的发动机。已知每台新发动机的购置费为10万而旧发动机的维修有两种方式：快修每台2万半年交货（即本期拆下来送修的下批即可用上）；慢修每台1万但需一年交货（即本期拆下来送修的需下下批才能用上）。设该新接受该项发动机更换维修任务又知这种型号战斗机三年后将退役退

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

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

从到甲乙从到

从到

甲

120

甲

120 80

100 乙

乙

160 40

0 120 C

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 10 12 13 12 16 17 15 16 14 15 11 12 15 16

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

E 甲

乙

丙

丁

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）如下表所示其中打三角符号的是基本可行解打星号的为最优解：

x5 △

-3-5 △

0-5 6

0-3 △

-9/2

5/2

0 △

5/2

0 *△

3/2

0 △* 4

5/2

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 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 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 1 X3-1 0 1-1-2 0 X2 2 1 0 0 1-M X7-2 0 0-1-2 σj 5-2M 0 0 1-M 表1.4-1.1 在迭代过程中人工变量一旦出基后不会在进基所以当人工变量X6出基后对应第六列的系数可以不再计算以减少计算量。

当用大M单纯形法计算得到最优解并且存在人工变量大于零时则表明原线性规划无可行解。两阶段单纯形法

首先化标准形同大M法第一、三约束分别加入人工变量x6 x7后构造

0 0 0 10 0 4 1 11

2-2M 第一阶段问题

用单纯形法求解得到第一阶段问题的计算表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/20 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＝（400）；X2＝（008）(3)无界解

(4)唯一最优解 X*＝（5/25/25/20）(5)唯一最优解 X*＝（2433）(6)唯一最优解 X*＝（140－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,但c1c2中至少一个为零（9）d＝0或d0而c10且d/4=3/a2（10）（11）（12）1.7 解：设xj表示第j年生产出来分配用于作战的战斗机数；yj为第j年已出来的驾驶员；（aj－xj）为第j年用于驾驶员的战斗机数；zj为第c10,d/43/a2 c20,a1≤0 x5为人工变量且c1≤0, c2≤0 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≤10x13≤6x23≤4x24≤5x25≤3x34≤5x35≤8x46≤11x54≤3x56≤7 xij≥0对所有ij 1.9

提示：设每个区段上班的人数分别为x1x2…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＝12…6S为总收入则问题的模型为：

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≥0yi≥0 i＝12…6 整数 1.13 解：用x1x2x3分别代表大豆、玉米、麦子的种植面积（hm2公顷）；x4x5分别代表奶牛和鸡的饲养数；x6x7分别代表秋冬和春夏季多余的劳动力（人日）则有

第二

章对偶理论和灵敏度分析 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*＝（2210）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）原问题的解互补的对偶问题的解第一步（000604080）（000－2－4－3）第二步（015002535）（10010－1）

第三步（020/350/30080/3）（5/62/3011/600）（3）对偶问题的解对偶问题互补的对偶问题的解第一步（000－2－4－3）（000604080）第二步（10010－1）（015002535）

第三步（（5/62/3011/600）（020/350/30080/3）

（4）比较（2）和（3）计算结果发现对偶单纯形法实质上是将单纯形法应用于对偶问题的求解又对偶问题的对偶即原问题因此两者计算结果完全相同。2.6

（1）15/4≤c1≤50,4/5≤c2≤40/3（2）24/5≤b1≤169/2≤b2≤15（3）X*=（8/5021/50）（4）X*=（11/3002/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代表原稿纸、日记本和练习本月产量建模求解最终单纯形表如下：

x5 x2

2000

7/3

1/10

-10 x1

1000

-4/3

-1/10

cj-zj

-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-1-（-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-1/2 s-370-7a/4 0 0-7/4 第三章 3.1 解：表3.1-1 B1 B2 B3 B4 量 A1(10)A2(16)运输问题

（6）（7）（12）（10）

（5）（9）9（10）A3(5)（4）（10）需要量 5 3 4 6 18 西北角法是优先从运价表的西北角的变量赋值当行或列分配完毕后再在表中余下部分的西北角赋值以此类推直到右下角素分配完毕。表3.1-1西北角素是x11, x11=min｛a1, b1｝= min｛4, 5｝= 4将4填在C11的左侧表示A14单位给B2。同时将第一行划去表示A1的产量全部运出得表3.1-2。在表3.1-2中西北角素是x21x21= min｛9, 5-4｝=1同时降第一列划去表示B1已满足需要得到表3.1-3。依次向右下角安排运量结果如表3.1-4所示。表3.1-2 B1 B2 B3 B4 量 A1 4(10)A2(16)（6）（7）（12）

（5）（9）9（10）4（10）

A3(5)（4）（10）需要量表3.1-3 B1 B2 B3 B4 量 A1 4(10)A2 1(16)5 3 4 6 18（6）（7）（12）（10）

（5）（9）9（10）A3(5)（4）（10）需要量表3.1-4 B1 B2 B3 B4 量 A1 4(10)5 3 4 6 18（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中最小素为C23C31任意选取其一这里选C31令x31= min｛5-3, 5｝=2同时将第三行划去得表3.1-6。依次进行下去其结果见表3.1-7。表3.1-5 B1 B2 B3 B4 量 A1(10)A2(16)（6）（7）（12）（10）

（5）（9）9

（10）A3(5)3（4）需要量表3.1-6 B1 B2 B3 B4 量 A1(10)A2(16)（10）3 4 6 18（6）（7）（12）（10）

（5）（9）9

（10）A3(5)3（4）需要量（10）3 4 6 18 表3.1-7 B1 B2 B3 B4 量

A1 3(10)（6）（7）1（12）4 A2(16)（10）

4（5）（10）

5（9）（10）5 A3 2(5)3（4）需要量 5 3 4 6 18 伏格尔法是最小素法的改进考虑到产地到销地的最小运价和此小运价之间的差额如果差额很大就选最小运价处险调运否

则会增加总运费。

在表3.1-1中求行差额和列差额。计算公式为

若同时将第三行与第一列划去最后即变量个数比小于3+4-1=6个因而应再x32x33,x34和x11,x12中任意选一个变量作为即变量运量为零这里选x11如表3.1-8所示。

求第二个基变量仍然是求差额因为第三行和第一列已满足所以只求u1,u2和v2v3v4即可结果见表3.1-9。此时有两个最大差额u2v2任选一个即可这里选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 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 3 4 6 18

vj — 4 2 3

表3.1-10 B1 B2 B3 B4 量 A1 0(10)3（6）1（7）（12）A2(16)（10）

3（5）

6（9）

A3 5(5)（4）（10）（10）需要量 5 3 4 6 18 3.4(1)

—4 9

B1 B2 B3 B4 量 A1 8（6）（7）0（5）

（8）8A2（4）（5）4（10）5（8）A3（2）6（9）需要量（2）

B1 B2 B3 B4 量 A1 8（6）（7）2（5）

1（7）

（3）7 8 6 5 5 24

（8）8+2A2（4）（5）4（10）5（8）A3（2）6（9）需要量 3.5

甲乙丙丁可量

1（7）5 24

（3）7 8 6 5+2 A

500

1000 B

1500

500

2000 C

500

1500

2000 销售量

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 自由泳泳 0(1)

赵钱张王周仰泳 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 29.2(0)26.4 29.6(1)28.5 31.1 0 0 0 0(0)泳

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 自由泳泳 0(0)29.2(1)26.4 29.6(0)28.5 31.1 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期及以后各期的需要。因此每期更换下来的发动机数也相当于量由此列出这个问题用运输问题求解时的产销平衡表与单位运价表为：

库存量

新购

660 第1期送修的M

第2期送修的M

第3期送修的M

第4期送修的M

第5期送修的M

需求量

120

140

520 3.11.解：转运问题最优解如下表

甲乙

产量

甲

1000

500

1500 乙

900

300

1500 A

1000

1000 B

1000

1000 C

900

1000 销量

1000

1300

1400

第四章目标规划

4.1分别用法和单纯形法求解下述目标规划问题

（1）满意解为X1＝（50/30）’X2＝（88/962/9）’间线段（2）满意解为X＝（46）’ 4.2.（1）满意解X＝（035）’d－1＝20d－3＝115d－4＝95其余d－i＝d＋i＝0（2）满意解X＝（0220/3）’d－1＝20d－2＝5/3d－4＝400/3其余d－i＝d＋i＝0（3）满意解X＝（035）’d－1＝20d－3＝115d－4＝95d－5＝27其余d－i＝d＋i＝0（4）满意解不变

相关专题运筹学习题集第二章运筹学习题集运筹学习题集第二章运筹学习题集

[其他范文]相关推荐

[其他范文]热门文章