//第三组 Java实现
import java.util.Scanner;
import java.util.regex.Pattern;
import javax.*;
public class 主函数 {
private int m; //约束条件的个数
private int n; //变量个数
private int m1; //<=的约束条件个数
private int m2; //=的约束条件个数
private int m3; //>=的约束条件个数
private int error; //判断是否是错误的
private int basic[];
private int nonbasic[];
private double a[][]; //约束条件的系数矩阵
public double minmax; //目标函数的最大值或最小值
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("请输入目标函数类型：1表示max;-1表示min:");
//容错处理稍后再做
double minmax= Integer.parseInt(sc.next());
System.out.println("请输入约束条件个数：");
int m=sc.nextInt();
System.out.println("请输入变量个数：");
int n=sc.nextInt();
int m1=0;
int m2=0;
int m3=m;
double a[][]=new double[m][n+1]; //矩阵
for(int i=0;i<m;i++){
System.out.println("请输入系数矩阵第"+(i+1)+"行：");
double b[]=new double[n+1];
String regex=",";
Pattern p=Pattern.compile(regex);
String r[]=p.split(sc.next());
for(int j=0;j<r.length;j++){
if(!((r[j].trim()).equals(""))){
b[j]=Double.parseDouble(r[j]);
a[i][j]=b[j];
}
}
}
System.out.println("系数矩阵为：");
for(int i=0;i<m;i++){
for(int j=0;j<n+1;j++){
System.out.print(a[i][j]+"\t");
}
System.out.println("");
}
double x[]=new double[n];
System.out.println("请输入目标函数系数：");
String regex=",";
Pattern p=Pattern.compile(regex);
String r[]=p.split(sc.next()); //目标函数系数
for(int j=0;j<r.length;j++){
if(!((r[j].trim()).equals(""))){
x[j]=Double.parseDouble(r[j]);
}
}
线性规划 线性规划 = new 线性规划(minmax,m,n,m1,m2,m3,a,x);
线性规划.solve();
}
}
public class 线性规划 {
private int m; //约束条件的个数
private int n; //变量个数
private int m1=0; //<=的约束条件个数
private int m2=0; //=的约束条件个数
private int m3; //>=的约束条件个数
private int error; //判断是否是错误的
private int basic[]; //基变量
private int nonbasic[]; //非基变量
private double a[][]; //约束条件的系数矩阵
private double minmax; //目标函数的最大值或最小值
public 线性规划(double minmax,int m,int n,int m1,int m2,int m3,double a[][],double x[]) //构造函数
{
double value;
this.error = 0;
this.minmax = minmax;
this.m = m;
this.n = n;
this.m1 = m1;
this.m2 = m2;
this.m3 = m3;
if(m != m1+m2+m3)
{
this.error = 1;
}
this.a = new double[m+2][]; //系数矩阵a
for(int i = 0; i < m+2; i++)
{
this.a[i] = new double[n+m+m3+1];
}
this.basic = new int[m+2]; //基变量矩阵
this.nonbasic = new int[n+m3+1]; //非基变量矩阵
for(int i = 0; i <= m+1; i++) //系数矩阵内数值全初始化为0
{
for(int j = 0; j <= n+m+m3; j++)
{
this.a[i][j] = 0.0;
}
}
for(int j = 0; j <= n+m3; j++)
{
nonbasic[j] = j;
}
for(int i = 1,j = n+m3+1; i <= m; i++,j++)
{
basic[i]=j;
}
for(int i = m-m3+1,j = n+1; i<= m; i++,j++)
{
this.a[i][j]=-1;
this.a[m+1][j]=-1;
}
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
value = a[i-1][j-1];
this.a[i][j]=value;
}
value = a[i-1][n];
if(value<0)
{
error = 1;
}
this.a[i][0]=value;
}
for(int j = 1; j <= n; j++) //价值系数即约束条件右端项
{
value = x[j - 1];
this.a[0][j] = value * minmax; //系统矩阵第一行为目标函数系数
}
for(int j = 1; j <= n; j++)
{
value = 0;
for(int i = m1+1; i <= m; i++)
value+=this.a[i][j];
this.a[m+1][j]=value;
}
}
public int enter(int objrow) //确定换入变量
{
int col = 0;
for(int j = 1; j <= this.n + this.m3; j++)
{
if(this.nonbasic[j] <= this.n + this.m1 + this.m3 && this.a[objrow][j] > 10e-8)
{
col=j;
break;
}
}
return col;
}
public int leave(int col) //确定换出变量
{
double temp=-1;
int row = 0;
for(int i = 1; i <= this.m; i++)
{
double val = this.a[i][col];
if( val > 10e-8)
{
val = this.a[i][0]/val;
if(val < temp || temp == -1)
{
row = i;
temp = val;
}
}
}
return row;
}
public void swapbasic(int row,int col) //换基变量和非基变量
{
int temp = this.basic[row];
this.basic[row] = this.nonbasic[col];
this.nonbasic[col] = temp;
}
public void pivot(int row,int col) //单纯型迭代
{
for(int j = 0;j <= this.n + this.m3; j++)
{
if(j != col)
{
this.a[row][j] = this.a[row][j] / this.a[row][col]; //主元所在的行做相应的变换
}
}
this.a[row][col] = 1.0 / this.a[row][col]; //主元化为1
for(int i = 0; i <= this.m + 1; i++)
{
if(i != row)
{
for(int j = 0; j <= this.n + this.m3; j++)
{
if(j != col)
{
this.a[i][j] = this.a[i][j] - this.a[i][col] * this.a[row][j]; //其他行做相应的变换
if(Math.abs(this.a[i][j]) < 10e-8)
this.a[i][j]=0; //主元所在的列的其他行元素化为0
}
}
this.a[i][col] = -this.a[i][col] * this.a[row][col];
}
}
swapbasic(row,col); //基变量和非基变量作相应的变化
System.out.println("系数矩阵变为：");
System.out.print("\n");
for(int i=0;i<=m;i++)
{
if(i==0)
{
System.out.print("ZB"+"\t");
}
else
{
System.out.print("X("+basic[i]+")"+"\t");
}
System.out.print("\t");
for(int j=0;j<=n+1;j++){
System.out.print(a[i][j]+"\t");
}
System.out.println("");
}
}
public int simplex(int objrow) //单纯型迭代
{
int row = 0;
while(true)
{
int col = enter(objrow);
if(col > 0)
{
row=leave(col);
}
else
{
return 0;
}
if(row > 0)
{
pivot(row,col);
}
else
{
return 2;
}
}
}
public int phase1() //第一阶段
{
this.error = simplex(this.m + 1);
if(this.error > 0)
{
return this.error;
}
for(int i = 1; i <= this.m; i++)
{
if(this.basic[i] > this.n + this.m1 + this.m3)
{
if(this.a[i][0] > 10e-8)
{
return 3;
}
for(int j = 1; j <= this.n; j++)
{
if(Math.abs(this.a[i][j]) >= 10e-8)
{
pivot(i,j);
break;
}
}
}
}
return 0;
}
public int phase2() //第二阶段
{
return simplex(0);
}
public int compute()
{
if(this.error > 0)
return this.error;
if(this.m != this.m1)
{
this.error = phase1();
if(this.error > 0)
return this.error;
}
return phase2();
}
public void solve() //入口，首先进行的判断解的情况
{
error=compute();
switch(error)
{
case 0:
output();
break;
case 1:
System.out.println("输入数据错误!");
break;
case 2:
System.out.println("无界解!");
break;
case 3:
System.out.println("无可行解!");
break;
default:
break;
}
}
public void output() //输出最后的结果
{
int basicp[] = new int[n+1];
for(int i = 0; i <= n; i++)
{
basicp[i] = 0;
}
for(int i = 1; i <= m; i++)
{
if(basic[i] >= 1 && basic[i] <= n)
{
basicp[basic[i]] = i;
}
}
for(int i = 1; i <= n; i++)
{
System.out.print("x"+i+"=");
if(basicp[i] != 0)
{
System.out.print(a[basicp[i]][0]);
}
else
{
System.out.print("0");
}
System.out.println();
}
System.out.println("最优值:"+-minmax*a[0][0]);
}
}
