青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
cj CB -M -z cj CB 3 -z 当???7，即?XB x3 b 2+θ x1 1 0 0 -5 x2 6/7 1/7 3 x3 0 1 0 x4 -1/7 1/7 -M x5 1/7 -1/7 -M x6 5/7 2/7 α XB b 2+θ x1 1 0 0 -5 x2 1/2 1/2 3 x3 -5/2 [7/2] 0 x4 -1/2 1/2 -M x5 1/2 -1/2 -M x6 0 1 0 α - 4/7 2+θ x1 5 x6 2 -6-θ/2+M/2 8+5θ/2+7M/2 1+θ/2+ M/2 -θ/2-M/2-1 2+θ x1 45/7 4/7 -50/7-6θ/7 0 -1/7+θ/7 -M+1/7-θ/7 -M-16/7-5θ/7 506?1?????时，最优解不变。 7777506?1?????时， 当???7，即?7777cj CB 3 -z cj CB -5 -z XB b 2+θ -5 x1 1 0 0 x2 0 1 3 x3 -6 7 0 x4 -1 1 -M x5 1 -1 -M x6 -1 2 α XB x3 b 2+θ x1 1 0 0 -5 x2 6/7 [1/7] 3 x3 0 1 0 x4 -1/7 1/7 -M x5 1/7 -1/7 -M x6 5/7 2/7 α 15/2 4 2+θ x1 45/7 4/7 -50/7-6θ/7 0 -1/7+θ/7 -M+1/7-θ/7 -M-16/7-5θ/7 2+θ x1 3 x2 4 0 40+6θ 7+θ -M-7-θ -M+12+θ T因此模型(3)的最优解为(3,4,0)，目标函数值为 z??3??14 T模型（1）的最优解为(3,29/7,0)，目标函数值为 z??3??14?5/7 （4）变化第一个约束条件时： cj CB -M -M -z XB x5 x6 b 10+s 7 2 x1 [2] 1 2+3M -5 x2 1 1 -5+2M 3 x3 -5 1 3-4M 0 x4 -1 0 M -M x5 1 0 0 -M x6 0 1 0 α 5+s/2 7 5?s/2?7，即s?4时
cj CB
XB b 2 x1 -5 x2 3 x3 0 x4 -M x5 -M x6 α 11
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
2 -M -z cj CB 2 3 -z x1 x6 5+s/2 2-s/2 1 0 0 2 x1 1 0 0 1/2 1/2 -5/2 [7/2] -1/2 1/2 1+ M/2 0 x4 -1/7 1/7 -1/7 1/2 -1/2 -M/2-1 -M x5 1/7 -1/7 -M+1/7 0 1 0 -M x6 5/7 2/7 -M-16/7 - 4/7-s/7 -6+M/2 8+7M/2 -5 x2 6/7 1/7 -50/7 3 x3 0 1 0 XB x1 x3 b 45/7+s/7 4/7-s/7 α 此时最优解为(45?s4?sT102?s,0,)，目标函数最大值为z?? 777 变化第二个约束条件时： cj CB -M -M -z XB x5 x6 b 10 7+t 2 x1 [2] 1 2+3M -5 x2 1 1 -5+2M 3 x3 -5 1 3-4M 0 x4 -1 0 M -M x5 1 0 0 -M x6 0 1 0 α 5 7+t 5?7?t，即t??2 cj CB 2 -M -z cj CB 2 3 -z 此时最优解为(XB x1 x3 b 45/7+5t/7 4/7+2t/7 2 x1 1 0 0 -5 x2 6/7 1/7 -50/7 3 x3 0 1 0 0 x4 -1/7 1/7 -1/7 -M x5 1/7 -1/7 -M+1/7 -M x6 5/7 2/7 -M-16/7 α XB x1 x6 b 5 2+t 2 x1 1 0 0 -5 x2 1/2 1/2 3 x3 -5/2 [7/2] 0 x4 -1/2 1/2 1+ M/2 -M x5 1/2 -1/2 -M/2-1 -M x6 0 1 0 α - 4/7+2t/7 -6+M/2 8+7M/2 45?5t4?2tT102?16t,0,)，目标函数最大值为 z?? 777很明显当扩大第二项约束时最有利。
3、已知线性规划问题：（2000,2004）
12
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
Min z?2x1?x2?2x3??x1?x2?x3?4 ?s.. t??x1?x2?kx3?6?x?0,x?0,x无约束23?1***其最优解为：x1??5;x2?0;x3??1
（1） 写出该问题的对偶问题，并求出对偶问题的最优解； （2） 求出k的值 解：（1）
Max w?4y1?6y2??y1?y2?2?y?y??1 ?12s.. t??y1?ky2?2??y1无约束，y2?0由z?w及互补松弛性质得
**?y1?y2?24y1?6y2??12
得到y1?0,y2??2，得到k=1.
4、设有线性规划问题（2002） Min z?2x1?2x2?4x3?2x1?3x2?5x3?2?3x?x?7x?3 ?123s.. t??x1?4x2?6x3?5?x2?0,x3?0,x1无约束?试求（1）该问题的对偶问题
（2）写出该问题的标准型，并写出单纯性法求解的初始单纯型表。 解：
Max w?2y1?3y2?5y3?2y1?3y2?y3?2?3y?y?4y?2 ?123s.. t??5y1?7y2?6y3?4?y1?0,y2?0,y3无约束? 13
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
??5(y4?y5)?0y6?0y7?My8?My9Max w?2y1?3y2??y4?y5?y8?2?2y1?3y2?3y?y??4(y?y)?y?y?2?124569s.. t???6(y4?y5)?y7?4?5y1?7y2??,y4,y5,y6,y7?0?y1,y2
5、设有线性规划问题：（2002）
MaxZ?2x1?4x2?x3?x4?x1?3x2?x4?8??2x1?x2?6?s..t?x2?x3?x4?6?x?x?x?9?123??xj?0,(j?1,2,3,4)
已知该问题的最优解为：X*?[2,2,4,0]T，试根据对偶理论直接求出其对偶问题的最优解。 解：对偶问题为
Min W?8y1?6y2?6y3?9y4?y1?2y2?y4?2?3y?y?y?y?41234??s..t?y3?y4?1?y?y?1?13??yi?0(i?1,2,3,4)
*由互补松弛性得y4?0，y1?y3?1，8y1?6y2?6y3?16，y3?1
解的y1?0,y2?5/3,y3?1,y4?0
四、指派问题
1、一个公司要分派5个推销员去5个地区推销某种产品，5个推销员在各个地区推销这种产品的预期利润如下表所示，问应如何分派这5个推销员才能使得公司总的利润最大。（2003，2005）
A B C D E甲?15 10 12 10 12?乙?11 12 9 9 9??? 丙?10 20 15 17 13???丁?18 17 9 9 13?戊??7 13 10 13 12?? 14
青辣椒考研试卷网，考研专业课特工！www.qinglajiao.net青辣椒2012科大专业课辅导班内部资料
解：引入变量xij，并令
?1 当第i个推销员去第j个地区推销产品 xij???0 当第i个推销员不去第j个地区推销产品 则该问题的数学模型为：
max z???cijxijij?xiij?1,j?1,2,...,5
?xjij?1,i?1,2,...,5xij?1或0该模型的目标函数可变化为
min z????bijxijij?xiij?1,j?1,2,...,5
?xjij?1,i?1,2,...,5xij?1或0其中bij?20?cij。 然后采用匈牙利法求解。
?5 10 8 10 8?5?0 5 3 5 3??0 5 3 5 0??9 8 11 11 11?8?1 0 3 3 3??1 0 3 3 0???????(bij)??10 0 5 3 7?0??10 0 5 3 7???10 0 5 3 4??????? ?2 3 1 1 7?1?1 2 0 0 6??1 2 0 0 3???3 7 10 7 8??3??0 4 7 4 5????0 4 7 4 2?? 3?? 5 3 5 ◎ ??0 5 0 2 0 ??? 5 ◎ 2 ? ??1 ? 3 3 ???1 0 0 0 0??1 ? ? ? ◎????????10 ◎ 5 3 4???10 0 2 0 4???10 ◎ 2 ? 4? ??????1 2 ◎ ? 34 5 0 0 64 5 ? ◎ 6????????◎ 4 7 4 2????0 4 4 1 2????◎ 4 4 1 2??因此相应的解矩阵为：
?0 0 1 0 0 ??0 0 0 0 1????0 1 0 0 0? ??0 0 0 1 0????1 0 0 0 0??
15