Вибір методу розвязання багатокритеріальної задачі лінійного програмування. Симплекс метод

Проаналізувавши різні методи розвязанням багатокритеріальних задач лінійного програмування, я обрала Симплекс-метод.

В останні роки в прикладній математиці велика увага приділяється новому класу задач оптимізації, які полягають у знаходженні в заданій області точок найбільшого або найменшого значення певної функції, що залежить від великого числа змінних. Це так звані завдання математичного програмування, що виникають у найрізноманітніших галузях людської діяльності і перш за все в економічних дослідженнях, в практиці планування і організації виробництва. Вивчення цього кола завдань і методів їх вирішення призвело до створення нової наукової дисципліни, що отримала пізніше назву лінійного програмування. В кінці 40-х років американським математиком Дж. Данцигом був розроблений ефективний метод вирішення даного класу завдань - симплекс-метод. До завдань, що вирішуються цим методом у межах математичного програмування належать такі типові економічні завдання як «Визначення найкращого складу суміші», «Завдання про оптимальний плані випуску продукції», «Оптимізація міжгалузевих потоків», «Завдання про вибір виробничої програми», «Транспортна задача» , «Завдання розміщення», «Модель Неймана розширюється економіки» та інші. Вирішення таких завдань дає великі вигоди як народному господарству в цілому, так і окремих його галузях.

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

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

Застосування симплекс-методу для задачі лінійного програмування передбачає попереднє приведення її формальної постановки до канонічної форми з n невідємними змінними: (X 1, ..., X n), де потрібно мінімізація лінійної цільової функції при m лінійних обмеженнях типу рівностей. Серед змінних завдання вибирається початковий базис з m змінних, для визначеності (X 1, ..., X m), які повинні матиневідємні значення, коли решта (nm) вільні змінні рівні 0. Цільова функція та обмеження рівності перетворяться до діагональної формі щодо базисних змінних, змінних, де кожна базисна змінна входить лише в одне рівняння з коефіцієнтом 1.

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

Верхній рядок симплекс-таблиці представляє цільову функцію завдання. Кожен рядок симплекс-таблиці, крім першої, відповідаєпевному обмеженню-рівності завдання. Вільні члени обмежень складають крайній лівий стовпець таблиці. Зліва від таблиці записані поточні базисні змінні (X 1, ..., X m). Зверху від таблиці наведено набір всіх змінних задачі, де X m +1, ..., X n - вільні змінні завдання.

На початковому кроці алгоритму симплекс-методу має бути вибрано базисне допустиме рішення (X 1, ..., X m)> = 0 при X j = 0 (j = m +1, ..., n), отже, всі вільні члени обмежень A i, 0> = 0 (i = 1, ..., m). Коли ця умова виконана, симплекс-таблиця називається прямо-допустимої, тому що в цьому випадку базисні змінні, рівні A i, 0, визначають дозволене рішення прямої задачі лінійного програмування.Якщо всі коефіцієнти цільової функції A 0, j> = 0 (j = 1, ..., m), то симплекс-таблиця називається двояко-допустимої, оскільки відповіднерішення є допустимим для двоїстої задачі лінійного програмування.

Якщо симплекс-таблиця є одночасно прямо і двояко допустимої, тобто одночасно всі A i, 0> = 0 і A 0, j> = 0, то рішення оптимально.

Дійсно, оскільки допустимими є лише невідємні значення керованих параметрів, то зміна цільової функції за рахунок варіації вільних змінних, через які вона виражена, можливо тільки в бік збільшення, тобто, буде погіршуватися. Якщо серед її коефіцієнтів є A 0, j <0, то значення цільової функції ще можна зменшити (т.e. поліпшити), збільшуючи значення будь-якої вільної змінної X j з негативним коефіцієнтом A 0, j при побічну зменшенні базисних змінних, щоб залишалися справедливі обмеження завдання. Теоретично можна використовувати будь-яку вільну змінну X j з A 0, j <0, але на практиці зазвичай діють у відповідності зі стратегією найшвидшого спуску, вибираючи мінімальний елемент A 0, p <0 з усіх негативних A 0, j <& nbsp0:

A 0, p = min A 0, j <0.

j

Стовпець p симплекс-таблиці, що відповідає обраному коефіцієнту A 0, p <0, називається провідним стовпцем. Вільна мінлива ведучого шпальти повинна бути введена в базис замість однієї з поточних базисних змінних. Очевидно, з базису слід виключити таку зміннуX q, яка раніше інших звертається в нуль при збільшенні змінної X p ведучого шпальти.

Її індекс легко визначити, якщо серед позитивних елементів ведучого шпальти p знайти елемент, здатний мінімізувати відношення (Ai, 0 / A i, p):

A q, 0 A i, 0

------ = Min ------, i = 1 ,..., m.

A q, p i A i, p

Елемент A q, p називається провідним елементом, c Троках q симплекс-таблиці, що містить ведучий елемент, називається, відповідно,провідною рядком. Змінна провідною рядки X q замінюється в базисі змінної ведучого шпальти X p і стає вільною змінної з значенням 0, у той час як нова базисна змінна X p досягне максимально можливого значення, рівного: max X p = (A q, 0 / A q, p).

Після зазначеного взаємного обміну змінними X p і X q між наборами вільних і базисних змінних потрібно модифікувати вихідну канонічну модель задачі шляхом приведення її до діагональної формі щодо нової множини базисних змінних. Для зазначеного перетворення можна формально використовувати процедуру виключення Гауса, яка, як відомо, складається з двох елементарних операцій, що застосовуються до системи алгебраїчних рівнянь (в даному випадку обмежень - рівностей) :

множення рівняння E 1 (X) = 0 на константу K 1 і заміна рівняння E 1 (X) = 0 рівнянням K 1 * E 1 (X) = 0;

складання рівнянь E 1 (X) = 0 і E 2 (X) = 0 c наступною заміною рівняння E 2 (X) = 0 рівнянням E 1 (X) + E 2 (X) = 0.

Винятки Гауса дозволяють привести систему рівнянь до діагональної формі щодо бажаного безлічі змінних. У даному випадку виключення Гауса застосовується так, щоб всі елементи симплекс-таблиці у провідному стовпці, крім ведучого елемента A q, p, стали нульовими, а ведучий елемент став рівним одиниці:

A i, p = 0, якщо i не дорівнює q

і

A i, p = 1, якщо i = q.

Зазначені кроки симплекс-методу повторюються, поки не буде отримана симплекс-таблиця, яка одночасно є прямо і двояко допустимої. Якщо покладе в такій симплекс-таблиці поточні базисні змінні рівними A i, 0, а вільні - нулю, то буде отримано оптимальне рішення.

Практика застосування симплекс методу показала, що кількість ітерацій, необхідних для вирішення задачі лінійного програмування зазвичай коливається від 2m до 3m, хоча для деяких спеціально побудованих завдань обчислення за правилами симплекс методу перетворюються на прямий перебір базисних допустимих рішень. Проте, важкі для симплекс методу завдання на практиці зустрічаються украй рідко, що пояснює широке розповсюдження і більшу популярність даного методу лінійного програмування в порівнянні з іншими підходами.