系统优算法设计与实现运筹学课设Word下载.doc
《系统优算法设计与实现运筹学课设Word下载.doc》由会员分享,可在线阅读,更多相关《系统优算法设计与实现运筹学课设Word下载.doc(24页珍藏版)》请在冰点文库上搜索。
教研室主任(签字)
设计总说明
分析线性规划灵敏度分析算法这个问题。
把解决问题所需条件、原始数据、输入输出信息等搞清楚。
对较大问题(单纯形法的计算和线性规划的矩阵描述)的用文字和流程图描述。
分析完后问题后建立数学模型,把问题数学化公式化,此算法中有矩阵的乘法运算,矩阵的分离与合并(比如将矩阵A分为BN,即A=BN),单纯形法,求最大最小值,设计X变化范围的计算公式
之后绘制程序流程图,可用文字概述为以下六步。
第一步:
从文件读入数据。
第二步:
根据要求分离矩阵。
第三步:
输入目标函数,检验最优性。
第四步:
若不是最优,设计单纯形表算法,进行计算,检验最优性。
重复第四步,直到最优。
第五步:
输出改变目标函数后最终单纯形表。
第六步:
输入要计算变化范围的X,利用公式计算,然后输出。
编制程序,画完流程图后,就可以进行编程了。
根据流程图编程,为防止最后检查时错误过多无从下手,对程序进行分模块编程,把一些小的算法先编程调试成功,再带入主程序。
编写主程序的时候,每写完一小部分,要进行调试,检查是否有逻辑或语法错误。
在编程中,还要对定义的变量和编写的语句进行解释,让程序更易理解。
如果还未编程等待编程的语句和可插入其他功能程序的地方也要进行解释说明,这样,对后续的程序修改和优化也有帮助。
编写完毕,对程序进行调试运行。
关键字:
线性规划,灵敏度,程序设计,C语言
目录
1绪论 1
1.1内容简介 1
1.2本次课设目的 1
1.3课设内容 1
2.线性规划灵敏度分析算法设计说明 3
2.1程序设计过程详述 3
2.2编程实现过程详述 3
2.4原代码 4
3实验研究小结 18
3.1使用说明详述 18
3.1.1本部分功能操作注意事项 18
3.1.2本部分功能与其他系统的关系 18
3.2测试案例详述 18
参考文献 20
1绪论
1.1内容简介
在线性规划问题中的参数往往是一些估计和预测的数字,随着环境的变化(如市场条件变化,工艺技术条件的变化),其最优解也会随之变化。
当这些参数中的一个或多个发生改变是,问题的最优解会有什么变化,或者这些参数在什么范围变化时,问题的最优解或最优基不变。
为解决线性规划的目标函数的这些问题,本程序中对此进行灵敏度分析。
1.2本次课设目的
本程序中对线性规划的目标函数做出灵敏度分析,以书(胡运权.《运筹学》.清华大学出版社,2012,P64)中例五为例,分析市场条件变化后利润的变化,导致目标函数改变,分析这些变化对结果的影响,以及目标函数在什么范围变化是,问题的最优解不变。
1.3课设内容
一:
调整目标函数系数,将参数的改变反映到最终单纯形表中,判断是否最优,若不是,继续计算
二:
设计单纯形法算法
三:
确定目标函数系数可变化的范围
2.线性规划灵敏度分析算法设计说明
2.1程序设计过程详述
一.分析问题,了解问题要求和目的。
二.程序分块和建立数学模型,用公式和文字把题目中涉及到的算法一步步分解成小模块,依次解决。
其中包括:
文件的读入,矩阵的乘法运算,矩阵的分离与合并(比如将矩阵A分为BN,即A=BN),单纯形法,求最大最小值,设计X变化范围的计算公式等
三.建立流程图,把二中的算法按照步骤组合起来。
四.对各个小模块进行编程,调试成功后,再根据流程图编写主程序,顺便把要用到小模块加进去,然后进行调试。
2.2编程实现过程详述
2.4原代码
#include"
stdio.h"
math.h"
string.h"
stdlib.h"
dos.h"
intmain()
{
doubleF[10][10],b[10][50],C[50][10];
intJ[10][50];
//初始矩阵:
F是AX+IX=b的AIb。
C是maxz=CX+0X的C0。
J是基
doubleFF[10][10],bb[10][50],CC[50][10],BB[10][10];
intJJ[10][50];
//最终单纯形表:
BB是B的逆矩阵
doubleR[50][10][20];
inti,j,k;
intr,l;
//r为约束条件矩阵的行。
l为约束条件矩阵的列
printf("
输入约束矩阵的行r和列l:
"
);
scanf("
%d%d"
&
r,&
l);
\n"
//---------------------输入初始单纯形表和最终单纯形表-----------------------------
FILE*fp=fopen("
D:
\\A.txt"
"
r"
//输入F[3][6]
if(!
fp)return0;
i=0;
j=0;
while(!
feof(fp))
{
fscanf(fp,"
%lf"
F[i][j]);
j++;
if(j==6)
{
i++;
}
}
fclose(fp);
FILE*fp1=fopen("
\\B.txt"
//输入C[0][5]
fp1)return0;
feof(fp1))
fscanf(fp1,"
C[0][i]);
i++;
fclose(fp1);
FILE*fp2=fopen("
\\C.txt"
//输入基j[3][0]
fp2)return0;
feof(fp2))
fscanf(fp2,"
%d"
J[i][0]);
fclose(fp2);
FILE*fpd=fopen("
\\D.txt"
//输入FF[3][6]
fpd)return0;
feof(fpd))
fscanf(fpd,"
FF[i][j]);
fclose(fpd);
FILE*fpe=fopen("
\\E.txt"
//输入CC
fpe)return0;
feof(fpe))
fscanf(fpe,"
CC[0][i]);
fclose(fpe);
FILE*fpf=fopen("
\\F.txt"
//输入基
fpf)return0;
feof(fpf))
fscanf(fpf,"
JJ[i][0]);
fclose(fpf);
//--------------------输出初始单纯形表和最终单纯形表-------------------------------------
printf("
线性规划的初始单纯形表为:
//输出初始单纯形表
Cj"
for(i=0;
i<
l-1;
i++)
{
printf("
%lf"
C[0][i]);
}
基"
printf("
b"
printf("
X%d"
i);
k=0;
for(i=0;
r;
printf("
X%d"
J[i][0]);
for(j=0;
j<
l;
j++)
printf("
F[i][j]);
k++;
if(k==6)
{
printf("
k=0;
}
}
printf("
\n\n"
最终单纯形表为:
//输出最终单纯形表
Cj-Zj"
CC[0][i]);
JJ[i][0]);
FF[i][j]);
}
//--------------------------分离出b[r][0],bb[r][0],BB[r][r](B的逆)----------------------
b[i][0]=F[i][l-1];
bb[i][0]=FF[i][l-1];
k=0;
for(j=l-r-1;
BB[i][k]=FF[i][j];
}
//------分离出CB[0][r]---------
doubleCB[100][r];
k=JJ[i][0];
//printf("
%d"
k);
CB[0][i]=C[0][k-1];
//------------------------------------------------------------------------------------------------
//--------------------------------------分析cj的变化----------------------------------------
//----------------------------------------------------------------------------------------------------
printf("
现在分析Cj的变化对最优解的影响\n请输入新的目标函数系数:
scanf("
C[1][i]);
//------分离出CB[1][r]---------
CB[1][i]=C[1][k-1];
//-----计算-CB*BB,这边设为E--------CB[1][r]BB[r][r]----------------------------
doubleE[1][r],H[1][r];
doublesum=0;
1;
i++)//i是CB的行
j++)//j是BB的列
for(k=0;
k<
k++)//k是CB的列和BB的行
sum=sum+CB[i+1][k]*BB[k][j];
}
E[i][j]=(-1)*sum;
sum=0;
j=0;
for(i=l-r-1;
CC[1][i]=E[0][j];
j++;
//-----------------------------单纯形法---------------------------------------------------------
ints,m,n,p,q;
//s用来判断是否进行单纯形表的计算
doubleQ[r];
intmaxl,minbi,minr;
//最小列maxl,最小行的基minbi,最小行minr
doublemaxC,minb,t;
//最大maxC,minb
s=0;
i++)//检验是否最优
if(CC[1][i]>
0)
s=1;
//如果存在检验数大于0,不是最优,则s=1
}
}
if(s==0)
{
新的目标函数对应的结果仍旧是最优解\n"
i++)//将FF[r][l]赋值给R[0][][]
R[0][i][j]=FF[i][j];
//----------不是最优还需继续进行解单纯形表---------
if(s==1)
{
//----------找出换出和换入的基--------------------
for(k=0;
s==1;
k++)
maxC=CC[k+1][0];
maxl=0;
for(i=0;
i++)//找出换入的基
{//找出检验数中最大的系数记为maxC,对应的基Xi记为maxl+1(下标),maxl为列,从第0列开始计算
if(CC[k+1][i]>
maxC)
{
maxC=CC[k+1][i];
maxl=i;
}
if(R[k][i][maxl]<
=0)
Q[i]=999999999;
}
else
Q[i]=bb[i][k]/R[k][i][maxl];
}
}
minb=Q[0];
minbi=J[0][k];
minr=0;
i++)//找出换出的基
{//找出检验数中最小的b记为minb,对应的基Xi记为minbi(下标),minr为行,从第0行开始计算
if(Q[i]<
minb)
minb=Q[i];
minbi=J[i][k];
minr=i;
t=R[k][minr][maxl];
R[k+1][minr][i]=R[k][minr][i]/t;
}
//------换基,计算新的单纯形表----------------
if(i==minr)
JJ[i][k+1]=maxl+1;
JJ[i][k+1]=JJ[i][k];
}
i++)//i是行
if(i!
=minr)
if(R[k][i][maxl]==0)
{
for(j=0;
{
R[k+1][i][j]=R[k][i][j];
}
}
else
t=R[k][i][maxl];
j++)//j是列
R[k+1][i][j]=R[k][i][j]-t*R[k+1][minr][j];
}
}
{
;
//分离出新的bb[3][k+1]----
bb[i][k+1]=R[k+1][i][l-1];
//--计算新的目标函数----
t=CC[k+1][maxl];
if(t==0)
for(i=0;
i++)
CC[k+2][i]=CC[k+1][i];
else
CC[k+2][i]=CC[k+1][i]-t*R[k+1][minr][i];
}
//------检验是否最优----如果最优的话s=0,否则s=1----
s=0;
if(CC[k+2][i]>
s=1;
//如果存在检验数大于0,不是最优,则m=1
}
}
printf("
printf("
改变Cj后的最终单纯形表为:
printf("
for(i=0;
{
printf("
CC[k+1][i]);
}
printf("
m=0;
for(i=0;
{
JJ[i][k]);
for(j=0;
R[k][i][j]);
m++;
if(m==6)
printf("
m=0;
//---------------------------------------------------------------------------------