第2章 ?图解法
1.解:
x
`
A 1 (1) 可行域为O ?A BC (2) 为图? ?
(3) 由图可知,最优解为B ?点, 最优解:1x =712,7
152=x 最优 ?数 :769
2.解: x 2 1
0 1
(1) 由图解法可? 解? 6
.02.021==x x , 数 为3?.6
(2) 无可行解 (3) 无界解 (4) 无可行解 (5)
无穷多解
(6) 解 3
83
20
21=
=
x x , 数 为392
3.解:
(1). 准形式:
3212100023m ax s s s x x f ++++=
,,,,922132330
2932121321221121≥=++=++=++s s s x x s x x s x x s x x
(2). 准形式:
21210064m in s s x x f +++=
,,,46710263212121221121≥=-=++=--s s x x x x s x x s x x
(3). 准形式:
21'
'2'2'10022m in s s x x x f +++-=
,,,,30
22350
55270
55321''2'2'12''2
'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x
4.解:
准形式:
212100510m ax s s x x z +++=
,,,8259
432121221121≥=++=++s s x x s x x s x x
松弛变量(0,0) 最优解为 1x =1,x 2=3/2.
准形式:
32121000811m in s s s x x f ++++=
,,,,3694183320
21032121321221121≥=-+=-+=-+s s s x x s x x s x x s x x
剩余变量(0.0.13) 最优解为 x 1=1,x 2=5.
6.解:
(1) 最优解为 x 1=3,x 2=7. (2) 311< 4 621==x x (5) 最优解为 x 1=8,x 2=0. (6) 变 为 ?3 1 121-≤-≤-c c ,最优解 变?, 变 ?为1, 最优解? 变. 7.解: 模型: 21400500m ax x x z += ,3005.12.1440225403300221211121≥≤+≤+≤≤x x x x x x x x (1) 1501=x ,702=x , 数?最优 是1?03000? (2) 2,4 剩余, 别是33?0,15, 为松弛变?量. (3) 50,0,200,0 (4) 在[]500,0变 ,最优解 变? 在400 ? 无穷变 ?,最优解 变?. (5) 为1430 450 21-≤-=- c c , ? 最优 ?合 变. (1) 模型:b a x x f 38min += ,30000010060000451200000 10050≥≥≥+≤+b a b b a b a x x x x x x x 基金a,b 别为4?000,10000?,回报 为6?0000 (2) 模型变为:b a x x z 45max += ,300000 1001200000 10050≥≥≤+b a b b a x x x x x 推导出:180001=x 30002=x ,故基金a ?资90万,基金b 资?30万 第3章 ? ?求解 1.解: (1) 1501=x ,702=x 数最?优 103?000 (2) 1,3 ? ?用完;2,4 ? 用?完; 用完 ? 数为? 2 33?0小 ,4 15?小 . (3) 50,0,200,0 含义:1 ? 1 , ?50元;3 ? 1 , ?200元;2 与4? ? , ? (4) 3 , 为 ? 最大 (5) 在400 ? 无穷 ? 变 ,最优 ? 合 变 (6) 变 为在 ?[]500,0 (7) ? ? ? 在? ?变 , 1? 在?[]440,200变 , ?为50( 解 ? ?) (8) ?了100×50=5000,最优 ?合 变 (9) , 为 ? 变 ? (10) 变 ?, 为 ? ?与 ? ? %10010050 10025≤+ (11) 变 ?, 为 ? ?与 ? ? %100140 60 14050≤+, 最大 ?为1030?00+50×50-60×200=93500?元 2.解: (1) 4000,10000?,62000? (2) 1?: 资 ? 1 ?, 数 ?降低0.057; 2?: 回报 ? 1 ?, 数 ?高2.167; 3?:基金B ?资 1? , 数 ?变 (3) 1? 松弛变量?是0, 资 ? 好为12?00000?; 2? 剩余变量?是0, 资回?报 好是?60000?; 3? 松弛变量?为7000?00, 资B ?基金 资? 为370?000 (4) 2c 变 ,1c 在3.75 无?穷 ?变 ,最优解 变?; 1c 变 ,2c 在 无穷 ?6.4 ?变 ,最优解 变? (5) 1? 在?[]1500000,780000变 , ?为0.057( ) (6) , 为 ? ?与 ? ? %1006 .32 25.44>+, 由 ? 法 ? 3.解: (1) 18000?,3000,10200?0,15300?0 (2) 资 ?松弛变量为?0, 资 ? 好为12?00000?;基金b ?资 剩余?变量为0, 资B ?基金 资? 好为3?00000?; (3) 资 ? 1 ? ,回报 ?0.1; 基金b ?资 ?1 ,回报 降?0.06 (4) 1c 变 ,2c 在 无穷 ?10 ? 变 , 最优解 ?变; 2c 变 ,1c 在2 无?穷 ?变 , 最优解 ?变 (5) 1? 在?30000?0 无穷? 变? , ?为0.1; 2? 在?0 120?0000 ? 变 ?, ?为-0.06 (6) =+900000 300000 900000600000100% 故 ? 变 4.解: (1) 5.81=x ,5.12=x ,03=x ,04=x ,最优 ?数18.5 (2) 2? 3, 为?2 3.5, 2? 3 数? ? ?数 别 高?2 3.5 (3) 第3 , 最优 ? 数 为?22 (4) 在 无穷 ?5.5 ?变 , 最优解 ?变, 最优? 数 ?变 (5) 在0 无?穷 ?变 , 最优解 ?变, 最优? 数 ?变 5.解: (1) 2? ? 1 ?, 数 ?将 3.622; (2) 2x 数 ?数 高 0?.703,最优解 ?2x 可 大?于零; (3) ? 法 ? , 为 ? ?与 ? ? %1002 583.141≤∞ +, 最优解? 变; (4) 为10015 25.11165 189.93015>-+-% ? 法 , ? ? 是 变? 第4章 在??应用 1.解:为了用最 ??10?, 合 ?用14?方案 设按14?方案 ??数别为x?1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,模型如 : 4-1 方?式 min f=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14 s.t. 2x1+x2+x3+x4≥80 x2+3x5+2x6+2x7+x8+x9+x10≥350 x3+x6+2x8+x9+3x11+2x12+x13≥420 x4+x7+x9+2x10+x12+2x13+3x14≥10 x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14 ≥0 用 ??可 求 ? 解为?: x1=40,x2=0,x3=0,x4=0,x5=116.667,x6=0,x7=0,x8=0,x9=0,x10 =0,x11=140,x12=0,x13=0,x14=3.333 最优 为3?00 2.解: 从 午11? 午1?0 成1?1 班次,设xi?第i班次 ??人数, 模型如 : min f=16(x1+x 2+x3+x4+x5+x6+x7+x8+x9+x10+x11) s.t.x1+1 ≥9 x1+x2+1 ≥9 x1+x2+x3+2 ≥9 x1+x2+x3+x4+2 ≥3 x2+x3+x4+x5+1 ≥3 x3+x4+x5+x6+2 ≥3 x4+x5+x6+x7+1 ≥6 x5+x6+x7+x8+2 ≥12 x6+x7+x8+x9+2 ≥12 x7+x8+x9+x10+1 ≥7 x8+x9+x10+x11+1≥7 x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11≥0 用 ??可 求 ? 解为?: x1=8,x2=0,x3=1,x4=1,x5=0,x6=4,x7=0,x8=6,x9=0,x10=0,x11=0 最优 为3?20 (1)在 ? 求 ? ,在11?8?,13?1?,14 ?1?,16?4?,18?6?可 ? 成?最小 (2) 是 ? 资? 为80?元, ?20? 班次? 松弛/剩余变量 ------- ------------- -------- 1 0 -4 2 0 0 3 2 0 4 9 0 5 0 -4 6 5 0 7 0 0 8 0 0 9 0 -4 10 0 0 11 0 0 剩余变?量 数 ?析可知,可 让11?8? 人 做3?小 ,13 ?1 人 ?作3小 ,可 成?更小 (3)设xi?第i班 班?4小 ?人数,yj 第?j班 班3?小 ?人数 min f=16(x1+x 2+x3+x4+x5+x6+x7+x8)+12(y1+y2+y3+y4+y5+y6+y7+y8+y9) s.t.x1+y1+1 ≥9 x1+x2+y1+y2+1 ≥9 x1+x2+x3+y1+y2+y3+2 ≥9 x1+x2+x3+x4+y2+y3+y4+2 ≥3 x2+x3+x4+x5+y3+y4+y5+1 ≥3 x3+x4+x5+x6+y4+y5+y6+2 ≥3 x4+x5+x6+x7+y5+y6+y7+1 ≥6 x5+x6+x7+x8+y6+y7+y8+2 ≥12 x6+x7+x8+y7+y8+y9+2 ≥12 x7+x8+y8+y9+1 ≥7 x8+y9+1≥7 x1,x2,x3,x4,x5,x6,x7,x8,y1,y2,y3,y4,y5,y6,y7,y8,y9≥0 用 ??可 求 ? 解为?: x1=0,x2=0,x3=0,x4=0,x5=0,x6=0,x7=0,x8=6,y1=8,y2=0,y3=1,y4=0,y5=1,y6=0,y7=4,y8=0,y9=0 最优 为2?64 如 : 在11:00-12:008? 小 ?班,在13:00-14:001? 小 ?班, 在15:00-16:001? 小 ?班,在17:00-18:004? 小 ?班,在18:00-19:006? 小 ?班 成 最小?为264元?, 第 ?节省:320-264=56元 3.解:设 A、B、C?数量 别?为x1,x2,x3, 可 ?面 数 模型: max z=10 x1+12x2+14x3 s.t. x1+1.5x2+4x320?≤00 2x1+1.2x2+x3100?≤0 x1≤200 x2250?≤ x3 ≤100 x1,x2,x3≥0 用 ??可 求 ? 解为?: x1=200,x2=250,x3=100,最优 为6?400 (1)在资 数量? 量??, A 200 ,B 250 ,C 100 ,可 ?最多 (2)A、B、C?量?别为1?0元,12元,14元 、 ? 为0?说明A? 量 ? 可 ??10元,B?量?可 ?12?元,C?量?可 ?14?元 ???数?? 如 ? 应 ?先C? ,如 ?资, 应在0??数量 ?器 数 4.解:设 ?? 数?为x11, ?无? 数为?x12,?? 数为?x21, ?无? 数为?x22, 可 ?面 数 模?型: min f=25x11?+20x12?+30x21?+24x22? s.t.x11+x12+x21+x22≥2000 x11+x12 =x21+x22 x11+x21≥700 x12+x22≥450 x11,x12,x21,x22≥0 用 ??可 求 ? 解为?: x11=700,x12=300,x21=0,x22=1000 最优 为4?7500 (1)?? 数为?700 , ?无? 数为?300 , ?? 数为?0,?无? 数为?1000?,可?费用最小 (2)?? 费用在?2026?元 , 方案? 变 ; ? 无 ? 费用在?1925?元 , 方案? 变 ; ?? 费用在?29 无?穷 , 方案? 变 ; ?无? 费用在?-2025?元 , 方案?变 (3)?数在14?00 无?穷 , ?变 ; ? 最 ?数在0 1?000 ?, ? 变 ; 无 ? 最 ?数在 无穷? 1300 ? , ? 变 5.解:设第i ? 合 ?打 租用j ? 面 ?为x ij , ? 面 数 ?模型: min f =2800x ?11+4500x ?12+6000x ?13+7300x ?14+2800x ?21+4500x ?22+6000x ?23+2800x ?31+ 4500x ?32+2800x ?41 s .t .x 11 ≥ 15 x 12+x 21 ≥ 10 x 13+x 22+x 31≥ 20 x 14+x 23+x 32+x 41 ≥12 x ij ≥ 0,i ,j =1,2,3,4 用 ? ?可 求 ? 解为?: x 11=15,x 12=0,x 13=0,x 14=0,x 21=10,x 22=0,x 23=0,x 31=20,x 32=0,x 41=12, 最优 为1?59600? 在 租?用1500? 方 ? ,在 租?用1000? 方 ,在 租?用2000? 方 ? , 租用?1200 ?方 ?,可 ? 租 费最小? 6.解:设xij ? 第i ?型 ?第j ? 量,可 面? 数 模型?: max z =9(x 11+x 12+x 13)+7(x 21+x 22+x 23)+8(x 31+x 32+x 33)-5.5(x 11+x 21 +x 31)-4(x 12+x 22+x 32)-5(x 13+x 23+x 33) s .t . x 11 ≥ 0.5(x 11+x 12+x 13) x 12 ≤0.2(x 11+x 12+x 13) x 21 ≥0.3(x 21+x 22+x 23) x 23 ≤ 0.3(x 21+x 22+x 23) x 33 ≥ 0.5(x 31+x 32+x 33) x 11+x 21+x 31 ≤30 x 12+x 22+x 32 ≤30 x 13+x 23+x 33 ≤ 30 x ij ≥ 0,i ,j =1,2,3 用 ? ?可 求 ? 解为?: x 11=30,x 12=10,x 13=10,x 21=0,x 22=0,x 23=0,x 31=0,x 32=20,x 33=20, 最优 为3?35 ? 50 ?, ? , ? 40 7.设X 为第i ?i ? I 数量? Y i 为第i ? II 数?量 Z i ,W 别为第?i i ?I 、II 数? S i 1,S 别为用?i 2于第(i+1) ? 租 ? ?( 方 ) 可 ?如 模型: Min z= ∑∑∑===+++++5 1 126 12 1 21)()75.4()85(i i i i i i i i i S S y x y x s.t X 1-10000?=Z 1 X 2+Z 1 -10000?=Z 2 X 3+Z 2 -10000?=Z 3 X 4+Z 3 -10000?=Z 4 X 5+Z 4 -30000?=Z 5 X 6+Z 5 -30000?=Z 6 X 7+Z 6 -30000?=Z 7 X 8+Z 7 -30000?=Z 8 X 9+Z 8 -30000?=Z 9 X 10+Z 9 -10000?0=Z 10 X 11+Z 10 -10000?0=Z 11 X 12+Z 11 -10000?0=Z 12 Y 1-50000?=W 1 Y 2+W 1 -50000?=W 2 Y 3+W 2 -15000?=W 3 Y 4+W 3 -15000?=W 4 Y 5+W 4 -15000?=W 5 Y 6+W 5 -15000?=W 6 Y 7+W 6 -15000?=W 7 Y 8+W 7 -15000?=W 8 Y 9+W 8 -15000?=W 9 Y 10+W 9 -50000?=W 10 Y 11+W 10-50000?=W 11 Y 12+W 11-50000?=W 12 S i 115000≤ 112≤≤i X i +Y i 120000≤ 112≤≤i 0.2Z i +0.4W i i i S S 21+= 3112≤≤i X i ,0≥0≥i Y ,Z i 0,0,0,021≥≥≥≥i i i S S W 用 ? ?可 求 ? 解为?: 最优 为4?91050?0 X 100001=,X 2=10000?,X 3=10000?,X 4=10000?, X 5=30000?, X 6=30000?, X 7=30000?, X 8=45000?, X 9=10500?0, X 10=70000?, X 11=70000?, X 12=70000?; Y 1=50000?, Y 2=50000?, Y 3=15000?, Y 4=15000?, Y 5=15000? Y 6=15000?, Y 7=15000?, Y 8=15000?, Y 9=15000?, Y 10=50000?, Y 11=50000?, Y 12=50000?; Z 8=15000?, Z 9=90000?, Z 10=60000?, Z 11=30000?; S 18=3000,S 19=15000?,S ;3000;6000,1200029111110===S S 余变量 ? 于0 8.解:设第i ?第j 型 ? 数量?为x ij ,可 ?面 数 模?型: ) (17)(20)(25m ax 53432313524232125141312111x x x x x x x x x x x x x ++++++++++++= +11)(442414x x x ++ s.t 14005141312111≤++++x x x x x 30052423212≥+++x x x x 12324252800x x x x +++≤ 800053432313≤+++x x x x 700442414≥++x x x 18000567514131211≤+++x x x x 15000336242321≤++x x x 41400033231≤+x x 12000242344434241≤+++x x x x 10000542535251≤++x x x x 5,4,3,2,1,0=≥i ij j=1,2,3,4 用 ? ?可 求 ? 解为?: **********************最优解如 ?************************* 数最?优 为 : 27940?0 变量 最优解 相差 ------- -------- -------- x 11 0 11 x 21 0 26.4 x 31 1400 0 x 41 0 16.5 x 51 0 5.28 x 12 0 15.4 x 32 800 0 x 42 0 11 x 52 0 10.56 x 13 1000 0 x 23 5000 0 x 43 0 8.8 x 53 2000 0 x 14 2400 0 x 24 0 2.2 x 44 6000 0 松弛/剩余变量 ------- ------------- -------- 1 0 25 2 500 0 3 0 20 4 0 3.8 5 7700 0 6 0 2.2 7 0 4.4 8 6000 0 9 0 5.5 10 0 2.64 数 ?数: 变量 前 ------- -------- -------- -------- x11无 25 36 x21无 25 51.4 x3119.72 25 无 x41无 25 41.5 x51无 25 30.28 x12无 20 35.4 x329.44 20 无 x42无 20 31 x52无 20 30.56 x1313.2 17 19.2 x2314.8 17 无 x43无 17 25.8 x53 3.8 17 无 x149.167 11 14.167 x24无 11 13.2 x44 6.6 11 无 数 数 ?: 前 ------- -------- -------- -------- 1 0 1400 2900 2 无 300 800 3 300 800 2800 5 无 700 8400 6 6000 18000?无 8 8000 14000?无 9 0 12000?无 2000 ,0 ,0 , 6000 ,0 ,0 ,0 , 800 , 1400 ,0 , 5000 ,0 , 2400 , 1000 ,0 ,0 53 52 51 44 43 42 41 32 31 24 23 21 14 13 12 11 = = = = = = = = = = = = = = = = x x x x x x x x x x x x x x x x 最优 为2?79400? (2) 5?可用 ? 做 ? 析可 ????行进行 9.解:设第 ?x? 1, 班 x? 2 ,x 3 ;第 ?x 4 , 班 x? 5 , x 6;第 ? x 7, 班 x ?8, x 9;第 ? x 10, 班 x ?11,可 ?面 数 模?型: Min f=200(x 1+ x 4+ x 7+ x 10)+300(x 2+ x 5+ x 8+ x 11)+60(x 3+ x 6+ x 9) s.t x 14000≤ 40004≤x x 40007≤ x 400010≤ x 31000≤ x 10006≤ x 91000≤ x 10002≤ x 10005≤ x 10008≤ x 100011≤ 4500321=-+x x x 30006543=-++x x x x 55009876=-++x x x x 450011109=++x x x 0,,,,,,,,,,1110987654321≥x x x x x x x x x x x 用 ? ?可 求 ? 解为?: 最优 为f ?=37100?00元 x 1=4000 ?,x 2 =500 ,x 3=0 ,x 4=4000 ?, x 5=0 x 6=1000 ?, x 7=4000 ?, x 8=500 , x 9=0 , x 10=4000 ?,x 11=500 第5章 纯形法 1.解: a、c、e、f是可行解?,a、b、f是基 解?,a、f是基 可?行解 2.解: (1)? 准型为?: max 5x1+9x2+0s1+0s2+0s3 s.t. 0.5x1+x2+s1=8 x1+x2-s2=10 0.25x1+0.5x2-s3=6 x1,x2,s1,s2,s3≥0 (2) 变量? 零, 为 ?基变量、 基变?量, 基变量 ?零 (3)(4,6,0,0,-2)T (4)(0,10,-2,0,-1)T (5) 是 为基 可?行解 求基?变量 ? (6)略 (2) 模?型为: max 6x1+30x2+25x3 s.t. 3x1+x2+s1=40 2x2+x3+s2=50 2x1+x 2-x3+s3=20 x1,x2,x3,s1,s2,s3≥0 (3) 解 基?为(s1,s2,s3)T, 解为(0,0,0,40,50,20)T, 应 ?数 为0? (4)第 次迭代?, 基变量 ?x2,出基变量为?s3 4.解:最优解为(2.25,0)T,最优 为9? 5.解: (1) 最优解为(2,5,4)T ,最优 为8?4 (2) 最优解为(0,0,4)T ,最优 为-4 6.解: 无界解 1237 x x +=12429 x x += 7.解: (1)无可行解 (2)最优解为(4,4)T,最优 为2?8 (3) 无界解 (4)最优解为(4,0,0)T,最优 为8? 第6章 纯形法 ? 析?与 1.解: (1)c1≤24 (2)c2≥6 (3)c s2≤8 2.解: (1)c1≥-0.5 (2)-2≤c3≤0 (3)c s2≤0.5 3.解: (1)b1≥250 (2)0≤b2≤50 (3)0≤b3≤150 4.解: (1)b1≥-4 (2)0≤b2≤10 (3)b3≥4 5.解: (1) 变 ?c1≤3,故 c1=2 最优解?变 (2)? 为?1 , 做法 ? (3)0≤b2≤45 (4)最优解 变?,故 ?? (5)??, 为 ??验数为-3小于零, ? ? 6.解: 为 最?优解, 从 ? 出 ? 出,如 松弛 ?剩余变量为?零 应 ??为零, 在 ? 为零 ?变量 ?相差 ?为零 ,可知 ? 无穷?多解 7.解: (1)min f= 10y1+20y2. s.t. y1+y2≥2 y1+5y2≥1 y1+y2≥1 y1,y2≥0 (2)max z= 100y1?+200y2?. s.t. 1/2y1+4y2≤4 2y 1+6y 2≤4 2y 1+3y 2≤2 y 1,y 2≥0 8. 解: (1) min f= -10y 1+50y 2+20y 3. s.t. -2y 1+3y 2+y 3≥1 -3y 1+y 2 ≥2 -y 1+y 2+y 3 =5 y 1,y 2≥0,y3 ? 制 (2) max z= 6y 1-3y 2+2y 3. s.t. y 1-y 2-y 3≤1 2y 1+y 2+y 3 =3 -3y 1+2y 2-y 3≤-2 y 1,y 2≥0,y3 ? 制 9.解: 123 1234 1235236max 2342820,1,,6j z x x x x x x x x x x x x x x x j =----+-+=-?? +++=?? -++=-? ?≥=? 用 纯?形法解 四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A ) 《管理运筹学》 一、 单选题(每题2分,共20分。) 1.目标函数取极小(minZ )的线性规划问题可以转化为目标函数取极大的线性规划问题求解,原问题的目标 函数值等于( )。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2. 下列说法中正确的是( )。 A.基本解一定是可行解 B.基本可行解的每个分量一定非负 C.若B 是基,则B 一定是可逆 D.非基变量的系数列向量一定是线性相关的 3.在线性规划模型中,没有非负约束的变量称为 ( ) 多余变量 B .松弛变量 C .人工变量 D .自由变量 4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时,可求得( )。 A.多重解 B.无解 C.正则解 D.退化解 5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验 但不完全满足 ( )。 A .等式约束 B .“≤”型约束 C .“≥”约束 D .非负约束 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i y 是( )。 A.多余变量 B.自由变量 C.松弛变量 D.非负变量 7.在运输方案中出现退化现象,是指数字格的数目( )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8. 树T的任意两个顶点间恰好有一条( )。 A.边 B.初等链 C.欧拉圈 D.回路 9.若G 中不存在流f 增流链,则f 为G 的 ( )。 A .最小流 B .最大流 C .最小费用流 D .无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足( ) A.等式约束 B.“≤”型约束 C.“≥”型约束 D.非负约束 二、多项选择题(每小题4分,共20分) 1.化一般规划模型为标准型时,可能引入的变量有 ( ) A .松弛变量 B .剩余变量 C .非负变量 D .非正变量 E .自由变量 2.图解法求解线性规划问题的主要过程有 ( ) A .画出可行域 B .求出顶点坐标 C .求最优目标值 D .选基本解 E .选最优解 3.表上作业法中确定换出变量的过程有 ( ) A .判断检验数是否都非负 B .选最大检验数 C .确定换出变量 D .选最小检验数 E .确定换入变量 4.求解约束条件为“≥”型的线性规划、构造基本矩阵时,可用的变量有 ( ) A .人工变量 B .松弛变量 C. 负变量 D .剩余变量 E .稳态 变量 5.线性规划问题的主要特征有 ( ) 《管理运筹学》(第二版)课后习题参考答案 第1章 线性规划(复习思考题) 1.什么是线性规划线性规划的三要素是什么 答:线性规划(Linear Programming ,LP )是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化工具,能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误 答:(1)唯一最优解:只有一个最优点; (2)多重最优解:无穷多个最优解; (3)无界解:可行域无界,目标值无限增大; (4)没有可行解:线性规划问题的可行域是空集。 当无界解和没有可行解时,可能是建模时有错。 3.什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答:线性规划的标准型是:目标函数极大化,约束条件为等式,右端常数项0≥i b ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答:可行解:满足约束条件0≥=X b AX ,的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示: 模拟试题一 一、单项选择题:(共7题,35分) 1、在线性规划模型中,没有非负约束的变量称为(C) A. 多余变量 B. 松弛变量 C. 自由变量 D. 人工变量 2、约束条件为AX=b,X≥0的线性规划问题的可行解集是(B ) A. 补集 B. 凸集 C. 交集 D. 凹集 3、线性规划的图解法适用于( B ) A. 只含有一个变量的线性规划问题 B. 只含有2~3个变量的线性规划问题 C. 含有多个变量的线性规划问题 D. 任何情况 4、单纯形法作为一种常用解法,适合于求解线性规划(A ) A. 多变量模型 B. 两变量模型 C. 最大化模型 D. 最小化模型 5、在单纯性法计算中,如果检验数都小于等于零,而且非基变量的检验数全为负数,则表明此问题有(D )。 A. 无穷多组最优解 B. 无最优解?? C. 无可行解 D. 唯一最优解 6、在线性规划中,设约束方程的个数为m,变量个数为n,m<n时,可以把变量分为基变量和非基变量两部分,基变量的个数为m个,非基变量的个数为(C ) A. m个 B. n个 C. n-m个 D. 0个 7、使用人工变量法求解极大化线性规划问题时,当所有的检验数在基变量中仍含有非零的人工变量,表明该线性规划问题(D ) A. 有唯一的最优解 B. 有无穷多最优解 C. 为无界解 D. 无可行解 二、填空题:(共5题,25分) 1、运筹学是一门研究如何有效地组织和管理决策的科学. 2、线性规划是一种合理利用资源、合理调配资源的应用数学方法,其基本特点是模型中的目标函数和约束方程都是线性表达式. 3、线性规划模型由三个要素构成:决策变量、目标函数、约束条件。 4、可行域中任意两点间联结线段上的点均在可行域内,这样的点集叫凸集。 5、线形规划的标准形式有如下四个特点:目标函数的最大化、约束条件为等式、决策变量费非负、右端常数项非负。 三、简答题:(共3题,40分) 1、简述线性规划模型的三个基本特征。 (1)每一个问题都有一个极大或极小的目标且能用有一组线性函数表示出来。 (2)问题中有若干约束条件且可用线性等式或不等式表示。 (3)问题中用一组决策变量来表示一科方案。 2、简述单纯型法的基本思想。 (1)确定初始基可行解(2)检验是否最优,由一个基可行解变换到另一个基可行基,直至找到最优解。 3、简述如何在单纯型表上判别问题有无界解。 答:如果存在一个非基变量的检验数为正数,但此变量当前系数中无正系数存在即可证明。 模拟试题二 一、单项选择题:(共5题,30分) 1、对偶问题的对偶是(D ) 《管理运筹学》第四版课后习题解析(上) 第2章 线性规划的图解法 1.解: (1)可行域为OABC 。 (2)等值线为图中虚线部分。 (3)由图2-1可知,最优解为B 点,最优解1x = 127,2157x =;最优目标函数值697 。 图2-1 2.解: (1)如图2-2所示,由图解法可知有唯一解12 0.2 0.6x x =??=?,函数值为3.6。 图2-2 (2)无可行解。 (3)无界解。 (4)无可行解。 (5)无穷多解。 (6)有唯一解 12203 8 3x x ?=????=?? ,函数值为923。 3.解: (1)标准形式 12123max 32000f x x s s s =++++ 1211221231212392303213229,,,,0 x x s x x s x x s x x s s s ++=++=++=≥ (2)标准形式 1212min 4600f x x s s =+++ 12112212121236210764,,,0 x x s x x s x x x x s s --=++=-=≥ (3)标准形式 1 2212min 2200f x x x s s ''''=-+++ 12 211 2212221 2212355702555032230,,,,0x x x s x x x x x x s x x x s s '''-+-+=''''-+=''''+--=''''≥ 4.解: 标准形式 1212max 10500z x x s s =+++ 1211221212349528,,,0 x x s x x s x x s s ++=++=≥ 松弛变量(0,0) 最优解为 1x =1,x 2=3/2。 5.解: 运 筹 学 考 卷 1 / 51 / 5 考试时间: 第十六周 题号一二三四五六七八九十总分 评卷得分 : 名 一、单项选择题。下列每题给出的四个答案中只有一个是正确的,将表示正确 姓 答案的字母写这答题纸上。(10 分, 每小题2 分) 1、使用人工变量法求解极大化线性规划问题时,当所有的检验数j 0 ,在 线 基变量中仍含有非零的人工变量,表明该线性规划问题() A. 有唯一的最优解; B. 有无穷多个最优解; C. 无可行解; D. 为无界解 2、对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中(): 号 A.b 列元素不小于零B.检验数都大于零 学 C.检验数都不小于零D.检验数都不大于零 3、在产销平衡运输问题中,设产地为m 个,销地为n 个,那么基可行解中非 零变量的个数() 订 A. 不能大于(m+n-1); B. 不能小于(m+n-1); C. 等于(m+n-1); D. 不确定。 4、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足() A. d 0 B. d 0 C. d 0 D. d 0,d 0 5、下列说法正确的为() : 业 A.如果线性规划的原问题存在可行解,则其对偶问题也一定存在可行解 专 B.如果线性规划的对偶问题无可行解,则原问题也一定无可行解 装 C.在互为对偶的一对原问题与对偶问题中,不管原问题是求极大或极小,原 问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D.如果线性规划问题原问题有无界解,那么其对偶问题必定无可行解 : 院 学 2 / 52 / 5 二、判断下列说法是否正确。正确的在括号内打“√”,错误的打“×”。(18 分,每 小题2 分) 1、如线性规划问题存在最优解,则最优解一定对应可行域边界上的一个点。() 2、单纯形法计算中,如不按最小比列原则选取换出变量,则在下一个解中至少有一 个基变量的值为负。() 3、任何线性规划问题存在并具有惟一的对偶问题。() 4、若线性规划的原问题有无穷多最优解,则其最偶问题也一定具有无穷多最优解。 ()5、运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列四种情况之 一:有惟一最优解,有无穷多最优解,无界解,无可行解。() 6、如果运输问题的单位运价表的某一行(或某一列)元素再乘上那个一个常数k , 最有调运方案将不会发生变化。() 7、目标规划模型中,应同时包含绝对约束与目标约束。() 8、线性规划问题是目标规划问题的一种特殊形式。() 9、指派问题效率矩阵的每个元素都乘上同一常数k,将不影响最优指派方案。() 三、解答题。(72 分) max z 3x 3x 1 2 1、(20分)用单纯形法求解 x x 1 2 x x 1 2 4 2 ;并对以下情况作灵敏度分析:(1)求 6x 2 x 18 1 2 x 0, x 0 1 2 5 c 的变化范围;(2)若右边常数向量变为2 b ,分析最优解的变化。 2 20 2、(15 分)已知线性规划问题: max z x 2x 3x 4x 1 2 3 4 s. t. x 2x 2x 3x 20 1 2 3 4 2x x 3x 2x 20 1 2 3 4 x x x x , , , 0 1 2 3 4 其对偶问题最优解为y1 1.2, y2 0.2 ,试根据对偶理论来求出原问题的最优解。 1 课程:管理运筹学 管理运筹学作业 第二章线性规划的图解法 P23:Q2:(1)-(6);Q3:(2) Q2:用图解法求解下列线性规划问题,并指出哪个问题具有唯一最优解,无穷多最优解,无界解或无可行解。 (1)Min f=6X1+4X2 约束条件:2X1+X2>=1, 3X1+4X2>=3 X1, X2>=0 解题如下:如图1 Min f=3.6 X1=0.2, X2=0.6 本题具有唯一最优解。 图1 (2)Max z=4X1+8X2 约束条件:2X1+2X2<=10 -X1+X2>=8 X1,X2>=0 解题如下:如图2: Max Z 无可行解。 图2 1 2 2 (3) Max z =X1+X2 约束条件 8X1+6X2>=24 4X1+6X2>=-12 2X2>=4 X1,X2>=0 解题如下:如图3: Max Z=有无界解。 图3 (4) Max Z =3X1-2X2 约束条件:X1+X2<=1 2X1+2X2>=4 X1,X2>=0 解题如下:如图4: Max Z 无可行解。 图 4 3 (5)Max Z=3X1+9X2 约束条件:X1+3X2<=22 -X1+X2<=4 X2<=6 2X1-5X2<=0 X1,X2>=0 解题如下:如图5: Max Z =66;X1=4 X2=6 本题有唯一最优解。 图5 (6)Max Z=3X1+4X2 约束条件:-X1+2X2<=8 X1+2X2<=12 2X1+X2<=16 2X1-5X2<=0 X1,X2>=0 解题如下:如图6 Max Z =30.669 X1=6.667 X2=2.667 本题有唯一最优解。 3 运筹学试题 Company Document number:WTUT-WT88Y-W8BBGB-BWYTT-19998 运筹学试题 一、填空题(本大题共8小题,每空2分,共20分) 1.线性规划闯题中,如果在约束条件中出现等式约束,我们通常用增加___的方法来产生初始可行基。 2.线性规划模型有三种参数,其名称分别为价值系数、___和___。 3.原问题的第1个约束方程是“=”型,则对偶问题相应的变量是___变量。 4.求最小生成树问题,常用的方法有:避圈法和 ___。 5.排队模型M/M/2中的M,M,2分别表示到达时间为___分布,服务时间服从负指数分布和服务台数为2。 6.如果有两个以上的决策自然条件,但决策人无法估计各自然状态出现的概率,那么这种决策类型称为____型决策。 7.在风险型决策问题中,我们一般采用___来反映每个人对待风险的态度。 8.目标规划总是求目标函数的___信,且目标函数中没有线性规划中的价值系数,而是在各偏差变量前加上级别不同的____。 二、单项选择题(本大题共l0小题,每小题3分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。多选无分。 9.使用人工变量法求解极大化线性规划问题时,当所有的检验数在基变量中仍含有非零的人工变量,表明该线性规划问题【】 A.有唯一的最优解 B.有无穷多最优解 C.为无界解 D.无可行解 10.对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中【】 A.b列元素不小于零 B.检验数都大于零 C.检验数都不小于零 D.检验数都不大于零 11.已知某个含10个结点的树图,其中9个结点的次为1,1,3,1,1,1,3,1,3,则另一个结点的次为【】 A.3 B.2 C.1 D.以上三种情况均有可能 12.如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【】 13.在运输方案中出现退化现象,是指数字格的数目【】 A.等于 m+n B.等于m+n-1 C.小于m+n-1 D.大于m+n-1 14.关于矩阵对策,下列说法错误的是【】 A.矩阵对策的解可以不是唯一的 C.矩阵对策中,当局势达到均衡时,任何一方单方面改变自己的策略,都将意味着自己更少的赢得和更大的损失 D.矩阵对策的对策值,相当于进行若干次对策后,局中人I的平均赢得或局中人Ⅱ的平均损失值 【】 A.2 8.—l C.—3 D.1 16.关于线性规划的原问题和对偶问题,下列说法正确的是【】 A.若原问题为元界解,则对偶问题也为无界解 四川大学网络教育学院模拟试题( A ) 《管理运筹学》 一、单选题(每题2分,共20分。) 1.目标函数取极小(minZ)的线性规划问题可以转化为目标函数取极大的线性规 划问题求解,原问题的目标函数值等于(C)。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2.下列说法中正确的是(B)。 A.基本解一定是可行解B.基本可行解的每个分量一定非负 C.若B是基,则B一定是可逆D.非基变量的系数列向量一定是线性相关的3.在线性规划模型中,没有非负约束的变量称为( D ) 多余变量B.松弛变量C.人工变量D.自由变量 4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时,可求得 ( A )。 A.多重解B.无解C.正则解D.退化解5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验 但不完全满足( D )。 A.等式约束 B.“≤”型约束 C.“≥”约束 D.非负约束 y是( B )。 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i A.多余变量B.自由变量C.松弛变量D.非负变量 7.在运输方案中出现退化现象,是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8.树T的任意两个顶点间恰好有一条(B)。 A.边B.初等链C.欧拉圈D.回路9.若G中不存在流f增流链,则f为G的( B )。 A.最小流 B.最大流 C.最小费用流 D.无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验 但不完全满足( D ) A.等式约束B.“≤”型约束C.“≥”型约束D.非负约束二、多项选择题(每小题4分,共20分) 1.化一般规划模型为标准型时,可能引入的变量有() A.松弛变量 B.剩余变量 C.非负变量 D.非正变量 E.自由变量 2.图解法求解线性规划问题的主要过程有() A.画出可行域 B.求出顶点坐标 C.求最优目标值 D.选基本解 E.选最优解 3.表上作业法中确定换出变量的过程有() A.判断检验数是否都非负 B.选最大检验数 C.确定换出变量 D.选最小检验数 E.确定换入变量 4.求解约束条件为“≥”型的线性规划、构造基本矩阵时,可用的变量有()A.人工变量 B.松弛变量 C. 负变量 D.剩余变量 E.稳态变量 5.线性规划问题的主要特征有() A.目标是线性的 B.约束是线性的 C.求目标最大值 D.求目标最小值 E.非线性 三、计算题(共60分) 1. 下列线性规划问题化为标准型。(10分) 1 / 17 管理运筹学 ——管理科学方法谢家平 第一章 第一章 1. 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量(Decision Variable)是决策问题待 定的量值,取值一般为非负;约束条件(Constraint Conditions)是指决策变量取值时受到的各种资源条件的限制, 保障决策方案的可行性;目标函数(Objective Function)是决策者希望实现的目标,为决策变量的线性函数表达式, 有的目标要实现极大值,有的则要求极小值。 2.(1)设立决策变量; (2)确定极值化的单一线性目标函数; (3)线性的约束条件:考虑到能力制约,保证能力需求量不能突破有效供给量; (4)非负约束。 3.(1)唯一最优解:只有一个最优点 (2)多重最优解:无穷多个最优解 (3)无界解:可行域无界,目标值无限增大 (4)没有可行解:线性规划问题的可行域是空集 无界解和没有可行解时,可能是建模时有错。 4. 线性规划的标准形式为:目标函数极大化,约束条件为等式,右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 5. 可行解:满足约束条件AX =b,X≥0的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 6. 计算步骤: 第一步,确定初始基可行解。 第二步,最优性检验与解的判别。 第三步,进行基变换。 第四步,进行函数迭代。 判断方式: 唯一最优解:所有非基变量的检验数为负数,即σj< 0 无穷多最优解:若所有非基变量的检验数σj≤ 0 ,且存在某个非基变量xNk 的检验数σk= 0 ,让其进基,目标函数 四、把下列线性规划问题化成标准形式: 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品,每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量,单位产品的利润如下表所示: 根据客户订货,三种产品的最低月需要量分别为200,250和100件,最大月销售量分别为250,280和120件。月销售分别为250,280和120件。问如何安排生产计划,使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋,今要截成长度为3米的钢筋90根,长度为4米的钢筋60根,问怎样下料,才能使所使用的原材料最省? 1. 某运输公司在春运期间需要24小时昼夜加班工作,需要的人员数量如下表所示: 每个工作人员连续工作八小时,且在时段开始时上班,问如何安排,使得既满足以上要求,又使上班人数 最少? 五、分别用图解法和单纯形法求解下列线性规划问题.并对照指出单纯形迭代的每一步相当于图解法可行 域中的哪一个顶点。 六、用单纯形法求解下列线性规划问题: 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x 1+3x 2,约束形式为“≤”,X 3,X 4为松驰变量.表中解代入目标函数后得Z=10 (1)求表中a ~g 的值 (2)表中给出的解是否为最优解? (1)a=2 b=0 c=0 d=1 e=4/5 f=0 g=-5 (2) 表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1.minZ=2x 1+2x 2+4x 3 六、已知线性规划问题 应用对偶理论证明该问题最优解的目标函数值不大于25 运筹学期末试卷(B卷) 系别:工商管理学院专业:考试日期:年月日姓名:学号:成绩: 1.[10分] 匹克公司要安排4个工人去做4项不同的工作,每个工人完成各项工作所消耗的时间(单位:分钟)如下表所示: 要求:(1)建立线性规划模型(只建模型,不求解) (2)写出基于Lindo软件的源程序。 2.[15分]某公司下属甲、乙两个厂,有A原料360斤,B原料640斤。甲厂用A、B两种原料生产x1,x2两种产品,乙厂也用A、B两种原料生产x3,x4两种产品。每种单位产品所消耗各种原料的数量及产值、分配等如下 (1) 建立规划模型获取各厂最优生产计划。 (2) 试用图解法 求解最优结果。 3.[10分] 考虑下面的线性规划问题: 目标函数:Min Z=16x 1+16x 2 +17x 3 约束条件: 利用教材附带软件求解如下: **********************最优解如下************************* 目标函数最优值为 : 148.916 变量 最优解 相差值 ------- -------- -------- x1 7.297 0 x2 0 .703 x3 1.892 0 约束 松弛/剩余变量 对偶价格 ------- ------------- -------- 13123123123300.56153420,,0 x x x x x x x x x x x +≤-+≥+-≥≥ 1 20.811 0 2 0 -3.622 3 0 -4.73 目标函数系数范围: 变量下限当前值上限 ------- -------- -------- -------- x1 1.417 16 16.565 x2 15.297 16 无上限 x3 14.4 17 192 常数项数范围: 约束下限当前值上限 ------- -------- -------- -------- 1 9.189 30 无上限 2 3.33 3 15 111.25 3 -2.5 20 90 试回答下列问题: (1)第二个约束方程的对偶价格是一个负数(为-3.622),它的含义是什么? (2)x2有相差值为0.703,它的含义是什么? (3)请对右端常数项范围的上、下限给予具体解释,应如何应用这些数 第2章 线性规划的图解法 1.解: x ` A 1 (1) 可行域为OABC (2) 等值线为图中虚线部分 (3) 由图可知,最优解为B 点, 最优解:1x = 712,7152=x 。最优目标函数值:769 2.解: x 2 1 0 1 (1) 由图解法可得有唯一解 6.02.021==x x ,函数值为3.6。 (2) 无可行解 (3) 无界解 (4) 无可行解 (5) 无穷多解 (6) 有唯一解 38320 21== x x ,函数值为392。 3.解: (1). 标准形式: 3212100023m ax s s s x x f ++++= 0,,,,9 2213 2330 2932121321221121≥=++=++=++s s s x x s x x s x x s x x (2). 标准形式: 21210064m in s s x x f +++= ,,,4 6710 26 3212121221121≥=-=++=--s s x x x x s x x s x x (3). 标准形式: 21''2'2'10022m in s s x x x f +++-= 0,,,,30 22350 55270 55321''2'2'12''2'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x 4.解: 标准形式: 212100510m ax s s x x z +++= ,,,8259 432121221121≥=++=++s s x x s x x s x x 松弛变量(0,0) 最优解为 1x =1,x 2=3/2. 07级工管运筹学期末习题课 一、考虑线性规划问题(P )max 0 z CX AX b X ==?? ≥? (1) 若12,X X 均为(P )的可行解,[0,1]λ∈,证明12(1)X X λλ+-也是(P ) 的可行解; (2) 写出(P )的对偶模型(仍用矩阵式表示)。 二、有三个线性规划: (Ⅰ) [Min] z =CX (Ⅱ) [Min] z =CX (Ⅲ) [Min] z =CX 约束条件AX =b 约束条件AX =b 约束条件AX =b X 0 X 0 X 0 已知 X 是(Ⅰ)的最优解,X 是(Ⅱ)的最优解,X *是(Ⅲ)的最优解,Y 是(Ⅰ)的对偶问题的最优解, 试证:(1)()()'-'-≤**C C X X 0; (2) C X X Y b b ()()***-≤-。 三、已知线性规划问题 ?? ? ??=≥+=++++=++++++++=)5,,1(03.00)(max 2 253232221212 143132121115 43322111Λj x t b x x a x a x a t b x x a x a x a st x x x c x c x t c z j 当1t =2t =0时,用单纯形法求得最终表如下: 要求:1. 确定23222113121121321,,,,,,,,,,a a a a a a b b c c c 的值; 2. 当2t =0时,1t 在什么范围内变化上述最优解不变; 3. 当1t =0时,2t 在什么范围内变化上述最优基不变。 1x 2x 3x 4x 5x 3x 5/2 0 1/2 1 1/2 0 1x 5/2 1 -1/2 0 -1/6 1/3 j j z c - -4 -4 -2 管理运筹学第二版课后 习题参考答案 Document number【980KGB-6898YT-769T8CB-246UT-18GG08】 《管理运筹学》(第二版)课后习题参考答案 第1章 线性规划(复习思考题) 1.什么是线性规划线性规划的三要素是什么 答:线性规划(Linear Programming ,LP )是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化工具,能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误 答:(1)唯一最优解:只有一个最优点; (2)多重最优解:无穷多个最优解; (3)无界解:可行域无界,目标值无限增大; (4)没有可行解:线性规划问题的可行域是空集。 当无界解和没有可行解时,可能是建模时有错。 3.什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答:线性规划的标准型是:目标函数极大化,约束条件为等式,右端常数项0 i b ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答:可行解:满足约束条件0≥=X b AX ,的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示: 5.用表格单纯形法求解如下线性规划。 . ??? ??≥≤++≤++0,,862383 21321321x x x x x x x x x 解:标准化 32124max x x x Z ++= . ?? ? ??≥=+++=+++0,,,,862385432153 214 321x x x x x x x x x x x x x 列出单纯形表 《管理运筹学》期中复习题 答案 标准化文件发布号:(9312-EUATWW-MWUB-WUNN-INNUL-DQQTY- 《管理运筹学》期中测试题 第一部分 线性规划 一、填空题 1.线性规划问题是求一个 目标函数 在一组 约束条件 下的最值问题。 2.图解法适用于含有 两个 _ 变量的线性规划问题。 3.线性规划问题的可行解是指满足 所有约束条件_ 的解。 4.在线性规划问题的基本解中,所有的非基变量等于 零 。 5.在线性规划问题中,基本可行解的非零分量所对应的列向量线性 无 关 6.若线性规划问题有最优解,则最优解一定可以在可行域的 顶点_ 达到。 7.若线性规划问题有可行解,则 一定 _ 有基本可行解。 8.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其 可行解 的集合中进行搜索即可得到最优解。 9.满足 非负 _ 条件的基本解称为基本可行解。 10.在将线性规划问题的一般形式转化为标准形式时,引入的松驰变量在目标函数中的系数为 正 。 11.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入 松弛 _ 变量。 12.线性规划模型包括 决策变量 、目标函数 、约束条件 三个要素。 13.线性规划问题可分为目标函数求 最大 _ 值和 最小 _值两类。 14.线性规划问题的标准形式中,约束条件取 等 _ 式,目标函数求 最大 _值,而所有决策变量必须 非负 。 15.线性规划问题的基本可行解与基本解的关系是 基本可行解一定是基本解,反之不然 16.在用图解法求解线性规划问题时,如果取得最值的等值线与可行域的一段边界重合,则 _ 最优解不唯一 。 17.求解线性规划问题可能的结果有 唯一最优解,无穷多最优解,无界解,无可行解 。 18.如果某个约束条件是“ ”情形,若化为标准形式,需要引入一个 剩余 _ 变量。 19.如果某个变量X j 为自由变量,则应引进两个非负变量X j ′ , X j 〞, 同时令X j = X j ′ - X j 〞 j 。 20.表达线性规划的简式中目标函数为 线性函数 _ 。 21.线性规划一般表达式中,a ij 表示该元素位置在约束条件的 第i 个不等式的第j 个决策变量的系数 。 22.线性规划的代数解法主要利用了代数消去法的原理,实现_ 基变量 的转换,寻找最优解。 23.对于目标函数最大值型的线性规划问题,用单纯型法代数形式求解时,当非基变量检验数_ 非正 时,当前解为最优解。 24.在单纯形迭代中,选出基变量时应遵循_ 最小比值 法则。 二、单选题 1. 如果一个线性规划问题有n 个变量,m 个约束方程(m 第一章 第一章 1. 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量(Decision Variable)是决策问题待定的量值,取值一般为非负;约束条件(Constraint Conditions)是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数(Objective Function)是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.(1)设立决策变量; (2)确定极值化的单一线性目标函数; (3)线性的约束条件:考虑到能力制约,保证能力需求量不能突破有效供给量; (4)非负约束。 3.(1)唯一最优解:只有一个最优点 (2)多重最优解:无穷多个最优解 (3)无界解:可行域无界,目标值无限增大 (4)没有可行解:线性规划问题的可行域是空集 无界解和没有可行解时,可能是建模时有错。 4. 线性规划的标准形式为:目标函数极大化,约束条件为等式,右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 5. 可行解:满足约束条件AX =b,X≥0的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 6. 计算步骤: 第一步,确定初始基可行解。 第二步,最优性检验与解的判别。 第三步,进行基变换。 第四步,进行函数迭代。 判断方式: 唯一最优解:所有非基变量的检验数为负数,即σj< 0 无穷多最优解:若所有非基变量的检验数σj≤ 0 ,且存在某个非基变量xNk 的检验数σk= 0 ,让其进基,目标函数的值仍然保持原值。如果同时存在最小θ值,说明有离基变量,则该问题在两个顶点上同时达到最优,为无穷多最优解。无界解:若某个非基变量xNk 的检验数σk> 0 ,但其对应的系数列向量P k' 中,每一个元素a ik' (i=1,2,3,…,m)均非正数,即有进基变量但找不到离基变量。 管理运筹学模拟试题及 答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】 四川大学网络教育学院模拟试题( A ) 《管理运筹学》 一、单选题(每题2分,共20分。) 1.目标函数取极小(minZ)的线性规划问题可以转化为目标函数取极大的线性 规划问题求解,原问题的目标函数值等于(C)。 A. maxZ B. max(-Z) C. –max(-Z) 2.下列说法中正确的是(B)。 A.基本解一定是可行解B.基本可行解的每个分量 一定非负 C.若B是基,则B一定是可逆D.非基变量的系数列向量一定是 线性相关的 3.在线性规划模型中,没有非负约束的变量称为( D ) 多余变量 B.松弛变量 C.人工变量 D.自由变量 4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时, 可求得(A)。 A.多重解B.无解C.正则解 D.退化解 5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满 足最优检验但不完全满足( D )。 A.等式约束 B.“≤”型约束 C.“≥”约束 D.非负约束 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i y是 (B)。 A.多余变量B.自由变量C.松弛变量D.非 负变量 7.在运输方案中出现退化现象,是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8.树T的任意两个顶点间恰好有一条(B)。 A.边B.初等链C.欧拉圈 D.回路 9.若G中不存在流f增流链,则f为G的( B )。 A.最小流 B.最大流 C.最小费用流 D.无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满 足最优检验但不完全满足(D) A.等式约束B.“≤”型约束C.“≥”型约束 D.非负约束 二、多项选择题(每小题4分,共20分) 1.化一般规划模型为标准型时,可能引入的变量有() A.松弛变量 B.剩余变量 C.非负变量 D.非正变量E.自由变量 2.图解法求解线性规划问题的主要过程有() 《管理运筹学》考试试卷(A) 一、(20 分)下述线性规划问题 Max z=-5x1+5x2+13x3 ST -x1+x2+3x3 ≤ 20 ——① 12x1+4x2+10x3 ≤ 90 ——② x1,x2,x3 ≥ 0 先用单纯形法求出最优解,然后分析在下列条件下,最优解分别有什么变化? ( 1 )约束条件①的右端常数由20 变为30 ; ( 2 )约束条件②的右端常数由90 变为70 ; ( 3 )目标函数中的x3 的系数由13 变为8 ; ( 4 )增加一个约束条件③2x1+3x2+5x3 ≤ 50 ( 5 )将原有约束条件②变为10x1+5x2+10x3 ≤ 100 二、(10 分)已知线性规划问题 Max z= 2x1+x2+5x3+6x4 对偶变量 2x1 +x3+x4 ≤ 8 y1 2x1+2x2+x3+2x4 ≤ 12 y2 x1,x2,x3,x4 ≥ 0 其对偶问题的最优解为y1*=4 ,y2*=1 ,试用对偶问题的性质,求原问题的最优解。 三、(10 分)某地区有三个化肥厂,除供应外地区需要外,估计每年可供应本地区的数字为:化肥厂 A —— 7 万吨,B —— 8 万吨,C —— 3 万吨。有四个产粮区需要该种化肥,需要量为:甲地区—— 6 万吨,乙地区—— 6 万吨,丙地区—— 3 万吨,丁地区—— 3 万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下表所示(单位:元/ 吨): 根据上述资料指定一个使总的运费最小的化肥调拨方案。 四、(10 分)需要分配5 人去做5 项工作,每人做各项工作的能力评分见下表。应如何分派,才能使总的得分最大? 五、(10 分)用动态规划方法求解: Max F=4x 1 2 -x 2 2 +2x 3 2 +12 3x 1 +2x 2 +x 3 =9 x1,x2,x3 ≥ 0 六、(10 分)公司决定使用1000 万元开发A 、B 、C 三种产品,。经预测估计开发 运筹学试题四 一、对约束条件(20分) ??? ?? ---++=---++=----+=-≥=x x x x x x x x x x x x x x j j 123 56346712474817223241029017,, 说明解X=(1,2,1,0,0,0,0)T 是不是基可行解,假定不是,试找出一个基可行解。 二、已知线性规划问题(20分) ??422m 321321=++-+-=x x x x x x inz 12 五、用动态规划方法求解下列问题(25分) ???? ? max ,,z x x x x x x x j j =++≥≥=349 0123122232 123 六、求解下图的中国邮路问题(20分) 一、解: (1) ??----=1001A 解出 0,01,09431=>=>=x x x 由互补松弛定理:011=?s y x 得2,0211-=+∴=y y y s ① 033=?s y x 得2,0213-=-∴=ky y y s ② ①②联立得k y k k y +-=+-= 14 *,126*21 而**,'*,12*21y y Z Z 将=-=代入③ 12*6*421-=+∴y y ③ 则2*,6*,321=-=-=y y k 综上,3-=k ,对偶问题最优解为T T y y Y )2,6(),(*21-== 三、解:(1)表上作业法求解得: 四、解:用匈牙利法求解 ??????? ? ?46255132433656395132454740274135~ ??601003111571174150203??????? ??80 1200612271090001 ∴最优方案为:肖恩 安 材料准备, 琼 记录管理运筹学模拟试题及答案
《管理运筹学》第二版课后习题参考答案
运筹学模拟试题答案
《管理运筹学》第四版课后习题解析(上)
运筹学试卷及答案.doc
管理运筹学作业 韩伯棠第3版高等教育出版社课后答案
运筹学试题
管理运筹学模拟试题附答案
管理学管理运筹学课后答案——谢家平
《管理运筹学》复习题及参考答案
管理运筹学期末试卷题目B卷
《管理运筹学》课后习题答案
运筹学考试练习题(天津大学)
管理运筹学第二版课后习题参考答案
《管理运筹学》期中复习题答案
2019管理运筹学课后答案
管理运筹学模拟试题及答案
《管理运筹学》考试试卷A,B卷
管理运筹学试题四(含答案)