Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Приклад
|
|
5x1 - 6x2 + x3 ® min
2x1 + 3x2 - 4x3 = 5
5x1 + 6x2 ³ 7
7x1 + 3x2 £ 8
x1, x2 ³ 0
приведемо рішення та обмеження до канонічного виду
f(x) ® max
gi(x) = bi , i = 1, N
x ³ 0
використовуємо графічний метод.
Варіанти використання графічного методу:
 |
Відповідь: 1 рішення Відповідь: множина рішень на
прямій (z ô ô цій прямій)
Відповідь: 1 рішення Відповідь: немає рішень Відповідь: немає рішень
 |
(ОДР необмежена знизу) (ОДР необмежена зверху) (ОДР порожня множина)
Примітка: ОДР для ЛП завжди випукла; вогнутостей не може бути.
СИМПЛЕКС МЕТОД або
Метод симплекс таблиць
Метод засновано на табличних перетвореннях (Джордана-Гауса) моделі, що представлена в канонічному вигляді. Канонічний вигляд моделі – це вигляд, необхідний для роботи з методом чи з програмою на ЕОМ. Для кожного методу існують свої вимоги до канонічного вигляду.
Вимоги для приведення до канонічного вигляду (для даного метода):
Z(f) ® max, Z(f) – цільова функція;
Наявність обмежень типу “рівність”;
Наявність одиничного додатнього базису;
Додатність правої частини;
Невід’ємність змінних;
Наявність додатнього опорного рішення.
Базисна змінна – змінна, яку потрібно додати в обмеження для отримання рівності та одиничного вектора.
Штучна змінна (M –змінна) - змінна, яку необхідно дописати в обмеження в якості базисної, а якщо необхідно – і в цільову функцію з коефіціентом М, з метою отримання при рішенні нуль.
ПРИКЛАДИ ПРИВЕДЕННЯ ДО КАНОНІЧНОГО ВИГЛЯДУ:
1) 3x1 + 2x2 ® min -3x1 – 2x2 ® max Розмірність задачі 2 * 4
6x1 - x2 £ 5 6x1 - x2 + x3 = 5 -3 -2 0 0
7x1 + x2 £ 7 7x1 + x2 + x4 = 7 6 -1 1 0 5
x1, x2 > 0 x1, …, x4 > 0 7 1 0 1 7
Відповідь: X = (0, 0, 5, 7).
2) 3x1 + 2x2 ® min -3x1 - 2x2 – 30x5 ® max 2 * 5
6x1 - x2 < 5 6x1 - x2 + x3 =5 -3 -2 0 0 0
7x1 + x2 > 7 7x1 + x2 – x4 + x5 = 7 6 -1 1 0 0 5
x1, x2 ³ 0 x1 , …, x4 > 0 7 1 0 -1 1 7
Відповідь: X = (0, 0, 5, 0, 7).
30x4 30 x5
3) 3x1 + 2x2 ® max 3x1+2x2 ® max 3x1+2x2-Mx4-Mx5®max 2 * 5
6x1 - x2 £ -5 -6x1+ x2 ³ 5 -6x1+ x2-x3+x4=5
7x1 + x2 = 7 7x1+ x2 = 7 7x1+ x2+x5=7
x1 , x2 > 0 x1 , x2 ³ 0 x1, …, x5 ³ 0
Відповідь: X = (0, 0, 0, 5, 7).
4) 7x1 + 2x2 ® min -7x1–2x2+2x3-Mx5®max
6x1 - x2 £ 5 6x1- x2+x3+x4=5
7x1 + x2 =-7 -7x1- x2+x3+x5=7
x1, x2 ³ 0 x1, …, x5 > 0
Введемо заміну x2 = x2 - x3
АЛГОРИТМ ПРИВЕДЕННЯ ДО КАНОНІЧНОГО ВИГЛЯДУ
Аналіз умови невід’ємності. Якщо не для всіх змінних задана умова невід’ємності, то кожну таку змінну (невід’ємну) замінюють різницею двох додатніх.
Права частина повинна бути додатньою. Якщо в будь яких обмеженнях права частина від’ємна, необхідно помножити її на (-1) для корегування знаку.
Якщо цільова функція Z(f) ® min, то необхідно змінити коефіцієнти на протилежні, а Z(f) ® max.
Для кожної нерівності типу “£ ” додаємо базисну змінну.
Якщо обмеження типу “=”, додаємо одну М-змінну (велике вигадане число, напр., 10, 20,...).
Якщо обмеження типу “ ³ ”, додаємо різницю двох додатніх, одна з яких М-змінна.