Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Симплекс-метод



План:


Введення

Не плутати з "симплекс-методом" - методом оптимізації довільній функції. Див Метод Нелдера - Міда

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


1. Опис

Перехід від однієї вершини до іншої

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

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

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

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

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


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

2.1. Посилена постановка задачі

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

c ^ Tx \ to max, Ax \ leqslant b, x \ geqslant 0.

Тепер поставимо це завдання в еквівалентній посиленою формі. Необхідно максимізувати Z, де:

\ Begin {bmatrix} 1 &-c ^ T & 0 \ \ 0 & A & E \ end {bmatrix} \ begin {bmatrix} Z \ \ x \ \ x_s \ end {bmatrix} = \ begin {bmatrix} 0 \ \ b \ end {bmatrix}, x, x_s \ geqslant 0

Тут x - змінні з вихідного лінійного функціоналу, x s - нові змінні, що доповнюють старі таким чином, що нерівність переходить в рівність, c - коефіцієнти вихідного лінійного функціоналу, Z - змінна, яку необхідно максимізувати. Півпростору x \ geqslant 0 і x_s \ geqslant 0 в перетині утворюють багатогранник, який представляє безліч допустимих рішень. Різниця між числом змінних і рівнянь дає нам число ступенів свободи. Простіше кажучи, якщо ми розглядаємо вершину багатогранника, то це число ребер, за якими ми можемо продовжувати рух. Тоді ми можемо присвоїти цьому числу змінних значення 0 і назвати їх "непростими". Інші змінні при цьому будуть обчислюватися однозначно і називатися "простими". Отримана точка буде вершиною в перетині відповідних непростим змінним гіперплоскостей. Для того, щоб знайти т. н. Початкова дозволене рішення (вершину, з якої ми почнемо рух), привласнимо всім початковим змінним x значення 0 і будемо їх вважати непростими, а все нові будемо вважати простими. При цьому початкова дозволене рішення обчислюється однозначно: \ Mathbf {x} _ {s i} = \ mathbf {b} _i .


2.2. Алгоритм

Тепер наведемо кроки алгоритму. На кожному кроці ми будемо міняти безлічі простих і непростих векторів (рухатися по ребрах), і матриця буде мати наступний вигляд:

\ Begin {bmatrix} 1 & c_B ^ TB ^ {-1} A - c ^ T & c_B ^ TB ^ {-1} \ \ 0 & B ^ {-1} A & B ^ {-1} \ end { bmatrix} \ begin {bmatrix} Z \ \ x \ \ x_s \ end {bmatrix} = \ begin {bmatrix} c ^ T_BB ^ {-1} b \ \ B ^ {-1} b \ end {bmatrix},

де c B - коефіцієнти вектора c відповідні простим змінним (змінним x s відповідають 0), B - стовпці [\ Mathbf {A} \ mathbf {E}] , Відповідні простим змінним. Матрицю, утворену залишилися стовпцями позначимо D. Чому матриця буде мати такий вигляд пояснимо в описі кроків алгоритму.

Перший крок.

Вибираємо початкове допустиме значення, як зазначено вище. На першому кроці B - одинична матриця, так як простими змінними є x s. C B - нульовий вектор з тих же причин.

Другий крок

Покажемо, що у виразі (C ^ T_BB ^ {-1} A - c ^ T) x + (c_B ^ TB ^ {-1}) x_s тільки непрості змінні мають ненульовий коефіцієнт. Зауважимо, що з виразу Ax + x s = b прості змінні однозначно виражаються через непрості, оскільки кількість простих змінних дорівнює числу рівнянь. Нехай x '- прості, а x' '- непрості змінні на даній ітерації. Рівняння Ax + x s = b можна переписати, як Bx '+ Dx' '= b. Помножимо його на B - 1 ліворуч: x '+ B - 1 D x''= B - 1 b . Таким чином ми висловили прості змінні через непрості, і у виразі B - 1 A x + B - 1 x s , Еквівалентному лівій частині рівності, всі прості змінні мають одиничні коефіцієнти. Тому, якщо додати до рівності Z - c T x = 0 рівність c ^ T_BB ^ {-1} Ax + c_B ^ TB ^ {-1} x_s , То в отриманому рівність всі прості змінні будуть мати нульовий коефіцієнт - всі прості змінні виду x скоротяться, а прості змінні виду x s не увійдуть у вираз c_B ^ TB ^ {-1} x_s .

Виберемо ребро, по якому ми будемо рухатися. Оскільки ми хочемо максимізувати Z, то необхідно вибрати змінну, яка буде більш всіх зменшувати вираз

(C ^ T_BB ^ {-1} A - c ^ T) x + (c_B ^ TB ^ {-1}) x_s .

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

Третій крок

Тепер необхідно зрозуміти, яка проста мінлива першими звернулися до нуль в міру збільшення вхідної змінної. Для цього достатньо розглянути систему:

\ Begin {bmatrix} B ^ {-1} AB ^ {-1} \ end {bmatrix} \ begin {bmatrix} x \ \ x_s \ end {bmatrix} = B ^ {-1} b

При фіксованих значеннях непростих змінних система однозначно розв'язна відносно простих, тому ми можемо визначити, яка з простих змінних перший досягне нуля при збільшенні вхідної. Цю змінну назвемо виходить. Це буде означати, що ми натрапили на нову вершину. Тепер вхідну і вихідну змінну поміняємо місцями - вхідна "увійде" в просту, а виходить з них "вийде" в непрості. Тепер перепишемо матрицю B і вектор c B відповідно до нових наборами простих і непростих змінних, після чого повернемося до другого кроку. X''

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


3. Двофазний симплекс-метод

3.1. Причини використання

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

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


3.2. Модифікація обмежень

Всі обмеження завдання модифікуються відповідно до таких правил:

  • обмеження типу "≤" переводяться на рівності створенням додаткової змінної з коефіцієнтом "+1". Ця модифікація проводиться і в однофазному симплекс-методі, додаткові змінні надалі використовуються як вихідний базис.
  • обмеження типу "≥" доповнюються однієї змінної з коефіцієнтом "-1". Оскільки така мінлива через негативного коефіцієнта не може бути використана у вихідному базисі, необхідно створити ще одну, допоміжну, змінну. Допоміжні змінні завжди створюються з коефіцієнтом "+1".
  • обмеження типу "=" доповнюються однієї допоміжної змінної.

Відповідно, буде створено певну кількість додаткових і допоміжних змінних. У вихідний базис вибираються додаткові змінні з коефіцієнтом "+1" і всі допоміжні. Обережно: рішення, якому відповідає цей базис, не є допустимим.


3.2.1. Відмінності між додатковими і допоміжними змінними

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

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

Тобто ненульове значення додаткової змінної може (але не повинно) сигналізувати про неоптимальності рішення. Ненульове значення допоміжної змінної сигналізує про неприпустимість рішення.


3.3. Фази рішення

Після того, як було модифіковано умова, створюється допоміжна цільова функція. Якщо допоміжні змінні були позначені, як y i, i ∈ {1, .., k}, то допоміжну функцію визначимо, як

z '= \ sum_ {i = 1} ^ k y_i \ to min .

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

Коли буде знайдено оптимальне значення допоміжної цільової функції, можуть виникнути дві ситуації:

  • оптимальне значення z ' більше нуля. Це значить, що як мінімум одна з допоміжних змінних залишилася в базисі. У такому випадку можна зробити висновок, що допустимих рішень даної задачі лінійного програмування не існує.
  • оптимальне значення z ' дорівнює нулю. Це означає, що всі допоміжні змінні були виведені з базису, і поточне рішення є допустимим.

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


4. Модифікований симплекс-метод

5. Двоїстий симплекс-метод

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

Література

  • Хемді А. Таха Глава 3. Симплекс-метод / / Введення в дослідження операцій = Operations Research: An Introduction - 7-е изд. - М .: "Вільямс", 2007. - С. 95-141. - ISBN 0-13-032374-8.
  • Акулич І. Л. Глава 1. Завдання лінійного програмування / / Математичне програмування в прикладах і завданнях - М .: Вища школа, 1986. - 319 с. - ISBN 5-06-002663-9.
  • Томас Х. Кормен та ін Глава 29. Лінійне програмування / / Алгоритми: побудова й аналіз = INTRODUCTION TO ALGORITHMS - 2-е вид. - М .: "Вільямс", 2006. - С. 1296. - ISBN 5-8459-0857-4.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Симплекс
Метод
Метод анкетування
Метод Шехтера
Метод Ейлера
Метод січних
Перенормування (метод)
Метод Бекона
Метод опитування
© Усі права захищені
написати до нас
Рейтинг@Mail.ru