用单纯形法求解线性规划问题.doc

目录

一．摘要 ………………………………………………………… 2
二．实验目的 …………………………………………………… 2
三．实验内容 …………………………………………………… 2
四．建立数学模型 ……………………………………………… 3
五．实验原理 …………………………………………………… 5
六．MALTAB程序代码及注释…………………………………… 7
七．结果运行测试 ………………………………………………… 13
八．心得与感悟 ………………………………………………… 15
一．摘要：
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写LP。
自1946年G.B.Dantizig提出单纯形法以来，它一直是求解线性规划问题的最有效的数学方法之一。单纯形法的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。通过引入普通单纯形法，依次迭代并判断，逐步逼近，最后得到最优解。若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
关键字：线性规划，单纯形法，最优值，最优解

二．实验目的：
1.加强学生分析问题能力，锻炼数学建模能力。
2.了解并掌握MATLAB软件中的线性规划问题的编程、求解和分析。
3.利用所学的MALTAB语言，完成对单纯形法问题的编程设计。

三．实验内容：
某商场决定，营业员每周连续工作5天后连续休息2天，轮流休息，据统计，商场每天需要营业员如下：星期一：300，二：300；三：350，四：400，五：480，六：600；日：500；
（1）商场人力资源部应如何安排每天上班的人数才能使商场总的营业员最少
（2）若商场可以雇佣临时工，上班时间同正式工，若正式工每天工资80，临时工每天100，问商场是否应雇佣临时工及雇佣多少名？

四．建立数学模型：
从实际问题中建立数学模型一般有以下三个步骤：
1.根据影响所要达到目的的因素找到决策变量；
2.由决策变量和所在达到目的之间的函数关系确定目标函数；
3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。

线性规划问题的标准形式：

由题可知，可设每天上班人数分别应为x1,x2,x3,x4,x5,x6,x7;
建立下列数学模型

将其转化为标准形式为：

即

价值向量

约束矩阵

右端向量

五．实验原理：
根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在三种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。
单纯形法的一般解题步骤可归纳如下：
① 把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。
② 若基本可行解不存在，即约束条件有矛盾，则问题无解。
③ 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。
④ 按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。
⑤ 若迭代过程中发现问题的目标函数值无界，则终止迭代。
流程图如下：
対原问题增加m个人工变量构造辅助问题

判断辅助问题最优值g=0
无解，停止
人工变量xj是否为非基变量

把人工变量对应的列从单纯形表中去掉

进行换基迭代得到新矩阵B

B中是否有人工变量

得到初始可行基B

求对应典式和检验数ξ

判断ξk≤0

得到最优解
进行换基迭代得到新基
判断Ak≤0

问题无界
否
是
否
否
是
是
否
是

六．MALTAB程序代码及注释：
function [x,minf,flag,cpt]=dcxsf(A,b,c)
format rat %使数据可以以分数形式输出
c=-c; %将目标函数系数向量加负号得到单纯形表第0行
[m,n]=size(A); %求约束矩阵的行数和列数
m1=m; %保存下原来的行数
s=eye(m); %生成秩为m的单位矩阵
A=[A s]; %将s矩阵添加到A矩阵右侧
A=[A b]; %将b向量添加到A矩阵右侧
g1=zeros(1,n); %生成一个1行n列的零矩阵g1
x=ones(1,m); %生成一个1行m列元素全为1的矩阵
g1=[g1 -x]; %将g1和-x合并，产生一个新的前n列为0后m列为-1的单行矩阵
g=[0]; %初始化一个单元素零矩阵
g1=[g1 g];%将单元素零矩阵添加到g1右侧，生成人工向量的检验向量g1
s1=n+m+1; %记录目前列数之和
s2=zeros(1,m+1);%生成1行m+1列的零矩阵s2
c=[c s2];%将s2添加到c右侧
A1=zeros(m,1);%生成一个m行1列的零矩阵A1
for i1=1:m
A1(i1,1)=i1+n;%基变量的数值存储区
end
for i=1:m
g1(1,:)= g1(1,:)+A(i,:);
end
decide=find(g1(1,1:m+n)>0); %寻找g1中大于零的数值列数存于decide数组中
while ~isempty(decide) %当decide不为空
i=decide(1); %将列数赋给i
text=find(A(1:m,i)>0); %text存放该列中所有数值大于零的行数
if isempty(text) %如果text为空则无解
flag=0;
break;
end
min=inf;%min初始化为无穷大
for i1=1:m % 当该列存在大于零的数值时
if A(i1,i)>0&A(i1,s1)/A(i1,i)<min % 寻找比值最小的
min=A(i1,s1)/A(i1,i);
x1=i1; % 将比值最小的行数赋给x1
end
end
A(x1,:)=A(x1,:)/A(x1,i); % 进行单位化
c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:));
g1(1,:)=g1(1,:)+(-1*g1(1,i)*A(x1,:));
for i1=1:m
if i1~=x1
A(i1,:)=A(i1,:)+(-1*A(i1,i)*A(x1,:)); % 进行换机迭代
end
end
A1(x1,1)=i; % 将列数既对应的非基变量转换为基变量
decide=find(g1(1,[1:m+n])>0); % 再进行查找
end
if g1(1,s1)>0 % 无解情况
flag=-1;
end
if g1(1,s1)==0 %置空矩阵
g1(1,:)=[];
for i6=1:m
A(:,n+1)=[];
end
for i6=1:m
c(n+1)=[];
end
decide=find(A1(1:m,1)>n); % 查找是否有人工变量

if ~isempty(decide)
while ~isempty(decide)
x1=decide(1); % 存放的是人工变量的行数
text=find(A(x1,1:n)~=0); % 该行的所有元素都不为零的列坐标
if isempty(text) %如果text为空
decide(1)=[];
A1(x1,:)=[];
A(x1,:)=[];
m=m-1;
else
i=text(1); % i保存列数
A(x1,:)=A(x1,:)/A(x1,i);%进行单位化
A1(x1,1)=i;

c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:));
for i1=1:m
if i1~=x1
A(i1,:)=A(i1,:)+(-1*A(i1,i)*A(x1,:));
%进行换基迭代
end
end
decide(1)=[];%赋值为空
text(1)=[];
end
end
end
decide=find(c(1,1:n)>0); %decide存放c中该行中所有数值大于零的列数
while ~isempty(decide)
i=decide(1); % 将列数赋给i
text=find(A(:,i)>0); % 保存大于零的项的行数
if isempty(text) % 为空的时候，则无解
flag=0; %有可行解但无最优值，flag记为0
c=[c;A]; %将c添加到A矩阵上方的到对应解的单纯形表
cpt=c;
x=zeros(n,1);

for o=1:n
for o1=1:m
if o==A1(o1,1)
x(o,1)=A(o1,n+1);
end
end
end
disp('该问题有可行解但没有最优解!')
minf=-inf;%无最优值，将minf赋值为无穷小
x=[];%解向量为空
return;
end
min=inf; %min初始化为无穷大
for i1=1:m
if A(i1,i)>0&A(i1,n+1)/A(i1,i)<min % 寻找比值最小的
min=A(i1,n+1)/A(i1,i);%更新最小值min
x1=i1; % 保存最小项的行数 赋给x1
end
end
A(x1,:)=A(x1,:)/A(x1,i); %单位化
j=c(1,i);
for j1=1:n+1
c(1,j1)=c(1,j1)+A(x1,j1)*(-1)*j; % 换基迭代
end
for i1=1:m
if i1~=x1
A(i1,:)=A(i1,:)+(-1*A(x1,:)*A(i1,i));
end
end
A1(x1,1)=i; %将列数既对应的非基变量转换为基变量
decide=find(c(1,1:n)>0); % 再进行查找
end
c=[c;A];%得到对应解的单纯形表
cpt=c;
x=zeros(n,1);

for o=1:n
for o1=1:m
if o==A1(o1,1)
x(o,1)=A(o1,n+1);
end
end
end
minf=c(1,n+1);%得到最优值
flag=1 ; %有最优值 记录flag为1
end

if flag==0 %有可行解但没有最优值情况
disp('该问题有可行解但没有最优解!')
x=[]; %赋值为空
minf=-inf;%最优值输出为无穷小
end
if flag==1 %有可行解有最优值情况
disp('该问题存在最优解!')
x=x;
minf=minf;
end;
if flag==-1 %没有可行解情况
disp('该问题没有可行解!')
x=[];%赋值为空
cpt=[];
minf=[];
end
end

七．结果运行测试：
输入测试数据：
>> A=[1 1 1 1 1 0 0 -1 0 0 0 0 0 0;0 1 1 1 1 1 0 0 -1 0 0 0 0 0;0 0 1 1 1 1 1 0 0 -1 0 0 0 0;1 0 0 1 1 1 1 0 0 0 -1 0 0 0;1 1 0 0 1 1 1 0 0 0 0 -1 0 0;1 1 1 0 0 1 1 0 0 0 0 0 -1 0;1 1 1 1 0 0 1 0 0 0 0 0 0 -1];
>> b=[300 300 350 400 480 600 550]';
>> c=[1 1 1 1 1 1 1 0 0 0 0 0 0 0];
>> [x,minf,flag,cpt]=dcxsf(A,b,c)

运行结果为：
该问题存在最优解!

x =

170
290/3
120
50/3
0
200/3
440/3
310/3
0
0
0
0
0
0

minf =

1850/3

flag =

1

cpt =

Columns 1 through 6

0 0 0 0 -1/3 0
1 0 0 0 -1 0
0 0 1 0 -1 0
0 0 0 0 2/3 0
0 0 0 0 2/3 1
0 1 0 0 2/3 0
0 0 0 0 -5/3 0
0 0 0 1 2/3 0

Columns 7 through 12

0 0 -1/3 0 -1/3 0
0 0 0 1 -1 1
0 0 0 0 0 1
1 0 2/3 -1 2/3 -1
0 0 -1/3 0 -1/3 0
0 0 -1/3 0 2/3 -1
0 1 -2/3 1 -2/3 1
0 0 -1/3 0 -1/3 0

Columns 13 through 15

-1/3 -1/3 1850/3
-1 0 170
-1 0 120
2/3 -1/3 440/3
-1/3 2/3 200/3
2/3 -1/3 290/3
-2/3 -2/3 310/3
2/3 -1/3 50/3

解得最优解为(170 97 120 17 0 67 146)
最优值为617
八．心得与感悟：
通过本学期学习MALTAB软件，初步了解并掌握了MATLAB软件中的线性规划问题的编程求解的方法。通过对编程问题的求解，我明白了掌握编程的重要性。我们可以把单纯形法的知识运用到企业中去，运用线性规划并配合计算机进行测算非常简便易行，几分钟就可以拿出最优方案，提高了企业决策的科学性和可靠性。
最开始学习的时候，我真的是一片茫然，完全不知道从何处入手，如何把问题和代码联系到一起，后来经过不断地探索，慢慢的掌握maltab软件的应用。期间也遇到了许许多多的问题和错误，通过和同学讨论，上网百度，一点一点将错误改正，最终完成了代码。我也知道干什么都不是一件容易的事，坚持下来总会有收获的。
13