运筹学（第2版）习题答案第1章 线性规划 P36~40第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页习题一1.1 讨论下列问题：（1）在例1.2中，如果设x j (j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路．（3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．(5)在单纯形法中，为什么说当00(1,2,,)k ik a i m λ>≤=并且时线性规划具有无界解。

1.2 工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．310和130.试建立该问题的数学模型,使每月利润最大．【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为123123123123123max 1014121.5 1.2425003 1.6 1.21400150250260310120130,,0Z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨≤≤⎪⎪≤≤⎪≥⎪⎩1.3 建筑公司需要用6m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：【解】设x j （j =1,2,…，14）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为14112342567891036891112132347910121314min 2300322450232400232346000,1,2,,14jj j Z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x j ==⎧+++≥⎪++++++≥⎪⎪++++++≥⎨⎪++++++++≥⎪⎪≥=⎩∑ 用单纯形法求解得到两个基本最优解 X (1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X (2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为134131412342567891036891112132347910121314min 0.60.30.70.40.82300322450232400232346000,1,2,,14j Z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x j =+++++⎧+++≥⎪++++++≥⎪⎪++++++≥⎨⎪++++++++≥⎪⎪≥=⎩ 用单纯形法求解得到两个基本最优解X (1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 X (2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 显然用料最少的方案最优。

1.4某企业需要制定1～6月份产品A 的生产与销售计划。

已知产品A 每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。

1～6月份产品A的单件成本与售价如表1－25所示。

（2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。

【解】设x j、y j（j＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为（1）112233445566111211223112233411223344511223344556max300350330340320350360420360410300340800800800800800Z x y x y x y x y x y x yxx y xx y x y xx y x y x y xx y x y x y x y xx y x y x y x y x y x=-+-+-+-+ -+-+≤-+≤-+-+≤-+-+-+≤-+-+-+-+≤-+-+-+-+-+≤111122112233112233441122334455112233445566800200200200200200200,0;1,2,,6j jx yx y x yx y x y x yx y x y x y x yx y x y x y x y x yx y x y x y x y x y x yx y j⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪-+≤⎨⎪-+-+≤⎪⎪-+-+-+≤⎪-+-+-+-+≤⎪⎪-+-+-+-+-+≤⎪-+-+-+-+-+-+≤⎪⎪≥=⎩（2）目标函数不变，前6个约束右端常数800改为1000，第7～11个约束右端常数200改为0，第12个约束“≤200”改为“＝－200”。

1.5 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资：方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元．投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.【解】是设x ij为第i年投入第j项目的资金数，变量表如下112131122334111211212312213134122334max 0.20.20.20.50.60.3300001.2300001.5 1.2300002000015000100000,1,,3;1,4ij Z x x x x x x x x x x x x x x x x x x x i j =+++++⎧+≤⎪-++≤⎪⎪--++≤⎪⎪≤⎨⎪≤⎪⎪≤⎪≥==⎪⎩最优解X=(30000，0，66000，0，109200，0)；Z ＝847201.6 炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利润5元，见表1－26。

表1－27解 设x ij 为第i （i ＝1,2,3,4）种成品油配第j (j =1,2,…,7)种半成品油的数量（桶）。

总利润：11121321222334353637444546475() 4.2()3() 1.5()Z x x x x x x x x x x x x x x =+++++++++++++高级汽油和一般汽油的辛烷值约束11121321222311121321222380115105)8011510594,8494x x x x x x x x x x x x ++++≥≤≤++++航空煤油蒸气压约束34353637343536371.50.60.051x x x x x x x x ++≤++＋＋一般煤油比例约束44454647:::10:4:3:1x x x x =即4546444546471043,,431x x x x x x === 半成品油供应量约束1121122213233444354536463747200010001500120010001000800x x x x x x x x x x x x x x +≤+≤+≤+≤+≤+≤+≤ 整理后得到111213212223343536374445464711121321222321222335363744454546464max 555 4.2 4.2 4.23333 1.5 1.5 1.5 1.5142111014211104312100.50.40.95041003403Z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x =+++++++++++++-++≥-++≤-++≥--≤-=-=-7112112221323344435453646374702000100015001200100010008000;1,2,3,4;1,2,,7ij x x x x x x x x x x x x x x x i j ⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪=⎪⎪+≤⎨⎪+≤⎪⎪+≤⎪+≤⎪⎪+≤⎪+≤⎪⎪+≤⎪≥==⎪⎩1.7 图解下列线性规划并指出解的形式：(1)12 1211212max 2.52 280.5 1.5210,0Z x x x xxx xx x=++≤⎧⎪≤⎪⎨+≤⎪⎪≥⎩【解】最优解X＝（2，4）；最优值Z=13(2)12 1212112max38122 23,0Z x x x xx xxx x=++≤⎧⎪+≤⎪⎨≤⎪⎪≥⎩【解】有多重解。

最优解X（1）＝（3/2，1/2）；X（2）＝（4/5，6/5）最优值Z=2(3)12 1212121212min32211410 2731,0Z x x x xx xx xx xx x=-++≤⎧⎪-+≤⎪⎪-≤⎨⎪-≤⎪⎪≥⎩【解】最优解X＝（4，1）；最优值Z=－10，有唯一最优解(4)12 1212212min4628830,0Z x x x xx xxx x=++≥⎧⎪+≤⎪⎨≤⎪⎪≥≥⎩【解】最优解X＝（2，3）；最优值Z=26，有唯一最优解(5) ⎪⎪⎩⎪⎪⎨⎧≥≤≥≥-+=0,6322max 21212121x x x x x x x x Z【解】无界解。

(6)12 121212min25262,0Z x x x xx xx x=-+≥⎧⎪+≤⎨⎪≥⎩【解】无可行解。

1.8 将下列线性规划化为标准形式 (1)123123123123123max 423205743103650,0,Z x x x x x x x x x x x x x x x =+-++≤⎧⎪-+≥⎪⎨++≥-⎪⎪≥≥⎩无限制【解】（1）令654''3'33,,,x x x x x x -=为松驰变量 ，则标准形式为'''1233'''12334'''12335'''12336'''1233456max 42332057443103665,,,,,,0Z x x x x x x x x x x x x x x x x x x x x x x x x x x =+-+⎧++-+=⎪-+--=⎪⎨---++=⎪⎪≥⎩ (2) 123123112123min 935|674|205880,0,0Z x x x x x x x x x x x x =-++-≤⎧⎪≥⎪⎨+=-⎪⎪≥≥≥⎩ 【解】（2）将绝对值化为两个不等式，则标准形式为123123412351612123456max 9356742067420588,,,,,0Z x x x x x x x x x x x x x x x x x x x x x '=-+-+-+=⎧⎪--++=⎪⎪-=⎨⎪--=⎪⎪≥⎩ (3)1211212max 231510,0Z x x x x x x x =+≤≤⎧⎪-+=-⎨⎪≥≥⎩【解】方法1：121314121234max 23151,,,0Z x x x x x x x x x x x x =+-=⎧⎪+=⎪⎨-=⎪⎪≥⎩ 方法2：令111111,1,514x x x x x '''=-+≤-=有＝ 1211212max 2(1)34(1)1,0Z x x x x x x x '=++'≤⎧⎪'-++=-⎨⎪≥⎩则标准型为121312123max 22340,,0Z x x x x x x x x x '=++'+=⎧⎪'-+=⎨⎪'≥⎩(4) 12123123123123123max min(34,)2304215965,0Z x x x x x x x x x x x x x x x x x =+++++≤⎧⎪-+≥⎪⎨++≥-⎪⎪≥⎩无约束、【解】令1212311134,,y x x y x x x x x x '''≤+≤++=-，线性规划模型变为11211231123112311231123max 3()42304()2159()65,,0Z yy x x x y x x x xx x x x x x x x x x x x x x x x ='''≤-+⎧⎪'''≤-++⎪⎪'''-++≤⎪⎨'''--+≥⎪⎪'''-++≥-⎪'''≥⎪⎩、 标准型为112411235112361123711238112345678max 33400230442159965,,,,,,,,0Z yy x x x x y x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ='''-+-+=⎧⎪'''-+--+=⎪⎪'''-+++=⎪⎨'''--+-=⎪⎪'''-+--+=⎪'''≥⎪⎩1.9 设线性规划⎪⎩⎪⎨⎧=≥=+-=+++=4,,1,06024503225max 42132121 j x x x x x x x x x Z j取基11322120(P )4041B B ⎡⎤⎡⎤==⎢⎥⎢⎥⎣⎦⎣⎦，P 、＝，分别指出B B 12和对应的基变量和非基变量，求出基本解，并说明B B 12、是不是可行基．【解】B 1：x 1，x 3为基变量，x 2，x 4为非基变量,基本解为X=（15，0，20，0）T，B 1是可行基。