第1章 线性规划与单纯形法
1、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。
(a)minz?2x1?3x?4x1?6x2?6 ??4x1?2x2?4?x，x?02?1(c)maxz?x1?x2?6x1?10x2?120 ?
5?x?10?1?3?x2?8?2(b)maxz?3x1?2x?2x1?x2?2 ?? 3x1?4x2?12?x,x?012?(d)maxz?5x1?6x?2x1?x2?2???2x1?3x2?2?x,x?012?2
2
2、用单纯形法求解下列线性规划问题。
(a)maxz?10x?3x1??5x1?x,?1?4x?2xx2?221?5x(b)maxz?2x1?x22??0?9? ?6x1?8??x1??x,?15x2x22????1524 50x2x23、用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。 (a)maxz?2x1?x2?2x?x1? ??2x1???x1,??x22x?x3?x323?x3x3x2,?x1?2 ??3x1?0?x,?1?0?6(b)minz?2x1?3x?4x?2xx2,2223?x3?8?6?2x
x3?04、已知线性规划问题的初始单纯形表（如表1所示）和用单纯形法迭代后得到的表（如表2所示）如下，试求括弧中未知数a～l的值。 表1
x4 x5 cj-zj 表2 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) 6 1 x1 (b) -1 (a) x2 (c) 3 -1 x3 (d) (e) 2 x4 1 0 0 x5 0 1 0
5、某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据见下表，试安排最优生产计划，使该厂获利最大。
设备 产品 Ⅰ 5 7 6 4 7 Ⅱ Ⅲ 设备有效台时 设备加工费 （元/小时） A1 A2 B1 B2 B3 10 9 8 12 11 6 000 10 000 4 000 7 000 4 000 0.05 0.03 0.06 0.11 0.05 原料费（元/件） 售价（元/件） 120.25 1.25 0.35 2.00 0.50 2.80 6、若X、X均为某线性规划的最优解，证明这两点连线上的所有点也是该问题的最优解。
7、线性规划问题 maxz?CX,AX?b,X?0，如果X*是该问题的最优解，又 ??0为某一常数，分别讨论下列情况时最优解的变化？
第2章 对偶问题和灵敏度分析
1、写出下列线性规划问题的对偶问题。 (a)minz?2x1?2x?3x2?x1??x2?2x1?x?4x2?1?x,x?0,?12?4x?3x3x3233?4x3?2?3 ?5x3无约束
n(b)maxz??cj?1jxj?n(i?1,?,m1?m)??aijxij?bi1?j? n??ax?bi(i?m1?1,?,m)??ijjj?1?(j?1,?,n1?n)?xj?0?(j?n1?1,?,n)??xj无约束2、已知线性规划问题：
maxz?x1?x2?x2?x3??x1 ???2x1?x2?x3?x，x，x?023?1?2?1
试应用对偶理论证明上述线性规划问题最优解为无界。 3、已知线性规划问题：
maxz?2x1?4x2?x3?x4????8669?3x2?x4?x1?2x1?x2? ?x2?x3?x4??x?x2?x3?1(j?1,?,4)??xj?0
要求：（1）写出其对偶问题；（2）已知原问题最优解为X=(2,2,4,0)，是根据对偶理论直接
求出对偶问题最优解。 4、已知线性规划问题：
maxz?2x1?x2?x3*
?1??x1?x?x2?x3?2x2?6 ?4?x,x,x?0?123先用单纯形法求出最优解，再分析在下列条件单独变化的情况最优解的变化。 （1）目标函数变为maxz?2x1?3x2?x3； （2）约束右端项由??变为??；
?4??4??6??3?（3）增添一个新的约束条件：?x1?2x3?2。
5、 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：(1)确定获利最大的产品生产计划；(2)产品A的利润在什么范围内变动时，上述最优计划不变；(3)如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产?(d)如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。 消 耗 定 资 源 额 产 品 A B C 6 3 5 可用量（单位） 45 劳动力 材料 产品利润（原/件）
3 4 5 3 1 5 30 第三章 运输问题
1、应用最小元素法和伏格尔法求解下列运输问题。
（1）
B1 A1 A2 A3 销量
（2） B1 A1 A2 A3 销量 5 2 3 9 B2 1 4 6 10 B3 6 0 7 10 产量 12 14 4
1 0 3 10 B2 2 4 1 10 B3 6 2 5 10 产量 7 12 11
2、在下面的运输问题中总需要量超过总供应量。假定对销地B1、B2和B3未满足需要量的单位罚款成本是5、3和2。求最优解(方框中的数字是单位运费)。
3、在下面的不平衡运输问题中，如果产地i有一个单位未运出，就要发生单位存储成本。假定在产地A1，A2，A3的单位存储成本是5、4和3。又假定产地A2的供应量必须全部运
A1 A2 A3 销量 B1 5 6 3 75 B2 1 4 2 20 B3 7 6 5 50 产量 10 80 15 出，求最优解(方框中的数字是单位运费)。
4、已知某运
A1 A2 A3 销量 B1 1 0 2 30 B2 2 4 3 20 B3 1 5 3 20 产量 20 40 30 输问题的供
需关系及单位运价表如下表所示。
A1 A2 A3 B1 4 3 1 B2 2 5 3 B3 5 3 2 产量 8 7 4
销量 4 8 5
要求：(a)用表上作业法找出最优调运方案；(b)分析从A1到B1的单位运价c11的可能变化范围，使上面的最优调运方案保持不变；(c)分析使该最优方案不变时从A2到B3的单位运价c23的变化范围。
5、某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机．已知该厂各季度的生产能力及生产每台柴油机的成本如下表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元．要求在完成合同的情况下，做出使该厂全年生产(包括储存、维护)费用最小的决策．
季度 Ⅰ Ⅱ Ⅲ Ⅳ
第四章 整数规划
1、试利用0-1变量对下列各题分别表示成一般线性约束条件。 (a) x1+x2≤2或2 x1+3x2≥5
(b) 变量x只能取值0、3、5或7中的一个 (c) 若x1≤2，则x2≥1，否则x2≤4
(d) 以下四个约束条件中至少满足两个：
x1+ x2≤5， x1≤2， x3≥2， x3+x4≥6
2、 已知分配问题的效率矩阵如下，试用匈牙利法分别求出最优解。
生产能力（台） 25 35 30 10 单位成本（万元） 10.8 11.1 11.0 11.3