文档介绍：单纯形法—大M法实验报告
目录
实验目的
使用目前熟悉的语言，实现所学的单纯形法之大M法，并正确运算测试结果。本组成员使用C语言实现。
单纯形法及大M法
单纯形法（Simplex Method）
单纯形法是解线性规划问题的一个重要方法。
其原理的基本框架为：
第一步：将LP线性规划变标准型，确定一个初始可行解（顶点）。
第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。
第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善—目标函数值增加，重复第二和第三步直到找到最优解。
用程序进行运算前，要将目标函数及约束方程变成标准形式。
对于非标准形式须作如下变换：
目标函数为极小值min z=CX时，转换为max z=-CX形式；
在约束方程中有 “≤”时，在加上一个松弛变量；
在约束方程中有 “≥”时，采用减去一个松弛变量，再加上一个人工变量；
在约束方程中有 “=”时，加上一个人工变量；
所有的人工变量，松弛变量的目标函数系数置为0。
对于标准形式的线性规划问题。用单纯形法计算步骤的框图
在程序运算过程中，采用单纯形表显示运算过程。
大M法
方法：在约束条件中，加入人工变量后，要求目标函数不受影响，目标函数中人工变量的系数取 –M（M为系统所能表示范围内的一个非常大的值本程序取），其运算过程同单纯形法。
理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。
数据结构及模块设计
程序中用到的数据结构：
#define M 20 //最大20个变量
#define N 40 //40个约束方程
#define Max //大M
double D[M][N];//系数矩阵
double C[M];//目标函数系数
double Cb[M];//基向量系数
double B[M];//约束常数
double Value[N];//检验数
int Xb[M];//基向量
double X0[M];//可行解
int op[M];//约束方程符号0---"<"、1---"="、2---">"
int m,n;//矩阵行数、列数
int begin_n;//初始变量数
int In_BaseX=-1;//进基变量
int in_n=-1;//进基列标示
int out_m=-1;//出基行标示
int Out_BaseX=-1;//出基变量
int best;//最优函数返回值
char name[30];//文件名
int ManX_num=0;//人工变量数目
int ManX_list[M];//人工变量存放数组
模块设计：
void read();//读取方程子函数
void print();//显示单纯表子函数
void init_change();//初始变换子函数
void compute_value();//计算检验数子函数
int best_Result();//判断是否得到最优解子函数
void in_base();//进基选子函数
void out_base();//出基选择子函数
void row_change();//行变换子函数
详细设计
文件格式定义
格式：
（行数/约束方程数：列数/变量数：）
m n
（约束矩阵：符号：0小于，1等于，2大于 B值）
D11 D12 D13 … Dn1 op1 b1
D21 D22 D23 … Dn2 op2 b2
….
Dm1 D2m Dm3 … Dnm opm bm
（最大值/最小值：1最大，2最小）
max/min
目标函数的变量系数：
C1 C2 C3 …. Cn
例：3 2
0 12000
0 4000
0 0 6000
1