Розв’язування оптимізаційних задач.
Графічний метод розв’язування ЗЛП
Графічний метод на площині застосовується насамперед для ЗЛП, заданих в стандартній формі відносно двох змінних х1 і х2 .
Нехай треба знайти максимум або мінімум лінійної функції
за умов
Для графічного розв’язування цієї задачі використовують наступний алгоритм:
1. Зобразимо на площині х1Ох2 множину точок, які задовольняють нерівності (2.2) і (2.3). Для цього побудуємо прямі: аі1х1 + аі 2 х2 = bі. Кожна пряма аі1х1 + аі2х2 = bi (і = 1,..., т) поділяє площину на дві півплощини. Точки однієї з цих півплощин задовольняють вказану нерівність, іншої - ні. Щоб визначити півплощину, точки якої задовольняють нерівність, треба в цю нерівність підставити координати будь-якої точки координатної площини (якщо b 0, то краще взяти початок координат). Якщо координати цієї точки задовольняють нерівність, то нерівність будуть задовольняти всі точки півплощини, яка її містить. Якщо координати цієї точки не задовольняють нерівність, то нерівність будуть задовольняти всі точки іншої півплощини.
Припустимо, що вже побудовані всі прямі і визначені півплощини, точки яких задовольняють відповідні нерівності. Перетином (спільною частиною) півплощин буде деяка область К, множина точок якої є множиною розв’язків системи (2.2). Множина точок, які задовольняють умову (2.3), утворює першу координатну чверть. Тому множиною точок, які задовольняють умови (2.2), (2.3), є та частина області К, яка лежить у першій координатній чверті. Позначимо цю множину (множину допустимих розв’язків ЗЛП) через М. Зауважимо, що М може бути порожньою множиною, опуклим многокутником або необмеженою опуклою многокутною областю. В першому випадку ЗЛП не має розв’язку, тому що її умови суперечливі. В другому випадку завжди існують точки, в яких функція набуває мінімального і максимального значень. В третьому випадку для лінійної форми може не існувати максимуму або мінімуму, або максимуму та мінімуму одночасно.
2. Побудуємо вектор нормалі n лінії рівня лінійної форми f, тобто вектор n = {с1; с2 }.
3. Побудувавши в середині області М лінію рівня, тобто перпендикулярну до n пряму, зміщуємо її паралельно самій собі в напрямку нормалі n, якщо необхідно знайти максимум лінійної форми f і в протилежному до n напрямку, якщо треба знайти мінімальне значення функції f. Зміщення продовжуємо до тих пір, поки ця пряма буде мати хоча б одну спільну точку з областю М, тоді в своєму крайньому положенні вказана пряма пройде через точку області М, в якій цільова функція прийме оптимальне значення. Якщо М - опуклий многокутник, то оптимальне значення лінійної функції завжди досягається в її вершині. Якщо оптимальне значення досягається в двох вершинах, то f набуває його в будь-якій точці, що лежить на відрізку, який їх з’єднує.
4. Координати потрібної вершини знаходимо, розв’язуючи систему рівнянь прямих, на перетині яких вона знаходиться.
Якщо оптимальним розв’язком є точки відрізку, то знаходимо координати кінцевих точок цього відрізку X1опт і Х2опт, а загальний розв’язок записуємо за формулою
У випадку необмеженої області М оптимальна межа може бути необмеженою. В цьому випадку, знайшовши один з оптимальних розв’язків X1опт, за Х2опт візьмемо довільну точку оптимальної межі. Тоді всі оптимальні розв’язки визначатимуться за формулою
Приклад.
Розв’язати графічним методом ЗЛП на максимум і мінімум:
Розв’ язання.
В площині xOy будуємо множину допустимих розв’язків ЗЛП - область М.
Для знаходження півплощини, яка визначається першою нерівністю, підставимо в цю нерівність координати т. О (О; О). Оскільки одержуємо вірну нерівність (О < 2), то шуканою півплощиною є та, яка містить т. О. Аналогічно, знаходимо півплощини, які визначаються другою та третьою нерівностями. Враховуючи вимогу x 0 і y 0, одержимо область М - п’ятикутник OAВСD.
1. Будуємо вектор n = {2; - 2} і лінію рівня l n .
Для знаходження точки максимуму зміщуємо лінію рівня l в напрямку n. В своєму крайньому положенні вона буде проходити через точку С області М. Її координати знаходимо, розв’язуючи систему
Для знаходження точок мінімуму функції f зміщуємо пряму І в напрямку протилежному вектору n. В своєму крайньому положенні пряма І буде містити відрізок АВ області М, тобто всі точки цього відрізку є оптимальними для мінімізації функції f. Такий розв’язок ЗЛП називається альтернативним.
Знаходимо координати кінцевих точок відрізку як точок перетину відповідних прямих: т. A (0;2) і т. B(1,25;3,25). Тоді
Xmin = t • (0;2) + (1 -t) • (1,25; 3,25) = (1,25 - 1,25t; 3,25 - 1,25t), 0 t 1.
Підставивши координати т. А в лінійну форму f, знаходимо мінімальне значення функції f: fmin = -4.
Відповідь: Xmax = {3;1}, fmax = 4,
Xmin = (1,25 - 1,25t; 3,25 - 1,25t), 0 t 1,
fmin=-4.
Зауваження. Графічний метод розв’язування ЗЛП використовується також для задач канонічної або загальної форми, якщо після перетворення їх у стандартну форму залишається лише дві змінні.
Розв’язати транспортну задачу (рекомендації щодо розв’язування)
У пунктах постачання А1, А2, А3 є однорідний вантаж в обсязі а1, а2, а3 одиниць відповідно; цей вантаж треба транспортувати у пункти В1, В2, В3 в обсязі відповідно b1, b2, b3 одиниць. Потреби замовника (в умовних одиницях), запаси вантажу на кожному пункті постачання (у тих же одиницях) і тарифи (вартість перевезення одиниці вантажу з даного пункту постачання даному замовнику) вказані в таблиці. Потрібно спланувати перевезення так, щоб загальна сума вартості перевезень була найменшою.
| В1 | В2 | В3 | |||
| А1 | |||||
| А2 | |||||
| А3 | |||||
Підсумки уроку.
Домашнє завдання.
1. Вивчити конспект.
2. Виконати завдання:
1. Графічним методом розв’язати задачу:
2. У пунктах постачання А1, А2, А3 є однорідний вантаж в обсязі а1, а2, а3 одиниць відповідно; цей вантаж треба транспортувати у пункти В1, В2, В3, В4, В5 в обсязі відповідно b1, b2, b3, b4, b5 одиниць. Потреби замовника (в умовних одиницях), запаси вантажу на кожному пункті постачання (у тих же одиницях) і тарифи (вартість перевезення одиниці вантажу з даного пункту постачання даному замовнику) вказані в таблиці. Потрібно спланувати перевезення так, щоб загальна сума вартості перевезень була найменшою.
Задачі для самостійного розв’язування