第四章 运筹学习题

第一章 线性规划1、由图可得：最优解为2、用图解法求解线性规划： Min z=2x 1+x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-01058244212121x x x x x x解：由图可得：最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x x x x x x解：由图可得：最优解Max z=5x 1+6x 2, Max z= +∞Maxz = 2x 1 +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,5242261552121211x x x x x x x由图可得：最大值⎪⎩⎪⎨⎧==+35121x x x ， 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥0,x 3’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束，321321321321,00632442392-x x x x x x x x x x x x解：令Z ’ = -z ，引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。

运筹学第四章习题答案4.1若用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？ （1）max ｛-d -+d ｝ （2）max ｛-d ++d ｝ （3）min ｛-d ++d ｝ （4）min ｛-d -+d ｝（1）合理，令f （x ）+-d -+d =b,当f （x ）取最小值时，-d -+d 取最大值合理。

(2)不合理，+d 取最大值时，f （x ）取最大值，-d 取最大值时，f （x ）应取最小值 （3）合理，恰好达到目标值时，-d 和+d 都要尽可能的小。

（4）合理，令f （x ）+-d -+d =b,当f （x ）取最大值时，-d -+d 取最小值合理。

4.2用图解法和单纯形法解下列目标规划问题（1）min ｛P 13+d ，P 2-2d ，P 3（-1d ++1d ）｝24261121=-+++-d d x x 52221=-+++-d d x x155331=-++-d d x3,2,1,0,,,21=≥+-i d d x x i i（2）min{P 1(+++43d d ),P 2+1d ,P 3-2d ,P 4(--+435.1d d )} 401121=-+++-d d x x1002221=-++--d d x x30331=-++-d d x 15442=-++-d d x4,3,2,1,0,,,21=≥+-i d d x x i i(1)图解法0 A B C X 1由图可知，满足域为线段EG,这就是目标规划方程的解，可求得：E,G 的坐标分别为（0，12），（3,3） 故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a(2)图解法 21由图可知，满足域为线段AB A(25,15),B(30,10)故该问题的解可表示为)1015,3025()10,30()15,25(212121a a a a a a ++=+ )1,0(212,1=+≥a a a a(1)单纯形法0 0 P1 0 0 P2 P3 P3CB XB x1 x2 bP3 P2 06 2 0 0 0 0 -1 1 245152 1 0 0 -1 1 0 05 0 -1 1 0 0 0 0P1P2P30 0 1 0 0 0 0 0-1 -1 0 0 1 0 0 0-6 -2 0 0 0 0 2 0P3P20 x1 0 2 1.2 -1.2 0 0 -1 1 6230 1 0.2 0.2 -1 1 0 01 0 -0.2 0.2 0 0 0 0P1 P2 P3 0 0 1 0 0 0 0 0 0 -1 -0.2 0.2 1 0 0 0 0 -2 -1.2 1.2 0 0 2 0P30 0x2x10 0 0.8 -0.8 2 -2 -1 1 2230 1 0.2 -0.2 -1 1 0 01 0 -0.2 0.2 0 0 0 0P1P2P30 0 1 0 0 0 0 00 0 0 0 0 1 0 00 0 -0.8 0.8 -2 2 2 00 0x2x10 0 0.4 -0.4 1 -1 -0.5 -0.5 1330 1 0.6 -0.6 0 0 0.5 0.51 0 -0.2 0.2 0 0 0 0P1P2P30 0 1 0 0 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 10 0 x22 0 0 0 1 -1 -0.5 -0.5 71253 1 0 0 0 0 0.5 0.55 0 -1 1 0 0 0 0P1P2P30 0 1 0 0 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 1故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a（2）P2P3P1P4P11.5P4CB XB x1 x2b 0 1 1 -1 1 00 0 0 0 0 401 1 0 0 -1 1 0 0 0 0 100 1 0 0 0 0 0 -1 1 00 301-1115P1 0 0 0 0 0 0 1 0 1 0P21P3 -1 -11 00 0 P4-11.5 0 0 1 0 -1 1 0 0 0 0 1 -1 251 0 0 0 -1 1 0 0 1 -1 85 1 0 0 0 0 0 -1 1 0 0 30 0x2 0 115P1 0 0 00 0 0 1 0 1 0P20 0-1 0P3 -1 01-1 1 P4 -1 00 51 0 x110 -1 1 0 0 0 0 1 -11-1-110 0 1 -1 0 0 -1 1 -1 1 30 0 x2 0 1 0 0 0 0 0 0 0 0 P1 0 0 0 0 0 0 1 0 1 0 P2 0 0 1 0 0 0 0 0 0 0 P3 0 0 -1 1 1 0 0 0 0 0P4-1111.54.3某商标的酒是用三种等级的酒兑制而成。

运筹学第三版课后习题答案第一章：引论1.1 课后习题习题1a)运筹学是一门应用数学的学科，旨在解决实际问题中的决策和优化问题。

它包括数学模型的建立、问题求解方法的设计等方面。

b)运筹学可以应用于各个领域，如物流管理、生产计划、流程优化等。

它可以帮助组织提高效率、降低成本、优化资源分配等。

c)运筹学主要包括线性规划、整数规划、指派问题等方法。

习题2运筹学的应用可以帮助组织提高效率、降低成本、优化资源分配等。

它可以帮助制定最佳的生产计划，优化供应链管理，提高运输效率等。

运筹学方法的应用还可以帮助解决紧急情况下的应急调度问题，优化医疗资源分配等。

1.2 课后习题习题1运筹学方法可以应用于各个领域，如物流管理、生产计划、供应链管理、流程优化等。

在物流管理中，可以使用运筹学方法优化仓储和运输的布局，提高货物的运输效率。

在生产计划中，可以使用运筹学方法优化产品的生产数量和生产周期，降低生产成本。

在供应链管理中，可以使用运筹学方法优化订单配送和库存管理，提高供应链的效率。

在流程优化中，可以使用运筹学方法优化业务流程，提高整体效率。

习题2在物流管理中，可以使用运筹学方法优化车辆的调度和路线规划，以提高运输效率和降低成本。

在生产计划中，可以使用运筹学方法优化生产线的安排和产品的生产量，以降低生产成本和提高产能利用率。

在供应链管理中，可以使用运筹学方法优化供应链各个环节的协调和调度，以提高整体效率和减少库存成本。

在流程优化中，可以使用运筹学方法优化业务流程的排布和资源的分配，以提高流程效率和客户满意度。

第二章：线性规划基础2.1 课后习题习题1线性规划是一种数学优化方法，用于解决包含线性约束和线性目标函数的优化问题。

其一般形式为：max c^T*xs.t. Ax <= bx >= 0其中，c是目标函数的系数向量，x是决策变量向量，A是约束矩阵，b是约束向量。

习题2使用线性规划方法可以解决许多实际问题，如生产计划、供应链管理、资源分配等。

第4章训练题实践能力训练1．某工厂生产A 、B 两种产品，产品A 每件利润为$10，而产品B 每件利润为$8，产品A 每件需3小时装配时间，而B 为2小时，每周总装配有效时间为120小时。

工厂允许加班，但加班生产出来的产品的利润得减去1美元，根据最近合同，厂商每天至少得向用户提供两种产品各30件。

通过与厂商经理交谈，确认如下事实：（1）与用户签定的合同必须遵守，且工厂正常工作时间只有120小时； （2）尽可能不加班；（3）求利润最大； 试建立此问题的数学模型。

1．设正常生产A 产品1x 件，B 产品3x 件，加班生产A 产品2x 件，B 产品4x 件。

则},,{m in 5443321ηρ-ηρ-η+η+η=a lex30..1121=ρ-η++x x t s 302243=ρ-η++x x 120233331=ρ-η++x x0234442=ρ-η++x x54078910554321=ρ-η++++x x x x0,,41≥x x 且为整数2．考虑双A 牌啤酒的混合问题。

D 厂用三种级别的白兰地（一，二，三）来生产三种混合酒(DT ,DTA ,QL )，三种级别的白兰地酒供应量受到严格限制，他们的供应量和成本如下： 一级 1,500加仑/日 $6.00 /加仑 二级 2,100加仑/日 $4.50 /加仑 三级 950 加仑/日 $3.00 /加仑双A 牌酒的信誉很高，为了保证质量，其生产配方受到严格控制，其配方如右表所示。

在此题中，把日供应量和混合比例设为硬约束，其余按其优先顺序表示如下：（1）求利润极大；（2）每日至少生产2，000加仑DT 酒。

试建立此问题的数学模型。

2．变量假设如表：},,{m in 1110987654321ηηη+ρ+η+ρ+η+ρ+ρ+ρ+ρ=a lex 1500..11312111=ρ-η+++x x x t s 210022322212=ρ-η+++x x x 95033332313=ρ-η+++x x x1.04413121112=ρ-η+++x x x x5.05513121111=ρ-η+++x x x x6.06623222123=ρ-η+++x x x x2.07723222121=ρ-η+++x x x x5.08833323133=ρ-η+++x x x x1.09933323131=ρ-η+++x x x x13650)(3)(5.4)(6)(5)(5.5)(61010332313322212312111333231232221131211=ρ-η+++-++-++-++++++++x x x x x x x x x x x x x x x x x x20001111131211=ρ-η+++x x x .3,2,1,,0=≥j i x ij3．动力公司生产单一类型的机动自行车（即小型汽油机动摩托车），称为美洲神风，这家公司同时也进口意大利的安全牌机器摩托车，神风牌每辆售价为$650，安全牌$725，需求情况是厂家生产或进口摩托车都能轻易地卖出去。

复习思考题第一章11判断下列说法是否正确：（a ）图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

（b ）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。

（c ）线性规划问题的每一个基解对应可行域的一个顶点。

（d ）如线性规划问题存在可行域，则可行域一定包含坐标的原点。

（e ）取值无约束的变量i x ，通常令'''i i i x x x =-，其中'''0,0i i x x ≥≥，在用单纯形法求得的最优解中，有可能同时出现'''0,0i i x x >>。

（f ）用单纯形法标准型的线性规划问题时，与0j σ>对应的变量都可以被选作入基变量。

（g ）单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。

（h ）单纯形法计算中，选取最大正检验数k σ对应的变量作为换入变量，将使目标函数值得到最快的增长。

（i ）一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。

（j ）线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。

(k)若1x 和2x 分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中1λ和2λ为任意正的实数。

（l ）线性规划用两阶段法求解时，第一阶段的目标函数通常写为min Giiz x=∑（G i x 为人工变量），但也可以写为mini Giiz k x=∑，只要所有i k 均为大于零的常数。

（m ）对一个有n 个变量，m 个约束的标准型的线性规划问题，其可行域顶点恰好是mn c 个。

（n)单纯形法的迭代计算过程是从一个可行解转到目标函数值更大的另一个可行解。

（o ）线性规划问题的可行解如为最优解，则该可行解一定是基本可行解。

《运筹学》第四章习题一、思考题1．运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等于1-+n m ？2． 用左上角法确定运输问题的初始基本可行解的基本步骤是什么？3． 最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到 运输问题的最优方案？4． 沃格尔法（V ogel 法）的基本思想是什么？它和最小元素法相比给出的运输问题的初始基本可行解哪一个更接近于最优解？为什么？5． 试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？6． 用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一的？7． 试述用位势法求检验数的原理、步骤和方法。

8． 试给出运输问题的对偶问题（对产销平衡问题）。

9． 如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。

10．一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？ 11．试述在表上作业法中出现退化解的涵义及处理退化解的方法。

二、判断下列说法是否正确1．运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形方法求解。

2．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。

3．在运输问题中，只要给出一组（1-+n m ）个非零的{}j i x ，且满足∑==nj i j i a x 1，∑==mi j j i b x 1，就可以作为一个基本可行解。

4．表上作业法实质上就是求解运输问题的单纯形法。

5．按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可以找到一闭回路，且此闭回路是唯一的。

6．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案将不会发生变化。

7．如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k ，最优调运方案将不会发生变化。