用单纯形法求解线性规划问题Word文档格式.docx
《用单纯形法求解线性规划问题Word文档格式.docx》由会员分享，可在线阅读，更多相关《用单纯形法求解线性规划问题Word文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
三：
350，四：
400，五：
480，六：
600；
日：
500；
（1）商场人力资源部应如何安排每天上班的人数才能使商场总的营业员最少
（2）若商场可以雇佣临时工，上班时间同正式工，若正式工每天工资80，临时工每天100，问商场是否应雇佣临时工及雇佣多少名？
四．建立数学模型：
从实际问题中建立数学模型一般有以下三个步骤：
1.根据影响所要达到目的的因素找到决策变量；
2.由决策变量和所在达到目的之间的函数关系确定目标函数；
3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。
线性规划问题的标准形式：
由题可知，可设每天上班人数分别应为x1,x2,x3,x4,x5,x6,x7;
建立下列数学模型
将其转化为标准形式为：
即
价值向量
约束矩阵
右端向量
五．实验原理：
根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…xn的值称为一个解,满足所有的约束条件的解称为可行解。
使目标函数达到最大值（或最小值）的可行解称为最优解。
这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。
求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一：
①存在着一个最优解；
②存在着无穷多个最优解；
③不存在最优解，这只在三种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。
单纯形法的一般解题步骤可归纳如下：
1把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。
2若基本可行解不存在，即约束条件有矛盾，则问题无解。
3若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。
4按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。
5若迭代过程中发现问题的目标函数值无界，则终止迭代。
流程图如下：
六．MALTAB程序代码及注释：
function[x,minf,flag,cpt]=dcxsf（A,b,c）
formatrat%使数据可以以分数形式输出
c=-c;
%将目标函数系数向量加负号得到单纯形表第0行
[m,n]=size（A）;
%求约束矩阵的行数和列数
m1=m;
%保存下原来的行数
s=eye（m）;
%生成秩为m的单位矩阵
A=[As];
%将s矩阵添加到A矩阵右侧
A=[Ab];
%将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=[g1g];
%将单元素零矩阵添加到g1右侧，生成人工向量的检验向量g1
s1=n+m+1;
%记录目前列数之和
s2=zeros（1,m+1）;
%生成1行m+1列的零矩阵s2
c=[cs2];
%将s2添加到c右侧
A1=zeros（m,1）;
%生成一个m行1列的零矩阵A1
fori1=1:
m
A1（i1,1）=i1+n;
%基变量的数值存储区
end
fori=1:
m
g1（1,:
）=g1（1,:
）+A（i,:
）;
decide=find（g1（1,1:
m+n）>
0）;
%寻找g1中大于零的数值列数存于decide数组中
while~isempty（decide）%当decide不为空
i=decide
（1）;
%将列数赋给i
text=find（A（1:
m,i）>
%text存放该列中所有数值大于零的行数
ifisempty（text）%如果text为空则无解
flag=0;
break;
end
min=inf;
%min初始化为无穷大
fori1=1:
m%当该列存在大于零的数值时
ifA（i1,i）>
0&
A（i1,s1）/A（i1,i）<
min%寻找比值最小的
min=A（i1,s1）/A（i1,i）;
x1=i1;
%将比值最小的行数赋给x1
A（x1,:
）=A（x1,:
）/A（x1,i）;
%进行单位化
c（1,:
）=c（1,:
）+（-1*c（1,i）*A（x1,:
））;
）=g1（1,:
）+（-1*g1（1,i）*A（x1,:
ifi1~=x1
A（i1,:
）=A（i1,:
）+（-1*A（i1,i）*A（x1,:
%进行换机迭代
A1（x1,1）=i;
%将列数既对应的非基变量转换为基变量
decide=find（g1（1,[1:
m+n]）>
%再进行查找
ifg1（1,s1）>
0%无解情况
flag=-1;
ifg1（1,s1）==0%置空矩阵
）=[];
fori6=1:
A（:
n+1）=[];
c（n+1）=[];
decide=find（A1（1:
m,1）>
n）;
%查找是否有人工变量
if~isempty（decide）
while~isempty（decide）
x1=decide
（1）;
%存放的是人工变量的行数
text=find（A（x1,1:
n）~=0）;
%该行的所有元素都不为零的列坐标
ifisempty（text）%如果text为空
decide
（1）=[];
A1（x1,:
m=m-1;
else
i=text
（1）;
%i保存列数
%进行单位化
%进行换基迭代
%赋值为空
text
（1）=[];
decide=find（c（1,1:
n）>
%decide存放c中该行中所有数值大于零的列数
%将列数赋给i
text=find（A（:
i）>
%保存大于零的项的行数
ifisempty（text）%为空的时候，则无解
%有可行解但无最优值，flag记为0
c=[c;
A];
%将c添加到A矩阵上方的到对应解的单纯形表
cpt=c;
x=zeros（n,1）;
foro=1:
n
foro1=1:
ifo==A1（o1,1）
x（o,1）=A（o1,n+1）;
disp（'
该问题有可行解但没有最优解!
'
）
minf=-inf;
%无最优值，将minf赋值为无穷小
x=[];
%解向量为空
return;
%min初始化为无穷大
A（i1,n+1）/A（i1,i）<
min%寻找比值最小的
min=A（i1,n+1）/A（i1,i）;
%更新最小值min
%保存最小项的行数赋给x1
%单位化
j=c（1,i）;
forj1=1:
n+1
c（1,j1）=c（1,j1）+A（x1,j1）*（-1）*j;
%换基迭代
）+（-1*A（x1,:
）*A（i1,i））;
%将列数既对应的非基变量转换为基变量
%得到对应解的单纯形表
cpt=c;
x=zeros（n,1）;
foro=1:
minf=c（1,n+1）;
%得到最优值
flag=1;
%有最优值记录flag为1
end
ifflag==0%有可行解但没有最优值情况
%赋值为空
%最优值输出为无穷小
ifflag==1%有可行解有最优值情况
该问题存在最优解!
x=x;
minf=minf;
end;
ifflag==-1%没有可行解情况
该问题没有可行解!
cpt=[];
minf=[];
七．结果运行测试：
输入测试数据：
>
A=[1111100-1000000;
01111100-100000;
001111100-10000;
1001111000-1000;
11001110000-100;
111001100000-10;
1111001000000-1];
b=[300300350400480600550]'
;
c=[11111110000000];
[x,minf,flag,cpt]=dcxsf（A,b,c）
运行结果为：
x=
170
290/3
120
50/3
0
200/3
440/3
310/3
minf=
1850/3
flag=
1
cpt=
Columns1through6
0000-1/30
1000-10
0010-10
00002/30
00002/31
01002/30
0000-5/30
00012/30
Columns7through12
00-1/30-1/30
0001-11
000001
102/3-12/3-1
00-1/302/3-1
01-2/31-2/31
Columns13through15
-1/3-1/31850/3
-10170
-10120
2/3-1/3440/3
-1/32/3200/3
2/3-1/3290/3
-2/3-2/3310/3
2/3-1/350/3
解得最优解为（1709712017067146）
最优值为617
八．心得与感悟：
通过本学期学习MALTAB软件，初步了解并掌握了MATLAB软件中的线性规划问题的编程求解的方法。
通过对编程问题的求解，我明白了掌握编程的重要性。
我们可以把单纯形法的知识运用到企业中去，运用线性规划并配合计算机进行测算非常简便易行，几分钟就可以拿出最优方案，提高了企业决策的科学性和可靠性。
最开始学习的时候，我真的是一片茫然，完全不知道从何处入手，如何把问题和代码联系到一起，后来经过不断地探索，慢慢的掌握maltab软件的应用。
期间也遇到了许许多多的问题和错误，通过和同学讨论，上网XX，一点一点将错误改正，最终完成了代码。
我也知道干什么都不是一件容易的事，坚持下来总会有收获的。
升级会员 