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

一、选择填空

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、判断正误

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三、将下列问题化为标准型

1.1234

123412313

24237..2358

,0,0,Max Z x x x x x x x x s t x x x x x x x =++++++≤⎧⎪-+=-⎨⎪≥≤⎩符号不限

[解] 令'22x x =-，'

44

5x x x =-，在约束1中引入非负的松弛变量6x ，约束2两边同乘以-1。整理得：

''

12345''

123456'

123''123456

23()()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 =-++-⎧-++-+=⎪-+--=⎨⎪≥⎩

即：

12345

123456123123456237..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 3

x 1 +x 2

- x 3 ≤ 6

1 - x

2 +3x

3 ≥ 5

x 1 + x 2 = 10

x 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 4

x 1

- x 2

- x 3+x 4+x 5 = 6

1 + x

2 +3x

3 - 3x

4 -x 6 = 5

x 1 - x 2 = 10 x 1, x 2, x 3, x 4, x 5, x 6≥ 0

四、用图解法求解下列线性规

1.

1+2x 2

x 1

- x 2 ≥ -2

x 1 +2x 2 ≤ 6

x 1, x 2 ≥ 0

[解]

根据上图，最优解为X *=（x 1, x 2）T =（6, 0）T ，最优值为-6。

1+2x 2

x 1

- x 2 ≥ -2

x 1 +2x 2 ≤ 6

x 1, x 2 ≥ 0 [

根据上图，最优解为*1228(,)(,)33

T T x x ==X ，最优值为14

3。

五、用单纯形法求解下列线性规划 1. Max Z=3x 1+5x 2

x 1 ≤

4

2 ≤ 12

3x 1 +2x 2 ≤18

x 1, x 2≥ 0

[解] 首先，标准化后线性规划如下： （1）Max Z=3x 1+5x 2+0x 3+0x 4+0x 5

x 1

+ x 3 = 4

2 + x 4 = 12

3x 1 +2x 2 + x 5 = 18

x 1, x 2, x 3, x 4, x 5, x 6≥ 0

max

2. Max Z=2x 1- x 2+x 3

3x 1

+x 2+x 3 ≤ 60

x 1-x 2+2x 3 ≤ 10

x 1 +x 2-x 3 ≤ 20

x 1, x 2, x 3 ≥ 0

[ （1）Max Z=2x 1-x 2+x 3

3x 1+x 2+x 3+x 4 = 60 x 1-x 2+2x 3+x 5 = 10

x 1 +x 2-x 3 +x 6 = 20

x 1, x 2, x 3, x 4, x 5, x 6≥ 0 max

六、表格单纯形法计算题

1. （2）初始线性规划模型如下：

Max Z=5x 1+20x 2+25x 3

2x 1+x 2

≤ 40

2x 2+x 3 ≤ 30

3x 1 -1/2x 3 ≤ 15

x 1, x 2, x 3 ≥ 0

（3）用单纯形法求出最优解及相应的最优值。

七、用大M 法和两阶段法求解下列线性规划

1+2x 2

-x 1 +2x 2 ≥ 2

x 1 ≤ 3

x 1, x 2 ≥ 0

[x 5后，线性规划模型如下：

M ax Z’=-x 1-2x 2-Mx 5

-x 1+2x 2 -x 3 +x 5 = 2

x 1 +x 4 = 3

x 1, x 2, x 3, x 4, x 5 ≥ 0

max 最优解X * =（0, 1, 0, 3）T ，最优值为Z min =2。 用两阶段法求解如下： 第一阶段：

标准化并引入人工变量x 5，对人工变量进行优化线性规划模型如下：

5

-x 1

+2x 2

-x 3

+x 5 = 2

x 1 +x 4 = 3

x 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 = 3

x 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 4

x 1+2x 2+3x 3 = 15 2x 1+x 2+5x 3 = 20

x 1 +2x 2+x 3+x 4 = 10

x 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 6

x 1+2x 2+3x 3+x 5 = 15 2x 1+x 2+5x 3+x 6 = 20

x 1 +2x 2+x 3+x 4 = 10 x 1, x 2, x 3, x 4 ≥ 0

max

1- x 2-x

3

x 1-2x 2+x 3 ≤ 11 -4x 1+x 2+2x 3 ≥ 3

-2x 1 +x 3 = 1

x 1, x 2, x 3 ≥ 0

[解] 首先，标准化并引入人工变量x 6, x 7后,线性规划如下：

1-x 2-x 3-Mx 6-Mx 7

x 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 = 1

x 1, x 2, x 3, x 4, x 5, x 6, x 7≥ 0 max

min

转入第二阶段求解如下：

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 ≥ 0

x31 ≤ 500-（100+x11-x12+x21-x22）

100+x11-x12+x21-x22+x31-x32 ≥ 0

x41 ≤ 500-（100+x11-x12+x21-x22+x31-x32）

100+x11-x12+x21-x22+x31-x32+x41-x42 ≥ 0

x51 ≤ 500-（100+x11-x12+x21-x22+x31-x32+x41-x42）

100+x11-x12+x21-x22+x31-x32+x41-x42+x51-x52 ≥ 0

x61 ≤ 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 ≥ 0

x11, x21, x31, x41, x51, x61, x12, x22, x32, x42, x52, x62 ≥ 0

3. 某厂生产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)工时约束：

1112212223323341435152485000

37911000

623000556000

634000

x x x x x x x x x x x +≤++≤+≤+≤+≤

（4）工序流程约束：甲工序加工的产品数＝乙工序加工的产品数（A 、B 、C ）

11214151

12223252233343

x x x x x x x x x x x +=++=+=+

则线性规划模型为：

1112212223

323341435152

111221

22233233414351521121

41511222325220.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 =++++------+≤++≤+≤+≤+≤+=++=+3

33431121415112223252233343,,,,,,,,,,0

x x x x x x x x x x x x x ⎧⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪=+⎪⎪≥⎩

九、研究讨论题

第1章 常见错误总结：

（1）表格单纯形法简便易行，但却不习惯用。虽然思路十分明确，但还是不方便。单纯形表格可以求最优解，也可以进行敏感性分析。最优表中有许多有用的信息。

（2）求解结果的表达：X ＊＝（…, …, …, …）T Z max =? Z min =? Max Z ＝？大写X 表示向量（通常是列向量）

(3) 单纯形表格不连续，自己写上第一次迭代，第二次迭代…；

（4）在添加人工变量时，系数矩阵中已经有现成的列向量，却不用。结果发现在单位阵中多出了单位列向量，有些人的单位矩阵有－1。松弛变量，剩余变量，人工变量的概念模糊。

（5）没给成绩的同学，要将没有做完的作业补上，做错了的要及时更正。

（6）最小比值原则已经失效，但还计算比值。甚至自己创造：（30＋40）／（0＋2）

（7）粗心大意，没有耐心，上面正确，抄下来就错了。要知道，这正是一种磨练！

（8）两阶段法变成了一阶段法，直接求出了最优解？第一阶段的最优解是辅助线性规划的最优解，若人工变量出基，表明原问题有解，已经找到了初始可行解。可以转入第二阶段，将目标函数换回来，在原来的最优表上继续求解。

（9）1~60x ≥,应该写成0(1,2,...,)j x j n ≥=

（10）迭代尚未结束，但因检验数算错，迭代终止。有的算错了，得出结论无解。 有人算错了，发现下一个解不再是基本可行解。

（11）宁可将“非基变量的系数”，也不说“检验数”；不写130σ=>

（12）“此时所有检验数均为负数”，“所有检验数均为0”说瞎话！不懂什么叫检验数。“此时结果为最终结果”

（13）尽管迭代不断进行，但右端常数却总用原来的b ，而不是新的b ’

(14) 有些人计算过程不对，但却得出了最优解和最优值，这是做不诚实，学习态度不端正。投机取巧，骗自己！

（15）一题接一题，中间没有空行。有些人的作业十分潦草，涂得乱七八糟；

（16）向量X 上面画箭头

（17）根据最小比值原则，将x4用x2换掉？

（18）原问题的最优解为1235,0,25x x x ===

（19）有人写的Z 和2一样，分不清楚。

（20）有人参考别人的作业，所以出错的地方一模一样。

（21）因为此时检验数均负，所以Z ＝36即为最优解，对不对？

（22）两阶段法：Max Z=…+M; Min Z=…-M “惩罚是核心”

（23）用非基变量表示目标函数的表达式为：235max 2032Z x x x =+--

（24）向量表示时用中括号［］，而不是（）；

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

一、选择填空 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、判断正误 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三、将下列问题化为标准型 1.1234 123412313 24237..2358 ,0,0,Max Z x x x x x x x x s t x x x x x x x =++++++≤⎧⎪-+=-⎨⎪≥≤⎩符号不限 [解] 令'22x x =-，' 44 5x x x =-，在约束1中引入非负的松弛变量6x ，约束2两边同乘以-1。整理得： '' 12345'' 123456' 123''123456 23()()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 =-++-⎧-++-+=⎪-+--=⎨⎪≥⎩ 即： 12345 123456123123456237..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 3 x 1 +x 2 - x 3 ≤ 6 1 - x 2 +3x 3 ≥ 5 x 1 + x 2 = 10 x 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 4 x 1 - x 2 - x 3+x 4+x 5 = 6 1 + x 2 +3x 3 - 3x 4 -x 6 = 5 x 1 - x 2 = 10 x 1, x 2, x 3, x 4, x 5, x 6≥ 0 四、用图解法求解下列线性规

运筹学部分课后习题解答

运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为 最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=

单纯形法： 原问题化成标准型为 12 1231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14

运筹学第3版熊伟编著习题答案

运筹学（第3版）习题答案 第1章线性规划 P36 第2章线性规划的对偶理论 P74 第3章整数规划 P88 第4章目标规划 P105 第5章运输与指派问题P142 第6章网络模型 P173 第7章网络计划 P195 第8章动态规划 P218 第9章排队论 P248 第10章存储论P277 第11章决策论P304 第12章 多属性决策品P343 第13章博弈论P371 全书420页 第1章 线性规划 1.1工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示． 表1－23 产品 资源 A B C 资源限量 材料(kg) 1.5 1.2 4 2500 设备(台时) 3 1.6 1.2 1400 利润(元/件) 10 14 12 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为 1231231 23123123max 1014121.5 1.2425003 1.6 1.21400 150250260310120130,,0 Z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨ ≤≤⎪⎪≤≤⎪≥⎪⎩ 1.2建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格 及数量如表1－24所示： 表1－24 窗架所需材料规格及数量 型号A 型号B 每套窗架需要 材料 长度（m ） 数量(根) 长度(m) 数量(根) A 1：2 2 B 1：2.5 2 A 2：1.5 3 B 2：2 3 需要量（套） 300 400

《管理运筹学》课后习题参考标准答案

《管理运筹学》(第二版)课后习题参考答案 第1章 线性规划(复习思考题) 1.什么就是线性规划？线性规划的三要素就是什么？ 答:线性规划(Linear Programming,LP)就是运筹学中最成熟的一个分支,并且就是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,就是一种重要的优化工具,能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量就是决策问题待定的量值,取值一般为非负;约束条件就是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数就是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误？ 答:(1)唯一最优解:只有一个最优点; (2)多重最优解:无穷多个最优解; (3)无界解:可行域无界,目标值无限增大; (4)没有可行解:线性规划问题的可行域就是空集。 当无界解与没有可行解时,可能就是建模时有错。 3.什么就是线性规划的标准型？松弛变量与剩余变量的管理含义就是什么？ 答:线性规划的标准型就是:目标函数极大化,约束条件为等式,右端常数项0≥i b ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不就是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答:可行解:满足约束条件0≥=X b AX ，的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示: 5.用表格单纯形法求解如下线性规划。

《运筹学》(第二版)课后习题参考答案

《管理运筹学》（第二版）课后习题参考答案 第1章线性规划（复习思考题） 1．什么是线性规划？线性规划的三要素是什么？ 答：线性规划（Linear Programming，LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？ 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。

答：可行解：满足约束条件的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5．用表格单纯形法求解如下线性规划。 s.t. 解：标准化 s.t. 列出单纯形表 4 1 2 0 0 b 0 2 [8] 3 1 1 0 2/8 0 8 6 1 1 0 1 8/6 4 1 2 0 0 4 1/4 1 3/8 [1/8] 1/8 0 (1/4)/(1/8) 0 13/2 6 －5/4 1/4 －3/4 1 (13/2)/(1/4) 0 －1/2 3/2 -1/2 0

运筹学(第五版) 习题答案

运筹学习题答案 第一章（39页） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max 12z x x =+ 51x +102x ≤50 1x +2x ≥1 2x ≤4 1x ，2x ≥0 （2）min z=1x +1.52x 1x +32x ≥3 1x +2x ≥2 1x ，2x ≥0 （3）max z=21x +22x 1x -2x ≥-1 -0.51x +2x ≤2 1x ，2x ≥0 （4）max z=1x +2x 1x -2x ≥0 31x -2x ≤-3 1x ，2x ≥0 解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。

（1）min z=-31x +42x -23x +54x 41x -2x +23x -4x =-2 1x +2x +33x -4x ≤14 -21x +32x -3x +24x ≥2 1x ，2x ，3x ≥0，4x 无约束 （2）max k k z s p = 11 n m k ik ik i k z a x ===∑∑ 1 1(1,...,)m ik k x i n =-=-=∑ ik x ≥0 (i=1…n; k=1,…,m) （1）解：设z=-z ',4x =5x -6x , 5x ,6x ≥0 标准型： Max z '=31x -42x +23x -5(5x -6x )+07x +08x -M 9x -M 10x s. t . -41x +2x -23x +5x -6x +10x =2 1x +2x +33x -5x +6x +7x =14 -21x +32x -3x +25x -26x -8x +9x =2 1x ,2x ,3x ,5x ,6x ,7x ,8x ,9x ,10x ≥0

运筹学第1章习题

运筹学第1章习题 运筹学 第1章线性规划与单纯形法习题详解(习题) 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max z x1 x2 5x1+10x2≤50 x1+x2≥1 x2≤4 x1，x2≥0 （2）min z=x1+1.5x2 x1+3x2≥3 x1+x2≥2 x1，x2≥0 （3）max z=2x1+2x2 x1-x2≥-1 -0.5x1+x2≤2 x1，x2≥0 （4）max z=x1+x2 x1-x2≥0

3x1-x2≤-3 x1，x2≥0 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。 （1）min z=-3x1+4x2-2x3+5x4 运筹学 4x1-x2+2x3-x4=-2 x1+x2+3x3-x4 14 -2x1+3x2-x3+2x4 2 x1，x2，x3 0，x4无约束 （2）max s nmzkpk zk aikxik i 1k 1 x k 1mik 1(i 1,...,n) xik 0 (i=1。n; k=1,。,m) 1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。 （1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3 x1,x2,x3,x4 0

（2）max z=5x1-2x2+3x3-6x4 x1+2x2+3x3+4x4=7 2x1+x2+x3+2x4=3 x1x2x3x4 0 1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。 （1）max z=2x1+x2 3x1+5x2 15 运筹学 6x1+2x2 24 x1，x2 0 （2）max z=2x1+5x2 x1 4 2x2 12 3x1+2x2 18 x1，x2 0 1.5以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。 1.6分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属于哪类解。 （1）max z=2x1+3x2-5x3

运筹学习题解答(chap1 线性规划及单纯形法)

第一章 线性规划及单纯形法 一、写出下列线性规划的标准形式，用单纯形法求解，并指出其解属于哪种情 况。 1、P55,1.3(a) 21510m ax x x Z += ⎪⎩⎪ ⎨⎧≥≤+≤+0x ,x 8x 2x 59x 4x 3. t .s 2 12121 解：将模型化为标准型 21510x x Z Max += ⎪⎩⎪ ⎨⎧≥=++=++0,,,825943. .4 32142 13 21x x x x x x x x x x t s 单纯形表如下

因所有检验数0j ≤σ，已达最优解，最优解是)2,1(*=X ，最优目标值为2 。由 检验数的情况可知，该问题有唯一最优解。 2、 P55,1.3(b) 21x x 2Z m ax += s.t ⎪⎪⎩⎪⎪⎨ ⎧ ≥≤+≤+≤0 ,5 24261552121212x x x x x x x 解：将模型化为标准型 21x x 2Z Max += t s . ⎪⎪⎩⎪⎪⎨ ⎧ ≥=++=++=+0 x ,...,x ,x ,5x x x ,24x x 2x 6,15x x 552152142 132 单纯形表如下

因所有检验数0j ≤σ，已达最优解，最优解是)0,0,2 ,2,2(X *=，最有目标值为 2 17 。由检验数的情况可知，该问题有唯一最优解。 3、 3212x x x Z Min -+=， t s . ⎪⎪⎩⎪⎪⎨ ⎧≥≤++≤+-≤-+0 ,,,5,822,4223213213 21321x x x x x x x x x x x x 解：将模型化为标准型： 3212x x x Z Min -+= t s . ⎪⎪⎩⎪⎪⎨ ⎧≥=+++=++-=+ -+0 ,,,5,822,42232163 2153 214 321x x x x x x x x x x x x x x x 用单纯形法迭代

运筹学习题答案(1)

第一章 线性规划及单纯形法 （作业） 1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行 解对应图解法中可行域的哪一顶点。 （1）Max z=2x 1+x 2 St.⎪⎩⎪ ⎨⎧≥≤+≤+0,242615532 12121x x x x x x 解：①图解法： 由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解 为直线⎩⎨⎧=+=+24 2615532121x x x x 的交点，解之得X=(15/4,3/4)T 。 Max z =33/4. ② 单纯形法： 将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4 St. ⎪⎩⎪ ⎨⎧≥≤++≤++0,,,242615535 421421321x x x x x x x x x x 其约束条件系数矩阵增广矩阵为：

P 1 P 2 P 3 P 4 ⎥⎦ ⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到 T 优解，代入目标函数得Max z=33/4. 1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。 （3）Min z=4x 1+x 2 ⎪⎪⎩⎪⎪⎨ ⎧=≥=++=-+=+) 4,3,2,1(0426343 34213 2121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2 ⎪⎪⎩ ⎪⎪⎨ ⎧=≥=++=-+=+)4,3,2,1(0426343 34213 2121j xj x x x x x x x x 添加人工变量y1,y2 Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2

《管理运筹学》(第二版)课后习题参考答案解析

《管理运筹学》〔第二版课后习题参考答案 第1章 线性规划〔复习思考题 1．什么是线性规划？线性规划的三要素是什么？ 答：线性规划〔Linear Programming,LP 是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化工具,能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性；目标函数是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2．求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误？ 答：〔1唯一最优解：只有一个最优点； 〔2多重最优解：无穷多个最优解； 〔3无界解：可行域无界,目标值无限增大； 〔4没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时,可能是建模时有错。 3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化,约束条件为等式,右端常数项0≥i b ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量；剩余变量取值为非零的话,则说明"≥"型约束的左边取值大于右边规划值,出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解,称为可行解。 基可行解：满足非负性约束的基解,称为基可行解。 可行基：对应于基可行解的基,称为可行基。 最优解：使目标函数最优的可行解,称为最优解。 最优基：最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示： 5．用表格单纯形法求解如下线性规划。

1 3 第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形

1 3 第一章线性规划与单纯形法运筹学习题集第一章线性 规划与单纯形 1 3 第一章 线性规划与单纯形法 运筹学习题集 第一章线性规划与单纯形法 复习思考题 1. 试述线性规划数学模型的结构及各要素的特征。 2. 求解线性规划问题时可能出现哪几种结果?哪些结果反映建模时有错误? 3. 什么是线性规划问题的标准形式?如何将一个非标准型的线性规划问题转化为标准形式? 4. 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。 5. 试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解? 6. 如果线性规划的标准型变换为求目标函数的极小化min z，则用单纯形法计算时如何判别问题已得到最优解? 7. 在确定初始可行基时，什么情况下要在约束条件中增添人工变量?在目标函数中人工变量前的系数为(-M)的经济意义是什么? 8. 什么是单纯形法计算的两阶段法?为什么要将计算分成两个阶段进行,如何根据第一阶段的计算结果来判定第二阶段的计算是否需要继续进行? 9. 简述退化的含义及处理退化的勃兰特规则。

10. 举例说明生产和生活中应用线性规划的可能案例，并对如何应用进行必要 描述。 11. 判断下列说法是否正确: (a) 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的; (b) 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大; (c) 线性规划问题的每一个基解对应可行域的一个顶点; (d) 如线性规划问题存在可行域，则可行域一定包含坐标的原点; (e) 对取值无约束的变量xj，通常令xj=x′j-x″j，其中x′j?0，x″j?0， 在用单纯形法求得的最优解中有可能同时出现x′j,0，x″j,0; (f) 用单纯形法求解标准型的线性规划问题时，与σj,0对应的变量都可以被 选作换入变量; (g) 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负; (h) 单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量， 将使目标函数值得到最快的增长; (i) 一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可 以从单纯形表中删除，而不影响计算结果; (j) 线性规划问题的任一可行解都可以用全部基可行解的线性组合表示; (k) 若X1，X2分别是某一线性规划问题的最优解，则X=λ1X1+λ2X2也是该线性规划问题的最优解，其中λ1、λ2可以为任意正的实数; (l) 线性规划用两阶段法求解时，第一阶段的目标函数通常写为min z=?ixai(xai为人工变量)，但也可写为min z=?ikixai,只要所有ki均为大于零的常数;

运筹学课后习题答案

第一章线性规划及单纯形法 1．用*j 〔j=1.2…5〕分别代表5中饲料的采购数，线性规划模型： 2.解：设123456x x x x x x *表示在第i 个时期初开场工作的护士人数，z 表示所需的总人数，则 3．解：设用i=1，2，3分别表示商品A ，B ，C ，j=1，2，3分别代表前，中，后舱，*ij 表示装于j 舱的i 种商品的数量，Z 表示总运费收入则： 5.〔1〕 Z = 4 〔2〕 解：如图：由图可得： 即该问题具有唯一最优解*(10,6)T x = 〔3〕 无可行解 (4) 如图： 由图知，该问题具有无界解。 6〔1〕 〔2〕 7．1〕系数矩阵A ：364)120C ⎛⎫ ⎪ - ⎪ ⎪-⎝⎭ =12345612363008102 0＝（p p p p p p 30000种组合 〔B ，b 〕=040⎛⎫⎛⎫ ⎪ ⎪- ⎪ ⎪ ⎪ ⎪⎝ ⎭⎝⎭12 3691008110＝0 116/33 00 1 -7/6

∴y1=〔0，16/3，-7/6，0，0，0〕T 同理y2=〔0，10，0，-7，0，0〕T y3=〔0，3，0，0，7/2，0〕T y4=〔7/4，-4，0，0，0，21/4〕T y5=〔0，0，-5/2，8，0，0〕T y6=〔0，0，3/2，0，8，0〕T y7=〔1，0，-1/2，0，0，3〕T y8=〔0，0，0，3，5，0〕T y9=〔5/4，0，0，-2，0，15/4〕T y10=〔0，3，-7/6，0，0，0〕T y11=〔0，0，-5/2，8，0，0〕T y12=〔0，0，-5/2，3，5，0〕T y13=〔4/3，0，0，0，2，3/4〕T y14=〔0，10，0，-7，0，0〕T y15=〔0，3，0，0，7/3，0〕T y16=〔0，0，3/2，0，8，0〕T 基可行解：〔每个*值都大于0〕，〔y3，y6，y8，y12，y13，y15，y16〕 最优解：〔y3，y6，y15，y16〕Z ma*=3 [p2 p3 p4]，[p2 p3 p5]，[p3 p4 p5]，[p2 p4 p5]为奇异，∴只有16个基。解：〔2〕该线性问题最多有246 C=个根本解。 8.基的定义 106 21350 314 B==-≠ ∴*1 *2 *3所对应的列向量可以构成基 B 由*1 *2 *3列向量构成= 106 213 314⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦ N 由非基变量对应的向量构成= 35 41 20⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦

《运筹学》课堂作业及相应答案解析

第一部分绪论 第二部分线性规划与单纯形法 1 判断下列说法是否正确： (a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的； (b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大； (c)线性规划问题的每一个基解对应可行域的一个顶点； (d)如线性规划问题存在可行域,则可行域一定包含坐标的原点； (e)对取值无约束的变量x i,通常令其中 ,在用单纯形法求得的最优解中有可能同时出现 (f)用单纯形法求解标准型的线性规划问题时,与对应的变量都可以被选作换入变量； (g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负； (h)单纯形法计算中,选取最大正检验数δk对应的变量x k作为换入变量,将使目标函数值得到最快的增长； (i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果； (j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示； (k)若x1,x2分别是某一线性规划问题的最优解,则 也是该线性规 划问题的最优解,其中λ1,λ2可以为任意正的实数； (1)线性规划用两阶段法求解时,第一阶段的目标函数通常写为 X ai为人工变量),但也可写为,只要所有 k i均为大于零的常数； (m)对一个有n个变量、m个约束的标准型的线性规划问题,其可行域的顶点恰好 为个； (n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解； (o)线性规划问题的可行解如为最优解,则该可行解一定是基可行解； (p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解； (q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；

运筹学第一章详解答案

运筹学详解答案： 1.1分别用图解法和单纯形法求解下列线性规划问题，（1）指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解；（2）当具有有限最优解时，指出单纯形表中的各基可行解对应可行域的那一顶点。 A. 图解法 图中蓝线代表目标函数线，箭头代表其运动的方向，根据可行域的形状可知此题无最优解。 B. 单纯形法 1.行变换法 写出此线性规划问题的标准形式 max z =5x 1+6x 2 s.t.{2x 1−x 2−x 3=2 −2x 1+3x 2+x 4=2x i ≥0,(i =1,2,3,4) 系数矩阵经过行变换后可的到等价的约束条件如下 max z =5x 1+6x 2 ⎪⎩⎪⎨⎧≥≤+-≥-+=0,23222.65max )4(21212121x x x x x x st x x Z

s.t.{x 1−12⁄x 2−12⁄x 3+0x 4=1 0x 1+2x 2−x 3+x 4=4x i ≥0,(i =1,2,3,4) 显然x 1,x 4是基变量利用单纯形表可以求出此题具有无界解。 当然还可以采用其他变量为基变量，例如将约束条件转化为 s.t.{x 1+0x 2−34⁄x 3+14⁄x 4=2 0x 1+x 2−12⁄x 3+12⁄x 4=2x i ≥0,(i =1,2,3,4) 此时x 1,x 2成为了基变量。然后在利用单纯形法可以解出此题具有无界解。 C. 大M 法 易知转换成标准形式后，约束问题的系数矩阵中不包含单位矩阵，这时我们可以添加一个人工变量x 5，并在系数矩阵中添加一列单位向量，同时令目标函数中人工变量的系数为任意大的负值，用“-M ”表示。具体形式如下 max z =5x 1+6x 2−Mx 5 s.t.{2x 1−x 2−x 3+x 5=2 −2x 1+3x 2+x 4=2x i ≥0,(i =1,2,3,4,5) 1.在进行第二次迭代时，因为人工变量已经移除基了，我们可以在后续的计算中不考虑它。 2.在进行第三次迭代时，进基的变量是x 3，而其对应的列向量都是小于0的，故此我们可以判断此问题有无界解。 D. 两阶段法 利用两阶段法，第一阶段先求解一个目标函数中只包含人工变量的线性规划问题，此时问题可以写为： min w =x 5

运筹学基础与应用课后习题答案(第一二章习题解答)

运筹学基础及应用 习题解答 习题一 P46 1.1 (a) 该问题有无穷多最优解，即满足2 1 0664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。 (b) 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 1.3 (a) 4

(1) 图解法 最优解即为⎩⎨⎧=+=+82594321 21x x x x 的解⎪⎭⎫ ⎝⎛=23,1x ，最大值235=z (2)单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 ⎩⎨⎧=++=+++++=8 25943 ..00510 max 421321 4321x x x x x x t s x x x x z 则43,P P 组成一个基。令021==x x 得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。5 839,58min =⎪⎭ ⎫ ⎝⎛=θ

02>σ，23 28,1421min =⎪⎭⎫ ⎝ ⎛=θ 新的单纯形表为 0,21<σσ，表明已找到问题最优解0 , 0 , 23 1,4321====x x x x 。最大值 2 35*=z (b) (1) 图解法

\\ 最优解即为⎩⎨ ⎧=+=+5 24262121x x x x 的解⎪⎭⎫ ⎝⎛=23,27x ，最大值217=z (2) 单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 1234523124125 max 2000515 .. 6224 5z x x x x x x x s t x x x x x x =+++++=⎧⎪ ++=⎨⎪++=⎩ 则3P ，4P ，5P 组成一个基。令021==x x 得基可行解()0,0,15,24,5x =，由此列出初始单纯形表 21=+x x 2621+x x

(北邮出版社)运筹学课本答案

No .1 线性规划 1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而 工厂有供纺纱的总工时7200h ，织带的总工时1200h 。 (1) 列出线性规划模型，以便确定产品的数量使总利润最大； (2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型 的解是否有影响？ 解：(1)设A 的产量为x 1，B 的产量为x 2，C 的产量为x 3，D 的产量为x 4，则 有线性规划模型如下： max f (x )=(168-42)x 1 +(140-28)x 2 +(1050-350)x 3 +(406-140)x 4 =126 x 1 +112 x 2 +700 x 3 +266 x 4 s.t. ⎪⎩ ⎪ ⎨⎧=≥≤+≤+++4,3,2,1 ,012005.02 720041023434321i x x x x x x x i (2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关， 故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。 2、将下列线性规划化为极大化的标准形式 解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x 4，在第二行添加人工变量x 5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x 6, x 7，并令x x x 333 ='-''，则有 max[-f (x )]= {-2 x 1 -3 x 2 -5('-''x x 33)+0 x 4 -M x 5+0 x 6 +0 x 7} s.t. 0,,,,,,,13 55719 13 55719 16 9976 5 765433217 3321633 215332143321≥'''=+''+'-+-=+''-'+-=+''+'-+-=+''-'+--⎪⎪ ⎪⎩ ⎪ ⎪⎪⎨⎧ 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 ⎪⎪⎩⎪⎪⎨ ⎧±≥≤+-=-+--≥-+++=不限 3213213213213 21 ,0,13|5719|169765 ..532)(min x x x x x x x x x x x x t s x x x x f