Алгоритм симплекс-методу

Вступ

Симплекс-метод - алгоритм рішення оптимізаційної задачі лінійного програмування шляхом перебору вершин опуклого багатогранника в багатовимірному просторі. Метод був розроблений американським математиком Джорджем Данцигом (George Dantzig) в 1947 році.

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

Зауважимо, що кожне з лінійних нерівностей на змінні обмежує півпростір у відповідному лінійному просторі. В результаті всі нерівності обмежують деякий багатогранник (можливо, нескінченний), називаний також поліедральних конусом. Рівняння W (x) = c, де W (x) - максімізіруемий (або мінімізіруемий) лінійний функціонал, породжує гіперплоскость L (c). Залежність від c породжує сімейство паралельних гіперплоскостей. Тоді екстремальна задача набуває наступне формулювання - потрібно знайти таке найбільше c, що гіперплоскость L (c) перетинає багатогранник хоча б в одній точці. Зауважимо, що перетин оптимальної гіперплоскості і багатогранника буде містити хоча б одну вершину, причому, їх буде більше однієї, якщо перетин містить ребро або k-мірну грань. Тому максимум функціоналу можна шукати в вершинах багатогранника. Принцип симплекс-методу полягає в тому, що вибирається одна з вершин багатогранника, після чого починається рух по його ребрах від вершини до вершини в бік збільшення значення функціоналу. Коли перехід по ребру з поточної вершини в іншу вершину з більш високим значенням функціоналу неможливий, вважається, що оптимальне значення c знайдено.

Послідовність обчислень симплекс-методом можна розділити на дві основні фази:

· знаходження вихідної вершини безлічі припустимих рішень,

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

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

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

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

Двохетапний симплекс-метод. Завдання за допомогою цього методу вирішується в два етапи: спочатку відшукується початкове допустиме рішення, що не містить штучних змінних, а потім на основі знайденого рішення шукається оптимальне рішення початкової задачі. Основні кроки, реалізації методу наступні.

1. Завдання лінійного програмування зводиться до стандартної форми.

2. Будується штучний базис.

3. Складається штучна цільова функція: сума всіх штучних змінних.

4. Реалізується перший етап двохетапного методу: за допомогою звичайних процедур симплекс-метода виконується мінімізація штучної цільової функції. Якщо її мінімальне значення рівне 0, то відповідне рішення є допустимим рішенням початкової задачі. Очевидно, що при нульовому значенні штучної цільової функції всі штучні змінні також нульові (оскільки штучна цільова функція - їх сума, і всі вони ненегативні). Якщо мінімальне значення штучної цільової функції виявляється відмінним від нуля, це означає, що завдання не має допустимих рішень.

5. Реалізується другий етап двохетапного методу: знайдене на кроці 4 допустиме рішення використовується як початкове рішення початкової задачі для пошуку її оптимального рішення.

1. Симплекс таблиця

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

В основі симплекс-методу є процес побудови початкової симплекс-таблиці, та перехід від однієї симплекс-таблиці до наступної згідно певних правил. Такі переходи виконуються доти, доки не буде виконано критерій оптимальності або не стане зрозумілим, що розв'язку не існує. Перехід від однієї симплекс-таблиці до наступної здійснюється наступним чином. Згідно певних критеріїв вибирається провідний елемент таблиці (b_k,l), який стоїть на перетині рядка, який виводиться з базису, та стовпчика, який буде введено до базису. Елементи таблиці перераховуються так:

Очевидним чином дану формулу можна спростити до наступної:

тобто всі елементи нової таблиці матимуть вигляд a_i,j / x, де х - провідний елемент попередньої таблиці (зауваження: якщо дроби можна скоротити, то цього НЕ слід робити для правильності подальших міркувань).

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

Таблиця- Симплекс-таблиця

Нехай на другому кроці провідним буде елемент d/x. Тоді елемент a/x перераховується за загальним правилом:

причому легко переконатися, що чисельник (ad-bc)/x буде цілим числом.

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

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

Таблиця- Симплекс-таблиця

Процес переходу від попередньої таблиці до наступної взагалі спрощується: достатньо дописати номер рядка та стовпчика провідного елемента до всіх мінорів таблиці, що стоять у чисельниках, крім елементів того ж рядка, та до всіх мінорів знаменників (в початковій таблиці знаменник рівний одиниці). Але слід звернути увагу на такий випадок: якщо провідний елемент опинився у тому ж рядку, що і раніше введений елемент, то "більш застарілий" слід викинути з мінору, а новий загальним чином дописати в кінець списку рядків та стовпчиків мінору відповідно. Звідси випливає, що рядки в мінорі не можуть повторюватись, тобто їх не може бути більше, ніж рівнянь обмежень, і мінори не будуть нескінченно розростатись.

Але може зустрітися випадок, коли в списку стовпців, з яких складається мінор, зустрінуться однакові стовпці, тобто мінор рівний нулю. Це якраз відповідає нульовим елементам таблиці на відповідному кроці і вписується в загальне правило. За допомогою даного методу можна набагато точніше обчислювати розв'язки задач лінійного програмування без накопичування похибки (при використанні комп'ютера), яка виникає при діленні. Цього можна досягти, якщо зберігати чисельники окремо, а знаменники взагалі завжди однакові.

2. Алгоритм симплекс методу

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

де - номера базисних векторів, а коефіцієнти розкладу векторів , по векторах даного базису.

Усі вказані коефіцієнти потрібно визначати на кожній із ітерацій вичислю вального процесу. Ця необхідність відпадає при розв'язуванні задач лінійного програмування модифікованим симплекс - методом. В цьому випадку на кожній із ітерацій обчислюють вектор

де - матриця обернена до матриці В, складеній із компонентів векторів даного базису, а потім знаходять числа за формулою

Знайдемо компоненти вектора і чисел у випадку розв'язування основної задачі лінійного програмування модифікованим симплекс-методом.

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

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

· по-перше тим, що замість стовпців векторів із відповідними числами записують стовпці векторів , координатами яких являються відповідні стовбці матриці ;

· по-друге в (т+1)-му рядку записують компоненти векторів , а не числа ;

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

Щоб визначити вектор спочатку знаходять вектор . Його компоненти визначають як скалярний добуток вектора на відповідні вектори по формулі. Знайдені компоненти вектора записують у останньому рядку таблиці і у рядку таблиці. Після цього по формулі знаходять елементи (т+1) - го рядка допоміжної таблиці. Якщо серед знайдених чисел (т+1)-го рядка допоміжної таблиці немає від'ємних, то вихідний опорний план виявляється оптимальним. Якщо таке є, то або задача не має розв`язків, або можна перейти до нового опорного плану, при якому значення цільової функції не зменшиться. Для визначення цього вибирають серед від`ємних чисел (т+1)-го рядка таблиці найбільше по абсолютній величині. В такому випадку, коли таких чисел декілька, одне. Нехай таким числом буде . Тоді останній рядок таблиці відводять для вектора . У перших т рядках цього стовпця записують компоненти вектора у базисі . Вони отримуються у результаті множення матриці , записаної у таблиці на вектор компоненти якого вказані у таблиці. Після знаходження чисел виясняють, є серед них додатні чи ні. Якщо таких чисел має, то задача не має розв`язку. Якщо є додатні числа переходять до нового опорного плану задачі. Для цього знаходять .

Нехай . Тоді новий опорний план визначається базисом , отриманим із попереднього виключенням із нього вектора і введенням замість нього вектора . Вважаючи елемент дозвільним, а r-ий рядок і стовпець направляючим, переходять до нової основної таблиці. Перший т стовпець векторів нової таблиці знаходять по відомим правилам переходу від однієї симплекс - таблиці до другої, розглянутим вище. Після того як ці елементи знайдені, знаходять вектор . Компоненти цього вектора записують як і в новій основній таблиці так і в допоміжній таблиці. Потім вираховують числа і перевіряють новий опорний план на оптимальність. Якщо план не оптимальний, то або встановлюють незакінченість попередньої задачі, або переходять до нового опорного плану. Продовжуючи інтеграційний процес, після скінченого числа кроків або знаходять оптимальний план задачі, або встановлюють її нерозв'язність.

Таким чином, процес знаходження розв`язку задачі модифікованим симплекс - методом включає наступні етапи:

1. Знаходять опорний план задачі.

2. Обчислюють матрицю , обернену матриці В, складену із компонентів векторів вихідного базису.

3. Знаходять вектор

4. Обчислюють числа . Якщо усі не від'ємні , то опорний план який ми шукаємо є оптимальним. Якщо серед чисел є від'ємні , то вибирають серед них найбільше по абсолютній величині. Нехай це .

5. Обчислюють компоненти вектора у даному базисі. Якщо серед компонентів вектора немає додатніх, то цільова функція задачі не обмежена на багатьох планах. Якщо серед компонентів вектора є додатні , то переходять до нового опорного плану.

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

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

Таблиця 1.1

Таблиця 1.2

3. Приклад алгоритму симплекс методу

Умова задачі: Знайти мінімум функції

Розв'язок. Побудуємо множину допустимих розв'язків системи нерівностей

Заштрихована область на малюнку є множиною допустимих розв'язків. Червоним показано лінію рівня цільової функції а також вектор-градіент, який має координати (-45;-36). Так як нам потрібно мінімізувати функцію, то будемо рухати лінію рівня в напрямку антіградієнта до перетину з межею допустимої області. Як видно з малюнку це точка (10;10). Вона обведена колом. Таким чином

Для розв'язку задачі симплекс методом запишемо умову задачі в канонічній формі задачі лінійного програмування

Будуємо симплекс таблицю. Як бачимо, розв'язок не допустимий, тому вводимо вільну змінну в базисні

Розв'язок знову не допустимий. Вводимо змінну у базисні

Розв'язок допустимий, але не оптимальний, тому робимо ще один крок.

Розв'язок знову не оптимальний, тому робимо ще один крок

Тепер розв'язок є оптимальним. Розв'язок прямої задачі ,

Сформулюємо двоїсту задачу. Для цього приведемо всі нерівності до вигляду

Тепер можемо сформулювати двоїсту задачу

Відповідність між змінними прямої та двоїстою задачі:

Складаємо симплекс таблицю

Бачимо, що розв'язок не допустимий, тому робимо ще один крок

Розв'язок двоїстою задачі . Оптимальне значення цільової функції

Зауважимо, що рядок коефіцієнтів цільової функції прямої задачі відповідає вільним змінним двоїстої задачі і навпаки. Крім того, максимум цільової функції двоїстою задачі співпадає з мінімумом цільової функції прямої задачі.

Висновок

Симплекс-метод застосовується до рішення будь-якої задачі лінійного програмування[3].

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

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

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

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

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

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

Двоїстий симплекс-метод і симплекс-метод за алгоритмом досить схожі. Однак двоїстий симплекс-метод можна застосовувати при рішенні задач лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при рішенні задачі симплексним методом ці числа передбачалися ненегативними).

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

Нехай

де - одиничні вектори.

Для того, щоб вирішити задачу двоїстим симплекс-методом потрібно виконати дві умови. Спочатку необхідно знайти так званий псевдо план задачі. Рішення системи лінійних рівнянь, приймаючи до уваги базис(одиничні вектори), називається псевдопланом задачі, якщо всі умови даної системи задоволені. Потім рішення зводиться до перевірки отриманого псевдоплану.

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

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

Литература

1. Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. -- М.: Высшая школа, 1986. -- 319 с.

2. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.

3. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти) "Інтелект - Захід", 2004. - 448 с.

4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.

5. Дегтярев Ю.И. Дослідження операцій. - М.: Вища школа, 1986.

6. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: „Рута", 1998.-168 с

7. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.: КНЕУ, 2003.- 452 с.

8. Смородинский С.С., Батин Н.В. Аналіз і оптимізація систем на основі аналітичних моделей. - Мн.: БГУИР, 1997.

9. Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.1. - Мн.: БГУИР, 1995.

10. Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.2. - Мн.: БГУИР, 1996.

11. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций. -- 7-е изд. -- М.: "Вильямс", 2007.