2017年湖北工业大学电气与电子工程学院910运筹学考研冲刺密押题
● 摘要
一、简答题
1． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐，即可求出目标规划的满意解。 次求解k 个线性规划（k 为优先级的个数）
2． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点的割平面（不见得一次就找到）
恰好是问题的最优解。
3． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
4． 什么是可行流?
【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j
）对于起点Vs ，记对于终点V t ，记
（2）平衡条件 对于中间点，流出量=流入量，即对每个
式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。
二、计算题
5． 某一运输问题的初始基可行解如表所示，括号内数据为非基变量的检验数，试确定新的基可行解。
表
【答案】选择空格A 2B 3，对其所在回路进行调整，调整量为min （5，30）=5，得新的基可行解如下:
表
6． 设有三种资源，每单位的成本分别为a ，b ，c ，给定的利润函数为ri （xi ，yi ，zi ）（i=1，2，…，n ），现有资金为，应购买各种资源多少单位分配给n 个行业才能使总利润最大，试给出动态规划的公式，并写出它的一维递推关系式。
【答案】由题意，可建立该问题的数学模型为:
按n 个行业划分为n 个阶段。阶段变量k=l，2，…，n ，第k 阶段为第k 个行业分配资源; 状
态变量为第1至第k 个行业的总金额; 决策变量（x k , y k , z k ）为第k 个行业所用三种资源的数
;
最优值函数
在状态
下从第1
量; 状态转移方程为:
阶段至第k 阶段的最大利润。
动态规划的一维递推关系式为:
7． 两家工厂x 1和x 2生产一种商品，商品通过如图所示的网络运送到市场y 1，y 2，y 3，试用标号法确定从工厂到市场所能运送的最大总量。
图
【答案】增加v s 和v t 令所有弧上可行流为零，同时给图中的中间点标上名称，如图所示。
图
用网络流的标号算法求该问题的最大流。 步骤一
到标号。
（2）调整过程。找到一条增广链为整，得到新的可行流
。
，如图所示，，进行流量调
相关内容
相关标签