1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.math.optimization.linear;
19
20 import org.apache.commons.math.optimization.OptimizationException;
21 import org.apache.commons.math.optimization.RealPointValuePair;
22 import org.apache.commons.math.util.MathUtils;
23
24
25
26
27
28
29
30 public class SimplexSolver extends AbstractLinearOptimizer {
31
32
33 private static final double DEFAULT_EPSILON = 1.0e-6;
34
35
36 protected final double epsilon;
37
38
39
40
41 public SimplexSolver() {
42 this(DEFAULT_EPSILON);
43 }
44
45
46
47
48
49 public SimplexSolver(final double epsilon) {
50 this.epsilon = epsilon;
51 }
52
53
54
55
56
57
58 private Integer getPivotColumn(SimplexTableau tableau) {
59 double minValue = 0;
60 Integer minPos = null;
61 for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
62 if (MathUtils.compareTo(tableau.getEntry(0, i), minValue, epsilon) < 0) {
63 minValue = tableau.getEntry(0, i);
64 minPos = i;
65 }
66 }
67 return minPos;
68 }
69
70
71
72
73
74
75
76 private Integer getPivotRow(final int col, final SimplexTableau tableau) {
77 double minRatio = Double.MAX_VALUE;
78 Integer minRatioPos = null;
79 for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getHeight(); i++) {
80 double rhs = tableau.getEntry(i, tableau.getWidth() - 1);
81 if (MathUtils.compareTo(tableau.getEntry(i, col), 0, epsilon) >= 0) {
82 double ratio = rhs / tableau.getEntry(i, col);
83 if (ratio < minRatio) {
84 minRatio = ratio;
85 minRatioPos = i;
86 }
87 }
88 }
89 return minRatioPos;
90 }
91
92
93
94
95
96
97
98
99 protected void doIteration(final SimplexTableau tableau)
100 throws OptimizationException {
101
102 incrementIterationsCounter();
103
104 Integer pivotCol = getPivotColumn(tableau);
105 Integer pivotRow = getPivotRow(pivotCol, tableau);
106 if (pivotRow == null) {
107 throw new UnboundedSolutionException();
108 }
109
110
111 double pivotVal = tableau.getEntry(pivotRow, pivotCol);
112 tableau.divideRow(pivotRow, pivotVal);
113
114
115 for (int i = 0; i < tableau.getHeight(); i++) {
116 if (i != pivotRow) {
117 double multiplier = tableau.getEntry(i, pivotCol);
118 tableau.subtractRow(i, pivotRow, multiplier);
119 }
120 }
121 }
122
123
124
125
126
127
128 private boolean isPhase1Solved(final SimplexTableau tableau) {
129 if (tableau.getNumArtificialVariables() == 0) {
130 return true;
131 }
132 for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
133 if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) < 0) {
134 return false;
135 }
136 }
137 return true;
138 }
139
140
141
142
143
144
145 public boolean isOptimal(final SimplexTableau tableau) {
146 if (tableau.getNumArtificialVariables() > 0) {
147 return false;
148 }
149 for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
150 if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) < 0) {
151 return false;
152 }
153 }
154 return true;
155 }
156
157
158
159
160
161
162
163
164 protected void solvePhase1(final SimplexTableau tableau)
165 throws OptimizationException {
166
167 if (tableau.getNumArtificialVariables() == 0) {
168 return;
169 }
170
171 while (!isPhase1Solved(tableau)) {
172 doIteration(tableau);
173 }
174
175
176 if (!MathUtils.equals(tableau.getEntry(0, tableau.getRhsOffset()), 0, epsilon)) {
177 throw new NoFeasibleSolutionException();
178 }
179 }
180
181
182 @Override
183 public RealPointValuePair doOptimize()
184 throws OptimizationException {
185 final SimplexTableau tableau =
186 new SimplexTableau(f, constraints, goalType, restrictToNonNegative, epsilon);
187 solvePhase1(tableau);
188 tableau.discardArtificialVariables();
189 while (!isOptimal(tableau)) {
190 doIteration(tableau);
191 }
192 return tableau.getSolution();
193 }
194
195 }