运筹学实验报告
一、实验目的：
通过实验熟悉单纯形法的原理，掌握matlab循环语句的应用，提高编程的能力和技巧，体会matlab在进行数学求解方面的方便快捷。
二、实验环境：
Matlab2012b,计算机
三、实验内容（包含参数取值情况）：
构造单纯形算法解决线性规划问题
Min z=cx
s.t. Ax=b
xj>=0,j=1,…,n
函数功能如下：
function[S,val]=danchun(A1,C,N)
其中，S为最优值，Val为最优解，A1为标准形式LP问题的约束矩阵及最后一列为资源向量（注：资源向量要大于零），A1=[A+b]；C是目标函数的系数向量，C=c；N为初始基的下标（注：请按照顺序输入，若没有初始基则定义N=[]）。
先输入A1,C,N三个必要参数，然后调用danchun（A1,C,N）进行求解。在此函数中，首先判断N的长度是否为空，若为空，则flag=1，进入初始解问题的迭代求值，添加辅助问题，构建单纯形表，求g所对应的RHS值，若其>0,则返回该问题无解，若其=0，则返回A1,C,N三个参数，继续构造单纯形表求解。A1为经过变换后的系数及资源向量，C为单纯形表的第一行，N为经过辅助问题求解之后的基的下标。否则，直接构建单纯形表，对该问题进行求解，此时flag=2,多次迭代后找到解。另外，若在大于零的检验数所对应的系数均小于零时，会显示“此问题无界”。
若找到最优解和最优值时，会输出“val”和“S=”以及具体数值。
四、源程序（在matlab中输入edit后回车，写在.M文件中，并保存为danchun.M）
function[S,val]=danchun(A1,C,N)
if(length(N)==0)
gN=zeros(1,length(A1(:,1)));
gC=[-C,gN,0];%原文题的检验数的矩阵
Z=gC;
G=[zeros(1,length(C)),-ones(1,length(gN)),0];
val=zeros(1,length(C));%val为最优解；
for i=(length(C)+1):length(C)+length(A1(:,1))%生成基变量
gN(i-length(C))=i;
end
Nn=gN;
%%%%%%%
ll=zeros(1,length(N));%比值最小原则
%生成除了最上端两行的表的矩阵
gb=A1(:,length(C)+1);
A1(:,length(C)+1)=[];
l=zeros(length(gN),length(gN));
gA=[A1,l,gb];
for i=1:length(gb)
gA(i,gN(i))=1;
end
for i=1:length(gN)%J为基本可行基所对应的检验数
J(i)=G(gN(i));
end
for i=1:length(gN)%找到基本可行基的检验数，将其赋值为0
if(J(i)~=0)
G=G-(J(i)/gA(i,gN(i)))*gA(i,:);
end
end
flag=1;
else
flag=2;
A=A1;
Z=[-C,0];%单纯形表的第一行
val=zeros(1,length(C));%val为最优解；
ll=zeros(1,length(N));%比值最小原则
end
%%初始解问题
while flag==1
for i=1:length(gN)%J为基本可行基所对应的G的检验数
J(i)=G(gN(i));
JZ(i)=Z(gN(i));%JZ为基本可行基所对应的Z的检验数
end
for i=1:length(gN)%找到基本可行基的检验数，将其赋值为0
if(J(i)~=0)
G=G-(J(i)/gA(i,gN(i)))*gA(i,:);
Z=Z-(JZ(i)/gA(i,gN(i)))*gA(i,:);
end
end
G1=G;%G1为检验数
G1(:,length(G1))=[];
D=max(G1);%找到检验数的最大值
if(D<=0)%检验数都小于0
if(G(length(G))>=1)
disp('此情况无解');
flag=0;
else
if(G(length(G))>=0)
for i=1:length(gN)
if(max(gN)<=length(A1(1,:)));
flag=2;
for j=1:length(Nn)
a=Nn(1);
gA(:,a)=[];
Z(a)=[];
end
A=gA;
N=gN;
break;
end
end
end
end
else%检验数大于0
for i=1:length(G)
if(G(i)==D)%找到最大的那个检验数所对应的元素
for j=1:length(gN)
if(gA(j,i)>0)
ll(j)=gA(j,length(G))/gA(j,i);%求比值
else
ll(j)=10000;
end
end
d=min(ll);
for k=1:length(ll)%找到进基和离基
if(ll(k)==d)
gN(k)=i;
gA(k,:)=gA(k,:)/gA(k,i);
for m=1:k-1
gA(m,:)=-(gA(m,i)/gA(k,i))*gA(k,:)+gA(m,:);
end
for n=k+1:length(ll)
gA(n,:)=-(gA(n,i)/gA(k,i))*gA(k,:)+gA(n,:);
end
break;
end
end
end
end
end
end
while(flag==2)
for i=1:length(N)%J为基本可行基所对应的检验数
J(i)=Z(N(i));
end
for i=1:length(N)%找到基本可行基的检验数，将其赋值为0
if(J(i)~=0)
Z=Z-(J(i)/A(i,N(i)))*A(i,:);
end
end
Z1=Z;%Z1为检验数
Z1(:,length(Z1))=[];
D=max(Z1);%找到检验数的最大值
if(D<=0)%检验数都小于0
disp('已找到最优解和最优值')
for i=1:length(N)
val(N(i))=A(i,length(Z));
end
S=Z(length(Z));
disp('val');
disp(val);
flag=0;
else%检验数大于0
for i=1:length(Z)
if(Z(i)==D)%找到最大的那个检验数所对应的元素
for j=1:length(N)
if(A(j,i)>0)
ll(j)=A(j,length(Z))/A(j,i);%求比值
else
ll(j)=10000;
end
end
d=min(ll);
if(d==10000)
disp('此问题无界')
flag=0;
break;
end
for k=1:length(ll)%找到进基和离基
if(ll(k)==d)
N(k)=i;
A(k,:)=A(k,:)/A(k,i);
for m=1:k-1
A(m,:)=-(A(m,i)/A(k,i))*A(k,:)+A(m,:);
end
for n=k+1:length(ll)
A(n,:)=-(A(n,i)/A(k,i))*A(k,:)+A(n,:);
end
break
end
end
end
end
end
end
五、运行结果与数据测试
参考例题：
例1：
Min z=3x1+x2+x3+x4
s.t. -2x1+2x2+x3=4
3x1+2x+x4=6
Xj>=0,j=1,2,3,4
在workspace中写入，形式如下：
>> A=[-2 2 1 0 4
3 1 0 1 6]
A =
-2 2 1 0 4
3 1 0 1 6
>> C=[3 1 1 1]
C =
3 1 1 1
>> N=[3 4]
N =
3 4
>> danchun(A,C,N)
已找到最优解和最优值
val
0 2 0 4
ans =
6
例2：初始解问题
Min z=5x1+21x3
s.t. x1-x2+6x3-x4=2
x1+x2+2x3-x5=1
xj>=0,j=1,…,5
在workspace中写入，形式如下：
>> A=[1 -1 6 -1 0 2
1 1 2 0 -1 1]
A =
1 -1 6 -1 0 2
1 1 2 0 -1 1
>> C=[5 0 21 0 0]
C =
5 0 21 0 0
>> N=[]
N =
[]
>> danchun(A,C,N)
已找到最优解和最优值
val
0.5000 0 0.2500 0 0
ans =
7.7500
六、求解实际问题（即解决附件中的实验题目）
实验题目
列出下列问题的数学模型，并用你自己的单纯形算法程序进行计算，最后给出计算结果。
某医院昼夜24小时各时段需要的护士数量如下
2:00---6:00 10人 6:00---10:00 15人 10:00---14:00 25人
14:00---18:00 20人 18:00---22:00 18人 22:00---2:00 12人
护士分别于2:00 , 6:00, 10:00, 14:00, 18:00, 22:00 分六批上班，并连续工作8小时。试确定：（1）该医院至少应设多少名护士，才能满足值班需要
（2）若医院可以聘任合同工护士，上班时间同正式护士。若正式护士报酬为每小时10元，合同工护士为每小时15元，问医院是否应聘任合同工护士及聘多少名？
解：（1）设护士分别于2:00 , 6:00, 10:00, 14:00, 18:00, 22:00 分六批上班的每批人数为x1,x2,x3,x4,x5,x6.
min z=x1+x2+x3+x4+x5+x6
s.t. x6+x1>=10
x1+x2>=15
x2+x3>=25
x3+x4>=20
x4+x5>=18
x5+x6>=12
xj>=0 j=1,2…,6
先将其化为标准形式：
Min z=x1+x2+x3+x4+x5+x6
s.t. x6+x1-x7=10
x1+x2-x8=15
x2+x3-x9=25
x3+x4-x10=20
x4+x5-x11=18
x5+x6-x12=12
xj>=0 j=1,2…,12
在workspace中写入，形式如下：
>> A=[1 0 0 0 0 1 -1 0 0 0 0 0 10
1 1 0 0 0 0 0 -1 0 0 0 0 15
0 1 1 0 0 0 0 0 -1 0 0 0 25
0 0 1 1 0 0 0 0 0 -1 0 0 20
0 0 0 1 1 0 0 0 0 0 -1 0 18
0 0 0 0 1 1 0 0 0 0 0 -1 12]
A =
Columns 1 through 11
1 0 0 0 0 1 -1 0 0 0 0
1 1 0 0 0 0 0 -1 0 0 0
0 1 1 0 0 0 0 0 -1 0 0
0 0 1 1 0 0 0 0 0 -1 0
0 0 0 1 1 0 0 0 0 0 -1
0 0 0 0 1 1 0 0 0 0 0
Columns 12 through 13
0 10
0 15
0 25
0 20
0 18
-1 12
>> C=[1 1 1 1 1 1 0 0 0 0 0 0]
C =
Columns 1 through 11
1 1 1 1 1 1 0 0 0 0 0
Column 12
0
>> N=[]
N =
[]
>> danchun(A,C,N)
得到的结果显示如下：
已找到最优解和最优值
val
Columns 1 through 11
0 15 10 10 8 10 0 0 0 0 0
Column 12
6
ans =
53
解得最优解为
x1=0, x2=15, x3=10, x4=10, x5=8, x6=10
最优值为
53
(2)
解：因为上述结果为53人是整数，所以该医院没有必要聘请护工。当该医院可以完全用护士满足值班要求时，不用额外聘请。如果医院的护士人数不满足值班需求时，应该在符合结果的要求下雇佣护士。
第二篇：运筹学实验报告1
实 验 报 告
项目名称
所属课程名称 运筹学
项目类型
实验(实训)日期 3月18号
班 级
学 号
姓 名
指导教师
浙江财经学院教务处制
一、 实验概述
（一）实验目的
掌握使用Excel软件求解线性规划问题。
（二）实验要求
用Excel软件完成案例求解并进行结果分析。
（三）实验工具
Excel软件
二、实验内容
案例 营养配餐问题
w 有A、B两种食品，含有每天必须的营养成分C、D，每天至少需要营养成分C和D分别为2和3个单位。食品A、B的成分和单价如下表，试做花钱最少的食谱，并求其费用。
（一）线性规划模型
w 1、确定决策变量：设A、B两种食品每天的购买量分别为x1,x2单位。
w 2、确定目标函数：min W=0.9x1+0.8x2
w 3、确定约束条件：成分C约束：x1+2x2 ≥2
成分D约束：3x1+x2 ≥3
x1 ≥0,x2 ≥0
（二）电子表格模型
（三）结果分析
分析：
由上表可知：目标函数的最小值为1.2，当产品A的购买量为0.8，产品B的购买量为0.6时取得最小值。取得最小值时成分C的含量与成分D的含量均达到最低要求。
分析：
有该表可知：产品A购买量下极限为0.8单位，取下极限时目标函数结果为1.2，上极限为无穷大，目标值也为无穷大；产品B购买量下极限为0.6单位，取下极限时目标函数结果为1.2，上极限为无穷大，目标值也为无穷大。