上交作业课程题目可以打印，答案必须手写，否则该门成绩0分。
管理运筹学 作业题
一、名词解释(每题3分，共15分)
1. 可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一
组决策变量的取值，都称为该线性规划的一个可行解，所有可行解构成的集合称为该线性规划的可行域（类似函数的定义域），记为K 。
2. 最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称
为该线性规划的一个最优解。
线性规划的最优解不一定唯一，若其有多个最优解，则所有最优解所构成的集合称为该线性规划的最优解域。
3. 状态：指每个阶段开始时所处的自然状态或客观条件。
4. 决策树：决策树(Decision Tree ）是在已知各种情况发生概率的基础上，通过构成决策
树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。
由于这种决策分支画成图形很像一棵树的枝干，故称决策树。
5. 最大最小准则：最大最小准则又称小中取大法或悲观法。
为不确定型决策的决策准则之
一，其决策的原则是“小中取大”。
这种决策方法的思想是对事物抱有悲观和保守的态度，在各种最坏的可能结果中选择最好的。
决策时从决策表中各方案对各个状态的结果选出最小值，即在表的最右列，再从该列中选出最大者。
这种方法的基本态度是悲观与保守。
其基本思路是首先找出最不利情况下的最大收益。
二、 简答题（每题6分，共24分） 1. 简述单纯形法的基本步骤。
答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数j σ对初始基可行解进行最优性检验，若0≤j σ ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至0≤j σ，求得最优解为止。
2. 简述动态规划的基本方程。
答：对于n 阶段的动态规划问题，在求子过程上的最优指标函数时，k 子过程与k+1过程有如下递推关系：
对于可加性指标函数，基本方程可以写为
n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)}(),({)(11)
( =+=++∈
终端条件：f n+1 (s n+1) = 0
对于可乘性指标函数，基本方程可以写为
n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)}
(),({)(11)
( =⨯=++∈
终端条件：f n+1 (s n+1) = 1
3. 简述破圈法求最小生成树的步骤。
答：第1 步: 令i=1, E0=Φ, G0=G;第2 步: 取边ei ∈E ( Gi- 1) 即E\Ei- 1, 令Ei =Ei- 1∪{ei}, 使得Gi= G [E\Ei] 连通, 且W ( ei) 权尽可能大; 第3 步: 若i<e- n+1, 令i=i+1, 返回第2 步,否则, Gi= G [E\Ei] 把Ei 中的边全部删除, 即是所求的最小支撑树。
4. 如何找计划网络图的关键路线？
答：关键线路就是由总时差为0的工作所组成的、各工作总的持续时间最长的线路。
(1)利用关键工作确定关键线路。
总时差最小的工作为关键工作。
将这些关键工作相连，并保证相邻两项关键工作之间的时间间隔为零而构成的线路就是关键线路。
(2)利用相邻两项工作之间的时间间隔确定关键线路。
从网络计划的终点节点开始，逆着箭线方向依次找出相邻两项工作之间时间间隔为零的线路就是关键线路。
三、计算题（1题13分，2、3、4题16分，共61分）
1. 利用单纯形法求下列线形规划问题的最优解
21x x 2z m ax +=
t s . ⎪⎪⎩
⎪⎪⎨⎧≥≤+≤+0x ,x 24x 2x 615x 5x 3212
121
解：（1）加入松弛变量43,x x 得到该线形规划问题的标准型
212m ax x x z +=
⎪⎩⎪
⎨⎧≥=++=++0,,,242615
534
321421321x x x x x x x x x x
最优解T
X )0,0,4/3,4/15(*
=，4/33*
=Z
2. 某工厂要用三种原料A 、B 、C 加工成三种不同规格的产品甲、乙、丙。
已知三种产品中A 、B 、C 原料的规格要求及三种产品的销售价格，见表1。
同时已知三种原料成本和各种原料的月供应量，如表2所示。
问：该厂应如何安排生产，使其利润为最大？试建立这个问题的数学模型。
表1
表2
解：设xij 为生产i 种面包所使用的j 种原材料数，i=1，2，3分别代表甲、乙、
丙，j=1，2，3分别代表A 、B 、C 。
其数学模型为：
max z=(3.40-0.50)(x11+x12+x13)+(2.85-0.40)(x21+x22+x23)+(2.25-0.30) (x31+x32+x33)-2.00(x11+x21+x31)-1.50(x12+x22+x32)-1.00(x13+x23+x33)
3. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如表3所示。
问这5台设备应如何分配给这3个工厂，使得所创造的总利润最大？
工厂
盈利
甲厂乙厂丙厂设备台数
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12 解：
4. 某电信公司准备在甲、乙两地沿路架设一条光缆线，下图给出了甲乙两地间的交通图，权数表示两地间公路的长度，利用Dijkstra算法分析如何架设使其光缆线路最短？（单位：公里）。
v 2
3
5 2
7
5
3
1
5
1
2
v 1
甲地
v 6
乙地
v 5
v v 4。