修正单纯形法·优化算法实现·Java
修正单纯性法
代码如下:
舍去了输入转化的内容,主要包含算法关键步骤。
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(); } }如有问题,请网友指正。
希望网友的交流,共同进步。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。