大连大学2010/2011学年第一学期期中考试卷
考试科目： 运 筹 学
(考试时间90分钟)（共4页）
题号
一
二
总得分
1 2 1 2 3 4 得分
一、用图解法求解（10分） 给定下述线性规划问题：
12max 2z x x =-
121212
433
3,0x x x x x x -+≤⎧⎪
-≤⎨⎪≥⎩ 画出其可行域并找出其最优解。 解:可行域:
最优解为(3,0), 3z *
=
二、模型转换（10分）
写出下列线性规划问题的对偶问题
23
11
min ij ij
i j z c x
===
∑∑
姓 名 学 号 学 院 专 业 班 级
密
封
线
适用专业 工程管理 适用年级
08 考试形式 闭
卷
送卷单位
任课教师
总印数
教研室主任
教学院长
11121314121222324
2112111222213233142440ij x x x x a x x x x a
x x b x x b x x b x x b x +++=⎧⎪+++=⎪⎪+=⎪
+=⎨⎪+=⎪
+=⎪⎪≥⎩
一切
解：112211223344max w a u a u b v b v b v b v =+++++
111112121313142121222223232412123400,,,,,u v c u v c u v c u v u v c u v c u v c u v u u v v v v +≤⎧⎪+≤⎪⎪+≤⎪
+≤⎪
⎪
+≤⎨⎪+≤⎪
+≤⎪
⎪+≤⎪⎪⎩无符号限制
三、计算题（每小题20分，共80分）
1. 用单纯形法求解下列线性规划问题(列出计算过程)。 12min 35z x x =--
12
12128
2123436,0
x x x x x x -≥-⎧⎪≤⎪⎨
+≤⎪⎪≤⎩ 解：标准化：1
234513241
251
23453500082123436,,,,0MaxW x x x x x x x x x x x x x x x x x ''=--+++'-+=⎧
⎪'-+=⎪⎨
''--+=⎪⎪''≥⎩(标准化可分两段，第一步把决策
变量变量，第二步标准化)
列单纯形表计算：
最优解X*=（3，5，0，0,0）T，最优值W*=34,故Z=-34
2. 用单纯形法中两阶段法求解下述线性规划问题(列出计算过程)。(注意步骤，区分人工变量与松驰变量)
12min 4z x x =+
12123
12433436240,1,2,3,4
i x x x x x x x x x i +=⎧⎪+-=⎪⎨++=⎪⎪≥=⎩
解：1)标准化；
'12max 4z x x =--
1212312433
(1)
436(2)
240,1,2,3,4
i x x x x x x x x x i +=⎧⎪+-=⎪⎨
++=⎪⎪≥=⎩
２）在上约束方程组(1)、（2）中加入人工变量，列出第一阶段线性规划问题
将正文中的问题化成标准型：
56min w x x =+
1251236
12433436240,1,2,3,4,5,6
i x x x x x x x x x x x i ++=⎧⎪+-+=⎪⎨
++=⎪⎪≥=⎩ 3)
4)因为第一阶段目标函数值为0，做去掉人工变量，写出第二阶段目标函数为
1234max 400z x x x x =--++，继续用单纯形法求解
故有唯一最优解(,,1,0,0,0),55
5
X Z *
*
==
3. 用对偶单纯形法求解下述线性规划问题(列出计算过程)。(此问题不是加人工变量，而是根据对偶理论，在保持对偶问题为可行解的基础上，通过迭代，使原问题也达到可行解，即得到了目标函数的最优解。)
123min 41218z x x x =++
1323123
33225,,0x x x x x x x +≥⎧⎪
+≥⎨⎪≥⎩
解：先将问题改写为：
12345max 4121800w x x x x x =---++
134235332250,1,2,3,4,5i
x x x x x x x i +-=⎧⎪
+-=⎨⎪≥=⎩ 约束条件两端乘“-1”得：
12345max 4121800w x x x x x =---++
134235332250,1,2,3,4,5i
x x x x x x x i --+=-⎧⎪
--+=-⎨⎪≥=⎩
4. 已知某运输问题的产销数量表与单位运价表如表4-1，用表上作业法求最优解(列出计算过程)。
表4-1
解：1.|最小元素法的初始方案
（注：括弧中的数位检验数，下同）
闭回路法调整（调整结果与V ogel法的初始方案一致）：
2.V
