一、判断题（本题共5小题，每小题３分, 共15分.下列叙述中正确的打√，错误的打×．） 1. 图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的. （ ） 2. 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解. （ ） 3. 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方
案将不会发生变化. （ ）
4. 对于极大化问题max Z =
ij
n i n
j ij
x c
∑∑==11
,令
{}ij ij ij c c b c c -==,max
转化为极小化问题
ij
n
i n
j ij x b W ∑∑===11m in ，则利用匈牙利法求解时，极大化问题的最优解就是极小化问题
的最优解，但目标函数相差： n+c. （ ） 5. 影子价格是对偶最优解，其经济意义为约束资源的供应限制. （ ） 二、填空题(本题共8小题, 每空3分, 共36分.把答案填在题中横线上.)
1、在线性规划问题的约束方程,0m n A X b X ⨯=≥中，对于选定的基B ，令非基变量X N =0，得到的解X= ；若 ，则称此基本解为基本可行解.
2、线性规划试题中，如果在约束条件中出现等式约束，我们通常用增加 的方法来产生初始可行基。
3、用单纯形法求解线性规划问题的迭代步骤中，根据k λ= 确定k x 为进基变量；根据最小比值法则θ= ，确定r x 为出基变量。
4、原问题有可行解且无界时，其对偶问题 ，反之，当对偶问题无可行解时，原问题 。
5、对于Max 型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：
则对应的割平面方程为 。
6、原问题的第1个约束方程是“=”型，则对偶问题相应的变量是 __________ 变量。
7、用LINGO 软件求解整数规划时，要说明变量X 是只可以取0或1的整数变量，则要用___________命令函数。
8、用匈牙利法解分配问题时，当 则找到了分配问题的最优解；称此时独立零元素对应的效益矩阵为 。
三、解答题 (本题共6小题,共49分)
1、已知线性规划问题123
123123123max 34236
347,,0
z x x x x x x x x x x x x =++-++≤⎧⎪-+-≤⎨⎪≥⎩ ，利用对偶理论证明其目标函数值无界。
(8分)
2、试用大M 法解下列线性规划问题。
(8分)
12121212max 35463218,0
z x x x x x x x x =+≤⎧
⎪≤⎪⎨
+=⎪⎪≥⎩ 3、福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下表所示，为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问该如何安排售货人员的休息，既满足了工作需要，又使配备的售货人员的人数最少，请列出此问题的数学模型。
(8分)
4、建立模型题(10分)
在高校篮球联赛中,我校男子篮球队要从８名队员中选择平均身高最高的出场阵容,队员的号码、身高及擅长的位置如下表：
同时，要求出场阵容满足以下条件：
⑴中锋最多只能上场一个。
⑵至少有一名后卫。
⑶如果１号队员和４号队员都上场，则６号队员不能出场
⑷２号队员和６号队员必须保留一个不出场。
问应当选择哪5名队员上场,才能使出场队员平均身高最高?
（1）建立该问题的数学模型；
（2）写出用LINGO软件求解它时的源程序。
5、从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示。
规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。
在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。
(8分)
6、用割平面法求解下面的纯整数规划问题：(7分)
参考答案
一、判断题（本题共5小题，每小题３分, 共15分. 下列叙述中正确的打√，错误的打×．） ××√×√
二、填空题(本题共8小题, 每空3分, 共36分.把答案填在题中横线上.)
1、10B b -⎛⎫ ⎪⎝⎭
，1
0B b -≥ 2、人工变量 3、max{}j λ，00min{|0}i r ij
rj b b b bij b >= 4、无可行解，或有无界解或无可行解 5、345313
444
x x x -
-+=- 6、无非负限制 7、＠bin （x ） 8、得到n 个独立零元素，最优解矩阵 三、解答题(本题共6小题,共49分) 1、证明：原问题的对偶问题是
12
121212
max 26..4520,0z x x x x s t x x x x =++≤⎧⎪+≤⎨⎪ ≥⎩且全为整数
12121212123min 673324341,,0
w y y y y y y y y y y y =+--≥⎧⎪+≥⎪⎨
-≥⎪⎪≥⎩
由于第一个约束条件不成立，所以对偶问题无可行解，由此可知原问题无最优解。
又容易知
()100T
X =是原问题的可行解，所以原问题具有无界解，即目标值无界。
2、加入人工变量，化原问题为标准形
1234512132412512345max 3500(33)(52)1842123218,,,,0
z x x x x Mx M x M x M x x x x x x x x x x x x =+++-=+++-+=⎧
⎪+=⎪⎨
++=⎪⎪≥⎩
单纯形表如下：
迭代一次后
再迭代一次后
再迭代一次后
所以最优解为*
(2,6,2,0,0),36X z ==
3、解：设i x 为从星期(1,2,,7)i i =……开始休息的人数。
则
7
1
5
1
6
2
7
3456715671267123
71234min 281524251931280(1,2,,7)i
i i i i i i i i
z x x x x x x x x x x x x x x x x x x x x x x x x x i =====⎧
≥⎪
⎪
⎪
≥⎪
⎪
⎪≥⎪
⎨
⎪++++≥⎪
++++≥⎪⎪++++≥⎪++++≥⎪⎪≥=⎩∑∑∑∑……
4、解：设0i 1i i x ⎧=⎨
⎩第个队员入选
第个队员不入选
1234567812678
146268
1
1
max (1.92 1.90 1.88 1.86 1.85 1.83 1.80 1.78)
5
1121501
i i i z x x x x x x x x x x x x x x x x x x x x ==++++++++≤⎧⎪++≥⎪⎪++≤⎪
+=⎨⎪⎪=⎪⎪⎩
∑取或
Modle ：
max (1.92*1 1.90*2 1.88*3 1.86*4 1.85*5 1.83*6 1.80*7 1.78*8)/5;121;
6781;
1462;261;
123456785;
x x x x x x x x x x x x x x x x x x x x x x x x x x =++++++++<++>++<+=+++++++=
＠bin （X1）； ＠bin （X2）； ＠bin （X3）； ＠bin （X4）； ＠bin （X5）； ＠bin （X6）； ＠bin （X7）； ＠bin （X8）； End 5、 解：
10 5 15 20
M 8 3 10 12 M 5 0 7 9 M-3 2 10 5 15 0 0 8 0 7 0 0 8 0 7 0 3 15 14 13 0 ~ 1 13 9 5 0 ~ 1 13 9 5 0 ~ 15 2 7 M 0 13 0 2 M-8 0 13 0 2 M-8 0 9 4 15 8 0 7 2 10 0 0 7 2 10 0 0
4 0 6 8 M-3 0 9 0 7 1 0 13 8 4 0
12 0 1 M-9 0 7 3 10 0 1
此时，费用最小，218553*
=+++=Z
其中，丙 一， 甲 二， 乙 三， 戌 四 6、解：
运用单纯形法得松弛问题的最优解为125813
,,max x x z =
== 。
对应最优单纯形表如下
由第一个约束条件得134x x x +
-= 则得到割平面方程为345x x x --+=-代入上表得
迭代一次得
由第一个约束条件得24541655x x x +-
= 则得到割平面方程为5611
55
x x -+=-代入上表迭代得 120,4,max 4x x z ===。