单纯性表

发表于 分类于 阅读次数： 本文字数： 8.2k 阅读时长 ≈ 7 分钟

用来求解线性规划问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package cn.sgnxotsmicf.Demo;
import java.text.DecimalFormat;
import java.util.Scanner;

public class Simplex_Method_Data {
    public static double[] c;  // 目标函数中变量xj的价值系数cj
    public static double[] pi; // 检验系数π
    public static double[] theta; // 入基时对应的θ
    public static double[] b0; // 基本可行解中基变量的值
    public static int m; // 秩
    public static int n; // 变量个数
    public static int[] basicVar; //用来存储基变量的索引
    public static double var;
    public static int[] MData;
    public static String YN;
    public static double[][] centreMatrix_Creat(Scanner sc){
        System.out.println("请输入约束矩阵A的秩:");
        m = sc.nextInt();
        System.out.println("请输入约束矩阵变量个数:"); // 同时也确定了基变量和非基变量的个数
        n = sc.nextInt();
        double[][]A = new double[m][n];
         inputA(A,sc);
         return A;
    }

    /**
     * 用于初始化A
     * @param A 为初始约束条件系数矩阵
     */
    public static void inputA(double[][]A,Scanner sc) {
        for (int i = 0; i < m; i++) {
            System.out.println("请输入第"+(i+1)+"行元素:");
            for (int j = 0; j < n; j++) {
                A[i][j] = sc.nextDouble();
            }
        }
    }

    /**
     * 打印单纯性表
     */
    public static void printMatrix(double[][] E){
        DecimalFormat sc = new DecimalFormat("0.00");
        for (int i = 0; i < m; i++) {
            System.out.print(sc.format(b0[i])+",");
            for (int j = 0; j < n; j++) {
                System.out.print(sc.format(E[i][j])+(j==n-1?"":","));
            }
            System.out.println();
        }
        System.out.print(var+",");
        for (int j = 0; j < n; j++) {
            System.out.print(sc.format(pi[j])+(j==n-1?"":","));
        }
        System.out.println();
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
package cn.sgnxotsmicf.Demo;

import java.text.DecimalFormat;
import java.time.LocalDateTime;
import java.time.temporal.ChronoUnit;
import java.util.Arrays;
import java.util.Scanner;

public class Simplex_Method extends Simplex_Method_Data{
    static {
        System.out.println("==================单纯形法求解线性规划=================");
    }

    /**
     * 主方法
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double[][] A = centreMatrix_Creat(sc);
        Search_XB(sc);
        Init(sc,A);
        LocalDateTime startTime = LocalDateTime.now();
        LogicLoopJudge(A);
        LocalDateTime endTime = LocalDateTime.now();
        IterationTime(startTime,endTime);
    }

    /**
     *用于计算迭代时间
     * @param startTime 迭代前时间
     * @param endTime  迭代后时间
     *
     */
    private static void IterationTime(LocalDateTime startTime, LocalDateTime endTime) {
        System.out.println("迭代时间大约为:"+ ChronoUnit.MILLIS.between(startTime, endTime)+"毫秒");
    }

    private static void LogicLoopJudge(double[][] A) {
        int number = 0;
        while (true){
            int tempt = 0;
            int negativeIndex = 0;
            for (int i = 0; i < pi.length; i++) {
                if (pi[i]<=0){
                    tempt++;
                }
                else if (pi[i]>0) {
                    for (int j = 0;j < m;j++){
                        if (A[j][i]<=0){
                            negativeIndex++;
                        }
                    }
                    if (negativeIndex ==m){
                        System.out.println("此线性规划问题无最优解！");
                        return;
                    }
                }
            }
            if (tempt == n){
                printResult(A,number);
                break;
            }
            // 开始操作；
            System.out.println("=================开始第"+(number+1)+"次迭代================");
            int index = IntoBaseVar_Judge();//入基索引
            UpDataTheta(A,index);
            int index2 = OutOfBaseVar_Judge(index);//出基索引
            RotationTransformation(A,index,index2);
            number++;
        }
    }

    /**
     *用于A的旋转变化，更新A
     * @param index 入基变量
     * @param index2 出基变量
     */
    private static void RotationTransformation(double[][] A,int index,int index2) {
        if (A[index2][index] != 1) {
            double positiveFactor = A[index2][index];
            //A[index2][index] = 1;
            for (int j = 0; j < n; j++) {
                A[index2][j] /= positiveFactor; //初等行变化
            }
            b0[index2] /= positiveFactor;
        }
        RotatingCenter(A,index,index2);
    }

    private static void RotatingCenter(double[][] A, int index, int index2) {
        for (int i = 0; i < m; i++) {
            if (A[i][index]!=0 && i!=index2){
                double factor = -A[index2][index]*A[i][index];
                double b0_factor = factor*b0[index2];
                b0[i] += b0_factor;
                for (int j = 0; j < n; j++) {
                    double A_factor = A[index2][j]*factor;
                    A[i][j] += A_factor;
                }
            }
        }
        double factor = -A[index2][index]*pi[index];
        for (int j = 0; j < n; j++) {
            double pi_factor = factor*A[index2][j];
            pi[j] += pi_factor;
        }
    }

    private static void printResult(double[][] A,int number) {
        for (int i = 0; i < m; i++) {
           var += c[basicVar[i]]*b0[i];
        }
        System.out.println("======================循环结束======================");
        System.out.println("最优值为:"+var);
        System.out.println("最优解为:");
        boolean logic = OptimalSolution();
        if (!logic){
            return;
        }
        System.out.println("基向量为:");
        for (int j : basicVar) {
            System.out.print("x" + (j + 1)+"\t");
        }
        System.out.println();
        System.out.println("迭代次数:"+number);
        System.out.println("最后一步单纯形表为:");
        printMatrix(A);
    }

    private static boolean OptimalSolution() {
        DecimalFormat sc = new DecimalFormat("0.00");
        String[] OptimalSData = new String[n];
        for (int i = 0; i < basicVar.length; i++) {
            OptimalSData[basicVar[i]] = sc.format(b0[i]);
        }
        for (int i = 0; i < OptimalSData.length; i++) {
            if (OptimalSData[i] == null){
                OptimalSData[i] = "0.00";
            }
        }
        System.out.println(Arrays.toString(OptimalSData));
        //0.25 0 0 1 0 -0.25   -2 0 -1 0 1 -3    1 1 0 0 0 1   1.5 6 10   2 3 0 0 10000 10000
        if (YN.equals("yes")) {
            for (int mDatum : MData) {
                for (int j = 0; j < m; j++) {
                    if (mDatum == basicVar[j] && b0[j] != 0) {
                        System.out.println("由于最优解中存在正的人工变量，则原问题是不可行的");
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     *
     * @param index 为入基索引
     * @return 返回出基索引
     * 使用的是Dantzig出基规则
     */
    private static int OutOfBaseVar_Judge(int index) {
        int index2 = 0;
        for (int i = 1; i < m; i++) {
            if (theta[index2]>theta[i]){
                index2 = i;
            }
        }
        System.out.println("出基变量为:x"+((basicVar[index2]+1)));
        basicVar[index2] = index;
        return index2;
    }

    /**
     *
     * @return 返回的是入基索引
     * 使用的是Dantzig入基规则
     */
    private static int IntoBaseVar_Judge() {
        int index = 0;
        for (int i = 1; i < n; i++) {
            if (pi[index]<pi[i]){
                index = i;
            }
        }
        System.out.println("入基变量为:x"+(index+1));
        return index;
    }

    /**
     * 用于更新θ
     * @param index 入基变量
     */
    private static void UpDataTheta(double[][] A,int index) {
            theta = new double[m];
        for (int i = 0; i < m; i++) {
            if (A[i][index]<=0){
                theta[i] = 1000;
            }else {
            theta[i] = b0[i]/A[i][index];
            }
        }
    }

    /**
     * 搜索单位矩阵
     */
    private static void Search_XB(Scanner sc) {
        basicVar = new int[m];
        System.out.println("请输入单位矩阵所对应的"+m+"个初始基变量的下标:");
        for (int i = 0; i < m; i++) {
            int tempt = sc.nextInt();
            basicVar[i] = (tempt-1);
        }
        System.out.println("基变量为:");
        for (int j : basicVar) {
            System.out.print("x" + (j + 1) + " ");
        }
        System.out.println();
    }

    /**
     * 数据初始化
     */
    private static void Init(Scanner sc,double[][] A) {
        int MJudge = TheBigMMethod(sc);
        // 初始化基变量的值
        b0 = new double[m];
        if (MJudge == 1){
            System.out.println("请输入人工变量的个数:");
            int M = sc.nextInt();
             MData= new int[M];
            for (int i = 0; i < M; i++) {
                System.out.println("请输入第"+(i+1)+"个人工变量下标:");
                int tempt = sc.nextInt();
                MData[i] = (tempt-1); //人工变量索引
            }
        }
        System.out.println("请输入基本可行解中基变量的初始值:"); //等于B^-1*b ---基于初始单位阵I
        for (int i = 0; i < m; i++) {
            b0[i] = sc.nextDouble();
        }
        // 初始化 价值系数c
        c = new double[n];
        System.out.println("请输入目标函数中变量xj的价值系数cj:");
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextDouble();
        }

        // 初始检验数
        initPi(A);
    }

    /**
     * 大M法判断
     * @return 返回判断逻辑
     */
    private static int TheBigMMethod(Scanner sc) {
        System.out.println("是否有人工变量？(yes/no)");
        String MJudge = sc.next();
        YN = MJudge;
        if (MJudge.equals("yes")){
            System.out.println("==================下面进行大M法求解线性最优化问题=============");
            return 1;
        }
        return 0;
    }

    /**
     *初始化检验数π
     */
    private static void initPi(double[][] A) {
        pi = new double[n];
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    pi[i] += c[basicVar[j]]*A[j][i];
                }
            pi[i] -= c[i];
        }
    }
}