招生专业：管理科学与工程

考试科目：运筹学

考试时间：3小时

一、填空题（每空格2分，共28分）

1．线性规划问题的可行解X=（ ， ，．．． ） 为基本可行解的充要条件是X的正分量对应的系数列向量是                    。

2．单纯形法中，要把数学模型化为标准型，须引入           ；若约束条件中附加变量的系数是             或原约束为         ，则必须引入         ，以构成初始可行基。

3．0-1规划的隐枚举法的基本思想是从所有变量等于     出发，依次指定一些变量为     ，直到得到一个可行解。

4．目标规划中， 和 分别表示           变量；对于第i个目标约束 （X）+ — = ，若希望 （X）≤ ，则目标函数为               。

5．建立目标规划的数学模型时，需要排定各目标的         ，确定各目标值 ，各权系数 。

6．动态规划模型中，状态变量的选择要能满足两个条件：             和               。

7．动态规划中，对于一个给定的问题，如果有固定的           和         ，则顺序递推和逆序递推会得到相同的最优结果。

二、计算题（共40分）

1．  已知线性规划的数学模型如下，请用图解法求该模型的最优解。（10分）

max Z=4 + 7

7 +13 ≤182

5 +3 ≤60

≥0，（i =1，2）

2．  采用隐枚举法求解0-1规划问题（15分）

min Z=16 + 10 +17

4 +2 ≤6

5 +2 + ≥2

4 –2 + 3 ≤7

5 +2 +3 ≥1

， ， =0或1

   3．已知线性规划的数学模型如下，请写出对偶问题的数学模型，并求其对偶问题的最优解。（15分）

max Z=5 + 3 +6

+2 + ≤18

2 + + 3 ≤16

+ + =10

 ， ≥0， 无约束

三、应用题（共70分）

1．某农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。各种作物每亩需施肥料分别为0.12吨、0.2吨、0.15吨。预计秋后玉米每亩可收获500千克，售价为0.24元/千克，大豆每亩可收获200千克，售价为1.20元/千克，小麦每亩可收获300千克，售价为0.70元/千克。农场年初规划时依次考虑以下的几个方面：

P1：年终收益不低于350万元；

P2：总产量不低于1.25万吨；

P3：小麦产量以0.5万吨为宜；

P4：大豆产量不少于0.2万吨；

P5；玉米产量不超过0.6万吨；

P6：农场现能提供5000吨化肥，若不够，可在市场高价购买，但希望高价采购量愈少愈好。试建立该目标规划问题的数学模型（不需要求解）。（16分）

2．现指派五位员工去完成五项不同的工作，每人做各项工作所需费用（元）如下表所示。问应该如何指派，才能使总的费用最小？相应的总费用为多少？（16分）

3．某农场生产四种农作物，每种农作物的成本和利润如下：

目前农场有400公斤肥料和500公斤杀虫剂，问每种农作物种植多少亩才使利润最大？（20分）

4．已知四个城市间的距离如下表所示，求从A城市出发，经其余城市一次且仅一次，最后返回到A城市的最短路径与距离。（18分）

四、证明题（12分）