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

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

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

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

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

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

Загальним завданням лінійного програмування (ОЗЛП), заданої в довільній формі записи, називають задачу, в якій потрібно максимізувати (мінімізувати) функцію

a ij x j <= a i0 ( i = 1, …, s) (2)

a ij x j = a i0 (i = s + 1, ..., m) (3)

x j> = 0 (j = 1, ..., t)

Існують різні форми запису ЗЛП, але по темі завдання нас цікавить канонічна форма запису ЗЛП, так як саме до такої форми запису застосуємо широко використовуваний симплекс-метод.

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

a ij x j = a i0 (i = 1, ..., m) (5)

x j> = 0 (j = 1, ..., n) (6)

Зауваження: завдання мінімізації f можна формально замінити завданням максимізації функції (-f).

Для того, щоб висловити загальну ідею симплексного методу, наведемо кілька основних понять, що відносяться до лінійного програмування:

Набір чисел Х = (x 1; ...; x n), що задовольняє всім обмеженням завдання називається планом.

Набір чисел Х = (x 1; ...; x n), називається опорним планом, якщо він відповідає крайній точці багатогранника рішень.

План Х = (x 1; ...; x n), який доставляє функцію в екстремум називається оптимальним.

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

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

Обмеження виду «# 63;» - ресурсні обмеження. Справа знаходиться те, що ми використовуємо на виробництві, зліва - то, що отримуємо. При таких обмеження вводять додаткові змінні з коефіцієнтом «1», що утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом «0». Ці змінні несуть певний економічний сенс. Зазвичай вони відображають недорасхода ресурсів (залишок).

Обмеження виду «=». Часто буває, незважаючи на те, що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. В цьому випадку вводяться штучні змінні для створення одиничного базису. У систему обмежень вони входять з коефіцієнтом «1», а в цільову функцію з коефіцієнтом «M», які прагнуть до нескінченності (при Fmin - «+ M», при Fmax - «-M»). (Метод штучного базису).

Обмеження виду «# 63;» - Планові обмеження. Додаткові змінні (X), що несуть певний економічний сенс - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом «-1», в цільову функцію - з коефіцієнтом «0». А штучні змінні як в попередньому випадку.

Рішення ЗЛП найбільш раціонально можна виконувати в табличній формі. Такі таблиці називаються симплексними. У різній літературі побудови симплекс таблиць трохи відрізняються один від одного. Найбільш прийнятними на мій погляд є таблиці, описані в табл. 1.

Метод штучного базису

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

F = cj xj - x n + i (7)

a ij + x n + i = a i0 (i = 1, ..., m) (8)

x j> = 0 (j = 1, ..., n + m) (9)

В системі (8) змінні x n + i (i = 1, ..., m) утворюють базис, званий штучним. При x 1 = ... = x n = 0 з (8) отримуємо початковий опорний план М-задачі: (0; ...; 0; a 10; ...; a m0).

Отримання оптимального плану вихідної завдання із залученням М-задачі засноване на наступних твердженнях:

1. Якщо в оптимальному плані М-задачі всі штучні змінні дорівнюють нулю (х 1; ...; х n; 0; ...; 0), то план (х 1; ...; хn) є оптимальним для вихідної завдання.

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

3. Якщо М-задача нерозв'язна, то і вихідна задача нерозв'язна.

При вирішенні ЗЛП методом штучного базису штучні змінні слід вводити лише в ті рівняння, які не дозволені щодо «природних» базисних змінних.

Як видно з (7), цільова функція тепер містить два доданків

тому в симплекс-таблицях для f відводять два рядки (табл.1.3.) і ознака оптимальності перевіряється спочатку по другому рядку, що відповідає сумі

Лише після того, як всі елементи цього рядка стануть рівними нулю, ознака оптимальності перевіряють по першому рядку, що відповідає сумі

У міру виключення з базису штучних змінних відповідні їм стовпці опускають (не враховують), так як штучні змінні назад в базис не вводяться.