ими умовами. Вирішити таке завдання - значить вибрати з всіх допустимо можливих (альтернативних) варіантів кращий, оптимальний. Важливість і цінність використання в економіці методу лінійного програмування полягають у тому, що оптимальний варіант вибирається з вельми значної кількості альтернативних варіантів. За допомогою інших способів вирішувати такі завдання практично неможливо. p> Дуже типовою завданням, розв'язуваної за допомогою лінійного програмування, є транспортна задача. [1]
Транспортна задача (transportation problem) - одна з найбільш поширених завдань математичного програмування (Зазвичай - лінійного). У загальному вигляді її можна представити так: потрібно знайти такий план доставки вантажів від постачальників до споживачів, щоб вартість перевезення (або сумарна дальність, або обсяг транспортної роботи в тонно-кілометрах) була найменшою. Отже, справа зводиться до найбільш раціонального прикріпленню виробників до споживачів і навпаки. [2]
1. Формулювання транспортної задачі
У найпростішому вигляді, коли розподіляється один вид продукту і споживачам все одно, від кого з постачальників його отримувати, завдання формулюється таким чином.
Вихідна інформація:
M i - кількість одиниць вантажу в i -м пункті відправлення ( i = 1, 2, ..., k );
N j - потреба в j -му пункті призначення ( j = 1, 2, ..., l ) (в одиницях вантажу);
a ij - вартість перевезення одиниці вантажу з i -гo пункту в j -й.
Позначимо через x ij плановану кількість одиниць вантажу для перевезення з i -ro пункту в j -й.
У прийнятих позначеннях:
- загальна (сумарна) вартість перевезень;
- кількість вантажу, вивозиться з i -ro пункту;
- кількість вантажу, доставляється в j -і пункт.
У простому випадку повинні виконуватися наступні очевидні умови:
В В В
Таким чином, математичної формулюванням транспортної задачі буде:
знайти
В
за умов
;
;
В
Це завдання носить назву замкнутої (Закритої, збалансованої) транспортної моделі. p> Зауважимо, що умова є природною умовою можливості розв'язання замкнутої транспортної задачі.
Більше спільної транспортної завданням є так звана відкрита (незбалансована) транспортна модель:
знайти
В
за умов
В В В
Ясно, що в цьому завданні не припускав, що весь вантаж, накопичений у i -му пункті, повинен бути вивезений. [3]
2. Математична модель транспортної задачі
Найпростішими транспортними завданнями є задачі про перевезення деякого однорідного вантажу з пунктів відправлення (Від постачальн...
