Статьи по экономическим темам
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

ОДНЕ ВДОСКОНАЛЕННЯ СИМПЛЕКСНОГО МЕТОДУ

Для вивчення економічних процесів досить часто використовують їх спрощений формалізований опис. Прикладом такої фор­малізації є поширене застосування для опису функціонування економічних об’єктів задач лінійного програмування. Навіть у складніших випадках, які приводять до дробово-лінійних, цілочисельних та стохастичних задач, для розв’язання їх зводять до лінійного випадку і застосовують відому обчислювальну процедуру — симплексний метод. Це ітеративна схема, що дозволяє здійснити впорядкований перехід від одного опорного плану до іншого та за скінченне число кроків отримати оптимальний план або встановити відсутність розв’язку. Симплексний метод є ефективною, досить простою процедурою, проте не позбавленою деяких недоліків. Цей факт пояснює численні спроби модифікації симплексного методу, які можна зустріти в літературі, наприклад [1, 2]. В основному вдосконалення симплексного методу стосуються факту зменшення кількості обчислень при переході від одного опорного плану до іншого. Проте залишається «непоміченим» недолік, що в найпростішому випадку може бути проілюстрований наступним чином.

Нехай необхідно знайти максимальне значення лінійного функ­ціоналу Z = C1x1 + C2x2 на багатокутникові допустимих розв’язків, що показано на рисунку.

Причому С2 > С1, а також Δx1 · C1 > Δx2 · C2. Припустимо, що початковий опорний план відповідає кутовій точці А, тоді наступ­ний крок симплексного методу приведе до точки Q, (Z(Q) > Z(A)) і в результаті наступної ітерації до точки К, де лінійна функція досягає максимального значення. Проте, якщо опорний план буде взято точку В, то включення вектора в базис по критерію minθ0j(Zj – Cj) приводить до того, що пряма С1x1 + С2x2 = const проходитиме через точку С і алгоритм симплексного метода приведе до точок D, E, F, K, тобто для отримання оптимального плану необхідно буде виконати ще чотири ітерації.

Отже, очевидно: кількість ітерацій при реалізації симплексного алгоритму визначається початковим опорним планом та кількістю кутових точок, що траплятимуться на шляху прямої С1x1 + С2x2 = const.

Наведемо модифікацію симплексного методу, що дає змогу позбутись згаданого недоліку.

Розглянемо задачу лінійного програмування, записану в канонічній формі:

(1)

або

(2)

Припустимо, що базисним розв’язком є перші m змінних. Тоді система обмежень матиме вигляд:

(3)

При цьому симплексна таблиця буде:

   

x1

x2

 

xm

xm + 1

...

xn

с0

0

0

...

0

с0, m + 1

...

c0n

х1

b01

1

0

   

a1, m + 1

...

a1n

x2

b02

0

1

   

a2, m + 1

...

a2n

       

...

       
       

...

       

xm

b0m

     

1

am, m + 1

...

amn

Стандартний симплексний метод передбачає вибір ведучого стовпчика s такий, для якого виконується умова c0s = minc0j < 0 , ведучого рядка r такий, для якого знайдено ars, що відповідає .

Уведемо позначення: , та .

Якщо М = Ø, оптимальний план знайдено, а коли знайдеться хоча б одна Мj = Ø, то задача не має розв’язку.

Модифікація симплексного методу відбувається за рахунок іншого способу визначення змінної, що має ввійти в базис, та змінної, що вийде з базису, а саме: ведучими обираються той стовпчик і рядок, які відповідають значенню

. (4)

Вибір заміни базисних змінних саме таким чином запобігає вказаному недоліку за рахунок усунення «зайвих» кутових точок, які необхідно розглянути на шляху до оптимуму та переходу саме до тієї кутової точки, що розташована найближче до оптимального розв’язку (хоча за відомим критерієм оптимальності необхідно вводити зовсім іншу змінну).

Доведемо вірність твердження (3).

Припустимо, що на наступному кроці в базис необхідно ввести змінну xm + 1 = > 0. Функціонал при цьому прийматиме значення

, (5)

тобто значення функціоналу зросло на величину (–tc0, m + 1). Система обмежень набуде вигляду:

(6)

або в загальному вигляді: . Звідси . Оскільки t > 0 і з усіх розглядаємо ті значення, для яких , величина зменшує значення змінної. Для задачі лінійного програмування з базису вилучається та змінна xi, яка перша при збільшенні t перетворюється на нуль. Тобто

.

Тому .

Як показано раніше, значення функціоналу (5) збільшується саме на величину (–tc0, m + 1), тобто на величину . Оскільки задача розв’язується на максимум, то вираз (5) набуватиме найбільшого значення, коли серед (–tc0j), буде обрано максимальну величину. Тобто приходимо до твердження, яке і необхідно було довести: максимального значення функціонал набуватиме при введені в базис змінної xrs, де значення r та s, визначають з (4).

Зазначений підхід дає можливість також спростити процес побудови початкового опорного плану. Відомий спосіб визначення опорного плану, який в більшості випадків використовує метод штучного базису, суттєво спрощується. Як опорний план обираємо довільний допустимий розв’язок, що означає можливість існування серед від’ємних значень.

Як цільову функцію обираємо xi.

Позначимо . Якщо , значить, допустимих розв’язків не існує. Інакше, розглянемо .

Для переходу до нового розв’язку використаємо умову, аналогічну (4), у вигляді:

. (7)

У результаті цієї процедури від’ємні значення bs збільшуватимуться, причому не з’явиться нових від’ємних значень. Після скінченої кількості кроків приходимо до оптимального розв’язку, де всі bs > 0.

Необхідно відмітити, що з практичної точки зору застосування даного модифікованого алгоритму для розв’язання задачі лінійного програмування дасть змогу суттєво підвищити точність розрахунків. Очевидно, що застосування сучасної обчислювальної техніки та програмних продуктів не дасть значного виграшу в часі при реалізації модифікованого симплексного методу порівняно зі стандартним. Однак головною проблемою здійснення обчислень за допомогою ЕОМ залишається не швидкість, а точність розрахунків. На кожній ітерації отриманий план маємо з деяким рівнем точності. Наступна ітерація, в свою чергу, приводить до нових наближених значень, чим остаточно нагромаджує значну похибку. Реальні економічні задачі складаються з тисяч обмежень та змінних. Вказана модифікація симплексного методу, реалізована на ЕОМ, зменшить у декілька разів кількість ітерацій за рахунок здатності вдосконаленого симплексного методу обирати найкоротший шлях до оптимуму, чим відповідно збільшить точність обчислень.

Література

1. Банди Б. Основы линейного программирования. — М.: Радио и связь, 1989. — 174 с.

2. Конюховский П. В. Математические методы исследования операций в экономике. — СПб.: Питер, 2000. — 208 с.

3. Ху Т. Целочисленное программирование и потоки в сетях. — М.: Мир, 1974. — 520 с.

В. О. Кутовий, канд. фіз.-мат. наук, доцент;

С. С. Савіна, канд. екон. наук, ст. викладач Київський національний економічний університет

Добавить комментарий


Защитный код
Обновить