3. Методи лінійного програмування

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

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

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

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

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

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

Етапи симплексного метода: задача на максимізацію прибутку.

1. Сформулюйте задачу: визначте цільову функцію і намітьте обмеження

2. Побудуйте вихідну таблицю з вільними змінними в сукупному рішенні і вирахуйте періоди Zj і Сj - Zj

3. Визначте, яку змінну слід ввести в рішення (найбільше значення Сj - Zj)

4. Визначте, яку змінну слід замінити (по найменшому позитивному коефіцієнті, отриманим діленням значень стовпця "Кількість" на відповідне йому значення із стовпця, вибраного на етапі 3).

5. Вирахуйте нові значення терміну для вводу змінної і вставте в таблицю новий рядок (рядок який підлягає заміні, плюс елемент перетину)

6. Відкоректуйте інші рядки і введіть їх в нову таблицю; вичисліть нові значення для рядків Zj і Сj-Zj, (показники вихідних рядків, мінус елемент перетину із вихідного рядка, помножений на відповідний йому елемент із нового рядка). Якщо в результаті ви не отримали ні одного позитивного результату значення Сj - Zj, значить дане рішення буде оптимальним. Якщо ж таке значення є, повторіть етапи з 3 по 6.

Транспортний метод (Transportation Method) представляє собою спрощений специфічний варіант симплексного методу.

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

Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей математичного програмування та теорії оптимізації. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого Канторовича Л. В. в 1939. В цій же роботі намічено один із методів розв'язання задачі — метод послідовного зменшення нев'язок.