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

上 机 实 验 报 告
班级：自动化班
专业/方向：自动化
姓名：
实 验 成 绩
(10分制)

学号：

上机实验名称：使用C语言实现单纯形法求解线性规划问题
上机时间：2015年5月20日
上机地点：信自234

一、实验目的和要求
1、目的：
l 掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。
l 了解算法à程序实现的过程和方法。
2、要求：
l 使用熟悉的编程语言编制单纯形算法的程序。
l 独立编程，完成实验，撰写实验报告并总结。

二、实验内容和结果
1、单纯形算法的步骤及程序流程图。
（1）、算法步骤
（1）将线性规划化为标准形。
（2）用最快的方法确定一个初始基本可行解X（0）。当s·t均为“≤”形式时，以松驰变量做初始基本变量最快。
（3）求X（0）中非基本变量xj的检验数σj。若，则停止运算，X（0）=X*（表示最优解），否则转下一步。
（4）①由确定xk进基；
②由确定xl出基，其中alk称为主元素；
③利用初等变换将alk化为1，并利用alk将同列中其它元素化为0，得新解X（1）。
（5）返回（3），直至求得最优解为止。

（2）、程序图

找出初始基可行解列出初始单纯形表
计算校验数
所有δj<=0?
对于某个δj>0，是否存在Pj<=0
确定为入基变量
确定出基变量
计算新的单纯形表
已得最优解，结束
无最优解，结束

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;ik;
}
(4)、确定出基变量，如果某个大于0的校验数，对应的列向量中所有元素小于等于0，则线性规划问题无解。
int danchunxing2(int a)
{
int i,k,j;
int flag=0;
float min;
k=a;
for(i=0;i0)
seta[i]=b[i]/A[i][k];
else seta[i]=M;
}
min=M;
for(i=0;i=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;jA[c][i]*temp3;
}
(6)、输入函数，输入方程组的系数矩阵、初始基变量的数字代码、方程组右边的值矩阵、目标函数各个变量的系数所构成的系数阵。
void print()
{
int i,j=0;
printf("\n--------------------------------------------------------------------------\n");
for(i=0;irintf("%8.2f ",A[i][j]);
printf("\n");
}
printf("\n--------------------------------------------------------------------------\n");
printf("\t\t\t");
for(i=0;id input()
{
int i,j; /*循环变量*/
int k;
printf("请输入方程组的系数矩阵A(%d行%d列):\n",m,n);
for(i=0;i函数各个变量的系数所构成的系数阵C:\n");
for(i=0;i\n");
printf(" \tCB\tXB\tb\t");
for(i=0;i
x[temp]=b[j];
}
for(i=0;i的系数矩阵A(3行5列)
（2）、输入初始基变量的数字代码num矩阵
（3）、输入方程组右边的值矩阵b
（4）、输入目标函数各个变量的系数所构成的系数阵C
输出：
（1）、输出是否为最优解
（2）、输出最优解为多少
3、使用所编程序求解如下LP问题并给出结果。
请输入方程组的系数矩阵A(3行5列):
2 2 1 0 0
4 0 0 1 0
0 5 0 0 1

请输入初始基变量的数字代码num矩阵:
3 4 5

请输入方程组右边的值矩阵b:
12 16 15

请输入目标函数各个变量的系数所构成的系数阵C:
2 3 0 0 0

--------------------------------------------------------------------------
CB XB b X(1) X(2) X(3) X(4) X(5)

------------------------------------------
0.00 X(3) 12.00 2.00 2.00 1.00 0.00 0.00
0.00 X(4) 16.00 4.00 0.00 0.00 1.00 0.00
0.00 X(5) 15.00 0.00 5.00 0.00 0.00 1.00

------------------------------------
2.00 3.00 0.00 0.00 0.00
--------------------------------------------------------------------------
p=2,q=1
--------------------------------------------------------------------------
0.00 X(3) 6.00 2.00 0.00 1.00 0.00 -0.40
0.00 X(4) 16.00 4.00 0.00 0.00 1.00 0.00
3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20
2.00 0.00 0.00 0.00 -0.60
-----------------------------
p=0,q=0
--------------------------------------------------------------------------
2.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20
0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80
3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20

--------------------------------------------------------------------------
0.00 0.00 -1.00 0.00 -0.20
--------------------------------------------------------------------------

P26 例5 程序运行结果
--------------------------------------------------------------------------
0.00 0.00 -1.00 0.00 -0.20
--------------------------------------------------------------------------

所得解已经是最优解!

最优解为:
x1=3.00 x2=3.00 x3=0.00 x4=4.00 x5=0.00 ZB=15.00

输出：
请输入方程组的系数矩阵A(3行5列):
1 0 0.5 0 -0.2
0 0 -2 1 0.8
0 1 0 0 0.2

请输入初始基变量的数字代码num矩阵:
3 4 5

请输入方程组右边的值矩阵b:
3 4 3

请输入目标函数各个变量的系数所构成的系数阵C:
3 3 0 0 0

---------------

CB XB b X(1) X(2) X(3) X(4) X(5)
0.00 X(3) 3.00 1.00 0.00 0.50 0.00 -0.20
0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80
0.00 X(5) 3.00 0.00 1.00 0.00 0.00 0.20

--------------------------------------------------------------------------
3.00 3.00 0.00 0.00 0.00
--------------------------------------------------------------------------

p=0,q=0

--------------------------------------------------------------------------
3.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20
0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80

----------------------------------------------------------------
0.00 3.00 -1.50 0.00 0.60
--------------------------------------------------------------------------

p=2,q=1
--------------------------------------------------------------------------
3.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20
0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80
3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20

P33 例7程序运行结果
所得解已经是最优解!

最优解为:
x1=4.00 x2=2.00 x3=0.00 x4=0.00 x5=5.00 ZB=18.00

输出：3.00 X(2) 300 0.00 1.00 0.00 0.00 0.20

--------------------------------------------------------------------------
0.00 0.00 -1.50 0.00 0.00
--------------------------------------------------------------------------

p=1,q=4
--------------
3.00 X(1) 4.00 1.00 0.00 -0.00 0.25 0.00
0.00 X(5) 5.00 0.00 0.00 -2.50 1.25 1.00
3.00 X(2) 2.00 0.00 1.00 0.50 -0.25 0.00

--------
0.00 0.00 -1.50 -0.00 0.00
--------------------------------------------------------------------------

请输入方程组的系数矩阵A(3行5列):
4 0 1 0 0
0 0 0 0 0
0 0 0 0 0

请输入初始基变量的数字代码num矩阵:
3 4 5

请输入方程组右边的值矩阵b:
16 0 0

请输入目标函数各个变量的系数所构成的系数阵C:
2 3 0 0 0

--------------------------------------------------------------------------
CB XB b X(1) X(2) X(3) X(4) X(5)

P34例8程序运行结果
所得解已经是最优解!

最优解为:
x1=0.00 x2=0.00 x3=16.00 x4=0.00 x5=0.00 ZB=-1.#

0.00 X(3) 16.00 4.00 0.00 1.00 0.00 0.00
0.00 X(4) 0.00 0.00 0.00 0.00 0.00 0.00
0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00

--------------------------------------------------------------------------
2.00 3.00 0.00 0.00 0.00
--------------------------------------------------------------------------

该线性规划无最优解!

p=-1,q1
--------------------------------------------------------------------------
0.00 X(3) 16.00 4.00 0.00 1.00 0.00 0.00
0.00 X(4) 0.00 0.00 0.00 0.00 0.00 0.00
0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00

--------------------------------------------------------------------------
-1.#J -1.#J -1.#J -1.#J -1.#J
--------------------------------------------------------------------------

输出：
请输入方程组的系数矩阵A(3行5列):
2 2 1 0 0
1 2 0 -1 1
0 0 0 0 0

请输入初始基变量的数字代码num矩阵:
3 4 5
请输入方程组右边的值矩阵b:
12 14 0

请输入目标函数各个变量的系数所构成的系数阵C:

P35 例9 程序运行结果

所得解已经是最优解!

最优解为:
x1=0.00 x2=6.00 x3=0.00 x4=2.00 x5=0.00 ZB=18.00

2 3 0 0 -M

CB XB b X(1) X(2) X(3) X(4) X(5)

--------------------------------------------------------------------------
0.00 X(3) 12.00 2.00 2.00 1.00 0.00 0.00

0.00 X(4) 14.00 1.00 2.00 0.00 -1.00 1.00
0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00

--------------------------------------------------------------------------
2.00 3.00 0.00 0.00 0.00
--------------------------------------------------------------------------

p=0,q=1
--------------------------------------------------------------------------
3.00 X(2) 6.00 1.00 1.00 0.50 0.00 0.00
0.00 X(4) 2.00 -1.00 0.00 -1.00 -1.00 1.00
0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00

--------------------------------------------------------------------------
-1.00 0.00 -1.50 0.00 0.00
--------------------------------------------------------------------------

输出：
三、实验总结
通过使用C语言实现单纯形法求解线性规划问题和用matlab优化工具箱求解LP问题，使得问题的求解更加简单和容易，而且也更加快速的求解问题，我们也对这两种方法有了更深刻的了解。

17 / 17