Загальна характеристика розподільної задачі

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

Більшість розподільних завдань можна представити у вигляді матриць, наведених у таблиці 5.1.

Елементи Cij. стоять в клітинах матриці, відповідають витратам або доходу, що відповідає виділенню, однієї одиниці ресурсу Ri на роботу Jj. Величини Cij можуть бути залежними і незалежними.

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

Якщо витрати (або дохід), що визначаються обсягом Хij ресурсу I, виділеного на виконання роботи Ji, рівні ХijCij, то маємо лінійну розподільну завдання.

Основні методи вирішення розподільних завдань, зокрема лінійного програмування, побудовані на припущенні, що обсяги, наявних ресурсів (bi), необхідні обсяги (aj) і витрати (Ci, j) точно відомі.

Якщо загальний обсяг наявних ресурсів # 931; bi (i = 1 ... m) дорівнює загальній потребі в них # 931; aj (i = 1 ... n), то має місце збалансована (закрита) розподільна завдання. Якщо ж # 931; aj ≠ # 931; bi. то завдання називається незбалансованої (відкритої). Якщо ресурси можна розділити між роботами, то деякі роботи можна виконувати за допомогою різних комбінацій ресурсів. Якщо роботи і ресурси вимірюються в одиницях однієї і тієї ж шкали, то такі завдання зазвичай називають транспортними або завданнями розкладання. Якщо ж роботи і ресурси виражаються в різних одиницях виміру, то завдання називається загальною розділової завданням. Таким чином, транспортна задача є окремим випадком загальної розподільної задачі.

Методика виконання роботи

Є М постачальників деякого товару. Кількість товару, що є у постачальників, становить А1. А2, ..., АМ одиниць. Є N споживачів цього товару; їх попит становить B1. B2. ..., BN одиниць. Сума запасів товару, наявних у постачальників, дорівнює сумі величин попиту всіх споживачів:

Відомі витрати на перевезення одиниці товару від кожного постачальника кожному споживачеві (вартості перевезень): Cij. i = 1, ..., M, j = 1, ..., N.

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

Розглянемо спочатку рішення закритої транспортної задачі, тобто коли сума всіх заявок дорівнює сумі всіх запасів.

Пояснити його простіше за все буде на конкретному прикладі:

Приклад 5.1. З чотирьох складів (СК1, СК2, СК3, СК4) доставляється товар в три магазини (МГ1, мг2, мг3). На складі СК1 є 40 тонн товару, на складі СК2 - 50 тонн, на складі СК3 - 60 тонн, на складі СК4 - 30 тонн. Магазину МГ1 потрібно 60 тонн товару, магазину мг2 - 80 тонн, магазину мг3 - 40 тонн. Витрати (в ден. Од.), Пов'язані з перевезенням однієї тонни товару з кожного складу в кожен магазин, наведені в табл. 5.2.

Потрібно визначити, скільки товару необхідно перевезти з кожного складу в кожен магазин, щоб доставити всіх магазинах необхідну кількість товару з мінімальними витратами.

Дану задачу можна представити як задачу лінійного програмування. Для побудови математичної моделі цієї задачі введемо змінні Xij. i = 1, ..., 4, j = 1, ..., 3, що позначають кількість товару, що перевозиться з i-го складу в j-й магазин.

На складах є 180 одиниць товару; магазинам потрібно також 180 одиниць товару. Тому для задоволення попиту всіх магазинів потрібно вивезти зі складів весь товар. Обмеження, які виражають цю вимогу, мають такий вигляд:

Кожен магазин має отримати рівно стільки товару, скільки йому потрібно. Обмеження, які виражають цю умову, такі:

Так як змінні позначають кількість перевезеного товару, на них накладається вимога позитивності:

Цільова функція являє собою витрати на виконання всіх перевезень:

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

При вирішенні транспортної задачі зручно користуватися розрахункової таблицею, що містить вартості перевезень, запаси товару у постачальників і величини попиту споживачів. По ходу виконання завдання в неї заносяться величини перевезень (значення змінних xij), а також допоміжні величини, що використовуються для вирішення завдання. Розрахункова таблиця для прикладу 5.1 показана в табл 5.3.