南开大学2004年运筹学考研试卷 下载

南开大学
2004年硕士研究生入学考试试题
考试科目：运筹学
适用专业：运筹学与控制

一、（20分）线性规划的目标函数是maxZ，在用单纯形法求解的过程中得到表1（其中d、e为常数）：
Cj—> 2 5 8 0 0 0
CB XB b x1 x2 x3 x4 x5 x6
x6 20 0 3 0
x2 e d 0.5
x4 8 -2 -1 1
Cj—>zj -2
1、请在表1空白处填上适当的内容；
2、判断以下四种情况在什么时候成立，并简要说明理由。
a）此解为最优解，并写出相应的基解和目标函数值
b）此解为最优解，且词问题有无穷多个最优解；
c）此问题有无界解；
d）此解不是最优解，且能用单纯形法得到下一个基可行解。
其对偶问题最优解为y1=1.2，y2=0.2，试根据对偶理论求出原问题的最优解。
三、（20分）证明：若线性规划问题有可行解，则必有可行解。
四、（20分）试用割平面法求解下面整数规划问题
五（20分）A、B、C三个工厂需要向甲、乙、丙三个地区供应某种物资，三个工厂与三个地区间的单位运价如表2所示。三个工厂的供应能力分别为200公斤、400公斤、500公斤。甲地区的需求量为300公斤，乙地区的需求量最低为200公斤，最高为500公斤，丙地区的需求量最低为200公斤，最高不限。试用表上作业法确定一个调运方案，在保障供应的基础上，使总运费支出最少。
七、（20分）某厂拟将5台数控机床分配给A、B、C三个车间，各车间可用。这些机床创造的利润如表3所示。
问该厂如何分配这些数控机床，才能使总利润最大。要求使用动态规划方法求解。