川大《管理运筹学》第二次作业答案

运筹学试题二
一、用单纯形法求解下述线性规划问题（20分）
⎧⎨⎪⎪⎩
⎪⎪0
,824424m ax 2121212121≥≤-≤-≤+-+=x x x x x x x x x x z
二、设一线性规划问题为（25分）
234
700件，且在第二、三周能加班生产。

加班后，每周可增产200件产品，但成本每件增加5元。

产品如不能在本周交货，则每件每周存贮费是3元。

问如何安排生产计划，使总成本最小，要求建立运输问题数学模型求解。

（25分）
四、某高校拟开设文学、艺术、音乐、美术四个学术讲座。

每个讲座每周下午举行一次。

经调查知，每周星期一至星期五不能出席某一讲座的学生数如下表：（20分）
座的学生总数。

试题二答案
()0
1310232>=⎪⎪⎭⎫
⎝⎛-=r
6
*=Z
（3） 最优解不满足新增加的约束条件2231≥+-x x ∴最优解要发生改变 将约束条件改写为 22631-=+-x x x
加入最优表中继续迭代。

《管理运筹学》（第二版）课后习题参考答案第1章 线性规划（复习思考题）1．什么是线性规划？线性规划的三要素是什么？答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。

线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。

建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。

决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。

2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？ 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解；（3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。

当无界解和没有可行解时，可能是建模时有错。

3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。

4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。

答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。

基可行解：满足非负性约束的基解，称为基可行解。

可行基：对应于基可行解的基，称为可行基。

最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。

它们的相互关系如右图所示：5．用表格单纯形法求解如下线性规划。

s .t . ⎪⎩⎪⎨⎧≥≤++≤++0,,86238321321321x x x x x x x x x解：标准化 32124max x x x Z ++=s .t . ⎪⎩⎪⎨⎧≥=+++=+++0,,,,862385432153214321x x x x x x x x x x x x x 列出单纯形表故最优解为T X )6,0,2,0,0(*=，即2,0,0321===x x x ，此时最优值为4*)(=X Z ． 6．表1—15中给出了求极大化问题的单纯形表，问表中d c c a a ,,,,2121为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以1x 代替基变量5x ；（4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。

《管理运筹学》课后习题答案第2章线性规划的图解法1.解决方案：X25`a1bo1c6x1可行的区域是oabc等值线为图中虚线部分从图中可以看出，最优解是B点，最优解是x1=121569，x2?。

最优目标函数值：7772．解：x21零点六0.100.10.61x1有唯一解、无可行解、无界解、无可行解和无限解x1?0.2x2?0.6，函数值为3.6。

三百六十九20923有唯一解，函数值为。

83x2？3x1？3.解决方案：(1).标准形式：麦克斯夫？3x1？2x2？0s1？0s2？0s39x1?2x2?s1?303x1？2x2？s2？132x1？2x2？s3？9x1，x2，s1，s2，s3？0(2).标准形式：明夫？4x1？6x2？0s1？0s23x1?x2?s1?6x1?2x2?s2?107x1?6x2?4x1,x2,s1,s2?0(3).标准形式：明夫？x1？2x2？2x2？0s1？0s2“”？3x1？5x2？5x2？s1？七十 '''2x1'?5x2?5x2?503x?2x?2x?s2?30'''x1',x2,x2,s1,s2?0'1'2''2标准形式：麦克斯？10x1？5x2？0s1？0s23x1?4x2?s1?95x1?2x2?s2?8x1，x2，s1，s2？0松弛变量（0，0）的最优解为X1=1，X2=3/23705.解决方案：标准形式：明夫？11x1？8x2？0s1？0s2？0s310x1?2x2?s1?203x1？3x2？s2？184x1？9x2？s3？36x1，x2，s1，s2，s3？0剩余变量（0.0.13）最优解为x1=1，x2=5.6.解决方案：(10)最优解为x1=3，x2=7.(11)1?c1?3(12)2?c2?6(13)x1？6x2？四(14)最优解为x1=8，x2=0.(15)不变化。

管理运筹学练习二一、判断题，错误的请说明原因。

（1）若线性规划问题的可行域无界，则该问题无最优解。

（2）单纯形法解线性规划问题时，非基变量一定为零。

（3）若线性规划问题有两个最优解，则一定有无穷多最优解。

（4）如果原问题没有可行解，那么对偶问题具有无界解。

（5）n 个变量，m 个约束的标准线性规划，其基可行解数目不超过mn C 。

（6）悬挂点的次一定为1，孤立点的次一定为0。

（7）图中所有奇点的数目一定为偶数。

（8）赋权有向图中的最短路是唯一的。

（9）下图中2v 的次为3，5v 的次为4。

（10）下图中（b ）为（a ）的支撑子图DB AC E BACE D（a ） (b)二、某公司饲养的动物需A 、B 、C 三种营养元素，每天对A 的需求量至少为700克，对B 的需求量至少为30克，而C 的需求量刚好为200毫克。

现有5种饲料供选用，其各种营养元素含量及单价如表所示。

为避免过多使用某种饲料，规定各饲料的最高含量分别为三、对于线性规划问题：⎪⎩⎪⎨⎧≥≥+++-≥++++++++=0,,3322432..32532min 51543215432154321x x x x x x x x x x x x t s x x x x x Z（1） 建立下述问题的对偶问题；（2） 采用图解法进行求解对偶问题； （3） 采用互补松弛定理求解原问题的解。

四、伦敦（L ）、墨西哥城（MC ）、纽约（NY ）、巴黎（Pa ）、秘鲁（Pe ）和东京（T ）之间的航线如下图所示。

其中2),(=Pa L w ，13),(=Pe T w ，21),(=NY MC w ，35),(=NY L w ，36),(=NY Pa w ，51),(=Pa Pe w ，51),(=Pe L w ，56),(=MC L w ，57),(=MC Pe w ，60),(=L T w ，61),(=Pa T w ，68),(=NY T w ，68),(=NY Pe w ，70),(=MC T w ，78),(=MC Pa w要游遍这六个城市，试问应如何设计航线使总航程最小？T LPe NYMCPa五、某电视机厂生产彩色电视机，有两条生产线，甲生产线每小时生产2台，乙生产线每小时生产1.5台。

《管理运筹学》（第二版）课后习题参考答案第1章 线性规划（复习思考题）1．什么是线性规划？线性规划的三要素是什么？答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。

线性规划属于规划论中的静态规划，是一种重要的优化工具，当无界解和没有可行解时，可能是建模时有错。

3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0 i b ，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。

4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。

答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。

基可行解：满足非负性约束的基解，称为基可行解。

可行基：对应于基可行解的基，称为可行基。

最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。

它们的相互关系如右图所示：5．用表格单纯形法求解如下线性规划。

s .t . ⎪⎩⎪⎨⎧≥≤++≤++0,,86238321321321x x x x x x x x x解：标准化 32124max x x x Z ++=s .t . ⎪⎩⎪⎨⎧≥=+++=+++0,,,,862385432153214321x x x x x x x x x x x x x 列出单纯形表于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以1x 代替基变量5x ；（4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。

表1—15 某极大化问题的单纯形表7．用大M 法求解如下线性规划。

s .t . ⎪⎪⎩⎪⎪⎨⎧≥=++≤++≤++0,,101632182321321321321x x x x x x x x x x x x解：加入人工变量，进行人造基后的数学模型如下：s .t . ⎪⎪⎩⎪⎪⎨⎧=≥=+++=+++=+++)6,,2,1(0101632182632153214321 i x x x x x x x x x x x x x i列出单纯形表x为“第i电站向第j城市分配的电量”（i=1,2; j=1,2,3），建立模型如下：解：设ijs .t . ⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧==≥≤+≥+=+≤+≥+=++=++3,2,1;2,1,035027025032029045040023132313221221112111232221131211j i x x x x x x x x x x x x x x x x x ij10s .t . ⎪⎪⎪⎪⎩⎨=≥≤≤≤4,3,2,1,0,,101520)3()2()1()1(4)1(3)1(2i x x x x x x i i i 通过LINGO 软件计算得：44,12,0,20,10)2(1)2(1)1(3)1(2)1(1=====x x x x x ． 10．某家具制造厂生产五种不同规格的家具。

12-2《管理运筹学》课后习题详解 第2章 线性规划的图解法1. （ 1）可行域为0, 3, A ，3围成的区域。

（2） 等值线为图中虚线所示。

（3） 如图，最优解为 A 点（12/7,15/7 ），对应最 优目标函数值 Z=69/7。

2.（ 1）有唯一最优解 A 点，对应最优目标函数 值 Z=3.6。

（2）无可行解。

（3）有无界解。

40.7 0-33X 1+ X2(4)无可行解。

9y -F 2.r, + 6 = 30 3x x+2X2 + s2 =13 2x{—2xi+6=9 gx”片宀宀二0max f = 一4形—— 0町—Os2(5)无可行解。

X22max最优解A点最优函数值3. (1)标准形式(2)标准形式Xj + 2X2 H-S2 = 107,v：—6.v* = 4M , .Y2 , % 出> O(3)标准形式|!_|_fifmax f = —x 1 + 2 屯—2 込—0® — 0^2—3x x * 5X 2 — 5X 2 + s x = 70 2x x — 5X 2 + 5X 2 = 50 3xj + 2X 2 — 2X 2 —=305x ；,歩1 .s 2 土 0max z = 10.^! + 5.Y 2 \ 0^t 1 0©3x 】十 4X 2 + S J = 95.巧 +2.Y 2 -b >s 2 = 8 x t ,x 2 ^s lr>s 2 > 04.解： (1)标准形式求解：3X 〔 4X 2 9 5X 〔 2X 28X , 1 X 21.5S , S 25.标准形式:x , x 2 6 x , 3.6 S 3 S 2 0 4x , 9x 2 16x 2 2.4s , 11.27. 模型: (1) X 1=150, X 2=150;最优目标函数值 Z=103000。

(2) 第2、4车间有剩余。

剩余分别为： 330、15,均为松弛变量。

川大《管理运筹学》第二次作业答案欢迎你，你的得分：100.0完成日期：2013年08月19日09点43分说明：每道小题括号里的答案是您最高分那次所选的答案，而选项旁的标识是标准答案。

一、单项选择题。

本大题共20个小题，每小题 2.0分，共40.0分。

在每小题给出的选项中，只有一项是符合题目要求的。

规划的目的是（）(C)合理利用和调配人力、物力，以取得最大收益。

合理利用和调配人力、物力，使得消耗的资源最少。

合理利用和调配现有的人力、物力，消耗的资源最少，收益最大。

合理利用和调配人力、物力，消耗的资源最少，收益最大。

线性规划问题标准型中bi（ｉ＝１，２，……ｎ）必须是（）。

(B)正数非负数无约束非零线性规划问题的基本可行解Ｘ对应于可行域Ｄ的（）。

(D)外点所有点内点极点满足线性规划问题全部约束条件的解称为（）。

(C)最优解基本解可行解多重解当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（）。

(A)多重解无解正则解退化解原问题与对偶问题的最优（）相同。

(B)解目标值解结构解的分量个数原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量yi是（）。

(B)多余变量自由变量松弛变量非负变量运输问题中，m+n-1个变量构成基本可行解的充要条件是他不含（）。

(C)松弛变量多余变量闭回路圈树Ｔ的任意两个顶点间恰好有一条（）。

(B)边初等链欧拉圈回路若Ｇ中不存在流f增流链，则f为Ｇ的（）。

(B)最小流最大流最小费用流无法确定对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（）(D)等式约束“≤”型约束“≥”型约束非负约束当线性规划问题的一个基解满足下列哪项要求时称之为一个可行基解（）(C)大于0小于0.非负非正在运输方案中出现退化现象，是指数字格的数目()(C)等于m＋n.大于m＋n－1.小于m＋n－1等于m＋n－1在线性规划模型中，没有非负约束的变量称为（）(C)多余变量松弛变量自由变量人工变量约束条件为AX=b，X≥0的线性规划问题的可行解集是（）(B)补集凸集交集凹集线性规划问题若有最优解，则一定可以在可行域的（）上达到。

《管理运筹学2449》19春在线作业2
【题目】若G中不存在流f增流链，则f为G的()
[A.]最小流
[B.]最大流
[C.]最小费用流
[D.]无法确定
[请仔细阅读以上题目]
------本题正确选项:B
【题目】若链中顶点都不相同，则称Q为()
[A.]基本链
[B.]初等链
[C.]简单链
[D.]饱和链
[请仔细阅读以上题目]
------本题正确选项:B
【题目】若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变量的()
[A.]值
[B.]个数
[C.]机会费用
[D.]检验数
[请仔细阅读以上题目]
------本题正确选项:D
【题目】若树T有n个顶点，那么它的边数一定是()
[A.]n＋2
[B.]n
[C.]n+1
[D.]n-1
[请仔细阅读以上题目]
------本题正确选项:D
【题目】当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得
[A.]多重解
[B.]无解
[C.]正则解
[D.]退化解
[请仔细阅读以上题目]。

《管理运筹学》（第二版）课后习题参考答案第1章线性规划（复习思考题）1．什么是线性规划线性规划的三要素是什么答：线性规划（Linear Programming，LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。

线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。

建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。

决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。

2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误答：（1）唯一最优解：只有一个最优点；（2）多重最优解：无穷多个最优解；（3）无界解：可行域无界，目标值无限增大；（4）没有可行解：线性规划问题的可行域是空集。

当无界解和没有可行解时，可能是建模时有错。

3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。

4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。

答：可行解：满足约束条件的解，称为可行解。

基可行解：满足非负性约束的基解，称为基可行解。

可行基：对应于基可行解的基，称为可行基。

最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。

它们的相互关系如右图所示：5．用表格单纯形法求解如下线性规划。

.解：标准化.列出单纯形表412b02[8]2 /80868 /641241/41/81/8]/8(1/4/(1/813/265/4/43/4(13/2/(1/4 0－1/23/21/222806－221－12－502故最优解为，即，此时最优值为．6．表1—15中给出了求极大化问题的单纯形表，问表中为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以代替基变量；（4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。