Симплекс-метод розв’язування задач ЛП. Початковий опорний план
Початковий опорний план
Початковий опорний план з одиничним базисом можна отримати, розв'язавши допоміжну задачу
Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m(-y_{n+i})\to\max ,
при обмеженнях
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^na_{ij}x_j+y_{n+i}=b_i,i=1,\ldots,n
Неможливо розібрати вираз (невідома помилка): y_{n+1}\geq0,i=1,\ldots,m
Неможливо розібрати вираз (невідома помилка): x_j\geq0,j=1,\ldots,n
яка містить одиничний базис, який складається із векторів Неможливо розібрати вираз (невідома помилка): A_{n+1},\ldots,A_{n+m}
. Цим векторам відповідають штучні змінні із значеннями y'_{n+i}=b_i,i=1,\ldots,m. Якщо в оптимальному розв'язку цієї задачі Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^my_{n+i}>0
, вихідна задача не має розв'язку. Якщо ж Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^my_{n+i}=0
та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення Неможливо розібрати вираз (невідома помилка): z_0
може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних Неможливо розібрати вираз (невідома помилка): \bar{x_l}
дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин Неможливо розібрати вираз (невідома помилка): b_i
на Неможливо розібрати вираз (невідома помилка): b_i + \varepsilon_i
, де Неможливо розібрати вираз (невідома помилка): \varepsilon_i
достатньо малі, при вдалому виборі Неможливо розібрати вираз (невідома помилка): \varepsilon_i не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.
Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця Неможливо розібрати вираз (невідома помилка): A^{-1} , обернена до базисної матриці.
Приклад побудови початкового опорного плану
Продукція чотирьох видів А, В, С і Д проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду задано таблицею.
| Верстат | Тривалість обробки, год, одиниці продукції | |||
| А | В | С | Д | |
| 1 | 2 | 3 | 4 | 2 |
| 2 | 3 | 2 | 1 | 2 |
Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-год становить 10 дол. для верстата 1 і 15 дол. — для верстата 2. Можливий час використання верстатів обмежений: для верстата 1 він становить 450 машино-год, а для верстата 2 — 380 машино-год. Ціна одиниці продукції кожного виду дорівнює відповідно 73, 70, 55 та 45 дол.
Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний чистий прибуток.
Нехай Неможливо розібрати вираз (невідома помилка): x_j
— план виробництва продукції j-го виду, де j може набувати значень від 1 до 4.
Умовами задачі будуть обмеження на час використання верстатів для виробництва продукції всіх видів:
для верстата 1 - Неможливо розібрати вираз (невідома помилка): 2x_1 + 3x_2 + 4x_3 + 2x_4 \leq 450
(машино-год);
для верстата 2 - Неможливо розібрати вираз (невідома помилка): 3x_1 + 2x_2 + x_3 + 2x_4 \leq 380
(машино-год);
Цільова функція задачі визначається як загальний чистий прибуток від реалізації готової продукції і складається з різниці між ціною та собівартістю виготовлення продукції кожного виду:
Неможливо розібрати вираз (невідома помилка): Z = (73 - (2*10 + 3*15))x_1 + (70 - (3*10 + 2*15))x_2 + (55 - (4*10 + 1*15))x_3 + (45 - (2*10 + 2*15))x_4
Неможливо розібрати вираз (невідома помилка): Z = 8x_1 + 10x_2 + 0x_3 - 5x_4
Отже математична модель поставленої задачі має вигляд:
Неможливо розібрати вираз (невідома помилка): \max (8x_1 + 10x_2 - 5x_4)
Неможливо розібрати вираз (невідома помилка): \begin{cases} 2x_1 + 3x_2 + 4x_3 + 2x_4 \leq 450, \\ 3x_1 + 2x_2 + x_3 + 2x_4 \leq 380, \end{cases}
Неможливо розібрати вираз (невідома помилка): x_j \geq 0, j = \bar{1,4}.
Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні Неможливо розібрати вираз (невідома помилка): x_5
та Неможливо розібрати вираз (невідома помилка): x_6
Неможливо розібрати вираз (невідома помилка): \begin{cases} 2x_1 + 3x_2 + 4x_3 + 2x_4 + x_5 & = 450, \\ 3x_1 + 2x_2 + x_3 + 2x_4 + x_6 & = 380, \end{cases}
Неможливо розібрати вираз (невідома помилка): x_j \geq 0, j = \bar{1,6}
Ці додаткові змінні за економічним змістом означають можливий, але не використаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:
Неможливо розібрати вираз (невідома помилка): \max (8x_1 + 10x_2 + 0x_3 - 5x_4 + 0x_5 + 0x_6)
Канонічну систему обмежень задачі запишемо у векторній формі:
Неможливо розібрати вираз (невідома помилка): x_1 * \vec{A_1} + x_2 * \vec{A_2} + x_3 * \vec{A_3} + x_4 * \vec{A_4} + x_5 * \vec{A_5} + x_6 * \vec{A_6} = \vec{A_0} ,
де
Неможливо розібрати вираз (невідома помилка): \vec{A_1} = \begin{pmatrix}2 \\ 3\end{pmatrix}, \vec{A_2} = \begin{pmatrix}3 \\ 2\end{pmatrix}, \vec{A_3} = \begin{pmatrix}4 \\ 1\end{pmatrix}, \vec{A_4} = \begin{pmatrix}2 \\ 2\end{pmatrix}, \vec{A_5} = \begin{pmatrix}1 \\ 0\end{pmatrix}, \vec{A_6} = \begin{pmatrix}0 \\ 1\end{pmatrix}, \vec{A_0} = \begin{pmatrix}450 \\ 380\end{pmatrix} .
Оскільки вектори Неможливо розібрати вираз (невідома помилка): \vec{A_5}
та Неможливо розібрати вираз (невідома помилка): \vec{A_6}
одиничні та лінійно незалежні, саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі Неможливо розібрати вираз (невідома помилка): x_5
та Неможливо розібрати вираз (невідома помилка): x_6
, що відповідають одиничним базисним векторам, називають базисними, а решту — вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:
Неможливо розібрати вираз (невідома помилка): x_1 = x_2 = x_3 = x_4 = 0,
Неможливо розібрати вираз (невідома помилка): x_5 = 450,
Неможливо розібрати вираз (невідома помилка): x_6 = 380
.
Згідно з визначеними Неможливо розібрати вираз (невідома помилка): x_j(j=\bar{1,6})
векторна форма запису системи обмежень задач матиме вигляд:
Неможливо розібрати вираз (невідома помилка): 0 * \vec{A_1} + 0 * \vec{A_2} + 0 * \vec{A_3} + 0 * \vec{A_4} + 450 * \vec{A_5} + 380 * \vec{A_6} = \vec{A_0}
Оскільки додатні коефіцієнти Неможливо розібрати вираз (невідома помилка): x_5
та Неможливо розібрати вираз (невідома помилка): x_6 відповідають лінійно незалежним векторам, то за означенням:
Неможливо розібрати вираз (невідома помилка): x_0 = (0;0;0;0;450;380)
є опорним планом задачі і для цього початкового плану
Неможливо розібрати вираз (невідома помилка): Z_0 = 8 * 0 + 10 * 0 - 5 * 0 + 0 * 450 + 0 * 380 = 0
Список використаної літератури
- Симплекс-метод
- Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
- Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003.- 452 с.
- Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.1. - Мн.: БГУИР, 1995.
- Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.2. - Мн.: БГУИР, 1996.
