Реферати українською » Информатика, программирование » Графічний метод рішення задач лінійного програмування


Реферат Графічний метод рішення задач лінійного програмування

Запровадження

 

Мета роботи

Реалізувати графічний метод вирішення завдань лінійного програмування.

 

1. Теоретичні відомості

 

Найпростішим і наочним методом лінійного програмування (ЛЗ) є графічний метод. Він застосовується вирішення завдань ЛЗ з цими двома перемінними.

Розглянемо завдання ЛЗ у кімнаті стандартного формі записи:

Поклавши >n=2, тобто. розглянемо це завдання на площині. Нехай система нерівностейсовместна (має хоча одне рішення).

Кожне нерівність цією системою геометрично визначаєполуплоскость зграничной прямий a>i1 x1 + a>i2 x2 = bі,i=1,2,…m. Умовинеотрицательности визначають напівплощини, відповідно, з граничними прямимиx1=0,x2 =0. Системасовместна, тому напівплощини, як опуклі безлічі, перетинаючись, утворюють загальну частина, що є опуклим безліччю і становить сукупність точок, координати кожної серед яких є розв'язання цієї системи. Сукупність цих точок називаютьмногоугольником рішень. Він то, можливо точкою, відрізком, променем,многоугольником, необмеженої багатокутної областю.

Отже, геометрично завдання лінійного програмування (>ЗЛП) є пошук такий точки багатокутника рішень, координати якої доставляють лінійної функції мети максимальне (мінімальне) значення, причому припустимими рішеннями є всі точки багатокутника рішень.

>Линейное рівняння описує безліч точок, лежачих в одній прямий.Линейное нерівність описує деяку область, на площині.Определим, яку частина площині описує нерівність >2х1+>3х2> 12. По-перше, побудуємо пряму >2х1+>3х2=12. Ця пряма проходить через точки (6, 0) і (0, 4). Щоб визначити, якаполуплоскость задовольняє нерівності необхідно вибрати будь-який пункт на графіці, не приналежну прямий, і підставити її координати в нерівність. Якщо нерівність виконуватиметься, то дана точка є допустимим рішенням іполуплоскость, що містить точку, задовольняє нерівності.Удобной від використання при підстановці в нерівність є початок координат.Подставим x1=x2=0 в нерівність >2х1+>3х2>12. Одержимо20+3012. Дане твердження є вірним, отже, нерівності2х1+>3х2>12 відповідає нижняполуплоскость, що містить точку (0.0). Це на графіці, зображеному на. 1.


>Рис. 1.Неравенству2х1+>3х2>12 відповідає нижняполуплоскость.


Аналогічно можна намалювати графік кожне обмеження завдання лінійного програмування.

Рішенням кожного нерівності системи обмеженьЗЛП єполуплоскость, що міститьграничную пряму і розташована з одного боку від нього. Перетинполуплоскостей, кожна з яких визначається відповідним нерівністю системи, називається областю допустимих рішень чи областю визначення. Необхідно пам'ятати, що область допустимих рішень задовольняє умовамнеотрицательности (xj0,j=1,…, n). Координати будь-який точки, що належить області визначення є допустимим рішенням завдання.

Для перебування екстремального значення цільової функції при графічному рішенні завдань ЛЗ використовуютьвектор–градиент, координати якого є приватними похідними цільової функції, тобто.

.

Цей вектор показує напрям якнайшвидшого зміни цільової функції. Пряма , у тому, що з паралельному зміщення лінії до однієї бік рівень перпендикулярнавектору–градиенту, є лінією рівня цільової функції. У будь-якій точці лінії рівня цільова функція приймає один і той ж значення.Приравняем цільову функцію постійної величині «a». Змінюючи значення «a», одержимо сімейство паралельних прямих, кожна з яких є лінією рівня.

Важливе властивість лінії рівня лінійної функції лише зростає, а під час звільнення у бік – убуває.

З геометричній погляду в завданню лінійного програмування шукається така кутова точка чи набір точок з припустимого безлічі рішень, у якому досягається сама верхня (нижня) лінія рівня, розташована далі (ближче) інших у напрямі якнайшвидшого зростання.

>Графический метод рішенняЗЛП складається з таких етапів:

1. Будується багатокутна область допустимих рішеньЗЛП –ОДР,

2. Будуєтьсявектор-градиентЦФ у якійсь точці Х0 що належитьОДР –

 

.

3. Лінія рівня З1x12x2 = а (а–стала величина) – пряма, перпендикулярна вектору – градієнту – пересувається у напрямку цієї вектора у разі максимізації >f(x1,x2) до того часу, доки залишить межОДР. Гранична точка (чи крапки) області лише за цьому рухові і є точкою максимуму >f(x1,x2).

4. Для перебування її координат досить вирішити два рівняння прямих, отримуваних з відповідних обмежень і дають в перетині точку максимуму. Значення >f(x1,x2), знайдене в одержуваної точці, є межею.

При мінімізації >f(x1,x2) лінія рівня переміщається у бік, протилежномувектору-градиенту. Якщо пряма при своєму русі важко позбутисяОДР, то відповідний максимум чи мінімум >f(x1,x2) немає.

Якщо лінія рівня паралельна якомусь функціональному обмеження завдання, то оптимальне значенняЦФ досягатиметься у будь-якій точці цього обмеження, лежачої між двома оптимальними кутовими точками, і, будь-яке з названих точок є оптимальним розв'язаннямЗЛП.

 


3. Опис інтерфейсу розробленого програмного продукту

Інтерфейс програми, реалізує графічний метод вирішення завдань лінійного програмування:

програмування графічний інтерфейс лінійний

Альтернативним є варіант організації інтерфейсу, коли основні області: область введення даних для реалізації методу і науковотехнологічна галузь побудови перебувають у одним робочим області. Запропонований альтернативний варіант оптимальним з погляду мінімізації тимчасових інтервалів, бо за такому розташуванні основних областей, користувач нічого очікувати змушений здійснювати зайві переміщення миші між зазначеними областями і зайвий кліки по робочої області, проте, існуючий інтерфейс є компактним, дозволяє відображати область побудови графіків більшому масштабі, тому ця реалізація інтерфейсу є найбільш кращою. Отже, реорганізація аналізованого інтерфейсу не доцільна.

Запроектований інтерфейс є оптимальним, лаконічним і простим використання.

3.Листинг

Клас «Line»

publicclass Line {

publicfloat a, b, з;

public Line() {

}

public Line (>float a,float b,float з) {

>this.a = a;

>this.b = b;

>this.c = з;

}

Line (Pointp1, Pointp2) {

>this (>p1.y –p2.y,p2.x –p1.x,p1.x*p2.y –p2.x*p1.y);

}

Line (>float A,float B, Pointpoint) {

>this (new Point (>point.x + B,point.y – A),point);

}

publicbooleanisParalellWithLine (Line line) {

>floatk = a *line.b –line.a * b;

>returnMathUtil.isEqualWithEplsilon (>k, 0);

}

public PointgetIntersection (Line line) {

>if (>isParalellWithLine(line))

>returnnull;

>floatznam = 1 / (a *line.b –line.a * b);

>float x = (b *line.c –line.b * з) *znam;

>float y = (з *line.a –line.c * a) *znam;

>return new Point (x, y);

}

publicdoublegetDistanceToPoint (Pointp) {

>return (a *p.x + b *p.y + з) /Math.sqrt (>a*a +b*b);

}

publicfloatgetA() {

>return – a;

}

publicvoidsetA (>float a) {

>this.a = – a;

}

publicfloatgetB() {

>return – b;

}

publicvoidsetB (>float b) {

>this.b = – b;

}

publicfloatgetC() {

>return з;

}

publicvoidsetC (>float з) {

>this.c = з;

}

publicStringgetView() {

>return (a < 0? – a: a) + «*x1 +» + (b < 0? – b: b) + «*x2 <=» + з;

}

}

Клас «>Polygon»

publicclassPolygon {

privateArrayList<Point>points = newArrayList<Point>();

privateArrayList<Boolean>infinity = newArrayList<Boolean>();

privateArrayList<Float>values = newArrayList<Float>();

privateRectviewBox;

publicRectgetViewBox() {

>returnviewBox;

}

publicArrayList<Point>getPoints() {

>returnpoints;

}

public PointgetPoint (>int і) {

>returnpoints.get(i);

}

publicbooleangetInfinity (>int і) {

>returninfinity.get(i);

}

publicfloatgetValue (>int і) {

>returnvalues.get(i);

}

privatevoidclear() {

>points.clear();

>infinity.clear();

>values.clear();

>viewBox =null;

}

privatevoidaddPoint (Pointp,booleaninf) {

>points.add(p);

>values.add (>0.0f);

>infinity.add(inf);

}

publicPolygon() {

}

privatePolygon (>BoundingBoxbb,boolean b) {

Point h =bb.getHigh();

Point l =bb.getLow();

>addPoint (newPoint(h), b);

>addPoint (new Point (>l.x,h.y), b);

>addPoint (newPoint(l), b);

>addPoint (new Point (>h.x,l.y), b);

}

publicPolygon (>ArrayList<Line>lines) {

 //this.lines =lines;

>BoundingBoxbb = newBoundingBox();

>for (Lineli:lines) {

>for (Linelj:lines) {

Pointp =li.getIntersection(lj);


>if (>p ==null)

>continue;

>booleanPointIn =true;

>for (Line l:lines) {

>if (l!=li && l!=lj &&l.getDistanceToPoint(p) < 0) {

>PointIn =false;

>break;

}

}

>if(PointIn) {

>bb.addPoint(p);

}

}

}

>if (!bb.isEmpty()) {

>bb.extend (>1.0f);

>viewBox = newRect(bb);

}

>cutPolygonWithLines (newPolygon (>bb,true),lines);

}

privatevoidcutPolygonWithLines (>Polygonp,ArrayList<Line>lines) {

>points =p.points;

>infinity =p.infinity;

>values =p.values;


>for (Line l:lines) {

>cutWithLine(l);

}

}

publicList<Point>getBoundingPoints (>RectviewRec) {

>returnpoints;

}

privatevoidcutWithLine (Line l) {

>Polygonp = newPolygon();

PointcrossingPt =null;

>for (>int і = 0; і <points.size(); і++) {

>int next =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));

}elseif (!orgIsInside &&destIsInside) {

>if (!MathUtil.isEqualWithEplsilon (>points.get(i),crossingPt)) {

>p.addPoint (>crossingPt,infEdge);

}

}elseif (!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;

}

publicintnextPointIndex (>int і) {

>if (і ==points.size() – 1) {

>return 0;

}else {

>returni+1;

}

}

publicintprevPointIndex (>int і) {

>if (і == 0) {

>returnpoints.size() – 1;

}else {

>returni-1;

}

}

>voidsetTargetLine (>float A,float B,booleanmax) {


>if (>points.isEmpty()) {

>extremums =null;

}

>for (>int і = 0; і <points.size(); і++) {

>infinity.get(i);

Pointp =points.get(i);

>floatvalue =p.x * A +p.y * B;

>values.set (і,value);

}

>LinkedList<Integer>extrList = newLinkedList<Integer>();

>extrList.add(0);

>for (>int і = 1; і <values.size(); і++) {

>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);

}

}elseif (>extr <values.get(i)) {

>extrList.clear();

>extrList.add(i);

}

}else {

>floatextr =values.get (>extrList.getLast());

>if (>MathUtil.isEqualWithEplsilon (>extr,values.get(i))) {

>if (>values.get(i) <extr) {

>extrList.add(i);

}else {

>extrList.addFirst(i);

}

}elseif (>extr >values.get(i)) {

>extrList.clear();

>extrList.add(i);

}

}

}

>extremums =extrList;

}

privateLinkedList<Integer>extremums;

>LinkedList<Integer>getExtremums() {

>returnextremums;

}

}


Укладання

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

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


Схожі реферати:

Навігація