运筹学课程设计报告书
专业
班级
学号
姓名 LMZZ
日期 2011.09.01
第二篇：运筹学实验报告
运筹学实验
（注：此代码还有一些未完善的地方，仅供参考，此实验报告纯属个人意见，同样仅供参考。话说一样的内容多了老师会发现的）
一、实验目的
通过实验熟悉单纯形法的原理，掌握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（A,C,N）进行求解。
在此函数中，
首先判断N的长度是否为空，
若为空，
则flag=1，进入初始解问题的迭代求值，
添加辅助问题，构建单纯形表，求g所对应的RHS值，
若其>0,则返回该问题无解
若其=0，则返回A1,Z,N三个参数，继续构造单纯形表求解
A1为经过变换后的系数及资源向量
Z为单纯形表的第一行
N为经过辅助问题求解之后的基的下标
否则，
直接构建单纯形表，对该问题进行求解，此时flag=2,多次迭代后找到解。
另外，
若在大于零的检验数所对应的系数均小于零时，会显示“此问题无界”
若找到最优解和最优值时，会输出“val”和“S=”以及具体数值。
四、源程序
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
例2：初始解问题
Min z=5x1+21x3
s.t. x1-x2+6x3-x4=2
x1+x2+2x3-x5=1
xj>=0,j=1,…,5
六、求解实际问题（即解决附件中的实验题目）
实验题目
列出下列问题的数学模型，并用你自己的单纯形算法程序进行计算，最后给出计算结果。
某医院昼夜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 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 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
解得最优解为
x1=0, x2=15, x3=10, x4=10, x5=8, x6=10
最优值为53
(2)
解：由于护工等同于护士，但工资却要高于护士，当该医院可以完全用护士满足值班要求时，不用额外雇佣护工，所以该医院不应该雇佣护工。