青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
2、证明：若线性规划问题的可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点处达到最优。 证明：p19
3、线性规划问题的可行域D是个凸集。（1999,2004） 证明：p16
4、若f(x)为定义在凸集D上的凸函数，证明：f(x)在D上任一极小值点就它在D上的最小值点（全局最小值点）（2002，2001） 证明：采用凸函数定义即可证明。
5、设有线性规划问题，{MaxX?CX;AX?b;X?0}，X为该问题的最优解，若目标函数中的C用C代替后，其最优解变为X，试证明[Co?C][Xo?X*]?0（2002）
o
o*
6、参考书76页，2.5题（2000）
三、单纯形法，对偶问题及灵敏度分析 1、试分析下面问题中最优解随参数?的变化（???????）(2008年，2000年)
max Z(?)?(2?5?)x1?(4?2?)x2?x1?x2?4?s.. t?2x1?x2?3???x?0,x?02?1解：标准型
max Z(?)?(2?5?)x1?(4?2?)x2?0x3?0x4?x1?x2?x3?4?s.. t?2x1?x2 ?x4?3???x?0,x?02?1
运用单纯型法求解 （1） 初始基可行解
X(0)?(0,0,4,3??)T
将相关数字填入单纯形表得到
cj CB 0
XB x3 b 4 2-5θ x1 1 4-2θ x2 1 0 x3 1 0 x4 0 α 6
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
0 -z x4 3-θ 0 2 2-5θ 1 4-2θ 0 0 1 0 （2） 检验数：
?1?c1?z1?2?5??0*1?0*2?2?5?
?2?c2?z2?4?2??0*1?0*1?4?2?
填入上表中。
（3.1）当??3时，无可行解。 （3.2）当3???2，即2?5??0且4?2??0时，最优解为(0,0,4,3??)T，目标函数取值为：Z(?)?0 （3.3）当?2/3???2，即4?2??0且4?2??2?5?时，有检验数大于0，且P1，P2有正分量存在。此时x2为换入变量。 计算α1=4/1，α2=（3-θ）/1，则min（α1，α2）=3-θ，因此x4为换出变量。 cj CB 0 0 -z cj CB 0 4-2θ -z XB x3 x2 b 1+θ 3-θ 0 2-5θ x1 -1 2 -6-θ 4-2θ x2 0 1 0 0 x3 1 0 0 0 x4 -1 1 0 α XB x3 x4 b 4 3-θ 0 2-5θ x1 1 2 2-5θ 4-2θ x2 1 [1] 4-2θ 0 x3 1 0 0 0 x4 0 1 0 α 4 3-θ 最后一行检验数全为负或零，因此当2/5???2时，最优解为(0,3??,1??,0)T，目标函数取值：Z(?)?(4?2?)(3??)。 （3.4）当???2/3，即0?4?2??2?5?时，检验数大于0，且P1，P2有正分量存在。 此时max(?1,?2)??1,因此x1为换入变量. 计算α1=4/1，α2=（3-θ）/2.
（3.4.1）当?5????2/3时，min（α1，α2）=（3-θ）/2，因此x4为换出变量。 cj CB 0 0 -z cj
XB x3 x4 b 4 3-θ 0 b 2-5θ x1 1 [2] 2-5θ 2-5θ 4-2θ x2 1 1 4-2θ 4-2θ 0 x3 1 0 0 0 0 x4 0 1 0 0 α 4 (3-θ)/2 α 7
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
CB 0 2-5θ -z XB x3 x1 (5+θ)/2 (3-θ)/2 0 x1 0 1 0 x2 1/2 1/2 3-θ/2 x3 1 0 0 x4 -1/2 1/2 5θ/2-1 5+θ 3-θ 因为3-θ/2>0,且5θ/2-1<0,因此x2为换入变量
(3.4.1.1) 当5+θ>3-θ时，即?1????2/3时，min（α1，α2）=3-θ，因此x1为换出变量。 cj CB 0 2-5θ -z cj CB 0 4-2θ -z T最后一行检验数全为负或零, 因此当?1????2/3时最优解为(0,3??,1??,0),目标函XB x3 x1 b (5+θ)/2 (3-θ)/2 0 2-5θ x1 0 1 0 2-5θ x1 -1 2 -6-θ 4-2θ x2 1/2 [1/2] 3+θ/2 4-2θ x2 0 1 0 0 x3 1 0 0 0 x3 1 0 0 0 x4 -1/2 1/2 5θ/2-1 0 x4 -1 1 -2+5θ α 5+θ 3-θ XB x3 x2 b 1+θ 3-θ 0 α 数取值：Z(?)?(4?2?)(3??)。 (3.4.1.2) 当?5????1，有5+θ<3-θ，min（α1，α2）=5+θ，因此x3为换出变量。 cj CB 0 2-5θ -z cj CB 4-2θ 2-5θ -z T最后一行检验数全为负或零，因此当?5????1时最优解为((3??)/2,?1??,0,0)，目
XB x3 x1 b (5+θ)/2 (3-θ)/2 0 2-5θ x1 0 1 0 2-5θ x1 0 1 0 4-2θ x2 [1/2] 1/2 3+θ/2 4-2θ x2 1 0 0 0 x3 1 0 0 0 x3 2 -1 -6-θ 0 x4 -1/2 1/2 5θ/2-1 0 x4 -1 1 2+3θ α 5+θ 3-θ XB x2 x1 b -1-θ (3-θ)/2 0 α 标函数取值：Z(?)?(2?5?)(3??)/2?(4?2?)(?1??)。
8
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
（3.4.2）当???5时，min（α1，α2）=4，因此x3为换出变量。 cj 2-5θ 4-2θ 0 b CB XB x1 x2 x3 0 0 -z cj CB 2-5θ 0 -z XB x1 x4 b 4 -5-θ 0 2-5θ x1 1 0 0 4-2θ x2 1 -1 2+3θ 0 x3 1 -2 -2+5θ 0 x4 0 1 0 α x3 x4 4 3-θ 0 [1] 2 2-5θ 1 1 4-2θ 1 0 0 0 x4 0 1 0 α 4 (3-θ)/2 最后一行检验数全为负或零, 因此当???5时最优解为(4,0,0,?5??)T,目标函数取值：Z(?)?4(2?5?)。 2、设有线性规划问题： max z?2x1?5x2?3x3?2x1?x2?5x3?71/7 (1) ?s.. t?x1?x2?x3?50/7?x?0,x?1/7,x?023?1试求：（1）该问题的对偶问题；（2）最优解；（3）若目标函数中x1的系数由2变为2+θ，试讨论最优解的变化；（4）在保持现行最优基不变的前提下，假如要把一个约束条件的右端扩大，应扩大哪个最有利？（2005） 解：（1）令x2??x2?1/7，则原规划问题变为： max z??2x1?5x2??3x3?2x?x??5x?103?12 (2) ??s.. t?x1?x2?x3?7?x1?0,x2??0,x3?0??因此对偶问题为：
min w?10y1+7y2?2y1+y2?2?y+y??5 ?12s.. t???5y1?y2?3??y1?0,y2无约束 9
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
max z??2x1?5x2??3x3?0x4?Mx5?Mx6?2x?x??5x?x?x?10345?12（2） ?s.. t?x1?x2??x3?x6?7?x1?0,x2??0,x3?0,x4?0,x5?0,x6?0??用单纯形法求最优解（P32）
cj CB -M -M -z cj CB 2 -M -z cj CB 2 3 -z XB x1 x3 b 45/7 4/7 2 x1 1 0 0 -5 x2 6/7 1/7 -50/7 TXB x5 x6 b 10 7 2 x1 [2] 1 2+3M 2 x1 1 0 0 -5 x2 1 1 -5+2M -5 x2 1/2 1/2 3 x3 -5 1 3-4M 3 x3 -5/2 [7/2] 0 x4 -1 0 M 0 x4 -1/2 1/2 1+ M/2 0 x4 -1/7 1/7 -1/7 -M x5 1 0 0 -M x5 1/2 -1/2 -M/2-1 -M x5 1/7 -1/7 -M+1/7 -M x6 0 1 0 -M x6 0 1 0 -M x6 5/7 2/7 -M-16/7 α 5 7 XB x1 x6 b 5 2 α - 4/7 -6+M/2 8+7M/2 3 x3 0 1 0 α 因此模型（2）的最优解为(45/7,0,4/7)，目标函数值为z??102/7 模型（1）的最优解为(45/7,1/7,4/7)，目标函数值为z??97/7 （3） 模型（2）变为 Tmax z??(2??)x1?5x2??3x3?2x?x??5x?103?12?s.. t?x1?x2??x3?7?x1?0,x2??0,x3?0??cj CB -M -M -z
10
(3) XB x5 x6 b 10 7 2+θ x1 [2] 1 -5 x2 1 1 3 x3 -5 1 3-4M 0 x4 -1 0 M -M x5 1 0 0 -M x6 0 1 0 α 5 7 2+θ+3M -5+2M