习题参考

习题一

一、 填空题（15）

1．在求极小值的线性规划问题中，松弛变量在目标函数中的价值系数为 ，人工变量在目标函数中的价值系数为 。

2. 某极小化线性规划问题（P）一个“≤”型的约束所对应的（P）对偶问题的决策变量 0，（P）中的一个取值“≤0”的决策变量对应了（P）对偶问题的一个 型约束。 3. 在线性规划的迭代过程中， 保证经过一次迭代得到的仍是基可行解。

4. 若整数规划MaxZx1x22x1x264x15x220x1,x20且x1，x2为整数2时均取得最优解，则其最优解x* ，, 在x10，f(x*) 。

5. 用动态规划求解某生产计划问题。已知第一期期初库存为0，第五期期末库存也必须是0，每期的生产数量不少于5，决策变量xk表示第k期生产量，状态变量vk表示第k期末库存量，则第三期的状态变量v3的取值范围是 。（已知第1~5期市场对产品的需求量分别为2，4，3，4，4。） 二、选择题（15）

1.关于线性规划的可行解和基解，下面 叙述正确。

A. 可行解必是基解； B.基解必是可行解

C. 可行解必然是非基变量为0，基变量均非负； D.非基变量均为0得到的解均为基解。 2.下列规定中， 是绘制网络图时可以不遵循的。

A. 网络图只能有一个起始点及一个终止点； B. 网络图中的有向边不允许交叉；

C. 网络图中不允许出现回路； D.任两个结点之间，最多只能有一条有向边。 3.求解总利润最大的运输问题时，下列叙述 正确。

A. 应选择最大检验数对应的非基变量为换入变量；B. 应选择正检验数对应的非基变量为换入变量； C. 应选择最小检验数对应的非基变量为换入变量；D. 应选择负检验数对应的非基变量为换入变量。 4. 对某线性规划问题（P）及其对偶问题（D），下列结果 永远不会同时出现。 A. （P）有可行解，（D）也有可行解； B. （P）无可行解，（D）也无可行解；

C. （P）有无界解，（D）也有无界解； D. （P）有最优解，（D）也有最优解。 5. 一个连通图的最小支撑树 ，该最小支撑树上边的总长度 。

A. 是唯一存在的； B. 可能不唯一； C.可能不存在； D. 一定有多个。 三、 简答题（15）

1. 什么是基解？什么是基可行解？

2. 试比较求解Max化、Min化线性规划问题的单纯形法在最优性判别定理及迭代过程上有何不同（假

设模型中不含人工变量）。

3. 网络计划中作业的四种时差的名称及计算公式是什么？ 4. 在中国邮递员问题的最优解判别定理是什么？ 5.为什么说产销平衡的运输问题必有最优解？ 四、判断对错 （10）

1. 若x为LP的可行解，则x亦为LP的基本解。（ ）

2. 设LP的可行域为D，D非凸集，则LP的最优点必在D的顶点上。（ ）

3. 若LP经过若干次迭代后已得到一退化的最优解，则继续迭代下去必可得到非退化的最优解。（ ） 4． 如果线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最优解。（ ） 5．一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而

不影响计算结果。（ ） 五、计算题 （35） 1. 用对偶单纯形法求解 Minw2x13x2~~x1x21x1x21x1,x20

2. 用单纯形法求解如下目标规划的满意解：

MinwP1(d1d2)P2(d3)  10x115x2d1d140100x1100x2d2d21000x2d3d37x,x,d,d,d,d,d,d0223312113． 出逆序解法求解下列动态规划问题的求解模型：

Maxzgi1ni(xi)

nxic,(c0)i1x0i六、 建模题（10）

某工厂用原料A，B，C加工成三种不同牌号的产品甲、乙、丙。已知各种牌号产品中A，B，C含量，原料成本，各种原料的每月用量，三种牌号产品的单位加工费及售价如表所示：

A B C 加工费（元/千克） 售价 数学模型（不求解）。

甲 ≥60% ≤20% 0.50 3.4 乙 ≥15% ≤60% 0.40 2.85 丙 ≤50% 0.30 2.25 原料成本（元/千克） 2.00 1.50 1.00 每月用量（千克） 2000 2500 1200 问该厂每月应生产这三种牌号产品各多少千克，使该厂获利最大？试建立这个问题的线性规划的

习题二

一、 填空题

1．一般线性规划求解的结果有 种，分别为 。 2. 若线性规划的原问题为Max Z=CX; AX≤b；X≥0，其最优解为 x,则其对偶问题的形式为 ，在最优点的目标函数值为 。

3．求解目标规划问题时，某非基变量的检验数为：-P1+10P2-2P3,该变量可否作为换入变量？ 。 4．若整数规划MaxZx1x2*

2x1x264x15x220x1,x20且x1，x2为整数, 在x10，2时均取得最优解，则其最优解x* ，

f(x*) 。

5. 用动态规划求解某生产计划问题。已知第一期期初库存为0，第五期期末库存也必须是0，每期的生产数量不少于5，决策变量xk表示第k期生产量，状态变量vk表示第k期末库存量，则第三期的状态变量v3的取值范围是 。（已知第1~5期市场对产品的需求量分别为2，4，3，4，4。） 二、 选择题

1．用图解法求解目标函数为 Max Z=2x1+3x2 的线性规划问题时，目标函数等值线应沿 方向移动，可以使目标函数值降低。

A. （2，3）； B. （2，-3）； C. （-2，3）； D.（-2，-3）； 2. 对某线性规划问题（P）及其对偶问题（D），下列结果 永远不会同时出现。 A. （P）有可行解，（D）也有可行解； B. （P）无可行解，（D）也无可行解； C. （P）有无界解，（D）也有无界解； D. （P）有最优解，（D）也有最优解。 3．对产销不平衡的运输问题，设产地有 m个。销地有 n个，则在基可行解中基变量的个数为 。 A. m+n个； B. m+n-1个； C. m+n+1个； D. m+n-2个； 4.一个连通图的最小支撑树 ，该最小支撑树上边的总长度 。

A. 是唯一存在的； B. 可能不唯一； C.可能不存在； D. 一定有多个。 5.在增广链中， 。

A. 所有的前向弧都是饱和弧，所有的后向弧都是零流弧； B. 所有的前向弧都是非饱和弧，所有的后向弧都是零流弧； C. 所有的前向弧都是饱和弧，所有的后向弧都是非零流弧； D. 所有的前向弧都是非饱和弧，所有的后向弧都是非零流弧。 三、 简答题

1． 求解Max化线性规划问题时，在迭代过程中选择最大正检验数对应的非基变量作为换入变量，可以使目标函数值增加最快。这正确吗？说明理由。

2. 试比较求解Max化、Min化线性规划问题的单纯形法在最优性判别定理及迭代过程上有何不同（假

设模型中不含人工变量）。

3. 网络计划中作业的四种时差的名称及计算公式是什么？ 4. 在中国邮递员问题的最优解判别定理是什么？ 5. 为什么说产销平衡的运输问题必有最优解？

四、判断对错 （10）

1. 若x为LP的可行解，则x亦为LP的基本解。（ ）

2. 设LP的可行域为D，D非凸集，则LP的最优点必在D的顶点上。（ ）

3． LP经过若干次迭代后已得到一退化的最优解，则继续迭代下去必可得到非退化的最优解。（ ） 4． 如果线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最优解。（ ） 5．一旦一个人工变量再迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（ ） 五、计算题

1.用对偶单纯形法求解 Minw2x13x2~~x1x21x1x21x1,x20

2. 用单纯形法求解如下目标规划的满意解：

MinwP1(d1d2)P2(d3)  10x115x2d1d140100x1100x2d2d21000x2d3d37x,x,d,d,d,d,d,d0223312113. 写出逆序解法求解下列动态规划问题的求解模型：

Maxzgi1ni(xi)

nxic,(c0)i1x0i六、 建模题

下表给出了A，B，C，D，E五种合金含铅，锌，锡的百分率。现要用这五种合金熔炼成一种含铅，锌，锡含量比例为3：2：5的新合金。求总费用最小的生产方案。只建模型，不求解。

合金 铅含量（%） 锌含量（%） 锡含量（%） 单价（元/kg）

A 30 60 10 8.5 B 10 20 70 6.0 C 50 20 30 8.9 D 10 10 80 5.7 E 50 10 40 8.8