《管理运筹学》作业题。
一、名词解释(每题3分，共15分)
1. 可行解满足所有约束条件的解。
2. 最优解在可行域中使目标函数达到最优的可行解。
3. 状态每个阶段开始时所处的自然状况或客观条件。
4. 决策树一种由结点和分支构成的由左向右展开的树状图形。
5. 最大最小准则决策者从最不利的角度去考虑问题，先选出每个方案在不同自然状态下的最小收益值（最保险），选这些最小收益值中的最大值对应的方案为行动方案。
二、 简答题（每题6分，共24分）
1. 简述单纯形法的基本步骤。
答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数对初始基可行解进行最优性检验，若，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至，求得最优解为止。
2. 简述动态规划的基本方程。
答：对于n阶段的动态规划问题，在求子过程上的最优指标函数时，k子过程与k+1过程有如下递推关系：
对于可加性指标函数，基本方程可以写为。
终端条件：fn+1 (sn+1) =0
对于可乘性指标函数，基本方程可以写为。
终端条件：fn+1 (sn+1) =1
3. 简述破圈法求最小生成树的步骤。
答：（1）在给定的赋权的连通图上任找一个圈。
（2）在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。
（3）如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。
4. 如何找计划网络图的关键路线？
答：（1）绘制计划网络图；（2）从网络的始点开始，按顺序计算出每个工序的最早开始时间（es )和最早结束时间（ef) ；3）从网络的终点开始，计算出在不影响整个工程最早结束时间的情况下，各个工序的最晚开始时间(缩写为ls)和最晚结束时间（缩写为lf)；（4）计算出每一个工序的时差ts；（5）时差等于零的工序为关键工序。把关键工序依次从始点到终点连接成的路线确定为关键线路。
三、计算题（1题13分题16分，共61分）
1. 利用单纯形法求下列线形规划问题的最优解。
1.解：（1）加入松弛变量得到该线形规划问题的标准型。
2）利用单纯形表逐步迭代。
最优解， 2. 某工厂要用三种原料a、b、c加工成三种不同规格的产品甲、乙、丙。已知三种产品中a、b、c原料的规格要求及三种产品的销售**，见表1。
同时已知三种原料成本和各种原料的月**量，如表2所示。问：该厂应如何安排生产，使其利润为最大？
试建立这个问题的数学模型。表1表2
解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。
对于甲： x11，x12，x13；
对于乙： x21，x22，x23；
对于丙： x31，x32，x33；
对于原料a： x11，x21，x31；
对于原料b： x12，x22，x32；
对于原料c： x12，x23，x33；
目标函数：max z = 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）
约束条件：x11 ≥0.6(x11+x12+x13)
x12 ≤0.20(x11 +x12+x13)
x21 ≥0.15(x21 +x22+x23)
x22 ≤0.6(x21+x22+x23)
x33≥0.50(x31+x32+x33)
(x11+x21+x31)≤3000
(x12+x22+x32)≤3000
(x12+x23+x33)≤1800
3. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，**可创造的利润如表3所示。问这5台设备应如何分配给这3个工厂，使得所创造的总利润最大？
表3解：该问题分为三个阶段，甲、乙、丙三厂分别为1,2,3阶段。
设：sk为没阶段初所拥有的设备台数。
xk为分配给第k个工厂的设备台数。
状态转移方程s2=s1-x1; s3=s2-x2
利用逆序法计算：
第3阶段计算结果见表1
表1第2阶段计算结果见表2
表2第1阶段计算结果见表3
表3按照计算的顺序推算可知最高的盈利为21万元。最优分配方案有两个：
1）分配给甲厂0台，乙厂2台，丙厂3台。
2）分配给甲厂2台，乙厂2台，丙厂1台。
4、某电信公司准备在甲、乙两地沿路架设一条光缆线，下图给出了甲乙两地间的交通图，权数表示两地间公路的长度，利用dijkstra算法分析如何架设使其光缆线路最短？（单位：公里）。
解：（1）给起点v1标号[0，v1]
（2）把结点集v分成两个集合： va:已标号点集；vb：未标号点集。
(3)考虑所有这样的边[vi ,vj]，其中vi∈va ,vj ∈vb（所有已标结点指向未标号结点的边）,挑选其中与起点v1距离最短的vj，对vj进行标号。
4）重复（2）、（3），直至终点vn表上号[dn,vi]，则dn即为v1至vn的最短距离，反向追踪即可求出最短路。
最短路线为v1 v3 v4 v6,最短距离为8公里。
管理运筹学
工程技术学院。管理运筹学 上机报告。2010 2011第2学期。指导教师彭艳 班级 市销 6 0 9 0 1 姓名 武逻浩 学号 2 0 0 9 6 0 5 2 2 管理系。管理运筹学上机报告。1 p34 习题一。图 11 解 x1 150 x2 70 是最优组合最大利润是103000 2 解 第一...
管理运筹学
基于线性规划法的。物流运输成本控制研究。姓名 崔婷婷。学号 12115040 学院 商学院。基于线性规划法的物流运输成本控制研究。摘要 在全球化经济发展的今天，企业之间竞争日益激烈。运输作为现代物流的必要环节之一，同时运输成本在物流成本中也起着举足轻重的作用，因此，如何控制运输成本便成了降低物流成本...
管理运筹学
班级会计1303 姓名彭艺。学号201307270322 指导老师黄毅。某农户年初承包了40亩土地，并备有生产专用资金25000元。该户劳动力情况为 春夏季4000工时，秋冬季3500工时。若有闲余工时则将为别的农户帮工，其收入为 春夏季5元 工时，秋冬季4元 工时。该户承包的土地只适宜种植大豆 玉...