- •Значення цільової функції повинно бути максимізовано.
- •Усі обмеження задачі повинні мати вигляд строгих рівнянь.
- •Так, в ліву частину нерівностей виду
- •Всі змінні задачі повинні бути невід’ємні.
- •Завдання для самостійного виконання
- •2. Знаходимо півплощини, що визначаються нерівностями.
- •3 . Знаходимо многокутник розв’язків. Він визначається як перетин усіх півплощин (рис.2).
- •5. Побудуємо лінію рівня lo , яка перпендикулярна до вектора напрямку і проходить через початок координат.
- •7. Визначаємо координати точок максимуму та мінімуму функції цілі, розв’язуючи системи відповідних рівнянь.
- •Геометричний метод розв’язування задач лінійного програмування
- •Приклад 2.
- •Розв’язання:
- •1. Будуємо прямі, рівняння яких отримуються внаслідок заміни в обмеженнях знаків нерівностей на знаки точних рівностей. Для нашого прикладу будуємо наступні прямі:
- •Знайдені розв’язки визначають оптимальні плани задачі, що розглядається.
- •8. Обчислюємо значення цільової функції в точках максимуму і мінімуму.
- •Розв’язування задач за допомогою симплекс-методу Приклад 3.
- •Розв’язання:
- •5. Записуємо робочу модель.
- •7. Алгоритм симплекс-методу.
- •З водимо систему обмежень до одиничного базису:
- •Виконуємо перерахунок елементів q-го ведучого рядка за формулою:
- •1. За допомогою симплекс-методу знайти такий план виробництва, який би забезпечував найбільший прибуток.
- •2. Скласти модель двоїстої задачі. Використовуючи відповідність між змінними прямої і двоїстої задач та симплексну таблицю для прямої задачі, записати оптимальний розв’язок двоїстої задачі.
- •3. Дати повний економічний аналіз основних і додаткових змінних обох задач.
- •Транспортна задача
- •Приклад 4. Для транспортної задачі, вихідні дані якої наведені в таблиці 2, знайти оптимальний план.
- •Розв’язання:
- •1. Визначаємо тип транспортної задачі.
- •2. Знаходимо опорний план транспортної задачі, використовуючи метод північно-західного (лівого верхнього) кута.
- •3. Перевіряємо опорний план тз на оптимальність за допомогою методу потенціалів.
- •4. Поліпшуємо опорний план.
Розв’язування задач за допомогою симплекс-методу Приклад 3.
Нехай на підприємстві можна виробляти два види продукції Р1 і Р2, для чого необхідно використовувати три види сировини S1, S2, S3, запаси яких обмежені і відповідно дорівнюють 60, 65, 135. Відомі норми витрат кожного виду сировини (і) на виробництві кожного виду продукції (j) – aij та прибуток від реалізації кожного виду продукції. Треба визначити такий план випуску кількості продукції кожного виду, щоб загальний прибуток від її реалізації був максимальним. Наведені умови задачі наочно подамо у вигляді таблиці.
Вид сировини |
Вид продукції Р1 |
Вид продукції Р2 |
Запаси сировини |
S1 |
2 |
2 |
60 |
S2 |
3 |
1 |
65 |
S3 |
2 |
9 |
135 |
Прибуток |
10 |
18 |
|
Розв’язання:
І. Побудуємо математичну модель задачі.
1. З’ясовуємо, які величини в задачі є невідомими, і вводимо відповідні змінні.
В розглянутій задачі невідомими є кількість продукції видів Р1 і Р2. Отже, вводимо відповідні змінні х1 і х2.
2. Визначаємо мету розв’язування задачі.
В даному прикладі – це максимізація загального прибутку від реалізації.
3. Будуємо цільову функцію, що відображує мету розв’язання задачі і обов’язково включає до свого складу змінні.
Цільова функція нашої задачі має вигляд:
L = 10 х1 + 18 х2 → max,
де кожний окремий доданок означає прибуток від випуску продукції відповідного виду, а символ → max відображає вимогу максимізації функції.
4. З’ясовуємо умови задачі і записуємо їх у вигляді обмежень.
Згідно з умовами прикладу запаси сировини S1, S2, S3 обмежені і відповідно дорівнюють 60, 65, 135, отже, кількість ресурсів кожного типу, які використовуються для виробництва всіх видів продукції, не повинна перевищувати наявної їх кількості в розпорядженні підприємства:
2 х1 + 2 х2 ≤ 60,
3 х1 + х2 ≤ 65,
2 х1 + 9 х2 ≤ 135,
i, очевидно, випуск продукції повинен бути невід’ємним:
х1 ≥ 0, х2 ≥ 0.
5. Записуємо робочу модель.
L = 10 х1 + 18 х2 → max,
2 х1 + 2 х2 ≤ 60,
3 х1 + х2 ≤ 65,
2 х1 + 9 х2 ≤ 135,
х1 ≥ 0, х2 ≥ 0.
6. Зводимо дану задачу лінійного програмування до канонічної форми. (Детально дана задача розглянуто у прикладі 1).
Вводимо в ліві частини нерівностей виду “≤” додаткові невід’ємні змінні х3, х4, х5 (балансові змінні) зі знаком “+” та отримуємо канонічну форму для заданої задачі лінійного програмування:
L = 10 х1 + 18 х2 → max,
2 х1 + 2 х2 + х3 = 60,
3 х1 + х2 + х4 = 65, (*)
2 х1 + 9 х2 + х5 = 135,
х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х4 ≥ 0, х5 ≥ 0.
7. Алгоритм симплекс-методу.
З водимо систему обмежень до одиничного базису:
а функцію цілі L = γ0 + γr+1xr+1 + … + γjxj + … + γnxn, що виражена через вільні змінні записуємо у вигляді: L - γr+1xr+1 - … - γjxj - … - γnxn= γ0
Подаємо умову задачі лінійного програмування у вигляді таблиці:
Таблиця 1.
Базисні змінні |
Вільні члени |
x1 |
x2 |
… |
xі |
… |
xr |
xr+1 |
… |
xj |
… |
xn |
x1 |
b1 |
1 |
0 |
… |
0 |
… |
0 |
a1, r+1 |
… |
a1, j |
… |
a1, n |
x2 |
b2 |
0 |
1 |
… |
0 |
… |
0 |
a2, r+1 |
… |
a2, j |
… |
a2, n |
…… |
……. |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
xі |
bi |
0 |
0 |
… |
1 |
… |
0 |
ai, r+1 |
… |
ai, j |
… |
ai, n |
…… |
……. |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
xr |
bn |
0 |
0 |
… |
0 |
… |
1 |
ar, r+1 |
… |
ar, j |
… |
ar, n |
L |
γ0 |
0 |
0 |
… |
0 |
… |
0 |
γr+1 |
|
γj |
|
γn |