运筹学习题答案
第一章（39页）
1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max z?x1?x2 5x1+10x2?50
x1+x2?1 x2?4 x1，x2?0
（2）min z=x1+1.5x2
x1+3x2?3 x1+x2?2 x1，x2?0
（3）max z=2x1+2x2
x1-x2?-1
-0.5x1+x2?2
x1，x2?0
（4）max z=x1+x2
x1-x2?0
3x1-x2?-3
x1，x2?0
解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解
1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
资料
（1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2
x1+x2+3x3-x4?14
-2x1+3x2-x3+2x4?2
x1，x2，x3?0，x4无约束
（2）max s?nmzkpk
zk???aikxik
i?1k?1??xk?1mik??1(i?1,...,n)
xik?0 (i=1…n; k=1,…,m)
（1）解：设z=-z?,x4=x5-x6, x5,x6?0 标准型：
Max z?=3x1-4x2+2x3-5(x5-x6)+0x7+0x8-Mx9-Mx10 s. t .
-4x1+x2-2x3+x5-x6+x10=2
x1+x2+3x3-x5+x6+x7=14
-2x1+3x2-x3+2x5-2x6-x8+x9=2
x1,x2,x3,x5,x6,x7,x8,x9,x10?0
初始单纯形表: 3 cj? CB XB -4 x2 2 x3 -5 x5 5 x6 0 x7 0 x8 -M x9 -M x10 ?i b 2 14 x1 -M 0 x10 x7 -4 1 1 1 -2 3 1 -1 -1 1 0 1 0 0 0 0 1 0 2 14 资料
-M x9 2 4M -2 [3] -1 2 -2 0 -1 -M 1 0 0 0 2/3 -z? 3-6M 4M-4 2-3M 3M-5 5-3M 0 (2)解：加入人工变量x1，x2，x3，…xn，得： Max s=(1/pk)?i?1n?k?1m?ikxik-Mx1-Mx2-…..-Mxn
s.t.
xi??xik?1 (i=1,2,3…,n)
k?1mxik?0, xi?0, (i=1,2,3…n; k=1,2….,m)
CB M是任意正整数 初始单纯形表： --M … -a11acj 12 pkpkM M b … XBxnx11 x1x2 x12 1 1 1 0 0 1 … 0 1 … 0 1 0 … 0 ?M… a1m… pk … an1… pk an2pk … … amnpk ?i x1m xn1 xn2 xnm -M -M … -M -s x1 x2 … … … … … 0 ?M… 0 … 0 … … … 1 ?M0 0 … 1 ?Man2?M… 0 … 0 … … … 1 … amn?M … … … … … … … 1 0 0 … 1 0 xn nM 0 0 … 0 a11 pka12pk… a1mpk … an1pkpkpk 1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。 （1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3
x1,x2,x3,x4?0
(2)max z=5x1-2x2+3x3-6x4
资料
运筹学(第五版)习题(答案)
