单纯形法

单纯形法（共3篇）

单纯形法 篇1

1 引言

在日常生活和企业生产经营管理工作中, 经常面临着给人分派工作、给机床指派加工任务等一般指派问题。指派问题的主要研究方法是定量化、系统化和模型化方法, 特别是运用各种数学模型和技术来解决这类问题。在实际中遇到的问题一般规模比较大, 即使建立了模型, 找到了求解的方法, 对于庞大的计算量也是望而却步。“工欲善其事, 必先利其器”, 有一个方便的求解最优化问题的工具极为重要。LINGO是一个利用线性规划和非线性规划来简洁地阐述、解决和分析复杂问题的简便工具, 其特点是程序执行速度快, 易于输入、修改、求解和分析数学规划问题, 对于线性规划 (LP) 、二次规划 (QP) 、非线性规划 (NLP) 问题, LINGO工具可以给出解决相应问题的方案。本文力图利用LINGO工具, 探讨求解一般指派问题。

2 一般指派问题的数学模型

一般指派问题 (Assignment Problem) 是指有m项任务, 需要有n个人来承担, 由于各人的专长不同, 各人完成的任务不同, 导致其效率也各不相同。因此, 需要科学地指派任务, 使完成m项任务所消耗的总资源最少 (或总体效益最优) 。根据m、n之间的数量关系, 指派问题可分为3种情况进行论述。

第一, 当m=n时, 即为每个人都被指派一项任务;

第二, 当m>n时, 即任务的数量大于人的数量。这时可虚设 (m-n) 个人构成一个m×m的效率矩阵, 并且这 (mn) 个人在执行m项任务时的成本最高;

第三, 当m

通过虚设任务或人, 指派问题要求最小化 (时间、成本、所消耗的n资源n) 时的数学模型为[1]:

约n束条件为:

目标函数 (1) 表示完成全部n项工作所消耗的总资源最少。cij表示指派第i个人去完成第j项任务时所消耗的资源, 由cij (i=1, 2, …, n;j=1, 2, …, n) 组成的方阵, 称为系数矩阵, 简记为c;约束条件 (2) 说明第j项任务只能由一个人去完成;约束条件 (3) 说明第i人只能完成1项任务, 约束条件 (4) 说明xij=1表示指派第i个人完成第j项工作, xij=0表示不指派第i个人完成第j项工作。

如果所要求的是最大化问题如maxF, 则可以转化为最小化问题。一般方法是:取e是一个很大的正数, 一般可以取e=max cij (i=1, 2, …, n;j=1, 2, …, n) 。

令bij=e-cij (i=1, 2, …, n;j=1, 2, …, n) 。

则: , 有F=ne-f, 从而最大化问题得解。

求解一般指派问题的算法很多, 包括匈牙利解法、穷举法、割平面法、单纯形法等。其中单纯形法方法灵活方便且便于计算机求解, 在LINGO中容易实现。

3 单纯形法原理及一般步骤

单纯形法是美国数学家George Dantzig于1947年首先提出的, 其理论根据是:线性规划问题的可行域是n维向量空间Rn中的多面凸集, 其最优值如果存在必在该凸集的某顶点处达到, 该顶点所对应的可行解称为基本可行解。单纯形法的基本思想是:先找出一个基本可行解, 对它进行鉴别, 看是否是最优解;若不是, 则按照一定法则转换到另一改进的基本可行解, 再鉴别;若仍不是, 则再转换, 按此重复进行。因基本可行解的个数有限, 故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

单纯形法的一般解题步骤可归纳如下[1]:

Step 1找出初始可行基, 确定初始基可行解, 建立初始单纯形表。

Step 2检验各非基变量xj的检验数 , 若σj≤0, j=m+1, …, n, 则已得到最优解, 可以停止计算。否则转入下一步。

Step 3在σj>0, j=m+1, …, n中, 若有某个σk对应xk的系数列向量Pk≤0, 则此问题是无界的, 停止计算。否则, 转入下一步。

Step 4根据maxσj=σk (σj>0) , 确定xk为换入变量, 按θ规则计算:

可确定xl为换出变量。转入下一步。

Step 5以alk为主元素进行迭代 (即用高斯消去或称旋转运算) , 把xk所对应的列向量

将XB列中的xl换为xk, 得到新的单纯形表。重复Step 2~Step 5, 直到终止。

4 LINGO程序实现

例4个工人被分派做4项工作, 规定每人只能做一项工作, 每项工作只能一个人做, 现设每个工人做每项工作所消耗的时间如表1, 求总耗时最少的分派方案。

LINGO程序求解过程如下:

Step 1构造两个集合。

sets:

!4个工人, 4个工作的分配问题;

Person/1.4/;

Job/1.4/

Assign (Person, Job) :c, x;

endsets

Step 2构造目标函数min=@sum (Assign:c*x) ;

Step 3构造约束条件。

@for (Person (i) :@sum (Job (j) :x (i, j) ) =1) ;

@for (Job (j) :@sum (Person (i) :x (i, j) ) =1) ;

Step 4求解结果。

LINGO采用单纯形方法, 经过7次迭代, 得出全局最优解70, 指派矩阵为: , 指派安排如下:工作1→工人1, 工作2→工人4, 工作3→工人3, 工作4→工人2, 总耗时为70。

5 结语

通过本实例可以看出, LINGO是一个利用线性规划和非线性规划来简洁地阐述、解决和分析复杂问题的简便工具。其特点是程序执行速度快, 易于输入、修改、求解和分析数学规划问题。另外, 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解。

摘要：本文首先介绍一般指派问题的数学模型和求解方法, 然后详细给出利用单纯形法求解一般指派问题的步骤, 并设计了基于单纯形法的指派问题算法流程, 最后通过LINGO对指派问题的应用实例进行了求解。运行结果表明:LINGO软件程序设计灵活, 能快速准确求解指派问题。

关键词：指派问题,单纯形法,LINGO

参考文献

[1]甘应爱, 田丰等.运筹学[M].北京:清华大学出版社, 1990.

[2]黄雍检.Matlab在经济管理中的应用[J].湖南大学学报:自然科学版, 2005, 32 (2) :121-124.

[3]白国仲, 陈雯, 苏芳荔等.基于特殊需要的指派问题[J].华中师范大学学报:自然科学版, 2006, 40 (3) :305-309.

单纯形法 篇2

题目：单纯形法的发展及其应用系别：理学院专业：信息与计算科学姓名：班级：信息

101班

单纯形法的发展及其应用

一． 单纯形法简介：

单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

二． 单纯形法在线性规划中的应用 1.单纯形法解线性规划问题

在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在一定条件下，如何实现目标最优化。单纯形法是求解线性规划问题的通用方法。

(1)单纯形法解线性规划问题的理论根据是：

线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。

(2)单纯形法的基本思想是：

先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

(3)单纯形法的一般解题步骤可归纳如下：

①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。(4)概述

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。

2.线性规划问题的标准化

使用单纯形法求解线性规划时，首先要化问题为标准形式 所谓标准形式是指下列形式：

maxzcj1njxj

naijxjbi(i1,,m)stj1

x0(j1,2,,n)j当实际模型非标准形式时，可以通过以下变换化为标准形式： ①当目标函数为minzcjxj时，可令Z′=-Z，而将其写成为

j1nminzcjxj

j1n求得最终解时，再求逆变换Z=-Z′即可。

②当s·t·中存在ai1x1ai2x2ainxnbi形式的约束条件时，可引进变量

xn1bi(ai1x1ai2x2ainxn)xn10便写原条件成为

ai1x1ai2x2ainxnxn1bi x0n1其中的xn+1称为松驰变量，其作用是化不等式约束为等式约束。同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量

xn1(ai1x1ai2x2ainxn)bi xn10使原条件写成

ai1x1ainxnxn1bi xn10

3.单纯形法迭代原理（1）确定初始可行解

① 当线性规划问题的所有约束条件均为≤号时，松弛变量对应的系数矩阵即为单位矩阵，以松弛变量为基变量可确定基可行解。

② 对约束条件含≥号或=号时，可构造人工基，人为产生一个m×m单位矩阵用大M法或两阶段法获得初始基可行解。

（2）最优性检验与解的判别（目标函数极大型）

① 当所有变量对应的检验数均非正时，现有的基可行解即为最优解。若存在某个非基变量的检验数为零时，线性规划问题有无穷多最优解；当所有非基变量的检验数均严格小于零时，线性规划问题具有唯一最优解。② 若存在某个非基变量的检验数大于零，而该非基变量对应的系数均非正，则该线性规划问题具有无界解（无最优解）。③ 当存在某些非基变量的检验数大于零，需要找一个新的基可行解，基要进行基变换。

4.确定初始可行解

确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定，为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，„Ｐm）为基变量x1，x2，„xm的系数列向量构成的可行基，Ｎ=(Ｐm+1，Pm+2，„Pn)为非基变量xm+1，xm+2，„xn的系数列向量构成的矩阵。

所以约束方程AX=b就可以表示为AX=(BN)XB=BXB+NXN=b XN用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：XB=B-1b-B-1NXN

若令所有非基变量XN=0，则基变量XB=B-1b

B1b由此可得初始的基本可行解X=

0

5.最优性检验

B1b假如已求得一个基本可行解X=将这一基本可行解代入目，0B1b-1标函数，可求得相应的目标函数值Z=CX=(CBCN)=CBBb

0其中CB=(c1,c2,cm), CN=(cm+1,cm+2,cn)分别表示基变量和非基变量所对应的价值系数子向量。

要判定Z=CBB-1b是否已经达到最大值，只需将XB=B-1b-B-1NXN代入目标函数，使目标函数用非基变量表示，即：

XZ=CX=(CBCN)BXN=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN

CBB-1b+σNXNCBB-1b+(σm+1,σm+1,xm+1xm+2 σn)xn其中N=CN-CBB-1N=(m+1,m+1,n)称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于等于0，即σN≤0，那么现在的基本可行解就是最优解。

6.解的判别

定理1：最优解判别定理

对于线性规划问题maxZ=CX,D=XRn/AX=b,X0，若某个基本可行解所对应的检验向量N=CN-CBB-1N0，则这个基本可行解就是最优解。

定理2：无穷多最优解判别定理

B1b若X=是一个基本可行解，所对应的检验向量0N=CN-CBB-1N0，其中存在一个检验数σm+k=0，则线性规划问题有无穷多最优解。定理3：无最优解判别定理

B1b若X=是一个基本可行解，有一个检验数m+k0，但是0B-1Pm+k0，则该线性规划问题无最优解。

7.基本可行解的改进

如果现行的基本可行解Ｘ不是最优解，即在检验向量N=CN-CBB-1N中存在正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：

（1）先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值）。

（2）再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。

xm+1xm+2σn)xn由此可得一个新的基本可行解，由ZCBB-1b+(σm+1,σm+1,可知，这样的变换一定能使目标函数值有所增加。

8.换入变量的确定--最大增加原则

把基检验数大于0的非基变量定为入基变量。若有两个以上的σj＞0，则选其中的σj最大者的非基变量为入基变量。

从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数增加得更大些，一般选其中的σj最大者的非基变量为入基变量。

9.换出变量的确定--最小比值原则

把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。

即若

bbxkmini|aik0laikalk

则应令xl出基。其中bi是目前解的基变量取值，aik是进基变量xk所在列的各个系数分量，要求仅对正分量做比，（这由前述作法可知，若aik≤0，则对应的xi不会因xk的增加减值而成为出基变量）。

10.两阶段法

用大M法求解含人工变量的LP时，用手工计算不会碰到麻烦，但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长的数字，这就可能造成一种计算上的误差，为克服这个困难，对添加人工变量后的LP分两个阶段来计算，称为两阶段法。

第一阶段：不考虑原问题是否存在基可行解，给原LP加入人工变量，并构造仅含人工变量的目标函数Minw,然后用单纯形法求解，若得w=0，说明原LP存在基可行解，可进行第二阶段计算，否则，停止计算。

第二阶段：将第一阶段计算得到的最终单纯形表除去人工变量，将目标函数行的系数换成原LP的目标函数，作为第二阶段计算的初始表。然后按照前面的方法进行计算。

11.大M法

大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。

为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。

以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。

三． 结论 单纯形法的创建标志着线性规划的诞生。单纯形法的创建统一了以往运输问题和营养问题等的算法，同时推进线性规划理论的发展。反过来，理论的发展也刺激算法的更新。线性规划在这样理论与算法相互促进和相互作用中发展。单纯形法有效地提升了数学规划的应用。很多重大理论诞生之初遭到人们的质疑和反对，但是线性规划不一样，一诞生就得到人们的青睐。这是因为，单纯形算法的计算简洁明了，计算结果精确有效。它求出的是最优解，超乎很多人的期望和想象力。因此被各个领域频频应用来提高工作效率、节

用c语言实现单纯形法的编程 篇3

用c语言实现单纯形法的编程

#include “stdio.h” #include “math.h” #include int M,N;float c[100],a[100][100],b[100],CZ[100],Dn[100],th[100],x[100];int Fn[100];int K,L,ths;float zy;int shuru();void findmm();void chang();main(){ float max_Z,sum=0,s=0;int i,j,r=0;if(!shuru()){ printf(“ERROR！!n”);return 0;} while(r0){findmm();if(ths==M){goto loop;} else chang();} else r++;} } loop: if(ths==M){printf(“n此线性规划没有有限最优解！!n”);printf(“n此线性规划最终迭代结果为：”);printf(“n Cj ”);for(j=0;jDn[K])max=i;K=max;for(i=0;i0)&&(th[i]Dn[K])K=i;for(i=0;i