Розв'язок задачі лінійного програмування
Задача 1
Розв’язати графічно задачу лінійного програмування

Розв’язання:
Розглянемо на площині х1Оx2 сумісну систему лінійних нерівностей
(1)
![]()
Кожна нерівність
цієї системи
геометрично
визначає півплощину
з граничною
прямою
(i = 1, 2,...,т). Умови
невід’ємності
визначають
півплощини
відповідно
з граничними
прямими
.
Система сумісна,
тому півплощини,
як опуклі множини,
перетинаючись,
утворюють
спільну частину,
що є опуклою
множиною і
являє собою
сукупність
точок, координати
кожній із який
є розв’язком
даної системи
(рис. 1.).

Рис. 1.
Сукупність цих точок (розв’язків) називають багатокутником розв’язків Він може бути точкою, відрізком, променем, багатокутником, необмеженою багатокутною областю.
Якщо в системі
обмежень (1) п
= 3, то кожна нерівність
геометрично
представляє
півпростір
тривимірного
простору, гранична
площина котрого
(i = 1, 2,...,т), а умови
невід’ємності
– півпростори
з граничними
площинами
відповідно
хі = 0 (і = 1,2,3). Якщо
система обмежень
сумісна, то ці
півпростори,
як опуклі множини,
перетинаючись,
утворять у
тривимірному
просторі спільну
частину, що
називається
багатогранником
розв’язків.
Багатогранник
розв’язків
може бути точкою,
відрізком,
променем,
багатокутником,
багатогранником,
багатогранною
необмеженою
областю.
Нехай у
системі обмежень
(1) п > 3; тоді кожна
нерівність
визначає півпростір
n-вимірного
простору з
граничною
гіперплощиною
(i = 1, 2,...,т),. Кожному
обмеженню виду
(3.7) відповідають
гіперплощина
та напівпростір,
який лежить
по один бік
цієї гіперплощини,
а умови невід’ємності
– півпростори
з граничними
гіперплощинами
хі = 0 (і = 1,2,3,...,n).
Якщо система обмежень сумісна, то по аналогії з тривимірним простором вона утворює спільну частину в n-вимірному просторі – опуклий багатогранник допустимих розв’язків.
Таким чином, геометрично задача лінійного програмування являє собою відшукання такої точки багатогранника розв’язків, координати, якої надають лінійній функції максимальне (мінімальне) значення, причому допустимими розв’язками є усі точки багатогранника розв’язків.
Цільову
функцію
в п-вимірному
просторі основних
змінних можна
геометрично
інтерпретувати
як сім’ю паралельних
гіперплощин,
положення
кожної з яких
визначається
значенням
параметра Z.
Запишемо систему нерівностей у вигляді:

Розв’яжемо задачу графічно.
Побудуємо систему обмежень (1), (2), (3).
Побудуємо також лінії рівня: х1 + х2 = С. С = const.

Розв’язок на перетині Ох2 та (3):
Отже, розв’язок
є точка
,
причому
.
Задача 2
Розв’язати симплекс методом:

Розв’язання:
Графічний
метод для визначення
оптимального
плану задачі
лінійного
програмування
доцільно
застосовувати
лише для задач
із двома змінними.
За більшої
кількості
необхідно
застосовувати
загальний метод
розв’язування
задач лінійного
програмування.
З властивостей
розв’язків
задачі лінійного
програмування
відомо: оптимальний
розв’язок
задачі має
знаходитись
в одній з кутових
точок багатогранника
допустимих
розв’язків.
Тому найпростіший
спосіб відшукання
оптимального
плану потребує
перебору всіх
кутових точок
(можливих допустимих
планів задачі).
Кожний опорний
план визначається
системою m лінійно
незалежних
векторів, які
містяться в
системі обмежень
задачі з n векторів
,
отже загальна
кількість
опорних планів
визначається
кількістю
комбінацій
.
Задачі, що описують реальні економічні процеси мають значну розмірність і простий перебір всіх можливих опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Отже необхідне використання методу, який дає можливість скоротити кількість обчислень. Такий метод запропоновано американським вченим Дж. Данцігом у 1949 році – так званий симплекс-метод.
Ідея методу полягає в здійсненні направленого перебору допустимих планів, таким чином, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який є хоча б не гіршим за попередній. Значення функціоналу при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум).
Процес розв’язування задачі симплекс-методом має ітераційний характер: однотипові обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.
Отже, симплекс-метод — це поетапна обчислювальна процедура, яка дозволяє починаючи з відомого опорного плану за скінчену кількість кроків отримати оптимальний план задачі лінійного програмування.
Розглянемо задачу лінійного програмування подану в канонічній формі:
Не втрачаючи загальності припустимо, що система містить перші m одиничних векторів:
(1)
(2)
(3)
Система (1) у векторній формі матиме вигляд:
(4)
де
,
,...,
,
,
,...,
,
– лінійно незалежні
одиничні вектори
m-вимірного
простору, що
утворюють
одиничну матрицю
і складають
базис цього
простору. Тому
в розкладі (4)
базисними
змінними будуть
,
інші – вільні
змінні. Покладемо
всі вільні
змінні рівними
нулю
.
Оскільки
,
а вектори
– одиничні,
отримаємо один
із розв’язків
системи (4), тобто
допустимий
план.
(5)
Такому плану відповідає розклад
(6)
де
– лінійно незалежні
і за властивістю
3 розв’язків
задачі лінійного
програмування
план
є кутовою точкою
багатогранника
розв’язків,
а отже може
бути початковим
опорним планом.
Розглянемо, як виходячи з початкового опорного плану (5) перейти до наступного опорного плану, що відповідає процесу перебору кутових точок багатогранника розв’язків.
Оскільки
є базисом m-вимірного
простору, то
кожен з векторів
співвідношення
(5) може бути
розкладений
за векторами
базису причому
єдиним чином:

Розглянемо
такий розклад
для довільного
не базисного
вектора, наприклад,
для
:
(7)
Припустимо,
що у виразі (7)
існує хоча б
один додатній
коефіцієнт
.
Введемо
до розгляду
деяку поки що
невідому величину
,
помножимо на
неї обидві
частини рівності
(3.34) і віднімемо
результат з
рівності (3.33),
маємо:
(8)
Таким чином вектор
![]()
є планом
у тому випадку,
коли його компоненти
невід’ємні.
За припущенням
,
отже ті компоненти
вектора
в які входять
будуть невід’ємними,
тому необхідно
розглядати
лише ті компоненти,
які містять
додатні
.
Отже необхідно
знайти таке
значення
,
при якому для
всіх
буде виконуватися
умова невід’ємності
плану задачі:
(9)
З (3.36) отримуємо,
що для шуканого
має виконуватися
умова
.
Отже вектор
буде планом
задачі для
будь-якого q,
що задовольняє
умову
,
де мінімум
знаходимо по
тих i, для яких
.
Опорний
план не може
містити більш
ніж m додатних
компонент, тому
в плані
необхідно
перетворити
в нуль хоча б
одну з компонент.
Припустимо,
що
для деякого
значення і,
тоді відповідна
компонента
плану
перетвориться
в нуль. Нехай
це буде перша
компонента
плану, тобто
.
Підставимо
значення
у вираз:
,
якщо позначити
,
,
то рівняння можна подати у вигляді розкладу:
,
якому відповідає наступний опорний план:
.
Для визначення
наступного
плану необхідно
аналогічно
продовжити
процес: будь-який
вектор, що не
входить в базис
розкласти за
базисними
векторами, а
потім визначити
таке
,
для якого один
з векторів
виключається
з базису.
Узагальнюючи розглянутий процес, маємо – визначення нових опорних планів полягає у виборі вектора, який має ввійти в базис і вектора, що має вийти з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана-Гауса.
Необхідно
відмітити, що
для випадку
коли вектор
підлягає включенню
в базис, а в його
розкладі всі
,
то, очевидно,
не існує такого
,
який виключав
би один з векторів
розкладу (3.35). В
такому випадку
план
містить m+1 додатних
компонент, отже
система векторів
буде лінійно
залежною і
визначає не
кутову точку
багатогранника
розв’язків,
а функціонал
не може в ній
досягати свого
максимального
значення. Це
означає, що
функціонал
є необмеженим
на багатограннику
розв’язків.
Симплексний метод здійснює направлений перебір опорних планів, що дозволяє переходити від одного плану до іншого, який є хоча б не гіршим від попереднього за значенням, що він надає функціоналу. Отже окремим питанням постає вибір вектору, який необхідно вводити в базис при здійсненні ітераційної процедури симплексного методу.
Теорема
1. Якщо для деякого
вектора
виконується
умова
,
то план
не є оптимальним
і можливо побудувати
такий план Х,
для якого
виконуватиметься
нерівність
.
Доведення.
Помножимо
(3.39) і (3.40) на
і віднімемо
результати
відповідно
з (3.37) та (3.38), отримаємо:
(*)
![]()
У співвідношенні
до обох частин
додається
величина
для
,
додатні, тому
завжди можливо
знайти таке
,
що всі коефіцієнти
при векторах
були невід’ємними,
іншими словами
отримати новий
план задачі
виду:
,
якому згідно відповідає значення функціоналу
Так як за умовою теореми
і
,
то
.
Що і потрібно було довести.
Теорема
2. Якщо для деякого
вектора
виконується
умова
,
то план
не є оптимальним
і можливо побудувати
такий план Х,
для якого
виконуватиметься
нерівність
.
Запишемо канонічну задачу:

Розв’яжемо симплекс-методом:
| 1 | 1 | 0 | -M | 0 | 0 | ||||
| x1 | x2 | x3 | x4 | x5 | x6 | B | T | ||
| x4 | 4 | 3 | -1 | 1 | 0 | 0 | 12 | 3 | ** |
| x5 | -1 | 2 | 0 | 0 | 1 | 0 | 4 | – | |
| x6 | 1 | -1 | 0 | 0 | 0 | 1 | 4 | 4 | |
| F | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | |
| Mf | -4 | -3 | 1 | 0 | 0 | 0 | -12 | 0 | |
| ** |
| 1 | 1 | 0 | -M | 0 | 0 | ||||
| x1 | x2 | x3 | x4 | x5 | x6 | B | T | ||
| x1 | 1 | 0,75 | -0,25 | 0,25 | 0 | 0 | 3 | 4 | |
| x5 | 0 | 2,75 | -0,25 | 0,25 | 1 | 0 | 7 | 2,545 | ** |
| x6 | 0 | -1,75 | 0,25 | -0,25 | 0 | 1 | 1 | – | |
| F | 0 | -0,25 | -0,25 | 0,25 | 0 | 0 | 3 | 0 | |
| Mf | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
| ** |
| 1 | 1 | 0 | -M | 0 | 0 | ||||
| x1 | x2 | x3 | x4 | x5 | x6 | B | T | ||
| x1 | 1 | 0 | -0,1818 | 0,1818 | -0,2727 | 0 | 1,091 | – | |
| x2 | 0 | 1 | -0,09091 | 0,09091 | 0,3636 | 0 | 2,545 | – | |
| x6 | 0 | 0 | 0,09091 | -0,09091 | 0,6364 | 1 | 5,455 | 60 | ** |
| F | 0 | 0 | -0,2727 | 0,2727 | 0,09091 | 0 | 3,636 | 0 | |
| Mf | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
| ** |
| 1 | 1 | 0 | -M | 0 | 0 | |||
| x1 | x2 | x3 | x4 | x5 | x6 | B | T | |
| x1 | 1 | 0 | 0 | 0 | 1 | 2 | 12 | – |
| x2 | 0 | 1 | 0 | 0 | 1 | 1 | 8 | – |
| x3 | 0 | 0 | 1 | -1 | 7 | 11 | 60 | 60 |
| F | 0 | 0 | 0 | 0 | 2 | 3 | 20 | 0 |
| Mf | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
Отже, х* = (12, 8, 60), L(x*)max = 20.
Задача 3
Для задачі побудувати двоїсту, розв’язати і за розв’язком знайти розв’язок двоїстої:

Розв’язання:
Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.
Економічну інтерпретацію кожної з пари задач розглянемо на прикладі виробничої задачі.
Початкова задача:
max z = c1x1 + c2x2 + … + cnxn
,
Визначити,
яку кількість
продукції
кожного j-го
виду
необхідно
виготовляти
в процесі
виробництва,
щоб максимізувати
загальну виручку
від реалізації
продукції
підприємства.
Причому відомі:
загальна кількість
ресурсів –
,
нормативи
використання
кожного і-го
виду ресурсу
на кожен j-ий
вид продукції
–
,
а також
– ціна реалізації
одиниці продукції.
Розглянемо
тепер ту саму
задачу з іншої
точки зору.
Припустимо,
що за певних
умов доцільно
продавати деяку
частину чи всі
наявні в господарстві
ресурси. Необхідно
визначити
цінність ресурсів.
Кожному ресурсу
поставимо у
відповідність
його оцінку
.
Умовно вважатимемо,
що
– ціна одиниці
і-го ресурсу.
На виготовлення
одиниці j-го
виду продукції
витрачається
згідно моделі
всі m видів ресурсів
у кількості
відповідно
.
Оскільки ціни
одиниці кожного
виду ресурсів
за припущенням
дорівнюють
,
то загальна
вартість ресурсів,
що витрачені
на виробництво
одиниці j-го
виду продукції
обчислюється
як
![]()
Продавати ресурси доцільно лише за умови, що кошти отримані в результаті продажу ресурсів будуть дорівнювати або