运筹学习题集二

运筹学习题集二

习题一

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 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）

4

（5） （9） 9 （10）

5

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

（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 （表一）

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代表原稿纸、日记本和练习本月产量建模求解最终单纯形表如下： 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

B1 B2 B3 B4 量 A1 8（6）

（7） 0（5）

（8） 8

9

A2 （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+2

9

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

甲乙丙丁可量

1（7） 5 24

（3） 7

8 6 5+2

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

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/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）满意解不变

本文来源：https://www.bwwdw.com/article/rnww.html