第2章 线性规划的图解法
1．解：
x
`
A 1 (1) 可行域为OABC
(2) 等值线为图中虚线部分
(3) 由图可知，最优解为B 点， 最优解：1x =712，7
152=x 。最优目标函数值：769
2．解： x 2
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.
5．解：
标准形式：
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 ，即目标函数最优值是103000 (2) 2，4有剩余，分别是330，15，均为松弛变量. (3) 50，0，200，0。 (4) 在[]500,0变化，最优解不变。在400到正无穷变化，最优解不变. (5) 因为1430 45021-≤-=- c c ,所以原来的最优产品组合不变. 8．解： (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 分别为4000，10000,回报率为60000。 (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 。目标函数最优值103000。 (2) 1，3车间的加工工时已使用完；2，4车间的加工工时没用完；没用完的加工工时数为 2车间330小时,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) 不发生变化，因为允许增加的百分比与允许减少的百分比之和 %1001005010025≤+ (11) 不发生变化，因为允许增加的百分比与允许减少的百分比之和%100140 60 14050≤+，其 最大利润为103000+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，表示投资额正好为1200000；约束条件2的剩余变量是0， 表示投资回报率正好是60000；约束条件3的松弛变量为700000，表示投资B 基金的投资额为370000。 (4) 当2c 不变时，1c 在3.75到正无穷的范围内变化，最优解不变； 当1c 不变时，2c 在负无穷到6.4的范围内变化，最优解不变。 (5) 约束条件1的右边值在[]1500000,780000变化，对偶价格仍为0.057（其它同理）。 (6) 不能，因为允许减少的百分比与允许增加的百分比之和 %1006 .32 25.44>+，理由见百分之一百法则。 3．解： (1) 18000，3000，102000，153000 (2) 总投资额的松弛变量为0，表示投资额正好为1200000；基金b 的投资额的剩余变量为 0，表示投资B 基金的投资额正好为300000； (3) 总投资额每增加1个单位，回报额增加0.1； 基金b 的投资额每增加1个单位，回报额下降0.06。 (4) 1c 不变时，2c 在负无穷到10的范围内变化，其最优解不变； 2c 不变时，1c 在2到正无穷的范围内变化，其最优解不变。 (5) 约束条件1的右边值在300000到正无穷的范围内变化，对偶价格仍为0.1； 约束条件2的右边值在0到1200000的范围内变化，对偶价格仍为-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种方案下料的原材料的根数分别为x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14，模型如下： 表4-1 各种下料方式 1234567891011121314 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 最优值为300。 2．解： 从上午11时到下午10时分成11个班次，设x i表示第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＝ 最优值为320。 (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）设x i表示第i班上班4小时临时工人数，y j表示第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 最优值为264。 安排如下： 在11：00－12：00安排8个三小时的班，在13：00－14：00安排1个三小时的班，在15：00－16：00安排1个三小时的班，在17：00－18：00安排4个三小时的班，在18：00－19：00安排6个四小时的班。 总成本最小为264元，能比第一问节省：320-264=56元。 3．解：设生产A、B、C三种产品的数量分别为x1，x2，x3，则可建立下面的 数学模型： max z＝10 x1＋12x2＋14x3 s.t. x1＋1.5x2＋4x3≤2000 2x1＋1.2x2＋x3≤1000 x1≤200 x2≤250 x3 ≤100 x1，x2，x3≥0 用管理运筹学软件我们可以求得此问题的解为： x1＝200，x2＝250，x3＝100，最优值为6400。 (1)在资源数量及市场容量允许的条件下，生产A 200件，B 250件，C 100件，可使生产 获利最多。 (2)A、B、C的市场容量的对偶价格分别为10元，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 最优值为47500。 (1)白天调查的有孩子的家庭的户数为700户，白天调查的无孩子的家庭的户数为300户， 晚上调查的有孩子的家庭的户数为0，晚上调查的无孩子的家庭的户数为1000户，可使总调查费用最小。 (2)白天调查的有孩子的家庭的费用在20到26元之间，总调查方案不会变化；白天调查 的无孩子的家庭的费用在19到25元之间，总调查方案不会变化；晚上调查的有孩子的家庭的费用在29到正无穷之间，总调查方案不会变化；晚上调查的无孩子的家庭的 费用在－20到25元之间，总调查方案不会变化。 (3)发调查的总户数在1400到正无穷之间，对偶价格不会变化； 有孩子家庭的最少调查数在0到1000之间，对偶价格不会变化； 无孩子家庭的最少调查数在负无穷到1300之间，对偶价格不会变化。 5．解：设第i个月签订的合同打算租用j个月的面积为x ij，则需要建立下面的数学模型：min f＝2800x11＋4500x12＋6000x13＋7300x14＋2800x21＋4500x22＋6000x23＋2800x31＋4500x32＋2800x41 s．t．x11≥15 x12＋x21≥10 x13＋x22＋x31≥20 x14＋x23＋x32＋x41≥12 x ij ≥0，i，j＝1，2，3，4 用管理运筹学软件我们可以求得此问题的解为： x11＝15，x12＝0，x13＝0，x14＝0，x21＝10，x22＝0，x23＝0，x31＝20，x32＝0，x41＝12，最优值为159600。即在一月份租用1500平方米一个月，在二月份租用1000平方米一个月，在三月份租用2000平方米一个月，四月份租用1200平方米一个月，可使所付的租借费最小。 6．解：设x ij表示第i种类型的鸡需要第j种饲料的量，可建立下面的数学模型：max z＝9（x11＋x12＋x13）＋7（x21＋x22＋x23）＋8（x31＋x32＋x33）－5.5（x11＋x21＋x31）－4（x12＋x22＋x32）－5（x13＋x23＋x33） s．t．x11≥0.5（x11＋x12＋x13） x12≤0.2（x11＋x12＋x13） x21≥0.3（x21＋x22＋x23） x23 ≤0.3（x21＋x22＋x23） x33≥0.5（x31＋x32＋x33） x11＋x21＋x31≤30 x12＋x22＋x32≤30 x13＋x23＋x33≤30 x ij ≥0，i，j＝1，2，3 用管理运筹学软件我们可以求得此问题的解为： x11＝30，x12＝10，x13＝10，x21＝0，x22＝0，x23＝0，x31＝0，x32＝20，x33＝20，最优值为335。即生产雏鸡饲料50吨，不生产蛋鸡饲料，生产肉鸡饲料40吨。 7．设X i 为第i 个月生产的产品I数量 Y i 为第i 个月生产的产品II数量 Z i ，W i 分别为第i 个月末产品I、II库存数 S i1，S i2 分别为用于第（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-100000=Z 10 X 11+Z 10-100000=Z 11 X 12+Z 11-100000=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 用管理运筹学软件我们可以求得此问题的解为： 最优值为4910500 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=105000, 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 用管理运筹学软件我们可以求得此问题的解为： **********************最优解如下************************* 目标函数最优值为 : 279400 变量 最优解 相差值 ------- -------- -------- 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 4 7000 8000 10000 5 无下限700 8400 6 6000 18000 无上限 7 9000 15000 18000 8 8000 14000 无上限 9 0 12000 无上限 10 0 10000 15000 即 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 最优值为279400 （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=3710000元 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 ，最优值为84。 (2) 最优解为（0，0，4）T ，最优值为-4。 6．解：有无界解 1237 x x +=12429 x x += 7．解： (1)无可行解 (2)最优解为（4，4）T，最优值为28。 (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 《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 《管理运筹学》复习题2014.12 一、填空题(每题3分，共18分) 1．运筹学中所使用的模型是数学模型。用运筹学解决问题的核心是建立数学模型，并对模型求解。 2.数学模型中，“s ·t ”表示约束。 3．运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。 4．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。 5．图解法适用于含有两个变量的线性规划问题。 6．线性规划问题的可行解是指满足所有约束条件的解。 7．在线性规划问题的基本解中，所有的非基变量等于零。 8．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。 9．满足非负条件的基本解称为基本可行解。 10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。 11．线性规划问题可分为目标函数求极大值和极小_值两类。 12．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。 13．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。 14.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。 15.物资调运问题中，有m 个供应地，A l ，A 2…，A m ，A j 的供应量为a i (i=1，2…，m)，n 个需求地B 1，B 2，…B n ，B 的需求量为b j (j=1，2，…，n)，则供需平衡条件为 ∑=m i i a 1= ∑=n j i b 1 16．物资调运方案的最优性判别准则是：当全部检验数非负时，当前的方案一定是最优方案。 17．可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n －1个(设问题中含有m 个供应地和n 个需求地) 18、供大于求的、供不应求的不平衡运输问题，分别是指∑=m i i a 1_＞∑=n j i b 1的运输问题、∑=m i i a 1_＜∑=n j i b 1的运输问题。 19．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。 20.运输问题的模型中，含有的方程个数为n+m 个 21．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。 22．在分枝定界法中，若选X r =4／3进行分支，则构造的约束条件应为X 1≤1，X 1≥2。 23．在0 - 1整数规划中变量的取值可能是_0或1。 24．分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 25.分枝定界法一般每次分枝数量为2个. 26．图的最基本要素是点、点与点之间构成的边 27．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。 28．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。 29．在图论中，图是反映研究对象_之间_特定关系的一种工具。 30．任一树中的边数必定是它的点数减1。 二、选择题（每题3分，共18分） 1．我们可以通过（ C ）来验证模型最优解。 A ．观察 B ．应用 C ．实验 D ．调查 2．建立运筹学模型的过程不包括（ A ）阶段。 A ．观察环境 B ．数据分析 C ．模型设计 D ．模型实施 3.运筹学运用数学方法分析与解决问题，以达到系统的最优目标。这个过程是一个（C ） A 解决问题过程 B 分析问题过程 C 科学决策过程 D 前期预策过程 4.从趋势上看，运筹学的进一步发展依赖于一些外部条件及手段，其中最主要的是（ C ） A 数理统计 B 概率论 C 计算机 D 管理科学 课程学习 《管理运筹学基础》 判断正误 线性规划问题的一般模型中不能出现等式约束。 正确答案：说法错误 2.在线性规划模型的标准型中,b j（j=1，2，…m）一定是非负的。正确答案：说法正确 解答参考： 3. 判断正误 线性规划问题的基本解一定是基本可行解 正确答案：说法错误 解答参考： 5. 判断正误 同一问题的线性规划模型是唯一的。 正确答案：说法错误 解答参考： 12.第一个顶点和最后一个顶点相同的闭链叫回路。 正确答案：说法错误 解答参考： 14. 判断正误 Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。 正确答案：说法正确 解答参考： 15.简述编制统筹图的基本原则。 参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点，没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。 17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。 参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是最优的。 2. 用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找出最优解。 正确答案：说法正确 单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的值增加更快。 正确答案：说法错误 解答参考： 6.若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。 正确答案：说法正确 解答参考： 8.表上作业法中，任何一种确定初始基本可行解的方法都必须保证有（m + n -1）个变量。正确答案：说法正确 解答参考： 9.用分枝定界法求解一个极大化整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界 正确答案：说法正确 《管理运筹学》第四版课后习题解析（上） 第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．解： 四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A ) 《管理运筹学》 一、 单选题（每题２分，共20分。） 1．目标函数取极小（minZ ）的线性规划问题可以转化为目标函数取极大的线性规 划问题求解，原问题的目标函数值等于（ C ）。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2. 下列说法中正确的是（ B ）。 Ａ．基本解一定是可行解 Ｂ．基本可行解的每个分量一定非负 Ｃ．若B 是基，则B 一定是可逆Ｄ．非基变量的系数列向量一定是线性相关的 3．在线性规划模型中，没有非负约束的变量称为 （ D ） 多余变量 B ．松弛变量 C ．人工变量 D ．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ A ）。 Ａ．多重解 Ｂ．无解 Ｃ．正则解 Ｄ．退化解 5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 （ D ）。 A ．等式约束 B ．“≤”型约束 C ．“≥”约束 D ．非负约束 6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y 是（ B ）。 Ａ．多余变量 Ｂ．自由变量 Ｃ．松弛变量 Ｄ．非负变量 7.在运输方案中出现退化现象，是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8. 树Ｔ的任意两个顶点间恰好有一条（ B ）。 Ａ．边 Ｂ．初等链 Ｃ．欧拉圈 Ｄ．回路 9．若G 中不存在流f 增流链，则f 为G 的 （ B ）。 A ．最小流 B ．最大流 C ．最小费用流 D ．无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ 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 / 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章线性规划(复习思考题) 1. 什么是线性规划？线性规划的三要素是什么？ 答：线性规划(Lin ear Programmi ng , LF)是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2. 求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答：(1)唯一最优解：只有一个最优点； (2)多重最优解：无穷多个最优解； (3)无界解：可行域无界，目标值无限增大； (4)没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3. 什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项 ' ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业 来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明 “遅 约束的左边取值大于右边规划值，出现剩余量。 4?试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关 系。 答：可行解：满足约束条件 扎—‘丸 的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5 ?用表格单纯形法求解如下线性规划 解：标准化 1 可行基：对应于基可行解的基，称为可行基。 基可行解 SA] + S 2 运筹学试题 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．若原问题为元界解，则对偶问题也为无界解 上交作业课程题目可以打印，答案必须手写，否则该门成绩0分。 管理运筹学 作业题 一、名词解释(每题3分，共15分) 1. 可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一 组决策变量的取值，都称为该线性规划的一个可行解，所有可行解构成的集合称为该线性规划的可行域（类似函数的定义域），记为K 。 2. 最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称 为该线性规划的一个最优解。线性规划的最优解不一定唯一，若其有多个最优解，则所有最优解所构成的集合称为该线性规划的最优解域。 3. 状态：指每个阶段开始时所处的自然状态或客观条件。 4. 决策树：决策树(Decision Tree ）是在已知各种情况发生概率的基础上，通过构成决策 树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。 5. 最大最小准则：最大最小准则又称小中取大法或悲观法。为不确定型决策的决策准则之 一，其决策的原则是“小中取大”。这种决策方法的思想是对事物抱有悲观和保守的态度，在各种最坏的可能结果中选择最好的。决策时从决策表中各方案对各个状态的结果选出最小值，即在表的最右列，再从该列中选出最大者。这种方法的基本态度是悲观与保守。其基本思路是首先找出最不利情况下的最大收益。 二、 简答题（每题6分，共24分） 1. 简述单纯形法的基本步骤。 答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数j σ对初始基可行解进行最优性检验，若0≤j σ ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至0≤j σ，求得最优解为止。 2. 简述动态规划的基本方程。 答：对于n 阶段的动态规划问题，在求子过程上的最优指标函数时，k 子过程与k+1过程有如下递推关系： 对于可加性指标函数，基本方程可以写为 n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)}(),({)(11) ( =+=++∈ 终端条件：f n+1 (s n+1) = 0 管理运筹学 ——管理科学方法谢家平 第一章 第一章 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 第一章 思考题、主要概念及内容 1、了解运筹学的分支，运筹学产生的背景、研究的内容和意义。 2、了解运筹学在工商管理中的应用。 3、体会管理运筹学使用相应的计算机软件，注重学以致用的原则。 第二章 思考题、主要概念及内容 图解法、图解法的灵敏度分析 复习题 1. 考虑下面的线性规划问题： max z=2x1+3x2； 约束条件： x1+2x2≤6， 5x1+3x2≤15， x1，x2≥0． (1) 画出其可行域． (2) 当z=6时，画出等值线2x1+3x2=6． (3) 用图解法求出其最优解以及最优目标函数值． 2. 用图解法求解下列线性规划问题，并指出哪个问题具有惟一最优解、无穷多最优解、无界解或无可行解． (1) min f=6x1+4x2； 约束条件： 2x1+x2≥1， 3x1+4x2≥3， x1，x2≥0． (2) max z=4x1+8x2； 约束条件： 2x1+2x2≤10， -x1+x2≥8， x1,x2≥0． (3) max z=3x1-2x2； 约束条件： x1+x2≤1， 2x1+2x2≥4， x1，x2≥0． (4) max z=3x1+9x2； 约束条件： -x1+x2≤4， x2≤6， 2x1-5x2≤0， x1，x2≥0 3. 将下述线性规划问题化成标准形式： (1) max f=3x1+2x2； 约束条件： 9x1+2x2≤30， 3x1+2x2≤13， 2x1+2x2≤9， x1，x2≥0． (2) min f=4x1+6x2； 约束条件： 3x1-x2≥6， x1+2x2≤10， 7x1-6x2=4， x1，x2≥0． (3) min f=-x1-2x2； 约束条件： 3x1+5x2≤70, -2x1-5x2=50， -3x1+2x2≥30， x1≤0，-∞≤x2≤∞． (提示：可以令x′1=-x1，这样可得x′1≥0．同样可以令x′2-x″2=x2，其中x′2，x″2≥0．可见当x′2≥x″2时，x2≥0；当x′2≤x″2时，x2≤0，即-∞≤x2≤∞．这样原线性规划问题可以化为含有决策变量x′1，x′2，x″2的线性规划问题，这里决策变量x′1，x′2，x″2≥0．) 4. 考虑下面的线性规划问题： min f=11x1+8x2； 约束条件： 10x1+2x2≥20， 3x1+3x2≥18， 4x1+9x2≥36， x1，x2≥0． (1) 用图解法求解． (2) 写出此线性规划问题的标准形式． (3) 求出此线性规划问题的三个剩余变量的值． 5. 考虑下面的线性规划问题： max f=2x1+3x2； 约束条件： x1+x2≤10， 2x1+x2≥4， 09 <<运筹>>期末考试试卷（A）答案 一、不定项选择题（每小题2分共20分） 1、A 2、B 3、ABCD 4、ABC 5、D 6、C 7、B 8、ABCD 9、ABC 10、ABC 二、名词解释（每小题4分，共20分） 1、运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用期并提供优化决策方案的科学。 2、线性规划是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。 3、如果系统中包含元素A、B、C、K….等，按照经典意义（非模糊，非统计意义）的原则来聚类。 4、系统的综合性原则是指系统内部各组成部分的联系与协调，包含要素间的协调及系统与环境问题的协调。 5、TSP问题称为“旅行推销员问题”，是指：有N个城市A、B、…….等，它们这间有一定的距离，要求一条闭合路径，由某城市出发，每个城市经历过一次，最终返回原城市，所经历的路程最短。 三、简答题（每小题5分，共28分） 1、列出一些企业产品结构优化的柔性模型约束条件。 （1）关键设备的生产能力（2）各类能源的约束（3）工艺的约束 （4）产品类结构关系，以及物流过程中上、下游产品供需的约束 （5）某些产品的下限约束（6）非负约束 2、排队规则：损失制等待制：先到先服务、后到先服务、随机服务、优先权 服务混合制 3、运筹学的特点：（1）以最优性为核心。（2）以模型化为特征（3）以计算机为主要实现手段。（4）多学科交融 4、神经元的功能：（1）整合功能（2）兴奋与抑制（3）突触延时与不应期（4）学习、遗忘与疲劳 四、应用题。（每题15分，共45分） 1、设A、B的产量为X、Y 模型：目标MAX利润=500X+900Y 约束条件：9X+4Y≤360 4X+5Y≤200 3X+10Y≤300 X、Y均大于或等于零 图解略 最优解：X=20千克 Y=24千克利润31600元 2、企业在选择运用“农村包围城市”还是“城市中心”的指导思想时，应考虑自己的条件，竞争对手的情况，宏观和中观形势。 如，我国不少实力较弱的汽车企业，在发展之初，面临国内合资企业和国外汽车巨头的压力下，以农村，或三、四线城市为突破口，先在这些国内合资企业和国外汽车巨头不太重视的地区发展市场，在积累资金、经验、管理、技术等生产经营资源后，向大城市等竞争激烈的地区进军。 如果企业与国外合资，或在资金、技术、品牌、管理等方面有较大的优势，企业可以一开始就以广州等一线城市为主战场。 3、（1）如果两国没有任何的协调，A国最终会选择报复，因为只要A国选择报复，不论B国如何选择，对A国来说都最佳选择。反之亦然。 （2）如果两国协调，如果协调成功两国的对策是都不报复，如果两国协调不成功，两国都会选择报复。 第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. 《运筹学》模拟试题及参考答案 一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。) 1. 图解法提供了求解线性规划问题的通用方法。( ) 2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数C j-Z j ≥0，则问题达到最优。( ) 3. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。( ) 4. 满足线性规划问题所有约束条件的解称为基本可行解。( ) 5. 在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。( ) 6. 对偶问题的目标函数总是与原问题目标函数相等。( ) 7. 原问题与对偶问题是一一对应的。( ) 8. 运输问题的可行解中基变量的个数一定遵循m＋n－1的规则。( ) 9. 指派问题的解中基变量的个数为m＋n。( ) 10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。( ) 11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。( ) 12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。( ) 13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。( ) 14. 单目标决策时，用不同方法确定的最佳方案往往是一致的。( ) 15. 动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。 ( ) 三、填空题 1. 图的组成要素；。 2. 求最小树的方法有、。 3. 线性规划解的情形有、、、。 4. 求解指派问题的方法是。 5. 按决策环境分类，将决策问题分为、、。 6. 树连通，但不存在。 1 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 列出单纯形表 管理运筹学试题（A） 一．单项选择（将唯一正确答案前面的字母填入题后的括号里。正确得1分，选错、多选或不选得0分。共15分） 1．在线性规划模型中，没有非负约束的变量称为（） A．多余变量B．松弛变量C．自由变量D．人工变量 正确答案：A: B: C: D: 2．约束条件为AX=b，X≥0的线性规划问题的可行解集是（）A．补集B．凸集C．交集D．凹集 正确答案：A: B: C: D: 3．线性规划问题若有最优解，则一定可以在可行域的（）上达到。A．内点B．外点C．极点D．几何点 正确答案：A: B: C: D: 4．对偶问题的对偶是（） A．基本问题B．解的问题C．其它问题D．原问题 正确答案：A: B: C: D: 5．若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变量的（） A．值B．个数C．机会费用D．检验数 正确答案：A: B: C: D: 6．若运输问题已求得最优解，此时所求出的检验数一定是全部（）A．大于或等于零B．大于零C．小于零D．小于或等于零 正确答案：A: B: C: D: 7．设V是一个有n个顶点的非空集合，V={v1，v2，……，vn}，E是一个有m条边的集合，E={e1，e2，……em}，E中任意一条边e是V 的一个无序元素对[u，v]，（u≠v），则称V和E这两个集合组成了一个（） A．有向树B．有向图C．完备图D．无向图 正确答案：A: B: C: D: 8．若开链Q中顶点都不相同，则称Q为（） A．基本链B．初等链C．简单链D．饱和链 正确答案：A: B: C: D: 9．若图G 中没有平行边，则称图G为（） A．简单图B．完备图C．基本图D．欧拉图 正确答案：A: B: C: D: 10．在统筹图中，关键工序的总时差一定（） A．大于零B．小于零C．等于零D．无法确定 正确答案：A: B: C: D: 11．若Q为f饱和链，则链中至少有一条后向边为f （） A．正边B．零边C．邻边D．对边 正确答案：A: B: C: D: 12．若f 是G的一个流，K为G的一个割，且Valf=CapK，则K一定是（） A．最小割B．最大割C．最小流D．最大流 正确答案：A: B: C: D: 13．对max型整数规划，若最优非整数解对应的目标函数值为Zc，最优整数解对应的目标值为Zd，那么一定有( ) A．Zc ∈Zd B．Zc =Zd C．Zc ≤Zd D．Zc ≥Zd 正确答案：A: B: C: D: 14．若原问题中xI为自由变量，那么对偶问题中的第i个约束一定为（）A．等式约束B．“≤”型约束C．“≥”约束D．无法确定 正确答案：A: B: C: D: 15．若f*为满足下列条件的流：Valf*=max{Valf |f为G的一个流}，则称f*为G的（） A．最小值B．最大值C．最大流D．最小流 正确答案：A: B: C: D:《管理运筹学》第二版课后习题参考答案
《管理运筹学》复习题2014.12
管理运筹学基础 答案
《管理运筹学》第四版课后习题解析(上)
管理运筹学模拟试题及答案
运筹学试卷及答案.doc
管理运筹学后习题参考答案汇总
运筹学试题
管理运筹学(本科)(参考答案)学习版.doc
管理学管理运筹学课后答案——谢家平
《管理运筹学》复习题及参考答案
管理运筹学课后习题
管理运筹学--答案
《管理运筹学》课后习题答案
运筹学试卷及答案完整版
运筹学考试练习题(天津大学)
管理运筹学第二版课后习题参考答案
管理运筹学试题
相关主题
文本预览