Введення
Мета роботи
Реалізувати графічний метод рішення задач лінійного програмування.
1. Теоретичні відомості
Найбільш простим і наочним методом лінійного програмування (ЛП) є графічний метод. Він застосовується для розв'язання задач ЛП з двома змінними.
Розглянемо задачу ЛП у стандартній формі запису:
Покладемо n = 2 , тобто розглянемо цю задачу на площині. Нехай система нерівностей совместна (Має хоча б одне рішення).
Кожне нерівність цієї системи геометрично визначає полуплоскость з граничної прямий a i1 x 1 + a i2 x 2 = b i , 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 відповідає нижня полуплоскость.
Аналогічно можна зобразити графічно кожне обмеження задачі лінійного програмування.
Рішенням кожного нерівності системи обмежень ЗЛП є полуплоскость, що містить граничну пряму і розташована по одну сторону від неї. Перетин полуплоскостей, кожна з яких визначається відповідним нерівністю системи, називається областю допустимих рішень або областю визначення. Необхідно пам'ятати, що область допустимих рішень задовольняє умовам неотрицательности (x j Ві 0, j = 1, ..., n). Координати будь-якої точки, що належить області визначення є допустимим рішенням завдання.
Для знаходження екстремального значення цільової функції при графічному рішенні задач ЛП використовують вектор-градієнт, координати якого є приватними похідними цільової функції, тобто
.
Цей вектор показує напрямок найшвидшого зміни цільової функції. Пряма, полягає в тому, що при паралельному зсуві лінії в одну сторону рівень перпендикулярна вектору-градієнту, є лінією рівня цільової функції. У будь-якій точці лінії рівня цільова функція приймає одне і те ж значення. Прирівняємо цільову функцію постійній величині В«aВ». Міняючи значення В«aВ» , отримаємо сімейство паралельних прямих, кожна з яких є лінією рівня.
Важливе властивість лінії рівня лінійної функції тільки зростає, а при зсуві в інший бік - убуває.
З геометричної точки зору в задачі лінійного програмування шукається така кутова точка або набір точок з допустимого безлічі рішень, на якому досягається сама верхня (нижня) лінія рівня, розташована далі (ближче) решти в напрямку якнайшвидшого росту.
Графічний метод розв'язання ЗЛП складається з наступних етапів:
1. Будується багатокутна область допустимих рішень ЗЛП - ОДР,
2. Будується вектор-градієнт ЦФ в якій-небудь точці Х 0 приналежної ОДР -
.
3. Лінія рівня C 1 x 1 + C 2 x 2 = а (а - постійна величина) - пряма, перпендикулярна вектору - градієнту - пересувається в напрямку цього вектора в разі максимізації f (x 1, x 2 ) до тих пір, поки не покине меж ОДР. Гранична точка (або точки) області при цьому русі і є точкою максимуму f (x 1, x 2 ).
4. Для знаходження її координат досить вирішити два рівняння прямих, одержуваних з відповідних обмежень і дають в перетині точку максимуму. Значення f (x 1, x 2 ), знайдене в одержуваної точці, є максимальним.
При мінімізації f (x 1, x 2 ) лінія рівня переміщається в напрямку, протилежному вектору-градієнту. Якщо пряма при своєму русі не покидає ОДР, то відповідний максимум або мінімум f (x 1, x 2 ) не існує.
Якщо лінія рівня паралельна якого-небудь функціонального обмеження задачі, то оптимальне значення ЦФ буде досягатися в будь-якій точці цього обмеження, що лежить між двома оптимальними кутовими точками, і, відповідно, будь-яка з цих точок є оптимальним рішенням ЗЛП.
3. Опис інтерфейсу розробленого програмного продукту
Інтерфейс програми, що реалізує графічний метод розв'язання задач лінійного програмування:
програмування графічний інтерфейс лінійний
Альтернативним є варіант організації інтерфейсу, коли основні області: область вводу даних для реалізації методу і область побудови розташовані в одній робочій області. Запропонований альтернативний варіант є оптимальним з точки зору мінімізації часових інтервалів, оскільки при такому розташуванні основних областей, користувач не буде змушений здійснювати зайві переміщення миші між зазначеними областями і зайві кліки по робочій області, проте, існуючий інтерфейс є більш компактним, дозволяє відображати область побудови графіків в більшому масштабі, тому дана реалізація інтерфейсу є найбільш кращою. Таким чином, реорганізація аналізованого інтерфейсу не доцільна.
Спроектований інтерфейс є оптимальним, лаконічним і простим у використанні.
3. Лістинг
Клас В«LineВ»
public class Line {
public float a, b, c;
public Line () {
}
public Line (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);
}
public boolean isParalellWithLine (Line line) {
float k = a * line.b - line.a * b;
return MathUtil.isEqualWithEplsilon (k, 0);
}
public Point getIntersection (Line line) {
if (IsParalellWithLine (line))
return null;
float znam = 1/(a ​​* line.b - line.a * b);
float x = (b * line.c - line.b * c) * znam;
float y = (c * line.a - line.c * a) * znam;
<...
