Глава 2. Елементи матричних ігор | Вступ | Приклади. | Лінійного програмування. | Метод штучного базису (М-метод) | Елементи теорії подвійності | Основна теорема подвійності | Третя теорема подвійності | Формальне представлення ігор. Поняття матричної гри | Принцип міінімакса рішення матричних ігор. |

загрузка...
загрузка...
На головну

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

  1. Алгоритм симплекс-методу
  2. Алгоритм симплекс-методу.
  3. Аналітичний симплекс-метод.

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

Проте, вихідна форма завдання, до якої безпосередньо застосуємо симплекс-метод, повинна мати спеціальний вид. Ця форма є окремим випадком основної форми (1.5) завдань лінійного програмування. Тут також система обмежень представлена ??обмеженнями-рівностями (лінійними рівняннями) і умовами невід'ємності. Однак в равенствах, крім того, виділяються так звані базисні змінні. У кожному з рівності присутня одна певна базисна змінна, взята з одиничним коефіцієнтом, а в інших равенствах її немає. Число базисних змінних, таким чином, збігається з числом обмежень-рівностей в системі і зазвичай строго менше загального числа змінних. Решта змінні називаються небазисними або вільними. Ще одна вимога полягає у виконанні умови невід'ємності вільних членів bi в равенствах. Нарешті, цільова функція завдання повинна бути виражена тільки через небазисних змінні. Деякі автори називають таку форму подання завдання лінійного програмування канонічної.

Відзначимо, що в багатьох випадках канонічна форма завдання виходить автоматично при переході від стандартної форми (1.4) до основної за допомогою введення нових змінних. Для цього потрібно, щоб вільні члени в нерівностях були невід'ємними, і все нерівності в (1.4) мали єдиний знак «?». Відзначимо, що модель задачі про складання виробничого плану, розглянута в параграфі 1.1 цілком відповідає цим вимогам.

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

L= 3x1+4x2+6x3®max

Перетворимо перше і друге нерівності в рівності, ввівши нові невід'ємні змінні x4 и x5. Отримаємо нову систему обмежень:

Мінлива x3 входить з одиничним коефіцієнтом тільки в перше рівняння, змінна x4 - Тільки в друге рівняння. Саме вони і складають базис завдання. Цільова функція виражена лише через небазисних змінні x1, x2, x3. Таким чином, маємо канонічну форму подання.

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

З геометричної точки зору кожного канонічного поданням завдання лінійного програмування (кожному базису) відповідає певна вершина допустимого безлічі (багатогранника рішень), яка, згідно з твердженнями параграфа 1.2, є «претендентом» на можливість бути оптимальним планом. Таким чином, рішення задачі симплекс-методом полягає в послідовному і цілеспрямованому переході від однієї вершини допустимого безлічі до іншого.

Абстрактним аналогом поняття вершини допустимого безлічі є поняття опорного плану.

Якщо задача лінійного програмування представлена ??в канонічній формі, то опорний план = (X1, x2,..., Xn),, Може бути отриманий за допомогою простого правила: його базисні компоненти рівні вільним членам обмежень-рівностей, його небазисних компоненти дорівнюють нулю.

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

Таблиця 1.1.

базис x1 ... xn xn+1 ... xn+m вільні члени
xn +1 a11 ... a1n ... b1
... ... ... ... ... ... ... ...
xn + m am1 ... amn ... bm
-c1 ... -cn ...  

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

Алгоритм симплекс-методу розглянемо на вирішенні завдання з прикладу 1.2. Відповідна симплекс-таблиця має вигляд:

Таблиця 1.2.

базис x1 х2 х3 x4 х5 вільні члени Симплекс-відносини
х4  6 *
х5
 -3  -4  -6 *

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

Даною симплекс-таблиці, згідно вище наведеним правилом, відповідає опорний план (вершина) виду

.

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



C. Графоаналитический спосіб вирішення завдань лінійного програмування | Алгоритм симплекс-методу
загрузка...
© um.co.ua - учбові матеріали та реферати