图1
图2
图1是线性规划问题转化后的标准形式，图2是对图1的另一种形式(即单纯形表)，具体编程按图2格式编写。
具体步骤如下：
第一步：作单纯形表.
(1)将原线性规划问题化为标准形式；
(2) 找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；
(3) 目标函数非基化；
(4) 作初始单纯形表.
简单讲就是将一个线性规划问题转换成图2的格式！
第二步：最优解的判定.
(1)
若所有检验数都是非正数，即在图2里面可以看到Z=Z0+rTXN
,这里rT 向量里面系数都是非正数的话，那么此时线性规划问题已取得最优解.
(2)
若存在某个检验数是正数并且其系数都为非负数的话无最优解。例如：在Z=Z0+rTXN
中xi的系数为正并且在图2中QXN里对应于xi的系数都为非负数，则些线性规划问题无最优解.
如果以上两条都不满足，则进行下一步.
第三步：换基迭代.
(1)找到最大正检验数(在rT中)，设为u并确定u 所在列的非基变量
xu为进基变量.
(2)对最大正检验数u所在列实施最小比值法，确定出主元.主元是最大正检验数 u所在列，用常数项
pi与进基变量xu 所对应的列向量中负分量的比值最小者；
下面两张图是解释为什么这么做的！
(3)换基：用进基变量 xu替换出基变量xv
,从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基；
(4)更新：更新其它存在xu的行，将其用非基本变量表示。因此Q，p, Z0,
rT相应更新。
(5)矩阵重新排列保证像x1,x3,x4这样有序排列的，而不是像x3,x4,x1
从而得到新的单纯形表；
(5)回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.
具体题目：
Question 1 Pivoting.
Write, in a programming language of your choice available in the
Faculty Linux Labs (but not in an LP solver) code that given a
simplex tableau and indices of variables to leave and enter the
basis, performs the corresponding pivot.
Input format
Input is whitespace delimited integers
u is the entering column, v is the leaving column.
m is the number of rows, n is the number of columns of the A
matrix in equational form.
B1 to Bm are the indices of the
basic columns.
Output format
Same as input format, without the first line specifying leaving
and entering variables.
Question 2 Ratio Testing.
Write a function or method that given a simplex tableau, chooses
entering and leaving variables, or reports the tableau as
infeasible or unbounded.
Input format
Same as input format for question 1, without the first line
specifying leaving and entering columns
Output format
Same as input format for question 1, unless the tableau is
optimal or unbounded. In this case print the single word "OPTIMAL"
or "UNBOUNDED" on a line by itself.
Question 3 Integration.
Write a main loop that integrates your code from the first two
questions and solves a linear program. Your code may assume that
the initial tableau is feasible.
Input format
Same as input format for question 1, without the first line
specifying leaving and entering variables.
Output format
Same as input format (although typically not the same
tableau!).
问题3代码如下：
#include
#include
double *p;
double **q;
double **A;
int *B;
double *R;
double *r;
double z;
int cmp(const void*a,const void*b)
{
return *(int *)a-*(int *)b;
}
int match(int t)
{ int k=1;
while(B[k]!=0)
{
if(t==B[k])
return 1;
k++;
}
return 0;
}
void transform(int m,int n)
{ int i,j,f;
for(i=1;i<=m;i++)
{ f=1;
for(j=1;j<=n;j++)
{
if(match(j)==1)
A[i][j]=0;
else
A[i][j]=q[i][f++];
}
}//put all the non-basic data into A[][];
f=1;
for(j=1;j<=n;j++)
{
if(match(j)==1)
R[j]=0;
else
R[j]=r[f++];
}//put all the non-basic data into R;
}
void pivot(int a,int b,int row,int col)//a is the entering column,b
is the leaving column
{
int k=1;int i,j;
while(B[k]!=0)
{
if(B[k]==b)
break;
k++;
};//get k as the row of the leaving
variable
B[k]=a;//a is the enter column;
for(j=1;j<=col;j++)
{
if(j==b)
A[k][j]=1/A[k][a];//A[k][a] is the coefficient of the entering
variable in this row
else
if(j!=a)
A[k][j]=-A[k][j]/A[k][a];
}
p[k]=-p[k]/A[k][a];//change
the p[k] after a enter the basis
z+=R[a]*p[k];//update z
for(j=1;j<=col;j++)
{
if(match(j)==0)
R[j]+=R[a]*A[k][j];
}
//update r
R[a]=0;
A[k][a]=0;
for( i=1;i<=row;i++)
{
if(i!=k)
if(A[i][a]!=0)
{
for(j=1;j<=col;j++)
{ if(match(j)==0)
A[i][j]+=A[i][a]*A[k][j];
}
p[i]+=A[i][a]*p[k]; A[i][a]=0;
}
}
}
void output(int u,int v,int row,int col)
{ int i,j;
printf("%d %d\n",row,col);
for(i=1;i<=row;i++)
printf("%d ",B[i]);
printf("\n");
for(i=1;i<=row;i++)
{ printf("%.0lf ",p[i]);
for(j=1;j<=col;j++)
{
if(match(j)==0)
printf("%.0lf ",A[i][j]);
}
printf("\n");
}
printf("%.0lf ",z);
for(j=1;j<=col;j++)
{
if(match(j)==0)
printf("%.0lf ",R[j]);
}
printf("\n"); }
int check_Opt(int m,int n)
{
int j;
for(j=1;j<=n;j++)
if(R[j]>0)
return 0;
return 1;
}
int check_Unbounded(int m,int n, int u)
{
int i;
for(i=1;i<=m;i++)
{
if(A[i][u]<0)
return 0;
}
return
1;
}
int decide_enter(int m,int n)
{ int max=1,j;
for(j=2;j<=n;j++)
if(R[j]>R[max])
max=j;
return max;
}
int decide_leave(int m,int n,int u)
{ int i=1,t,min;
while(i!=m)
{
if(A[i][u]<0)
break;
i++;
}
min=i;
for(t=i+1;t<=m;t++)
{
if((A[t][u]<0)&&(-p[t]/A[t][u]
min=t;
}
return
min;
}
int find(m,n,u)
{int i;
for(i=1;i<=m;i++)
if(B[i]==u)
return i;
}
void adjust(int leave_row,int correct_row,int n)
{ double temp;int i,j,t;
if(leave_row>correct_row)
{
t=leave_row-correct_row;
for(i=1;i<=t;i++)
{ for(j=1;j<=n;j++)
{
temp=A[leave_row][j];
A[leave_row][j]=A[leave_row-1][j];
A[leave_row-1][j]=temp;
}
temp=p[leave_row];
p[leave_row]=p[leave_row-1];
p[leave_row-1]=temp;
leave_row-=1;