当前位置:文档之家› 《运筹学》课后习题答案 第1章 线性规划与单纯形法

《运筹学》课后习题答案 第1章 线性规划与单纯形法

一、选择填空1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、判断正误1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三、将下列问题化为标准型1.123412341231324237..2358,0,0,Max Z x x x x x x x x s t x x x x x x x =++++++≤⎧⎪-+=-⎨⎪≥≤⎩符号不限[解] 令'22x x =-,'445x x x =-,在约束1中引入非负的松弛变量6x ,约束2两边同乘以-1。

整理得:''12345''123456'123''12345623()()7..23()58,,,,,0Max Z x x x x x x x x x x x s t x x x x x x x x x =-++-⎧-++-+=⎪-+--=⎨⎪≥⎩即:12345123456123123456237..2358,,,,,0Max Z x x x x x x x x x x x s t x x x x x x x x x =-++--++-+=⎧⎪---=⎨⎪≥⎩2. Min Z=-x 1+5x 2-2x 3x 1 +x 2- x 3 ≤ 61 - x2 +3x3 ≥ 5x 1 + x 2 = 10x 1 ≥ 0, x 2 ≤ 0, x 3符号不限[x 3进行处理,令x 3 = x’3- x 4;再令x’2 = - x 2。

然后对目标函数和约束条件进行标准化。

Max Z=x 1+5x 2+2x 3-2x 4x 1- x 2- x 3+x 4+x 5 = 61 + x2 +3x3 - 3x4 -x 6 = 5x 1 - x 2 = 10 x 1, x 2, x 3, x 4, x 5, x 6≥ 0四、用图解法求解下列线性规1.1+2x 2x 1- x 2 ≥ -2x 1 +2x 2 ≤ 6x 1, x 2 ≥ 0[解]根据上图,最优解为X *=(x 1, x 2)T =(6, 0)T ,最优值为-6。

1+2x 2x 1- x 2 ≥ -2x 1 +2x 2 ≤ 6x 1, x 2 ≥ 0 [根据上图,最优解为*1228(,)(,)33T T x x ==X ,最优值为143。

五、用单纯形法求解下列线性规划 1. Max Z=3x 1+5x 2x 1 ≤42 ≤ 123x 1 +2x 2 ≤18x 1, x 2≥ 0[解] 首先,标准化后线性规划如下: (1)Max Z=3x 1+5x 2+0x 3+0x 4+0x 5x 1+ x 3 = 42 + x 4 = 123x 1 +2x 2 + x 5 = 18x 1, x 2, x 3, x 4, x 5, x 6≥ 0max2. Max Z=2x 1- x 2+x 33x 1+x 2+x 3 ≤ 60x 1-x 2+2x 3 ≤ 10x 1 +x 2-x 3 ≤ 20x 1, x 2, x 3 ≥ 0[ (1)Max Z=2x 1-x 2+x 33x 1+x 2+x 3+x 4 = 60 x 1-x 2+2x 3+x 5 = 10x 1 +x 2-x 3 +x 6 = 20x 1, x 2, x 3, x 4, x 5, x 6≥ 0 max六、表格单纯形法计算题1. (2)初始线性规划模型如下:Max Z=5x 1+20x 2+25x 32x 1+x 2≤ 402x 2+x 3 ≤ 303x 1 -1/2x 3 ≤ 15x 1, x 2, x 3 ≥ 0(3)用单纯形法求出最优解及相应的最优值。

七、用大M 法和两阶段法求解下列线性规划1+2x 2-x 1 +2x 2 ≥ 2x 1 ≤ 3x 1, x 2 ≥ 0[x 5后,线性规划模型如下:M ax Z’=-x 1-2x 2-Mx 5-x 1+2x 2 -x 3 +x 5 = 2x 1 +x 4 = 3x 1, x 2, x 3, x 4, x 5 ≥ 0max 最优解X * =(0, 1, 0, 3)T ,最优值为Z min =2。

用两阶段法求解如下: 第一阶段:标准化并引入人工变量x 5,对人工变量进行优化线性规划模型如下:5-x 1+2x 2-x 3+x 5 = 2x 1 +x 4 = 3x 1, x 2, x 3, x 4, x 5 ≥ 0 524 第二阶段:M ax Z’=-x 1-2x 2-1/2x 1+x 2 -1/2x 3 = 1 x 1 +x 4 = 3x 1, x 2, x 3, x 4≥ 0由于上表中所有非基变量的检验数小于等于0,因此,原问题已经达到最优解,即X * =(0, 1, 0, 3)T ,最优值为Z min =2。

2. Max Z=x 1+2x 2+3x 3-x 4x 1+2x 2+3x 3 = 15 2x 1+x 2+5x 3 = 20x 1 +2x 2+x 3+x 4 = 10x 1, x 2, x 3, x 4 ≥ 0[解] 首先,标准化并引入人工变量x 5, x 6后,线性规划如下: (1)Max Z=x 1+2x 2+3x 3-x 4-Mx 5-Mx 6x 1+2x 2+3x 3+x 5 = 15 2x 1+x 2+5x 3+x 6 = 20x 1 +2x 2+x 3+x 4 = 10 x 1, x 2, x 3, x 4 ≥ 0max1- x 2-x3x 1-2x 2+x 3 ≤ 11 -4x 1+x 2+2x 3 ≥ 3-2x 1 +x 3 = 1x 1, x 2, x 3 ≥ 0[解] 首先,标准化并引入人工变量x 6, x 7后,线性规划如下:1-x 2-x 3-Mx 6-Mx 7x 1-2x 2+x 3 +x 4 = 11 -4x 1+x 2+2x 3 -x 5+x 6 = 3-2x 1 +x 3+x 7 = 1x 1, x 2, x 3, x 4, x 5, x 6, x 7≥ 0 maxmin转入第二阶段求解如下:max八、线性规划建模1. 某商店制定一种商品的7~12月进货与销售计划。

由于商店仓库容量的限制,存货不能超过500件。

6月底已存货100件,以后每月1日进货一次。

假设各月份该种商品买进及销售单价如下表所示,问各月应进货、销售各多少,才能是总收入最多?试列出线性规划模型。

[解]设7-12月份进货量分别为x11, x21, x31, x41, x51, x61; 销售量分别为x12, x22, x32, x42, x52, x62。

则最大化目标函数可以表示为各个月的销售总收入与各个月进货总成本的差额。

而约束条件包括两方面:月初库存量、月末库存量约束,库存要求介于[0,500]区间,因此,模型构造如下:Max Z =(29x12+24x22+26x32+28x42+22x52+25x62)-(28x11+24x21+25x31+27x41+23x51+23x61)100+x11-x12 ≥ 0 (或者x12 ≤ 100+ x11)x21 ≤ 500-(100+x11-x12)100+x11-x12+x21-x22 ≥ 0x31 ≤ 500-(100+x11-x12+x21-x22)100+x11-x12+x21-x22+x31-x32 ≥ 0x41 ≤ 500-(100+x11-x12+x21-x22+x31-x32)100+x11-x12+x21-x22+x31-x32+x41-x42 ≥ 0x51 ≤ 500-(100+x11-x12+x21-x22+x31-x32+x41-x42)100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52 ≥ 0x61 ≤ 500-(100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52)100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52+x61-x62 ≥ 0x11, x21, x31, x41, x51, x61, x12, x22, x32, x42, x52, x62 ≥ 03. 某厂生产A、B、C 三种产品,每种产品都要经过甲、乙两道工序。

设该厂有两种规格的设备,甲1和甲2可以完成甲工序;有3种规格的设备乙1、乙2、乙3能完成乙工序。

每种设备完成每个产品的加工工时、每小时的费用以及每件产品的原料费用和销售价格如表1.12所示,其中空缺位置表示该设备不能加工解:(1)决策变量:设A 产品经过甲乙两道工序(5种规格)加工的产品数分别为1121314151,,,,x x x x x ; B 产品经过甲乙两道工序(5种规格)加工的产品数分别为1222324252,,,,x x x x x ; C 产品经过甲乙两道工序(5种规格)加工的产品数分别为1323334353,,,,x x x x x ;(2)目标函数:总利润=收益-工时成本C1-材料成本C2收益=A 产品数×单价+B 产品数×单价+C 产品数×单价=11211222231.5() 2.5()4x x x x x ⨯++⨯++⨯C1=11120.10(48)x x ⨯++2122230.05(379)x x x ⨯+++32330.08(62)x x ⨯++41430.12(55)x x ⨯++51520.07(63)x x ⨯+C2=11211222230.3()0.5()0.8x x x x x ⨯++⨯++⨯(3)工时约束:111221222332334143515248500037911000623000556000634000x x x x x x x x x x x +≤++≤+≤+≤+≤(4)工序流程约束:甲工序加工的产品数=乙工序加工的产品数(A 、B 、C )1121415112223252233343x x x x x x x x x x x +=++=+=+则线性规划模型为:11122122233233414351521112212223323341435152112141511222325220.8 1.2 1.05 1.65 2.750.480.160.60.60.420.2148500037911000623000556000634000..Max Z x x x x x x x x x x x x x x x x x x x x x x s t x x x x x x x x x =++++------+≤++≤+≤+≤+≤+=++=+333431121415112223252233343,,,,,,,,,,0x x x x x x x x x x x x x ⎧⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪=+⎪⎪≥⎩九、研究讨论题第1章 常见错误总结:(1)表格单纯形法简便易行,但却不习惯用。

相关主题