Вступ.

Одне з найбільш поширених завдань математичного (зазвичай — лінійного) програмування — транспортне завдання. У загальному вигляді її можна представити так: потрібно знайти такий план доставки вантажів від постачальників до споживачів, щоб вартість перевезення (або сумарна дальність, або об'єм транспортної роботи в тонно-километрах) була найменшою. Отже, справа зводиться до найбільш раціонального прикріплення виробників до споживачів продукції (і навпаки). У простому вигляді, коли розподіляється один вид продукту і споживачам байдуже, від кого з постачальників його отримувати.

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

Типове розподільне завдання.

Таблиця №1

Більшість розподільних завдань можна представити у вигляді матриць, приведених в таблиці №1. Елементи Сi,j матриці, що стоять в клітках, відповідають витратимо або доходу, що відповідає виділенню, однієї одиниці ресурсу Ri на роботу Jj. Величини _Сi,j можуть бути незалежними або залежними. Так наприклад, витрати, обумовлені призначенням однієї автомашини на деякий маршрут доставки вантажів, не залежать від того які машини призначені на обслуговування інших маршрутів. В той же час при розподілі засобів між підрозділами фірми дохід від витрат  певної кількості грошей одним її підрозділом (скажемо виробництвом) зазвичай залежить від того, які засоби будуть витрачені іншими підрозділами (скажемо відділом збуту). У теорії розподіли розглядаються переважно завдання з незалежними витратами і доходами. Це пояснюється не тим, що такі завдання важливіші, а лише тим, що для них значно легше будувати моделі і отримувати рішення.