运筹学大作业单纯性法与对偶单纯性法比较

2013-2014(1)学期《管理运筹学A》复习题二参考答案1．对偶单纯形法与单纯形法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（非负）约束。

2．若原问题有最优解，那么对偶问题（一定）有最优解，且原问题与对偶问题的最优（目标函数值）相等。

3．原问题可行，而对偶问题不可行，则原问题（无）界。

4．一般的图都具有（点）和（边）两个要素。

5. 网络中从一点到另一点的所有路中各边权数之和最小的路称为（最短路）。

6. 线性规划问题的基本解一定是基本可行解。

（×）7.用单纯形法求解标准型线性规划问题时，与检验数大于0相对应的变量都可被选作换入变量。

（√）8. 在运输问题中，只要给出一组含有（m + n -1）个非零的x ij且满足全部约束，就可以作为基本可行解。

（×）9.表上作业法实质上就是求解运输问题的单纯形法。

（√）10．如果网络G中不含有流f的增流链，则网络的流为最大流。

（√）11. 增流链一定是不饱和链，不饱和链不一定是增流链。

（√）12. 如果网络G中含有流f的增流链，则网络的流值可以增加。

（√）13.网络的最小费用流与最小费用最大流是什么关系？答：网络的最小费用流是指网络的流值等于某一目标流的流值时，在这所有的流中费用最小的流；也就是在满足某一目标运输量下，所有的运输方案中，运输费用最小的运输方案。

而网络的最小费用最大流是指在网络流值达到最大时，所有流中费用最小的流；也就是达到运输网络最大运输量的所有运输方案中，运输费用最小的运输方案。

可以看出，网络的最小费用最大流是网络的最小费用流的一种特殊情况，即目标流的流值等于最大流的的流值的情况。

14．当线性规划的可行解集合非空时一定（D）A．包含原点X=(0,0,…,0) B．有界C．无界D．是凸集15. 有5个产地6个销地的平衡运输问题模型具有特征（D）A．有11个变量B．有10个约束C．有30约束D．有10个基变量16. 根据所给的表和一组解判断是否最优解，若不是，请求出最优解。

天⼤18春《运筹学》在线作业⼀⼆满分天⼤18春《运筹学》在线作业⼀-0001试卷总分:100 得分:100⼀、单选题 (共 40 道试题,共 100 分)1.在求极⼤值的线性规划问题中，松弛变量在⽬标函数中的系数为A.0B.极⼤的正数C.绝对值极⼤的负数D.极⼤的负数正确答案 :A更多 Q Q 2959415429 微信 open45112.⽬标函数取极⼩化的线性规划可以转化为⽬标函数取极⼤化后两者的最优解（）A.maxZB.max（-Z）C.相关⼀个符号D.相同正确答案 :D3.在求极⼩值的线性规划问题中，松弛变量在⽬标函数中的系数为A.0B.极⼤的正数C.绝对值极⼤的负数D.极⼤的负数正确答案 :A4.关于树的概念，叙述不正确的是（）A.树中的线数等于点数减1B.树中再添⼀条连线后必定含圈C.树中删去⼀条连线后不连通D.树中两点之间的通路可能不唯⼀正确答案 :D5.⽬标函数取极⼩化的线性规划可以转化为⽬标函数取极⼤化即（）的线性规划问题求解A.maxZB.max（-Z）C.相关⼀个符号D.相同6.服务机构的研究内容包括（）A.服务台数量B.服务规律C.到达规律D.服务台数量和服务规律7.在完全不确定下的决策⽅法不包括下列的哪⼀项（）A.悲观法B.乐观法C.最⼤收益法D.等可能性法8.离散型动态规划常⽤求解⽅法是（）A.表格⽅式B.公式递推C.决策树D.多阶段决策9.ABC分类法是对库存的物品采⽤按（）分类的A.物品质量B.物品价格C.物品数量D.物品产地10.设置了安全库存量后，（）将会增加。

A.经济订货量B.年订货次数C.销售量D.库存保管费⽤11.在求极⼩值的线性规划问题中，⼈⼯变量在⽬标函数中的系数为A.0B.极⼤的正数C.绝对值极⼤的负数D.极⼤的负数12.（）表⽰各个阶段开始时所处的⾃然状况或客观条件。

A.状态B.决策C.状态转移D.指标函数13.可⾏流应满⾜的条件是（）A.容量条件B.平衡条件C.容量条件和平衡条件D.容量条件或平衡条件14.从起点到终点的任⼀线路上的流量能⼒取决于（）A.其中具有最⼤流量的⽀线B.其中具有最⼩流量的⽀线C.其中各⽀线流量能⼒之和D.其中各⽀线的数⽬15.从起点到终点的最短路线，以下叙述（）正确A.从起点出发的最短连线必包含在最短路线中B.整个图中的最短连线必包含在最短路线中C.整个图中的最长连线可能包含在最短路线中D.从起点到终点的最短路线和最短距离都是唯⼀的16.从带连数长度的连通图中⽣成的最⼩⽀撑树，叙述不正确的是（）A.任⼀连通图⽣成的各个最⼩⽀撑树总长度必相等B.任⼀连通图⽣成的各个最⼩⽀撑树连线数必相等C.任⼀连通图中具有最短长度的连线必包含在⽣成的最⼩⽀撑树中D.最⼩⽀撑树中可能包括连通图中的最长连线17.下列假设不是经济批量库存模型的是（）A.需求量均匀B.提前量为零C.允许缺货D.瞬时补充18.设某企业年需1800吨钢材，分三次订货，则平均库存量为（）A.1800吨B.900吨C.600吨D.300吨19.（）是⽤来衡量所实现过程优劣的⼀种数量指标。

2023年运筹学大作业单纯性法与对偶单纯性法的比较目前，运筹学领域中的单纯性法和对偶单纯性法是两种最为常用的线性规划求解方法。

随着科技和工业的不断发展，未来的运筹学研究也将越来越受到人们的关注。

因此，在未来的2023年中，我们不仅需要掌握这两种方法的基本概念和原理，还需要深入的了解它们的比较和应用。

第一章单纯性法的基本原理单纯性法是一种常用的线性规划求解方法，其基本流程可以归纳为以下几个步骤：1. 确定一个基本可行解；2. 判断该基本可行解是否是最优解；3. 如果不是最优解，则选择一个入基变量和一个出基变量；4. 对出基变量进行互换，更新基本可行解；5. 重复执行步骤2至步骤4，直至得到最优解。

单纯性法的优点在于可快速地求得最优解，特别是在少数变量和简单约束的情况下，可以快速解决线性规划问题。

但是，当规模较大或者约束条件复杂时，单纯性法很可能会陷入循环，导致计算时间过长。

第二章对偶单纯性法的基本原理对偶单纯性法是单纯性法的一种扩展，其实质是对线性规划模型的对偶模型进行求解。

其基本流程可以归纳为以下几个步骤：1. 确定一个对偶基本可行解；2. 判断该对偶基本可行解是否是最优解；3. 如果不是最优解，则选择一个入基变量和一个出基变量；4. 对出基变量进行互换，更新对偶基本可行解；5. 重复执行步骤2至步骤4，直至得到最优解。

对偶单纯性法的优点在于可以避免陷入循环的情况，同时，还可以通过求解对偶问题来产生原问题的最优解。

第三章两种方法的比较从计算复杂度的角度来比较单纯性法和对偶单纯性法，很明显对偶单纯性法更加高效。

因为对偶单纯性法的目标函数和限制条件比原问题要少，因此需要的计算步骤相对更少。

但是，在实际操作中，对偶单纯性法的计算结果通常需要进行一次转换才能得到原问题的最优解。

从求解结果的角度来比较单纯性法和对偶单纯性法，也可以发现它们的区别。

在某些情况下，单纯性法得出的最优解不一定是方案的唯一最优解，而对偶单纯性法则可以直接得到原问题的唯一最优解。

线性规划的解法线性规划是现代数学中的一种重要分支，它是研究如何在一定约束条件下优化某种目标函数的一种数学方法。

在现实生活中，许多问题都可以用线性规划求解。

如在生产中，如何安排产品的产量才能最大化利润；在运输中，如何安排不同的运输方式最大程度降低成本等等。

线性规划的解法有多种，下面我们就来对其进行详细的介绍。

1. 单纯形法单纯形法是线性规划中最重要的求解方法之一，它是由Dantzig于1947年提出的。

单纯形法的基本思路是从某一个初始解出发，通过挑选非基变量，使得目标函数值逐步减少，直到得到一个最优解。

单纯形法的求解过程需要确定初始解和逐步迭代优化的过程，所以其求解复杂度较高，但是在实际中仍有广泛应用。

2. 对偶线性规划法对偶线性规划法是一种将线性规划问题转化为另一个线性规划问题来求解的方法。

这种方法的主要优势是，它可以用于求解某些无法用单纯形法求解的问题，如某些非线性规划问题。

对偶线性规划法的基本思路是将原问题通过拉格朗日对偶性转化为对偶问题，然后求解对偶问题，最终得到原问题的最优解。

3. 内点法内点法是一种由Nesterov和Nemirovsky于1984年提出的方法，它是一种不需要寻找可行起点的高效的线性规划求解方法。

内点法的基本思路是通过不断向可行域的内部靠近的方式来求解线性规划问题。

内点法的求解过程需要实现某些特殊的算法技术，其求解效率高，可以解决一些规模较大、约束条件复杂的线性规划问题。

4. 分枝定界法分枝定界法是一种通过逐步将线性规划问题分解成子问题来求解的方法。

这种方法的基本思路是，在求解一个较大的线性规划问题时，将其分解成若干个较小的子问题，并在每个子问题中求解线性规划问题，在不断逐步求解的过程中不断缩小问题的规模，最终得到问题的最优解。

总之，不同的线性规划解法各有千秋，根据实际问题的需要来选择合适的求解方法是非常重要的。

希望本文能够对您有所帮助。

《管理运筹学》第四版课后习题解析第6章单纯形法的灵敏度分析与对偶1．解： （1）c 1≤24 （2）c 2≥6 （3）c s 2≤82．解：（1）c 1≥−0.5 （2）−2≤c 3≤0 （3）c s 2≤0.53．解：（1）b 1≥250 （2）0≤b 2≤50 （3）0≤b 3≤1504．解： （1）b 1≥−4 （2）0≤b 2≤10 （3）b 3≥45. 解：最优基矩阵和其逆矩阵分别为：⎪⎪⎭⎫ ⎝⎛=1401B ，⎪⎪⎭⎫ ⎝⎛-=-14011B ； 最优解变为130321===x x x ，，最小值变为-78； 最优解没有变化； 最优解变为2140321===x x x ，，，最小值变为-96；6．解：（1）利润变动范围c 1≤3，故当c 1=2时最优解不变。

（2）根据材料的对偶价格为1判断，此做法有利。

（3）0≤b 2≤45。

（4）最优解不变，故不需要修改生产计划。

（5）此时生产计划不需要修改，因为新的产品计算的检验数为−3小于零，对原生产计划没有影响。

7. 解：(1)设321,,x x x 为三种食品的实际产量，则该问题的线性规划模型为,, 4005132 4505510 35010168 325.2max 321321321321321≥≤++≤++≤++++=x x x x x x x x x x x x x x x z 约束条件：解得三种食品产量分别为0,75.43321===x x x ，这时厂家获利最大为109.375万元。

(2)如表中所示，工序1对于的对偶价格为0.313万元，由题意每增加10工时可以多获利3.13万元，但是消耗成本为10万元，所以厂家这样做不合算。

（3）B 食品的加工工序改良之后，仍不投产B ，最大利润不变；若是考虑生产甲产品，则厂家最大获利变为169.7519万元，其中667.31110,167.144321====x x x x ，，；（4）若是考虑生产乙产品，则厂家最大获利变为163.1万元，其中382.70,114321====x x x x ，，；所以建议生产乙产品。

《运筹学》作业参考答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

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

（╳）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。

（√）4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。

（√）5.单纯形法计算中，如果不按最小比值规划选出基变量，则在下一个解中至少有一个基变量的值为负。

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

（╳）7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。

（╳）8.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为mnC个。

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

（√）10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。

（√）二、线性规划建模题：1.某公司一营业部每天需从A、B两仓库提货用于销售，需提取的商品有：甲商品不少于240件，乙商品不少于80台，丙商品不少于120吨。

已知：从A仓库每部汽车每天能运回营业部甲商品4件，乙商品2台，丙商品6吨，运费200元/每部；从B仓库每部汽车每天能运回营业部甲商品7件，乙商品2台，丙商品2吨，运费160元/每部。

问：为满足销售量需要，营业部每天应发往A、B两仓库各多少部汽车，并使总运费最少？解：设营业部每天应发往A、B两仓库各x1，x2部汽车,则有：12 121212min200160 47240 2280 621200(1,2)jW x xx xx xx xx j=++≥⎧⎪+≥⎪⎨+≥⎪⎪≥=⎩2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。

线性规划的求解算法 线性规划（linear programming ）是运筹学中的一个重要分支，在现代工业、农业、商业、交通运输、国防军事及经济管理等诸多领域都有着广泛重要的应用。

在数学系的竞赛数学建模中，也多次应用线性规划来建模从而解决实际问题。

在这里介绍单纯性法和对偶单纯形法两种求解线性规划的方法。

一、单纯形法算法主体思想标准线性规划简记如下：LP-max LP-mins.t {0Ax b x =≥ s.t {0Ax b x =≥ 这里只以LP-min 为例。

1、算法思想单纯形法是在已知一个可行基的前提下采用的解决线性规划的算法。

步骤如下：（1）输入初始矩阵：01020,111121,112,1n n m m m n a a a a a a a a a +++⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦K L M M O M K ，并化为典则形式。

用R （i ）记录单位矩阵I 中元素1的位置。

（2）求{}0min |0,1j j a j n t >≤≤@若t 不存在，则得到最优解；(i),1R i n x a += （i=1,2,...m ）.其他j x =0，停。

否则，转到（3）。

（3）求,1min{|0,1}i n it it a a i m a λ+>≤≤@。

若λ不存在，则LP-min 无下届，所以无最优解，停；否则，求,1min (i)|,0,1(s)i n it it a R a i m R a λ+⎧⎫=>≤≤⎨⎬⎩⎭@，转到（4）。

（4）sjsj sta a a ⇐，（j=1，2....n+1） ij ij sj it a a a a ⇐-,(i=0,1,2...m;i ≠s;j=1,2,....,n+1), (s)t R ⇐,转到（2）.二、对偶单纯形法对偶单纯形法是在已知一个正则基的条件下的求解线性规划的方法。

步骤如下:(1)输入初始矩阵：01020,111121,112,1n n m m m n a a a a a a a a a +++⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦K L M M O M K ，并化为典则形式。

第一部分绪论第二部分线性规划与单纯形法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)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；(r)将线性规划约束条件的“≤”号及“≥”号变换成“＝”号,将使问题的最优目标函数值得到改善；(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值；(t)一个企业利用3种资源生产4种产品,建立线性规划模型求解得到的最优解中,最多只含有3种产品的组合；(u)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解；(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少,与约束条件的数量关系相对较小。

用图解法求解下列线性规划问题, 并指出问题具有惟一最优解, 无穷多最优解, 无界解还是无可行解。

⎪⎩⎪⎨⎧≤≤≤≤≤++=83105120106max 212121x x x x x x z2.将下述线性规划问题化成标准形式。

（1）⎪⎪⎩⎪⎪⎨⎧≥≥-++-≤+-+-=-+-+-+-=无约束4,03,2,12321422245243min 4321432143214321x x x x x x x x x x x x x x x x x x x x z解: 令,⎪⎪⎩⎪⎪⎨⎧≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,232142222455243'max 65''4'43216''4'43215''4'4321''4'4321''4'4321x 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 z 3.分别用图解法和单纯形法求解下述线性规划问题, 并比照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。

⎪⎩⎪⎨⎧≥≤+≤++=0,825943510max 21212121x x x x x x x x z解: ①图解法:②单纯形法: 将原问题标准化:⎪⎩⎪⎨⎧≥=++=+++=0,,,825943510max 42132121x x x x x x x x x x x x z C j105 0 0对应图解法中的点C B B b x 1 x 2 x 3 x 4 0 x 3 9 3 4 1 0 3 O 点x 4 8 [5] 2 0 1 8/5 j0 10 5 0 0 0 x 3 21/5 0 [14/5] 1 -3/5 3/2 C 点10 x 18/5 1 2/5 0 1/5 4 j-16 0 1 0 -2 5 x 2 3/2 0 1 5/14 -3/14 B 点10x 11 1 0 -1/7 2/7 j35/2-5/14-25/14单纯型法步骤: 转化为标准线性规划问题；找到一个初始可行解, 列出初始单纯型表；最优性检验, 求cj-zj, 若全部的值都小于0, 则表中的解便是最优解, 否则, 找出最大的值的那一列, 求出bi/aij, 选取最小的相对应的xij, 作为换入基进行初等行变换, 重复此步骤。