第二部分 南开大学其他学院运筹学历年考研真题 2012年南开大学商学院915运筹学考研真题
2011年南开大学商学院915运筹学考研真题
2011年南开大学商学院915运筹学考研真题及详解
南开大学2011年硕士研究生入学考试试题
学 院：140商学院 考试科目：897运筹学（商学院）
专业：管理科学与工程
一、某厂生产A、B两种产品，需经过金工和装配两个车间加工，有关数据如表1所示．产品B无论生产批量大小，每件产品生产成本总为400元。产品A的生产成本分段线性：第1件至第70件，每件成本为200元；从第71件开始，每件成本为190元。试建立线性整数规划模型，使该厂生产产品的总利润最大。（本题共15分）
?1，当x1?71答：设x1，x2为产品A、B的个数，???
?0，当x2?70则建立线性整数规划模型如下： 二、现有一个线性规划问题（p1） maxz1＝CX
其对偶问题的最优解为Y*＝（y1，y2，y3，…，ym）。另有一线性规划（p2）： maxz2＝CX
其中，d＝（d1，d2，…，dm）T。求证：maxz2≤maxz1＋Y*d（南开大学2011年研）
证：问题1的对偶问题为： 问题2的对偶问题为：
易见，问题1的对偶问题与问题2的对偶问题具有相同的约束条件，从而，问题1的对偶问题的最优解
***Y*??y1,y2,L,ym?一定是问题2的对偶问题的可行解。
令问题2的对偶问题的最优解为Y2*，则Y2*?b?d??Y*?b?d??Y*b?Y*d。 因为原问题与对偶问题的最优值相等，所以：
三、某工厂计划生产甲、乙、丙3种产品，各产品需要在设备A、B、C上进行加工，其所需加工小时数、设备的有效台时和单位产品的利润表2所示。
请回答下面三个问题：（本题共20分，其中第一小题10分，后两小题各5分）
1．如何安排生产计划，可使工厂获得最大利润?
2．若每月可租用其他工厂的A设备360台时，租金200万元，问是否租用这种设备?若租用．能为企业带来多少收益?
3．若另外有一种产品，它需要设备A、B、C的台时数分别为2、1、4，单位产品利润为4万元，假定各设备的有效台时数不变，投产这种产品在经济上是否合算?
答：1．设生产甲、乙、丙三种产品各为x1，x2，x3单位.，则由题意得： 加入松弛变量后，利用单纯形法计算如下： cj CB 0 0 0 4 0 0 4 3 0 单位。
?0?获得最大利润z=?2,4,3??200/3??766.7（万元）
????500/3??2 b 600 400 800 150 250 350 200/3 500/3 x1 3 2 1 2 3/4 5/4 －5/4 －1 1/3 5/6 －4/9 4 x2 [4] 1 3 4 1 0 0 0 1 0 0 0 3 x3 2 2 2 3 1/2 [3/2] 1/2 1 0 1 0 0 0 x4 1 0 0 0 1/4 －1/4 －3/4 －1 1/3 －1/6 －2/3 －5/6 0 x5 0 1 0 0 0 1 0 0 －1/3 2/3 －1/3 －2/3 0 x6 0 0 1 0 0 0 1 0 0 0 1 0 XB x4 x5 x6 x2 x5 x6 x2 x3 x6 800/3 －3/5 因此已得到最优解，即不生产产品甲，乙和丙的产量分别为200/3，和500/32．即?b??360,0,0?，此时，各非基变量的检验数不发生变化，故最优基B
T不改变。
?0?z???2,4,3??560/3??1066.7（万元）；
????320/3???z?z??z?1066.7?766.7?300（万元）； 为企业带来收益300－200＝100（万元）。
3．设这种产品产量为x7单位，则约束方程增加一列向量???2，1，4?
T? 1/3 -1/3 0??2??1/3???1???1/3? ?1/6 2/3 0在最终单纯性表为???B?1????????????2/3 -1/3 1????4????7/3??故投产这种产品合算。
四、某科学试验可用1#、2#，3#三套不同仪器中的任一套去完成。每做完一次试验后．如果下次仍用原来的仪器，则需要对该仪器进行检查整修而中断试验：如果下次换用另外一套仪器，则需拆装仪器。也要中断试验。假定一次试验时间比任何一套仪器的整修时间都长，因此一套仪器换下来隔一次再重新使用时，不会由于整修而影响试验。设i#仪器换成j#仪器所需中断试验的时间为tij，如表3所示。现要做4次试验，问应如何安排使用仪器的顺序，使总的中断试验的时间最小?（本题共20分）
答：设A、B、C分别代表三套仪器1#、2#，3#，Ai表示在第i次实验中用仪器A，依此类推Bi、Ci，并设虚拟开始S和结束点D。则得如下网络图：
A1
9 14 0 B9 S 0 1 10 0 6 5 8 C1
10 12 A2
10 A3
C2
14 9 B2 9 12 10 6 5 8
C3
14 B3 9 12 10 6 5 8
10 9 A4
0
B4 0 0
C4
D
求总的中断试验的时间最小，即找最短路问题，利用Dijkstra算法计算如下： （1）j＝0，S0＝{S}，P（S）＝0
∵A1，B1，C1到S点距离相同，∴可同时标号。
（A1/B1/C1）=S。 则S1＝（S、A1、B1、C1），?（2）j＝1
则S2＝（S、A1、B1、C1、A2、B2、C2）