2016年浙江工商大学信息学院830运筹学考研内部复习题及答案
● 摘要
一、填空题
1． 无向连通图G 是欧拉图的充要条件是___。 【答案】G 中无奇点
2． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_。
【答案】均有 【解析】若存在实数
，使对于任意的
，就称方向
）为
均有下式成立:
点的一个下降方向。
3． 若x 为某极大化线性规划问题的一个基可行解，用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。 【答案】
。
【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以
4． 当极大化线性规划模型达到最优时。某非基变量x j 的检验数为马. 当价格系数为c j 的变化量为△c j 时，原 线性规划问题最优解保持不变的条件是_____。 【答案】
，极大化
【解析】x j 为非基变量，其价格系数变化△c j 后，其检验数变为
二、计算题
5． （1）试用最速下降法求解【答案】（1）
，选初始点
，用最速下降法迭代计算的过程如表所示。
表
，要求做
三次迭代，并验证相 邻两步的搜索方向正交。（2） 试用牛顿法重解习题.
由上表中各布的搜索方向（4, -4, 4）, （1, -1, -2）,
索迭代方向正交。
第 2 页，共 29 页
可知，相邻两步的搜
（2）有
因为f （x ）为二次函数，所以又
，进一步计算f （X ）的H （X ）得
，
6． 写出下列问题的动态规划的基本方程。
【答案】（l ）设状态转移方程为状态s k 到第n 阶段使
，最优值函数
最大的值，则动态规划的基本方程为:
，或
（2）设状态变量为表示
在s k 状态下从第k 阶段到第n 阶段使
最小的值，则动态规划的基本方程为:
第 3 页，共 29 页
表示从第k 阶段
，状态转移方程为
，最优值函数
7． 设有三个电视机厂生产同一种彩色电视机，日生产能力分别是:50，60，50（台），供应三个，从各分厂运往个门市部的单位运费如表所示，试安门市部，日销售量分别是:60，40，60（台）
排一个运费最低的运输计划。 若工厂1到门市部1的运价由9减为6，试寻求最优运输计划。
表
【答案】（l ）此问题是运输平衡问题。 第一步，用伏格尔法寻找得到初始基可行答:
表
第二步，用位势法计算各空格处的检验数为:
表
从所有非基变量的检验数可以看出都是非负数，其中存在一个0的检验数，说明该题有多重最优解。
（2）若工厂1到门市部1的运价由9减到6时，代入计算得第一步，用伏格尔法寻找得到初始基可行
表
第二步，用位势法计算各空格处的检验数为:
表
第 4 页，共 29 页