Постановка транспортного завдання лінійного програмування

ПО МЕТОДУ ПОТЕНЦІАЛІВ

МЕТОДИ КОЛОКАЦІЇ ТА НАЙМЕНШИХ КВАДРАТІВ.

Лекция 12

ТРАНСПОРТНЕ ЗАВДАННЯ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ОБЧИСЛЮВАЛЬНА СХЕМА РІШЕННЯ ЗАВДАННЯ

Розглянемо наступну ситуацію:

якийсь однорідний продукт (наприклад, цукровий пісок) повинен бути доставлений від декількох постачальників до декількох споживачів; точніше: є m постачальників, що містять, відповідно, a ₁,..., a _m кг якогось однорідного продукту, і n споживачів, що вимагають, відповідно, b ₁,..., b _n кг цього ж продукту (замість кг можуть бути будь-які інші кількісні одиниці). Організація доставки продукту являє собою призначення чисел x _ij, i= 1,..., m, j= 1,..., n таких, що x _ij - кількість продукту, яку треба доставити від постачальника № i споживачеві № j; відома ціна c _ij перевезення одиниці продукту від постачальника № i споживачеві № j; таким чином, сумарна вартість перевезень в описаній ситуації є число

;

потрібно знайти такі числа x _ij, щоб зазначена вище сумарна вартість виявилася мінімальною.

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

(12.1.1)

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

Дата добавления: 2014-01-15