运筹学单纯形法教程范文

导语：如何才能写好一篇运筹学单纯形法教程，这就需要搜集整理更多的资料和文献，欢迎阅读由公务员之家整理的十篇范文，供你借鉴。

篇1

关键词：线性规划问题；单纯形法；分块；并行求解

中图分类号： O15 文献标识码：A 文章编号：1672-3791（2016）04（b）-0000-00

Abstract： Simplex method is still the most effective and most commonly used algorithm for solving linear programming problems. Analysis of the calculation principle and process of the simplex method and the correlation operation and swapping based iterative process were divided into blocks， on this basis， design and implementation of the a kind of parallel processing algorithm for solving the mechanism of the linear programming problem. The practical application shows that the new algorithm has a good speedup， and is easy to be implemented in a computer with multi core architecture.

Key words： linear programming problem； simplex method； block； parallel solution

中图分类号：O151.21 文献标识码：A

佛山职业技术学院校级科研基金资助项目： 2014KY017

1 引言

规划问题所涉及的是，对有限的资源进行合理的利用或调配，从而达到所期望的目的。这些问题的特点是，有大量的方案（解）满足每个问题的基本条件，究竟把哪一方案（解）选为最优，则与问题中某一个实际要求或目标有关[1]。而线性规划（Linear Programming）问题则是规划问题例，该类问题的数学模型可用线性的关系式进行描述。通常，线性规划所研究的问题有两类，一类为资源（人力、物力、财力）是给定的，要求充分利用这些资源，最大限度地实现预期的目标（产量、产值最大、利润最高等）；另一类为任务是给定的，要求以消耗最少的资源（原料、工时、成本）来完成它。前一类问题称为极大值问题，后一类问题称为极小值问题[2-4]。

在线性规划的解法中，单纯形法是一个最著名的方法。它在理论上是完善和严格的，在实践上是方便和有效的。注意到当前的微机普遍具有多核计算架构，为更好地发挥这一特性，我们对线性规划问题中的单纯形求解法进行了分块并行计算的改进。

2 线性规划问题的数学模型及其标准形式

2.1 线性规划问题的数学模型

现实生活中的线性规划问题是各式各样的，但经过抽象处理后，它们普遍具有如下的共同特点：表示问题的最优化的目标指标是线性函数，表示约束条件的数学式子是一组变量 的线性等式或线性不等式组，为此，可以得到线性规划问题其数学模型的一般形式为[5]：

求一组决策变量 的值，使之满足下列约束条件：

从图2可知，单纯形的分块并行计算的加速比随着计算规模的增加而增长，在矩阵 的阶数为8000阶时，其加速比达到51.2%。

5 结语

在单纯形法的基础上，提出了一种线性规划问题的分块并行求解算法，新算法具有良好的加速比和易于实现的特点，理论分析及相关实验均表明它是有效的。

参考文献：

1・范玉妹，徐尔，赵金玲等.数学规划及其应用（第3版）[M].北京：冶金工业出版社，2009，1-7.

2・张香云.线性规划[M].杭州：浙江大学出版社，2009，1-173.

3・杜红.应用运筹学 [M].杭州：浙江大学出版社，2010，19-72.

4・张惠恩.管理线性规划[M].大连：东北财经大学出版社，2001，1-91.

5・胡运权.运筹学教程[M].北京：清华大学出版社，2007，11-14.

6・庞碧君.线性规划与随机线性规划[M].郑州： 郑州大学出版社，2007，17-55.

7・周伟明.多核计算与程序设计[M].武汉：华中科技大学出版社，2009，75-124.

8・武汉大学多核架构与编程课程组编.多核架构与编程技术[M].武汉：武汉大学出版社，2010，23-96・

篇2

Abstract： Physical distribution process needs to allocate and transport the materials by the specified requirements and it needs the lowest cost. The table dispatching method can effectively solve the problems.

关键词： 物资调运；建模；表上作业法

Key words： physical distribution；modeling；table dispatching method

中图分类号：F224.3 文献标识码：A 文章编号：1006-4311（2015）36-0105-03

0 引言

在物资调运过程中，完成指定点的调运任务是最基本的要求，在完成基本的任务之外，往往有更高的追求，比如如何使总运费最省？怎样才能使得运输时间最短？如何选择运输路径使得运输总距离最短等等。这些更高的追求往往是企业期望达到的目标，为了解决这些类似问题，有必要对物资调运的过程进行数学模型的建立，以期通过模型来理解和分析物资调运的过程，并为其找到解决的方法。现以具体的案例进行分析研究。

案例：某物流公司有三个仓库，每天向四个超市供应某种货物，其供销及单位运费（元/箱）见表1。要求设计出物资调运方案，使得总运费最省。

现设每个发货点运往每个收货点的具体物资的数量为xij（i=1，2，…m；j=1，2，…n），cij为其对应的单位运费。根据案例中的已知信息可建立物资调运问题的数学模型：

通过上面案例的模型，可得到一般的物资调运问题模型如下：

现设有某种产品，它有m个发货点：A1，A2…Am，发货量分别为a1，a2，…am，Ai表示第i个发货点，ai表示第i个发货点的发货量；它又有n个收货点：B1，B2…Bn，收货量分别为b1，b2，…bn， Bj表示第j个收货点，bj表示第j个收货点的收货量；cij表示从Ai到Bj的单位运费。

从上述建模的过程可以看出，物资调运问题是一类特殊的线性规划问题，可以用一般的单纯形法求解，但是应去掉一个多余的约束条件，计算往往比较复杂，这里不予讨论。

根据模型，物资调运的方案有多种，即有多个解，但如何能从多个解中寻找到满足条件的最优解，这才是最为关键的问题。为了寻找出最优解，需要使用一种迭代法，一般将迭代过程在表格中进行，通过不断地调整方案，最后得到最优方案，这种方法多称为“表上作业法”。目前表上作业法为求解物资调运问题的一种简便而实用的方法，下面将具体介绍如何用表上作业法求解物资调运问题。

表上作业法要求先整理出产销平衡表和单位运费表，再根据产销平衡表和运费表编制出初始调运方案。初始方案不一定是最优方案，需要检验方案是否为最优，若不是最优的，则需在初始方案上进行调整，调整后再检验，经过若干次调整检验，终能得到最优的调运方案。 运用表上作业法求得物资调运问题的最优解，需要解决三个关键问题：一是初始调运方案如何制定；二是怎样判断方案是否为最优；三是如方案不是最优，怎样调整出最优。接下来将重点从这三个方面来分析物资调运问题的解法。

1 制定初始调运方案

制定初始调运方案目前有三种方法：最小元素法、西北角法、沃格尔法。从简单易理解角度出发，习惯使用最小元素法（即寻找单位运费最小的点处优先安排运输量，以节省运费）制定初始调运方案：

①从运费表所有元素中选取最小元素。

②寻找这个元素所在的行对应的发货量和列对应的收货量中的较小者，将较小者填入初始调运方案中这个元素所对应的空格处，并在运费表中划去较小者所在的行或列。案例的运费表中最小的元素为1，1对应的行的总发货量为40箱，而列对应的总收货量为30箱，所以在初始调运方案中将1对应处即发点A2仓库处运送30箱到B1超市，又因为列对应的总收量为30箱，所以该列的总收量已经全部满足，该列的其余元素3和7对应处则不再安排运输任务，于是运费表中B1对应列可以划掉，以方便寻找运费表剩下元素中的最小元素。

③依此类推，直到收货量和发货量全部满足。

注意：1）每在初始调运方案中填入一个数字，运费表中至少有一列或一行被满足，划去该行或该列的元素，直到运费表全部被划完，此时初始调运方案表中有填数字的格数是m+n-1。

2）如果某行或列的供应量都已经满足，但该行或列还未被划去，应在初始调运方案表内相应位置填入0，然后再划去该行或列，并将填0的格子与其他填数的格子同等对待，保证每填入一个数，只能划去一行或一列。

3）最后一个填入数字的格应使行或列同时满足。

通过上述制定初始方案过程，可以得到案例对应的初始调运方案如表2所示。

2 检验调运方案是否为最优

检验的过程是在运费表中进行，在运费表中把对应于有调运数字的运费用圆圈圈起，通过闭回路法求检验数，根据检验数来检验方案是否为最优方案。

闭回路的寻找方法如下：从任意一个空格出发，沿水平或垂直方向前进，遇到有数字的格子转向，经过若干次转向后，回到原来出发的空格，形成闭回路。注意：有数字的格子处可以转向，也可以不转向，但要转向的地方必为有数字的格子处。

求检验数：从空格（即无调运对应处）出发，沿闭回路，将其对应的闭回路中偶数次转向点对应的运费总和减去奇数次转向点对应的运费总和，所得的差为该空格处检验数。

检验过程：如果所有的检验数均非负，则该方案为最优方案，反之，则不是最优，需调整。

表3为运用闭回路法求得的初始调运方案对应的检验数。

3 调整

上面已经提到，如果所有的检验数均非负，则该方案为最优方案，无需调整。反之，只要任意一个（或多个）检验数是负数，则需对初始调运方案进行调整。由初始方案对应的检验数表中可以看到，A2行B4列对应处检验数为-1，需要调整。

调整过程是在初始调运方案中进行，首先将检验数中最小负值对应的初始调运方案处找到，作出对应空格的闭合回路。奇数次转向点中最小运量作为调整量，所有奇数次转向点运量减去调整量，偶数次转点运量加上该调整量，得到新的调运方案。（表4）

新调运方案依然无法确定其是否为最优方案，所以仍需对新方案继续求检验数以便再次检验，如所有检验数非负，则为最优方案，若有负数的检验数，则继续一次次调整，再检验，直到得到最优方案。新方案对应的检验数如表5所示。

从新方案对应的检验数来看，所有的检验数均非负，故此新方案已是最优方案。即从A1仓库分别运50箱和20箱到B3和B4超市；从A2分别运30箱和10箱到B1和B4超市；从A3仓库分别运60箱和30箱到B2和B4超市。其最小总运费为：30×1+60×4+50×3+20×10+10×8+30×5=850元。

运用表上作业法求解物资调运过程，从确定初始调运方案到检验是否为最优，不是则调整出最优，整个思维过程不仅仅适用于求总运费最省的情形，同样适用于求耗时最少或是路程最短问题。表上作业法虽然为求解物资调运问题的一种行之有效的方法，但是仍然有不少问题需要解决，比如如何能一次得到最优方案，规避调整多次的情形；产销不平衡又如何解决等等，这些都是值得继续探讨的问题。

参考文献：

[1]傅维潼.物流数学[M].高等教育出版社，2006.