2017年兰州大学综合考试之运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大
; 。分支定界法就是将B 的可行域分成
:， 最终求到z*。
按如下规则:
二、计算题
3． 写出下列问题的动态规划的基本方程。
【答案】（l ）设状态转移方程为阶段状态s k 到第n 阶段使
，最优值函数
最大的值，则动态规划的基本方程为:
，或
（2）设状态变量为表示
第 2 页，共 35 页
表示从第k
，状态转移方程为
，
最优值函数
在s k 状态下从第k 阶段到第n 阶段使
最小的值，则动态规划的基本方程为:
4． 两家工厂x 1和x 2生产一种商品，商品通过如图所示的网络运送到市场y 1，y 2，y 3，试用标号法确定从工厂到市场所能运送的最大总量。
图
【答案】增加v s 和v t 令所有弧上可行流为零，同时给图中的中间点标上名称，如图所示。
图
用网络流的标号算法求该问题的最大流。 步骤一
到标号。
（2）调整过程。找到一条增广链为整，得到新的可行流
。
，如图所示，
，进行流量调
第 3 页，共 35 页
图
步骤二
（l ）标号过程。对图中的可行流
。V t 得到标号。
（2）调整过程。找到一条新的增广链，在
上调整流量，得新的可行流
，如图所示。
，如图中双箭头所示，
令
进行重新标号:
图
步骤五
（l ）标号过程。将图重新标号:
v t 得到标号。
（2）调整过程。在增广链新的可行流
，如图所示。
上，令
调整流量，于是得
第 4 页，共 35 页
相关内容
相关标签