Відмінності між версіями «Симплекс-метод розв’язування задач ЛП. Початковий опорний план»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показано 28 проміжних версій цього учасника)
Рядок 1: Рядок 1:
−
== Вступ ==
+
== Початковий опорний план ==
−
Симплекс-метод - алгоритм рішення оптимізаційної задачі лінійного програмування шляхом перебору вершин опуклого багатогранника в багатовимірному просторі. Метод був розроблений американським математиком Джорджем Данцигом (George Dantzig) в 1947 році.
+
−
Задача лінійного програмування полягає в тому, що необхідно максимізувати або мінімізувати деякий лінійний функціонал на багатовимірному просторі при заданих лінійних обмеженнях.
+
  
−
Зауважимо, що кожне з лінійних нерівностей на змінні обмежує півпростір у відповідному лінійному просторі. В результаті всі нерівності обмежують деякий багатогранник (можливо, нескінченний), називаний також поліедральних конусом. Рівняння <math>W(x) = c</math>, де <math>W(x)</math> - максімізіруемий (або мінімізіруемий) лінійний функціонал, породжує гіперплоскость <math>L(c)</math>. Залежність від <math>c</math> породжує сімейство паралельних гіперплоскостей. Тоді екстремальна задача набуває наступне формулювання - потрібно знайти таке найбільше <math>c</math>, що гіперплоскость <math>L(c)</math> перетинає багатогранник хоча б в одній точці. Зауважимо, що перетин оптимальної гіперплоскості і багатогранника буде містити хоча б одну вершину, причому, їх буде більше однієї, якщо перетин містить ребро або k-мірну грань. Тому максимум функціоналу можна шукати в вершинах багатогранника. Принцип симплекс-методу полягає в тому, що вибирається одна з вершин багатогранника, після чого починається рух по його ребрах від вершини до вершини в бік збільшення значення функціоналу. Коли перехід по ребру з поточної вершини в іншу вершину з більш високим значенням функціоналу неможливий, вважається, що оптимальне значення c знайдено.
+
Початковий опорний план з одиничним базисом можна отримати, розв'язавши допоміжну задачу
−
Послідовність обчислень симплекс-методом можна розділити на дві основні фази:
+
−
*знаходження вихідної вершини безлічі припустимих рішень,
+
−
*послідовний перехід від однієї вершини до іншої, що веде до оптимізації значення цільової функції.
+
−
При цьому в деяких випадках оригінал рішення очевидно або його визначення не вимагає складних обчислень, наприклад, коли всі обмеження представлені нерівностями виду "менше або дорівнює" (тоді нульовий вектор абсолютно точно є припустимим рішенням, хоча і, швидше за все, далеко не найбільш оптимальним) . У таких завданнях першу фазу симплекс-методу можна взагалі не проводити. Симплекс-метод, відповідно, ділиться на однофазний і двофазний.
+
  
−
Основна ідея симплекс-метода полягає в тому, що екстремум цільової функції завжди досягається в кутових точках області допустимих рішень. Симплекс-метод, званий також методом послідовного поліпшення плану, реалізує перебір кутових точок області допустимих рішень у напрямі поліпшення значення цільової функції. Основна ідея цього методу наступна. Перш за все, знаходиться яке-небудь допустиме початкове (опорное) рішення, тобто яка-небудь кутова точка області допустимих рішень. Процедура методу дозволяє відповісти на питання, чи є це рішення оптимальним. Якщо "так", то завдання вирішене. Якщо "ні", то виконується перехід до суміжної кутової точки області допустимих рішень, де значення цільової функції поліпшується, тобто до негіршого допустимого рішення. Якщо деяка кутова крапка має декілька суміжних, то обчислювальна процедура методу забезпечує перехід до тієї з них, для якої поліпшення цільової функції буде найбільшим. Процес перебору кутових точок області допустимих рішень повторюється, поки не буде знайдена крапка, якою відповідає екстремум цільової функції Е.
+
<math>\sum_{i=1}^m(-y_{n+i})\to\max</math>,
  
−
При побудові початкового базису в заданому завданні використовувався метод штучного базису, тому знайдене рішення не є допустимим. В цьому випадку для вирішення завдання необхідно використовувати двохетапний симплекс-метод.
+
при обмеженнях
  
−
Двохетапний симплекс-метод. Завдання за допомогою цього методу вирішується в два етапи: спочатку відшукується початкове допустиме рішення, що не містить штучних змінних, а потім на основі знайденого рішення шукається оптимальне рішення початкової задачі. Основні кроки, реалізації методу наступні.
+
<math>\sum_{j=1}^na_{ij}x_j+y_{n+i}=b_i,i=1,\ldots,n</math>
−
#Завдання лінійного програмування зводиться до стандартної форми.
+
 
−
#Будується штучний базис.
+
<math>y_{n+1}\geq0,i=1,\ldots,m</math>
−
#Складається штучна цільова функція: сума всіх штучних змінних.
+
 
−
#Реалізується перший етап двохетапного методу: за допомогою звичайних процедур симплекс-метода виконується мінімізація штучної цільової функції. Якщо її мінімальне значення рівне 0, то відповідне рішення є допустимим рішенням початкової задачі. Очевидно, що при нульовому значенні штучної цільової функції всі штучні змінні також нульові (оскільки штучна цільова функція - їх сума, і всі вони ненегативні). Якщо мінімальне значення штучної цільової функції виявляється відмінним від нуля, це означає, що завдання не має допустимих рішень.
+
<math>x_j\geq0,j=1,\ldots,n</math>
−
#Реалізується другий етап двохетапного методу: знайдене на кроці 4 допустиме рішення використовується як початкове рішення початкової задачі для пошуку її оптимального рішення.
+
 
 +
яка містить одиничний базис, який складається із векторів <math>A_{n+1},\ldots,A_{n+m}</math>. Цим векторам відповідають штучні змінні із значеннями y'_{n+i}=b_i,i=1,\ldots,m. Якщо в оптимальному розв'язку цієї задачі <math>\sum_{i=1}^my_{n+i}>0</math>, вихідна задача не має розв'язку. Якщо ж <math>\sum_{i=1}^my_{n+i}=0</math> та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення <math>z_0</math> може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних <math>\bar{x_l}</math> дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин <math>b_i</math> на <math>b_i + \varepsilon_i</math>, де <math>\varepsilon_i</math> достатньо малі, при вдалому виборі <math>\varepsilon_i</math> не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.
 +
 
 +
Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця <math>A^{-1}</math>, обернена до базисної матриці.
 +
 
 +
== Приклад побудови початкового опорного плану ==
 +
Продукція чотирьох видів А, В, С і Д проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду задано таблицею.
 +
 
 +
{|border="1"
 +
|rowspan="2" |Верстат
 +
|colspan="4" |Тривалість обробки, год, одиниці продукції
 +
|-
 +
|А
 +
|В
 +
|С
 +
|Д
 +
|-
 +
|1
 +
|2
 +
|3
 +
|4
 +
|2
 +
|-
 +
|2
 +
|3
 +
|2
 +
|1
 +
|2
 +
|}
 +
 
 +
Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-год становить 10 дол. для верстата 1 і 15 дол. — для верстата 2. Можливий час використання верстатів обмежений: для верстата 1 він становить 450 машино-год, а для верстата 2 — 380 машино-год. Ціна одиниці продукції кожного виду дорівнює відповідно 73, 70, 55 та 45 дол.
 +
 
 +
Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний чистий прибуток.
 +
 
 +
Нехай <math>x_j</math> — план виробництва продукції j-го виду, де j може набувати значень від 1 до 4.
 +
 
 +
Умовами задачі будуть обмеження на час використання верстатів для виробництва продукції всіх видів:
 +
 
 +
для верстата 1 - <math>2x_1 + 3x_2 + 4x_3 + 2x_4 \leq 450</math> (машино-год);
 +
 
 +
для верстата 2 - <math>3x_1 + 2x_2 + x_3 + 2x_4 \leq 380</math> (машино-год);
 +
 
 +
Цільова функція задачі визначається як загальний чистий прибуток від реалізації готової продукції і складається з різниці між ціною та собівартістю виготовлення продукції кожного виду:
 +
 
 +
<math>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</math>
 +
 
 +
<math>Z = 8x_1 + 10x_2 + 0x_3 - 5x_4</math>
 +
 
 +
Отже математична модель поставленої задачі має вигляд:
 +
 
 +
<math>\max (8x_1 + 10x_2 - 5x_4)</math>
 +
 
 +
<math>\begin{cases}
 +
2x_1 + 3x_2 + 4x_3 + 2x_4 \leq 450, \\
 +
3x_1 + 2x_2 + x_3 + 2x_4 \leq 380,
 +
\end{cases}
 +
</math>
 +
 
 +
<math>x_j \geq 0, j = \bar{1,4}.</math>
 +
 
 +
Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні <math>x_5</math> та <math>x_6</math>:
 +
 
 +
<math>\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}
 +
</math>
 +
 
 +
<math>x_j \geq 0, j = \bar{1,6}</math>
 +
 
 +
Ці додаткові змінні за економічним змістом означають можливий, але не використаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:
 +
 
 +
<math>\max (8x_1 + 10x_2 + 0x_3 - 5x_4 + 0x_5 + 0x_6)</math>
 +
 
 +
Канонічну систему обмежень задачі запишемо у векторній формі:
 +
 
 +
<math>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}</math>,
 +
 
 +
де
 +
 
 +
<math>\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}</math>.
 +
 
 +
Оскільки вектори <math>\vec{A_5}</math> та <math>\vec{A_6}</math> одиничні та лінійно незалежні, саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі <math>x_5</math> та <math>x_6</math>, що відповідають одиничним базисним векторам, називають базисними, а решту — вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:
 +
 
 +
<math>x_1 = x_2 = x_3 = x_4 = 0,</math>
 +
 
 +
<math>x_5 = 450,</math>
 +
 
 +
<math>x_6 = 380</math>.
 +
 
 +
Згідно з визначеними <math>x_j(j=\bar{1,6})</math> векторна форма запису системи обмежень задач матиме вигляд:
 +
 
 +
<math>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}</math>
 +
 
 +
Оскільки додатні коефіцієнти <math>x_5</math> та <math>x_6</math> відповідають лінійно незалежним векторам, то за означенням:
 +
 
 +
<math>x_0 = (0;0;0;0;450;380)</math>
 +
 
 +
є опорним планом задачі і для цього початкового плану
 +
 
 +
<math>Z_0 = 8 * 0 + 10 * 0 - 5 * 0 + 0 * 450 + 0 * 380 = 0</math>
 +
 
 +
== Список використаної літератури ==
 +
#[http://uk.wikipedia.org/wiki/Симплекс-метод Симплекс-метод]
 +
#Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
 +
#Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003.- 452 с.
 +
#Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.1. - Мн.: БГУИР, 1995.
 +
#Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.2. - Мн.: БГУИР, 1996.

Поточна версія на 19:18, 4 травня 2012

Початковий опорний план

Початковий опорний план з одиничним базисом можна отримати, розв'язавши допоміжну задачу

Неможливо розібрати вираз (невідома помилка): \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


Список використаної літератури

  1. Симплекс-метод
  2. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
  3. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003.- 452 с.
  4. Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.1. - Мн.: БГУИР, 1995.
  5. Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.2. - Мн.: БГУИР, 1996.
Отримано з https://wiki.cusu.edu.ua/index.php?title=Симплекс-метод_розв’язування_задач_ЛП._Початковий_опорний_план&oldid=66847