Введение/> Цельработы/>/>
Реализовать графическийметод решения задач линейного программирования.
1. Теоретическиесведения
/>
Наиболеепростым и наглядным методом линейного программирования (ЛП) являетсяграфический метод. Он применяется для решения задач ЛП с двумя переменными.
Рассмотримзадачу ЛП в стандартной форме записи:
/>
Положим n=2,т.е. рассмотрим эту задачу на плоскости. Пусть система неравенств совместна(имеет хотя бы одно решение).
Каждоенеравенство этой системы геометрически определяет полуплоскость с граничнойпрямой ai1 x1 + ai2 x2 = bi, i=1,2,… m. Условиянеотрицательности определяют полуплоскости, соответственно, с граничнымипрямыми x1=0, x2 =0. Система совместна, поэтому полуплоскости, как выпуклыемножества, пересекаясь, образуют общую часть, которая является выпуклыммножеством и представляет собой совокупность точек, координаты каждой изкоторых являются решением данной системы. Совокупность этих точек называютмногоугольником решений. Он может быть точкой, отрезком, лучом,многоугольником, неограниченной многоугольной областью.
Такимобразом, геометрически задача линейного программирования (ЗЛП) представляетсобой отыскание такой точки многоугольника решений, координаты которойдоставляют линейной функции цели максимальное (минимальное) значение, причемдопустимыми решениями являются все точки многоугольника решений.
Линейноеуравнение описывает множество точек, лежащих на одной прямой. Линейноенеравенство описывает некоторую область на плоскости. Определим, какую частьплоскости описывает неравенство 2х1+3х2£12. Во-первых, построимпрямую 2х1+3х2=12. Эта прямая проходит через точки(6, 0) и (0, 4). Для того чтобы определить, какая полуплоскость удовлетворяетнеравенству необходимо выбрать любую точку на графике, не принадлежащую прямой,и подставить ее координаты в неравенство. Если неравенство будет выполняться,то данная точка является допустимым решением и полуплоскость, содержащая точку,удовлетворяет неравенству. Удобной для использования при подстановке внеравенство является начало координат. Подставим х1=х2=0в неравенство 2х1+3х2£12. Получим 2´0+3´0£12. Данное утверждениеявляется верным, следовательно, неравенству 2х1+3х2£12 соответствует нижняяполуплоскость, содержащая точку (0.0). Это отражено на графике, изображенном на.1./> />
Рис. 1. Неравенству2х1+3х2£12 соответствует нижняя полуплоскость.
Аналогичноможно изобразить графически каждое ограничение задачи линейного программирования.
Решениемкаждого неравенства системы ограничений ЗЛП является полуплоскость, содержащаяграничную прямую и расположенная по одну сторону от нее. Пересечениеполуплоскостей, каждая из которых определяется соответствующим неравенствомсистемы, называется областью допустимых решений или областью определения.Необходимо помнить, что область допустимых решений удовлетворяет условиямнеотрицательности (xj ³0, j=1,…, n). Координатылюбой точки, принадлежащей области определения являются допустимым решениемзадачи.
Длянахождения экстремального значения целевой функции при графическом решениизадач ЛП используют вектор–градиент, координаты которого являются частнымипроизводными целевой функции, т.е.
/>.
Этотвектор показывает направление наискорейшего изменения целевой функции. Прямая />, состоит в том, что припараллельном смещении линии в одну сторону уровень перпендикулярнаявектору–градиенту, является линией уровня целевой функции. В любой точке линииуровня целевая функция принимает одно и то же значение. Приравняем целевуюфункцию постоянной величине «a». Меняя значение «a», получимсемейство параллельных прямых, каждая из которых является линией уровня.
Важноесвойство линии уровня линейной функции только возрастает, а при смещении вдругую сторону – убывает.
Сгеометрической точки зрения в задаче линейного программирования ищется такаяугловая точка или набор точек из допустимого множества решений, на которомдостигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе)остальных в направлении наискорейшего роста.
Графическийметод решения ЗЛП состоит из следующих этапов:
1. Строитсямногоугольная область допустимых решений ЗЛП – ОДР,
2. Строитсявектор-градиент ЦФ в какой-нибудь точке Х0 принадлежащей ОДР –
/>.
3. Линияуровня C1x1+C2x2 = а (а–постояннаявеличина) – прямая, перпендикулярная вектору – градиенту /> – передвигается внаправлении этого вектора в случае максимизации f(x1,x2)до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) областипри этом движении и является точкой максимума f(x1,x2).
4. Длянахождения ее координат достаточно решить два уравнения прямых, получаемых изсоответствующих ограничений и дающих в пересечении точку максимума. Значение f(x1,x2),найденное в получаемой точке, является максимальным.
Приминимизации f(x1,x2) линия уровня перемещается внаправлении, противоположном вектору-градиенту. Если прямая при своем движениине покидает ОДР, то соответствующий максимум или минимум f(x1,x2)не существует.
Если линияуровня параллельна какому-либо функциональному ограничению задачи, тооптимальное значение ЦФ будет достигаться в любой точке этого ограничения,лежащей между двумя оптимальными угловыми точками, и, соответственно, любая изэтих точек является оптимальным решением ЗЛП.
/>
/>3. Описание интерфейса разработанного программного продукта
Интерфейспрограммы, реализующей графический метод решения задач линейногопрограммирования:
программированиеграфический интерфейс линейный
/>/>
Альтернативнымявляется вариант организации интерфейса, когда основные области: область вводаданных для реализации метода и область построения расположены в одной рабочейобласти. Предложенный альтернативный вариант является оптимальным с точкизрения минимизации временных интервалов, так как при таком расположенииосновных областей, пользователь не будет вынужден совершать лишние перемещениямыши между указанными областями и лишние клики по рабочей области, однако,существующий интерфейс является более компактным, позволяет отображать областьпостроения графиков в большем масштабе, поэтому данная реализация интерфейсаявляется наиболее предпочтительной. Таким образом, реорганизация анализируемогоинтерфейса не целесообразна.
Спроектированныйинтерфейс является оптимальным, лаконичным и простым в использовании.3. ЛистингКласс «Line»
publicclass Line {
publicfloat a, b, c;
publicLine() {
}
publicLine (float a, float b, float c) {
this.a= a;
this.b= b;
this.c= c;
}
Line(Point p1, Point p2) {
this(p1.y – p2.y, p2.x – p1.x, p1.x*p2.y – p2.x*p1.y);
}
Line(float A, float B, Point point) {
this(new Point (point.x + B, point.y – A), point);
}
publicboolean isParalellWithLine (Line line) {
floatk = a * line.b – line.a * b;
returnMathUtil.isEqualWithEplsilon (k, 0);
}
publicPoint getIntersection (Line line) {
if(isParalellWithLine(line))
returnnull;
floatznam = 1 / (a * line.b – line.a * b);
floatx = (b * line.c – line.b * c) * znam;
floaty = (c * line.a – line.c * a) * znam;
returnnew Point (x, y);
}
publicdouble getDistanceToPoint (Point p) {
return(a * p.x + b * p.y + c) / Math.sqrt (a*a + b*b);
}
publicfloat getA() {
return– a;
}
publicvoid setA (float a) {
this.a= – a;
}
publicfloat getB() {
return– b;
}
publicvoid setB (float b) {
this.b= – b;
}
publicfloat getC() {
returnc;
}
publicvoid setC (float c) {
this.c= c;
}
publicString getView() {
return(a
}
}Класс «Polygon»
publicclass Polygon {
privateArrayList points = new ArrayList();
privateArrayList infinity = new ArrayList();
privateArrayList values = new ArrayList();
privateRect viewBox;
publicRect getViewBox() {
returnviewBox;
}
publicArrayList getPoints() {
returnpoints;
}
publicPoint getPoint (int i) {
returnpoints.get(i);
}
publicboolean getInfinity (int i) {
returninfinity.get(i);
}
publicfloat getValue (int i) {
returnvalues.get(i);
}
privatevoid clear() {
points.clear();
infinity.clear();
values.clear();
viewBox= null;
}
privatevoid addPoint (Point p, boolean inf) {
points.add(p);
values.add(0.0f);
infinity.add(inf);
}
publicPolygon() {
}
privatePolygon (BoundingBox bb, boolean b) {
Pointh = bb.getHigh();
Pointl = bb.getLow();
addPoint(new Point(h), b);
addPoint(new Point (l.x, h.y), b);
addPoint(new Point(l), b);
addPoint(new Point (h.x, l.y), b);
}
publicPolygon (ArrayList lines) {
//this.lines = lines;
BoundingBoxbb = new BoundingBox();
for(Line li: lines) {
for(Line lj: lines) {
Pointp = li.getIntersection(lj);
if(p == null)
continue;
booleanPointIn = true;
for(Line l: lines) {
if(l!= li && l!= lj && l.getDistanceToPoint(p)
PointIn= false;
break;
}
}
if(PointIn){
bb.addPoint(p);
}
}
}
if(! bb.isEmpty()) {
bb.extend(1.0f);
viewBox= new Rect(bb);
}
cutPolygonWithLines(new Polygon (bb, true), lines);
}
privatevoid cutPolygonWithLines (Polygon p, ArrayList lines) {
points= p.points;
infinity= p.infinity;
values= p.values;
for(Line l: lines) {
cutWithLine(l);
}
}
publicList getBoundingPoints (Rect viewRec) {
returnpoints;
}
privatevoid cutWithLine (Line l) {
Polygonp = new Polygon();
PointcrossingPt = null;
for(int i = 0; i
intnext = nextPointIndex(i);
booleanorgIsInside = (l.getDistanceToPoint (points.get(i)) > 0);
booleandestIsInside = (l.getDistanceToPoint (points.get(next)) > 0);
booleaninfEdge = 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;
}
publicint nextPointIndex (int i) {
if(i == points.size() – 1) {
return0;
}else {
returni+1;
}
}
publicint prevPointIndex (int i) {
if(i == 0) {
returnpoints.size() – 1;
}else {
returni-1;
}
}
voidsetTargetLine (float A, float B, boolean max) {
if(points.isEmpty()) {
extremums= null;
}
for(int i = 0; i
infinity.get(i);
Pointp = points.get(i);
floatvalue = p.x * A + p.y * B;
values.set(i, value);
}
LinkedListextrList = new LinkedList();
extrList.add(0);
for(int i = 1; i
if(max){
floatextr = 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
extrList.clear();
extrList.add(i);
}
}else {
floatextr = values.get (extrList.getLast());
if(MathUtil.isEqualWithEplsilon (extr, values.get(i))) {
if(values.get(i)
extrList.add(i);
}else {
extrList.addFirst(i);
}
}else if (extr > values.get(i)) {
extrList.clear();
extrList.add(i);
}
}
}
extremums= extrList;
}
privateLinkedList extremums;
LinkedListgetExtremums() {
returnextremums;
}
}
Заключение
/>/>Графическийметод основан на геометрической интерпретации задачи линейного программированияи применяется в основном при решении задач двумерного пространства и тольконекоторых задач трехмерного пространства, так как довольно трудно построитьмногогранник решений, который образуется в результате пересеченияполупространств. Задачу пространства размерности больше трех изобразитьграфически вообще невозможно.
/>Графический метод,несмотря на свою очевидность и применимость лишь в случае малой размерностизадачи, позволяет понять качественные особенности задачи линейногопрограммирования, характерные для любой размерности пространства переменных илежащие в основе численных методов ее решения.