修正单纯性法
代码如下：
舍去了输入转化的内容，主要包含算法关键步骤。
public class LPSimplexM {
private static final double inf = 1e9;
private int n; // 约束个数
private double[][] A; // 输入函数参数
private double[] b; // 约束值
private double[] c; // 目标函数系数
private double Z; // 目标值
private void InitF() { // 初始化 First
/* problem 1.
* max Z = 5*x1 + 4*x2; min Z = -5*x1 - 4*x2;
* x1 + 3*x2 <= 90; x1 + 3*x2 + x3 = 90;
* 2*x1 + x2 <= 80; => 2*x1 + x2 + x4 = 80;
* x1 + x2 <= 45; x1 + x2 + x5 = 45;
* xi >= 0
*/
/* problem 2.
* min Z = -7*x1 - 12*x2;
* 9*x1 + 4*x2 + x3 = 360;
* 4*x1 + 5*x2 +x4 = 200;
* 3*x1 + 10*x2 + x5 = 300;
* xi >= 0
*/
n = 3;
A = new double[n+1][n+1];
b = new double[n+1];
// c = new double[n<<1];
Z = inf;
// 约束初始条件
A[1][1] = 1; A[1][2] = 3;
A[2][1] = 2; A[2][2] = 1;
A[3][1] = 1; A[3][2] = 1;
// 条件值
// problem 1.
// b[1] = 90;
// b[2] = 80;
// b[3] = 45;
// problem 2.
b[1] = 360;
b[2] = 200;
b[3] = 300;
// for(int i = 1; i <= n; i++)System.out.println("b[" + i + "] = " + b[i]);
// 目标函数系数
// c[1] = -5; c[2] = -4;
}
int m;
private double[][] p;
private double[][] e, oe;
private double[][] E, oE;
private double[] X;
private boolean[] G;
private int[] S;
private void InitS() {
m = 2;
p = new double[n+1][n+m+1];
e = new double[n+1][n+1];
oe = new double[n+1][n+1];
E = new double[n+1][n+1];
oE = new double[n+1][n+1];
X = new double[n+1];
G = new boolean[n+m+1];
S = new int[n+1];
c = new double[n+m+1];
// problem 1.
// c[1] = -5; c[2] = -4; c[3] = 0; c[4] = 0; c[5] = 0;
// problem 2.
c[1] = -7; c[2] = -12; c[3] = 0; c[4] = 0; c[5] = 0;
// problem 1.
// p[1][1] = 1; p[1][2] = 3; p[1][3] = 1; p[1][4] = 0; p[1][5] = 0;
// p[2][1] = 2; p[2][2] = 1; p[2][3] = 0; p[2][4] = 1; p[2][5] = 0;
// p[3][1] = 1; p[3][2] = 1; p[3][3] = 0; p[3][4] = 0; p[3][5] = 1;
// problem 2.
p[1][1] = 9; p[1][2] = 4; p[1][3] = 1; p[1][4] = 0; p[1][5] = 0;
p[2][1] = 4; p[2][2] = 5; p[2][3] = 0; p[2][4] = 1; p[2][5] = 0;
p[3][1] = 3; p[3][2] = 10; p[3][3] = 0; p[3][4] = 0; p[3][5] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i == j)E[i][j] = oE[i][j] = 1;
else E[i][j] = oE[i][j] = 0;
for(int i = 1; i <= n; i++)
X[i] = b[i];
G[1] = false; G[2] = false; G[3] = true; G[4] = true; G[5] = true;
S[1] = 3; S[2] = 4; S[3] = 5;
}
public LPSimplexM() {
InitF();
InitS();
AlgorithmProcess();
solve();
}
private void AlgorithmProcess() {
double[] coE = new double[n+1]; // c * E^-1
double[] r = new double [n+m+1]; // c - c * E^-1 * p
double[] oEp = new double[n+1]; // E^-1 * p;
boolean flag = false;
while(true) {
// x = E^-1 * b
for(int i = 1; i <= n; i++){
X[i] = 0;
for(int j = 1; j <= n; j++)
X[i] += oE[i][j]*b[j];
}
// c * E^-1
for(int i = 1; i <= n; i++){
coE[i] = 0;
for(int j = 1; j <= n; j++)
coE[i] += c[S[j]]*oE[j][i];
}
// r = c - c * E^-1 * p => min r‘ id -> k
int k = -1;
flag = false;
for(int i = 1; i <= n+m; i++)if(!G[i]){
double ans = 0;
for(int j = 1; j <= n; j++)
ans += coE[j]*p[j][i];
r[i] = c[i] - ans;
if(!flag && r[i] < 0){
k = i;
flag = true;
}else if(flag && r[i] < r[k]){
k = i;
}
}
if(k == -1)return ; // solution output 1（X, S 为最优解）
// E^-1 * p; => min theta>0‘ id -> s
int s = -1;
flag = false;
for(int i = 1; i <= n; i++){
oEp[i] = 0;
for(int j = 1; j <= n; j++){
oEp[i] += oE[i][j]*p[j][k];
}
if(oEp[i] > 0){
if(!flag){
s = i;
flag = true;
}else if(flag && X[i]/oEp[i] < X[s]/oEp[s]){
s = i;
}
}
}
if(!flag)return ; // no solution 1（无允许解）
if(s == -1)return ; // no solution 2（该问题有无解集）
// p[s] = p[k], 形成新的矢量基 E
G[S[s]] = false; G[k] = true;
S[s] = k;
// System.out.println("k = " + k + "; s = " + s);
for(int i = 1; i <= n; i++){
p[i][k] = -1.0*oEp[i]/oEp[s];
if(i == s)
p[i][k] = 1/oEp[s];
}
for(int i = 1; i <= n; i++){
int id = S[i];
for(int j = 1; j <= n; j++){
if(i == s){
e[j][i] = p[j][k];
}else{
if(j == i){
e[j][i] = 1;
}else{
e[j][i] = 0;
}
}
}
}
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= n; j++){
// System.out.print(oE[i][j] + " ");
// }System.out.println();
// }System.out.println("{oE}");
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= n; j++){
// System.out.print(e[i][j] + " ");
// }System.out.println();
// }System.out.println("{e}");
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
oe[i][j] = 0;
for(int t = 1; t <= n; t++){
oe[i][j] += e[i][t]*oE[t][j];
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
oE[i][j] = oe[i][j];
//System.out.print(oE[i][j] + " ");
}//System.out.println();
}//System.out.println();
}
}
// 最优解输出
private void solve() {
Z = 0;
for(int i = 1; i <= n; i++){
int id = S[i];
Z += c[id]*X[i];
System.out.println(id + " : " + X[i] + " * " + -c[id]);
}
System.out.println("Z = " + -Z);
}
public static void main(String[] args) {
new LPSimplexM();
}
}如有问题，请网友指正。
希望网友的交流，共同进步。