运筹学期末考试题

一、填空题（每小题3分,共15分）

1. 用单纯形法求解线性规划问题时,单纯形表中的每个解对应的是线性规划问题的一个 ,与图解法中其 一一对应。 2. 在对偶单纯形法中，确定换入变量时采用的是最小比值规则（θ规则）,采用该规则的主要目的是保证对偶问题的解总是 。 3. 用表上作业法（运输单纯形法)解运输规划模型时,作业表应满足的两个基本条件是 . 4. 在动态规划模型中，状态变量表示每个阶段 时所处的自然状况或客观条件,它要满足 的特性。 5. 若解整数规划的单纯形表的最终表中有约束行为:x1128x3x4，其453中x1为基变量，则其对应的割平面方程为 。

二、单项选择题（每题3分，共15分）

1、 下面哪一个表达式可以作为目标规划的目标函数 A、mind1d1 B、maxd1d1 C、mind1d1 D、maxd1d1

2、 线性规划问题可行域的每一个顶点，对应的是一个 . A、基本可行解 本解

3、 在整数规划割平面方法最终单纯形表中得到的一个各变量之间关系式为

418x1x2x3，则其确定的割平面方程为 。

5

B、非可行解

C、最优解

D、基

113133113x2x3 B、x2x3 C、x2x3 D、A、555113x2x3 5

4、 已知某个含10个节点的树，其中9个节点的次为1，1，3，1，1,1，3，1，3，另一个节点的次为 . A、1

5、 用标号法寻找网络最大流时，发生标号中断(没有增广链），这时若用V表示

已标号的节点的集合，用V表示未标号的节点集合,则在网络中所有V→V方向上的弧有 .(f为当前流，c为弧的容量） A、 fc

B、fc

C、fc

D、f0

B、4

C、3

D、2

三、已知线性规划问题（第一问8分,第二问7分，共15分)

minz2x1x22x3x1x2x34 xxx6123x0,x0,x无约束231（1） 写出其对偶问题.

（2） 其原问题的最优解为x15,x20,x31，根据对偶性质直接求解

对偶问题的最优解。

四、(共20分，其中第1、3问各7分，第2问6分） 某厂用两种原材料生产两

种产品，已知数据见表1，根据该表列出的数学模型如下，加松弛变量,并用单纯形法求解得最终单纯形表见表2

表1: 原材料A（kg/件) 原材料B（kg/件） 收入（元 / 件） 产品I 产品II 资源 2 2 3 3 1 2 14 9 表2： CB 2 3 XB x2 x1 cj – zj b 5/2 13/4 x1 0 1 0 x2 1 0 0 x3 1/2 -1/4 -1/4 x4 —1/2 3/4 —5/4 maxz3x12x22x13x2142x1x29 x0,x021 (1）求c1 的变化范围以使最优解保持不变. （2）现在市场上原材料B的价格为1元，问是否需要买入原材料B，为什么？ （3）如果需要买入原材料B,最多买入多少？