线性规划问题的单纯形算法研究

【摘要】线性规划（LP）是运筹学中较早发展起来并已经成熟广泛地应用于各个领域的一个重要数学理论和方法.线性规划是研究在存在线性约束条件下目标函数的最优解或极值问题.单纯形算法是线性规划算法中发展最早、应用最广泛的算法，本文阐述了单纯形算法的基本算法及其发展.

【关键词】运筹学；线性规划；单纯形算法

一、线性规划简介

线性规划研究的主要内容为在一定的约束条件下，如何合理地安排人力、物力等各项资源以获得最优最好的经济效果.从数学层面来说即求解线性目标函数在特定线性约束条件下的最大或最小值的极值问题.线性规划是运筹学的一个重要分支，早在1832年法国数学家傅里叶便提出了线性规划的想法，经过近200年的发展，已经广泛地运用在军事管理、经济运营和工程技术等领域＼[1＼].

二、单纯形算法

单纯形算法最早是在1947年由美国数学家G.B.Dantzig提出，一经提出便成为了线性规划问题的基本求解方法，为线性规划的发展奠定了基础.单纯形算法的基本思路是先求得一个初始基本可行解，并以这个初始基本可行解在可行域中对应的顶点为出发点，根据最优判别准则判断此基本可行解是否为最优解，如果不是则沿着可行域的某个可行下降边方向转换到一个相邻的“更好”极点，即得到一个新的基可行解，并使目标函数值不增，如此反复迭代，直至找到原问题的最优解或判断原问题无界或判断原问题不可行＼[2＼].针对于单纯形算法，目前也出现了许多改进的方法.

1.单纯形的基本算法

对于标准型的线性规划问题：minz=∑n1j=1CjXj

st∑n1j=1aijxj=bj（i=1，2，…，m）

xj≥0（j=1，2，…，n）

单纯形算法的基本步骤为：

（1）找出初始可行基B，确定初始基可行解，建立初始单纯形表（如表1-1）.

表1-1单纯形表

1cj11c11…1cm1…1cj1…1cnCB1基1b1x11…1xm1…1xj1…1xnc1

c2

…

cm1x1

x2

…

xm1b1

b2

…

bm11

0

…

01…

…

…

…10

0

…

11…

…

…1a1j

a2j

…

amj1…

…

…

…1a1n

a2n

…

amn1cj-zj1101…101…1cj-∑m1i=1ciaij1…1cn-∑m1i=1ciaij（2）检验各非基变量xj的检验数为σj=cj-∑ni=1ciaij.若其中σj≤0，j=m+1，…，n则代表已经得到最优解，可停止计算，若σj>0，j=m+1，…，n，并且在其中有σk对应的xk的数列向量pk≤0，则表示此问题无界，可停止计算.

（3）以θ规则θ=minbj1aikaik>0，i=1，2，…，m=b11aik确定换出向量.

（4）进行迭代运算，把所对应的数列向量转变为PB1得到新的基，对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表（表1-2）.

（5）重复迭代运算及判定过程，就能得到最优解或判断出无有限最优解.

表1-2初始单纯形表

1cj11c11…1cr1…1cm1…1cj1…1ck1…CB1基1b1x11…1xr1…1xm1…1xj1…1xk1…c1

推荐访问:线性规划 算法 研究