Смекни!
smekni.com

Графический метод решения задач линейного программирования (стр. 2 из 2)

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;

}

}

Заключение

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно.

Графический метод, несмотря на свою очевидность и применимость лишь в случае малой размерности задачи, позволяет понять качественные особенности задачи линейного программирования, характерные для любой размерности пространства переменных и лежащие в основе численных методов ее решения.