第1章 线性规划与单纯形法
1、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。
(a)minz?2x1?3x2?4x1?6x2?6 ??4x1?2x2?4?x，x?02?1(b)maxz?3x1?2x2?2x1?x2?2 ?? 3x1?4x2?12?x,x?012?
(c)maxz?x1?x2 ?(d)maxz?5x1?6x2?2x1?x2?2???2x1?3x2?2?x,x?012?
?6x1?10x2?120
5?x?10?1?3?x?82?(a)maxz?10x1?5x2?3x1??5x1?x,?1?4x2?2x2x2? 2、用单纯形法求解下列线性规划问题。
(b)maxz?2x1?x2?15?24 ?5?05x2??9? ?6x1?2x2?8??x1?x20?x2?x1,3、用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。
(a)maxz?2x1?x2?2x3?x1? ??2x1????x1,?x22x2x2,?x3?x3?x3x3?6?2 ?0?0(b)minz?2x1?3x2?x3?x1??3x1?x,?1?4x2?2x2x2,?2x3x3?8 ?6?04、已知线性规划问题的初始单纯形表（如表1所示）和用单纯形法迭代后得到的表（如表2所示）如下，试求括弧中未知数a～l的值。
表1
x4 x5 cj-zj 表2 6 1 x1 (b) -1 (a) x2 (c) 3 -1 x3 (d) (e) 2 x4 1 0 0 x5 0 1 0
x1 x5 cj-zj (f) 4 x1 (g) (h) 0 x2 2 (i) -7 x3 -1 1 (j) x4 1/2 1/2 (k) x5 0 1 (l) 5、某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据见下表，试安排最优生产计划，使该厂获利最大。
设备 产品 Ⅰ 5 7 6 4 7 Ⅱ Ⅲ 设备有效台时 设备加工费 （元/小时） 0.05 0.03 0.06 0.11 0.05 A1 A2 B1 B2 B3 10 9 8 12 11 6 000 10 000 4 000 7 000 4 000 原料费（元/件） 售价（元/件） 0.25 1.25 0.35 2.00 0.50 2.80 6、若X1、X2均为某线性规划的最优解，证明这两点连线上的所有点也是该问题的最优解。
7、线性规划问题 maxz?CX,AX?b,X?0，如果X是该问题的最优解，又
*??0为某一常数，分别讨论下列情况时最优解的变化？
第2章 对偶问题和灵敏度分析
1、写出下列线性规划问题的对偶问题。
(a)minz?2x1?2x2?4x3?x1?3x2?2x?1?x2??x1?4x2??x1,x2?0,?4x3?3x33x3?2?3 ?5x3无约束
(b)maxz??cjxjj?1n?n(i?1,?,m1?m)??aijxij?bi1?j? n???aijxj?bi(i?m1?1,?,m)?j?1??xj?0(j?1,?,n1?n)???xj无约束(j?n1?1,?,n)2、已知线性规划问题：
maxz?x1?x2??x1?x2?x3 ???2x1?x2?x3?x，x，x?0?123?2?1
试应用对偶理论证明上述线性规划问题最优解为无界。 3、已知线性规划问题：
maxz?2x1?4x2?x3?x4?x4?x1?3x2?2x?x21 ??x2?x3?x4??x?x2?x3?1(j?1,?,4)??xj?0?8?6?6?9
要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=(2,2,4,0)，是根据对偶理论直接求出对偶问题最优解。 4、已知线性规划问题：
maxz?2x1?x2?x3 ?1??x1?x?x2?x3?6
?2x2?4??x1,x2,x3?0先用单纯形法求出最优解，再分析在下列条件单独变化的情况最优解的变化。
（1）目标函数变为maxz?2x1?3x2?x3； （2）约束右端项由??变为??；
（3）增添一个新的约束条件：
B1 B2 B3 产量 ?6??4??3??4??x1?2x3?2。
5、 某厂生产A、B、C三种产品，其
A1 1 2 6 7 所需劳动力、材料等有关数据见下表。要
求：(1)确定获利最大的产品生产计划；(2)
A2 0 4 2 12 产品A的利润在什么范围内变动时，上
A3 3 1 5 11 述最优计划不变；(3)如果设计一种新产
品D，单件劳动力消耗为8单位，材料消
销量 10 10 10 耗为2单位，每件可获利3元，问该种产
品是否值得生产?(d)如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。
消 耗 定 资 源 额 产 品 A B C 6 3 5 3 4 5 3 1 5 可用量（单位） 45 30 劳动力 材料 产品利润（原/件）
第三章 运输问题
1、应用最小元素法和伏格尔法求解下列运输问题。
（1）
（2）
2、在下面的运输问题中总需要量超过总供应量。假定对销地B1、B2和B3未满足需要量的单位罚款成本是5、3和2。求最优解(方框中的数字是单位运费)。 B1 B2 B3 产量 A1 5 1 7 10
产量 A2 6 4 6 80 B1 B2 B3 A3 3 2 5 15 A1 5 1 6 12
销量 75 20 50
A2 2 4 0 14 A3 3 6 7 4 3、在下面的不平衡运输问题中，如果产销量 9 10 10 地i有一个单位未运出，就要发生单位存储成本。假定在产地A1，A2，A3的单位存储成本是5、4和3。又假定产地A2的供应量必须全部运出，求最优解(方框中的数字是单位运费)。
B1 B2 B3 产量
A1 1 2 1 20
A2 0 4 5 40
A3 2 3 3 30
销量 30 20 20 4、已知某运输问题的供
需关系及单位运价表如下表所示。
B1 B2 B3 产量
线性规划与单纯形法 - 图文
