使用C语言实现单纯形法求解线性规划问题

上机实验报告

一、实验目的和要求

1、目的：

●掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。

●了解算法→程序实现的过程和方法。

2、要求：

●使用熟悉的编程语言编制单纯形算法的程序。

●独立编程，完成实验，撰写实验报告并总结。

二、实验内容和结果

1、单纯形算法的步骤及程序流程图。

（1）、算法步骤

（2）、程序图

各段代码功能描述：

（1）、定义程序中使用的变量

#include

#include

#define m 3 /*定义约束条件方程组的个数*/

#define n 5 /*定义未知量的个数*/

float M=1000000.0;

float A[m][n]; /*用于记录方程组的数目和系数;*/

float C[n]; /*用于存储目标函数中各个变量的系数*/

float b[m]; /*用于存储常约束条件中的常数*/

float CB[m]; /*用于存储基变量的系数*/

float seta[m]; /*存放出基与入基的变化情况*/

float delta[n]; /*存储检验数矩阵*/

float x[n]; /*存储决策变量*/

int num[m]; /*用于存放出基与进基变量的情况*/

float ZB=0; /*记录目标函数值*/

（2）、定义程序中使用的函数

void input();

void print();

int danchunxing1();

int danchunxing2(int a);

void danchunxing3(int a,int b);

(3)、确定入基变量，对于所有校验数均小于等于0，则当前解为最优解。

int danchunxing1()

{

int i,k=0;

int flag=0;

float max=0;

for(i=0;i

if(delta[i]<=0)

flag=1;

else {flag=0;break;}

if(flag==1)

return -1;

for(i=0;i

if(max

{ max =delta[i];k=i;}

}

return k;

}

(4)、确定出基变量，如果某个大于0的校验数，对应的列向量中所有元素小于等于0，则线性规划问题无解。

int danchunxing2(int a)

{

int i,k,j;

int flag=0;

float min;

k=a;

for(i=0;i

if(A[i][k]<=0)

flag=1;

else {flag=0;break;}

if(flag==1)

{printf("\n该线性规划无最优解!\n"); return -1;} for(i=0;i

{

if(A[i][k]>0)

seta[i]=b[i]/A[i][k];

else seta[i]=M;

}

min=M;

for(i=0;i

{

if(min>=seta[i])

{min=seta[i];j=i;}

}

num[j]=k+1;

CB[j]=C[k];

return j;

}

(5)、迭代运算，计算新的单纯形表。

void danchunxing3(int p,int q)

{

int i,j,c,l;

float temp1,temp2,temp3;

c=p;/*行号*/

l=q;/*列号*/

temp1=A[c][l];

b[c]=b[c]/temp1;

for(j=0;j

A[c][j]=A[c][j]/temp1;

for(i=0;i

{

if(i!=c)

if(A[i][l]!=0)

{

temp2=A[i][l];

b[i]=b[i]-b[c]*temp2;

for(j=0;j

A[i][j]=A[i][j]-A[c][j]*temp2;

}

}

temp3=delta[l];

for(i=0;i

delta[i]=delta[i]-A[c][i]*temp3;

}

(6)、输入函数，输入方程组的系数矩阵、初始基变量的数字代码、方程组右边的值矩阵、目标函数各个变量的系数所构成的系数阵。

void print()

{

int i,j=0;

printf("\n--------------------------------------------------------------------------\n");

for(i=0;i

{

printf("%8.2f\tX(%d) %8.2f ",CB[i],num[i],b[i]);

for(j=0;j

printf("%8.2f ",A[i][j]);

printf("\n");

}

printf("\n--------------------------------------------------------------------------\n");

printf("\t\t\t");

for(i=0;i

printf(" %8.2f",delta[i]);

printf("\n--------------------------------------------------------------------------\n");

}

void input()

{

int i,j; /*循环变量*/

int k;

printf("请输入方程组的系数矩阵A(%d行%d列):\n",m,n);

for(i=0;i

for(j=0;j

scanf("%f",&A[i][j]);

printf("\n请输入初始基变量的数字代码num矩阵:\n");

for(i=0;i

scanf("%d",&num[i]);

printf("\n请输入方程组右边的值矩阵b:\n");

for(i=0;i

scanf("%f",&b[i]);

printf("\n请输入目标函数各个变量的系数所构成的系数阵C:\n");

for(i=0;i

scanf("%f",&C[i]);

for(i=0;i

delta[i]=C[i];

for(i=0;i

{

k=num[i]-1;

CB[i]=C[k];

}}

(7)、主函数，调用前面定义的函数。