线性规划的求解算法精选文档.docx

TTMS system office room 【TTMS16H-TTMS2A-TTMS8Q8-TTMSHHJ8】
线性规划的求解算法精选文档
线性规划的求解算法
线性规划（linear programming）是运筹学中的一个重要分支，在现代工业、农业、商业、交通运输、国防军事及经济管理等诸多领域都有着广泛重要的应用。在数学系的竞赛数学建模中，也多次应用线性规划来建模从而解决实际问题。在这里介绍单纯性法和对偶单纯形法两种求解线性规划的方法。
一、单纯形法算法主体思想
标准线性规划简记如下：
LP-max LP-min
{ {
这里只以LP-min为例。
1、算法思想
单纯形法是在已知一个可行基的前提下采用的解决线性规划的算法。步骤如下：
输入初始矩阵：，并化为典则形式。
用R（i）记录单位矩阵I中元素1的位置。
求
若t不存在，则得到最优解； （i=1,2,...m）.其他=0，停。否则，转到（3）。
求。
若不存在，则LP-min无下届，所以无最优解，停；否则，求，转到（4）。
，（j=1，2....n+1）
,(i=0,1,2...m;is;j=1,2,....,n+1),
,转到（2）.
对偶单纯形法
对偶单纯形法是在已知一个正则基的条件下的求解线性规划的方法。步骤如下:
(1)输入初始矩阵：，并化为典则形式。
用R（i）记录单位矩阵I中元素1的位置。
(2)求
若s不存在，则得到最优解； （i=1,2,...m）.其他=0，停。否则，转到（3）。
(3)求。
若不存在，则LP-min无下届，所以无最优解，停；否则，求，转到（4）。
(4)，（j=1，2....n+1）
,(i=0,1,2...m;is;j=1,2,....,n+1),
,转到（2）.
程序代码
1、单纯形法。
% 求解标准型线性规划:max c*x; . A*x=b;x>=0
%A1是标准系数矩阵及最后一列是资源向量，C是目标函数的系数向量
% N是(初始的)基变量的下标
%M=10000 人工变量系数
% 本函数中的A是单纯形表，包括:最后一行是初始的检验数，最后一列是资源向量b
%c1是基变量系数
%输出变量sol是最优解
%输出变量val是最优值，k是迭代次数
%flag1的值代表有无最优解，0无界解，1无可行解，2无穷多解，3唯一最优解

function [sol,val,k,flag1]=ssimplex(A1,C,N)
M=10000;
[mA1,nA1]=size(A1);
C1=[C,0];
val=zeros(1,length(C));
for i=1:length(N)
c1(i)=C1(N(i));
end
for i=1:nA1
a(i)=C1(i)-c1*A1(:,i);%计算初始检验数
end
A=[A1;a]; %构造初始单纯