for (int i = 0; i < points.size(); i++) {
int next = nextPointIndex(i);
boolean orgIsInside = (l.getDistanceToPoint (points.get(i)) > 0);
boolean destIsInside = (l.getDistanceToPoint (points.get(next)) > 0);
boolean infEdge = infinity.get(i);
if (orgIsInside!= destIsInside) {
crossingPt = l.getIntersection (new Line (points.get(i), points.get(next)));
}
if (orgIsInside && destIsInside) {
p.addPoint (points.get(i), infinity.get(i));
} else if (! orgIsInside && destIsInside) {
if (! MathUtil.isEqualWithEplsilon (points.get(i), crossingPt)) {
p.addPoint (crossingPt, infEdge);
}
} else if (! orgIsInside &&! destIsInside) {
} else {
if (! MathUtil.isEqualWithEplsilon (points.get(i), crossingPt)) {
p.addPoint (points.get(i), infinity.get(i));
}
p.addPoint (crossingPt, false);
}
}
this.points = p.points;
this.infinity = p.infinity;
this.values = p.values;
}
public int nextPointIndex (int i) {
if (i == points.size() – 1) {
return 0;
} else {
return i+1;
}
}
public int prevPointIndex (int i) {
if (i == 0) {
return points.size() – 1;
} else {
return i-1;
}
}
void setTargetLine (float A, float B, boolean max) {
if (points.isEmpty()) {
extremums = null;
}
for (int i = 0; i < points.size(); i++) {
infinity.get(i);
Point p = points.get(i);
float value = p.x * A + p.y * B;
values.set (i, value);
}
LinkedList<Integer> extrList = new LinkedList<Integer>();
extrList.add(0);
for (int i = 1; i < values.size(); i++) {
if(max) {
float extr = values.get (extrList.getLast());
if (MathUtil.isEqualWithEplsilon (extr, values.get(i))) {
if (values.get(i) > extr) {
extrList.add(i);
} else {
extrList.addFirst(i);
}
} else if (extr < values.get(i)) {
extrList.clear();
extrList.add(i);
}
} else {
float extr = values.get (extrList.getLast());
if (MathUtil.isEqualWithEplsilon (extr, values.get(i))) {
if (values.get(i) < extr) {
extrList.add(i);
} else {
extrList.addFirst(i);
}
} else if (extr > values.get(i)) {
extrList.clear();
extrList.add(i);
}
}
}
extremums = extrList;
}
private LinkedList<Integer> extremums;
LinkedList<Integer> getExtremums() {
return extremums;
}
}
Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно.
Графический метод, несмотря на свою очевидность и применимость лишь в случае малой размерности задачи, позволяет понять качественные особенности задачи линейного программирования, характерные для любой размерности пространства переменных и лежащие в основе численных методов ее решения.