лінійне програмування

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

Алгоритм симплекс-методу наступний:

1. Вихідну задачу переводимо в канонічний вигляд шляхом введення додаткових змінних. Для нерівності виду ≤ додаткові змінні вводять зі знаком (+), якщо ж виду ≥ то зі знаком (-). У цільову функцію додаткові змінні вводять з відповідними знаками з коефіцієнтом, рівним 0. тому цільова функція не повинна при цьому міняти свій економічний сенс.

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

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

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

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

Так надходять до тих пір, поки в f - рядку всі елементи не стануть позитивними.

Розглянемо рішення задачі з використанням розглянутого вище алгоритму.
дано:

Наводимо завдання до канонічного вигляду:

Заповнюємо симплекс - таблицю:

Правило прямокутників:
Перерахуємо перший елемент вектора Р0. для чого складаємо прямокутник з чисел: і отримуємо:.

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

В отриманому плані f - рядок містить один негативний елемент - (-5/3), вектора P1. Він містить в своєму стовпці єдиний позитивний елемент, який і буде вирішальним елементом. Зробимо перерахунок таблиці щодо цього елемента:

Відсутність негативних елементів в f - рядку означає, що знайдений оптимальний план:
F * = 36/5, Х = (12/5, 14/5, 8, 0, 0).

рекомендована література

Рішення лінійного програмування на замовлення

Замовити будь-які завдання по цій дисципліні можна у нас на сайті. Прикріпити файли і вказати терміни можна на сторінці замовлення.