第一章 线性规划习题

1. 将下列线性规划问题变换成标准型，并列出初始单纯形表。 1) minZ＝－3x1＋4x2－2x3＋5x4

?4x1?x2?2x3?x4??2?x1?x2?3x3?x4?14?s.t.? ??2x1?3x2?x3?2x4?2??x1,x2,x3?0,x4无约束.2) maxS＝zx／pk

nm??zk???aikxik,i?1k?1??m(i?1,2,...,n),s.t.???xik??1

?k?1?xik?0(i?1,2,...,n;k?1,2,...,m).??2. 分别用单纯法中的大M法和两阶段法求解下述线性规划问题：

minZ＝2x1＋3x2＋x3

?x1?4x2?2x3?8,??6, s.t.?3x1?2x2?x,x,x?0.?123并指出该问题的解属哪一类解。

3. 【表1-6】是某求极大化线性规划问题计算得到单纯形表。表中无人工变量，

a1, a2, a3, d, c1, c2为待定常数。试说明这些常数分别取何值时，以下结论成立。

1) 表中解为唯一最优解；

2) 表中解为最优解，但存在无穷多最优解； 3) 该线性规划问题具有无界解；

4) 表中解非最优，为对解进行改进，换入变量为x1，换出变量为x6。

表1-6

基 x3 x4 x6 b d 2 3 x1 4 －1 a3 c1 x2 a1 －3 －5 c2 x3 1 0 0 0 x4 0 1 0 0 x5 a2 －1 －4 －3 x6 0 0 1 0 4. 某饲料厂用原料A、B、C加工成三种不同牌号的饲料甲、乙、丙。已知各

种牌号饲料中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号的饲料的单位加工费及售价如【表1-7】所示。

表1-7

甲 乙 丙 原料成本 每月限制用（元/千克） 量（千克） 1

A B C 加工费 （元/千克） 售价 ≥60% ≤20% 0.50 3.40 ≥15% ≤60% 0.40 2.85 ≤50% 0.30 2.25 2.00 1.50 1.00 2000 2500 1200 问该厂每月应生产这三种牌号饲料各多少千克，使该厂获利最大？试建立这个问题的的线性规划的数学模型。 5. 考虑下列问题

maxf(x)?2x1?4x2S.t ?x1?x2?1??x1?0,x2?01) 建立此问题的对偶问题，然后以观察法求出其最优解。

2) 使用主对偶原理及对偶问题的最优解求出原问题的最优解目标函数值。 3) 假设原问题中x1的系数为c1（c1可为任意实数）。当c1为何值时，此对

偶问题无可行解？对这些值而言，原问题的解有什么意义？ 6. 求下列问题的对偶问题 1)

maxf(x)?2x1?5x2?3x3S.t??30?3x1?6x2 ?6x?12x?3x?75?123?x?0,x?0,x?023?12) minf(x)??2x1?x2?4x3?3x4S.t?x1?x2?3x3?2x4?10?x?x?3x?2x?40234?1??x4?10 ?x1?x2??20?2x1?x2?x1?2x2?x3?2x4?20???x2,x3,x4?0,x1无限制7. 某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。

这四种产品的产值、成本、加工工时等资料列表如下：

表1-8

产品 项目 单位产值 (元) 单位成本 (元) 单位纺纱用时 (h) 单位织带用时 (h) A 168 42 3 0 B 140 28 2 0 C 1050 350 10 2 D 406 140 4 0.5 工厂有供纺纱的总工时7200h，织带的总工时1200h。

2

1) 列出线性规划模型，以便确定产品的数量使总利润最大；

2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型

的解是否有影响？ 8. 将下列线性规划化为极大化的标准形式

minf(x)?2x1?3x2?5x3? x1s.t. ?? x?6x2? x3??5??1?7x2?9x3?16 ?|19x1?7x?02?5x?, x3|?13?x1,x23?不限9. 用单纯形法解下面的线性规划

maxf(x)?2x1?5x2?3x3?3x1?2x2?x3?610?s.t. ???x1?6x2?3x3?125 ??2x1?x2?0.5x3?420??x1,x2,x3?0, 10. 用两阶段法解下面问题：

minf(x)?4x1?6x2?x1s.t. ??2x2?80?3x

?1?x2?75?x1,x2?011. 用大M法解下面问题，并讨论问题的解

maxf(x)?10x1?15x2?12x3??5x1?3x2?x3?9s.t. ???5x1?6x2?15x3?15

?2x1?x2?x3?5??x1,x2,x3?0, 12. 写出下列线性规划问题的对偶问题 1)

maxf(x)?2x1?3x2?5x32)

minf(x)?4x1?3x2?8x3?? x1?x2?x3?x4?5??2?x1?s.t. ?? 2x1 ?x3 ?4 s.t. ?6?4?x? x2?x3?x4?6?2?14??12?x3??8??x1?0,x2,x3?0, x4?不限

3

13. 写出下问题的对偶问题，解对偶问题，并证明原问题无可行解

maxf(x)??4x1?3x2?x1?x2?1 ?? ?x2??1s.t. ??x?2x2?1 ?1??x1,x2?0,

14. 用对偶单纯形法求下面问题

minf(x)?4x1?6x2?x1?2x2?80?s.t. ?3x1?x2?75??x1,x2?0

15. 下表是一线性规划最优解的单纯形表

CB 21 0 9 XB x1 x5 x2 Cj ? b 4 2 23 zj cj ? zj 21 x1 1 0 0 21 0 9 x2 0 0 1 9 0 4 x3 1/3 ?2/3 1/3 10 ?6 0 x4 2/3 ?4/3 ?1/3 11 ?11 0 x5 0 1 0 0 0 0 x6 1/3 1/3 ?2/3 1 ?1 原问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题： 1) 资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6

是资源3的剩余变量) 2) 求C1, C2 和C3的灵敏度范围； 3) 求?b1，?b2的灵敏度范围。

4