Розподільна завдання

Багато задач лінійного програмування, що зустрічаються при вирішенні питань планування, можуть бути зведені до задачі, одна з численних економічних інтерпретацій якої така. Є т видів сировини в кількостях одиниць. Існують п пунктів виробництва, у яких будь-який вид цієї сировини може перероблятися в готовий продукт, причому на виготовлення одиниці готового продукту в j-м пункті виробництва йде a ij одиниць сировини i -го виду. Задані кількості одиниць продукту, які повинні бути виготовлені на кожному з пунктів виробництва. Нехай - кількість продукту, що виготовляється в j -му пункті виробництва із сировини i -го виду, а - вартість виготовлення одиниці продукту цим способом.

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

Вимоги відсутності перевитрати кожного виду сировини можуть бути записані у вигляді нерівностей

(4.13)

Решта умов, що накладаються на невідомі, мають той же вигляд, що і в транспортній задачі: кількість продукту, виготовлене в кожному пункті виробництва, має дорівнювати заданому:

(4.14)

а все невідомі повинні бути невід'ємними:

(4.15)

Вартість виробництва, яка визначається планом , виражається формулою

(4.16)

Таким чином, приходимо до наступної математичної формулюванні завдання: знайти мінімум лінійної функції (4.16) при обмеженнях (4.13) - (4.15), що накладаються на невідомі.

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

Числа означають теплотворну здатність палива з i-го пункту відправлення, яка передбачається залежить не тільки від джерела постачання, а й від того, який споживач це паливо спалює. Витрати на транспортування однієї вагової одиниці палива з i -го пункту відправлення до j -го споживача позначимо через і будемо вважати також відомими. Будь-яка сукупність чисел , що означають величини перевезень, що здійснюються з пунктів відправлення до споживачів, є планом задачі, якщо вона задовольняє вимогам по забезпеченню калоріями кожного споживача, тобто

(4.17)

і якщо вона не передбачає перевищення запасів палива, наявних в пунктах відправлення:

(4.18)

При цьому слід вважати перевезення невід'ємними:

(4.19)

Завдання полягає в тому, щоб відшукати план перевезень, звертає в мінімум сумарні витрати на транспортування:

(4.20)

Отже, потрібно знайти мінімум лінійної функції (4.20) при умовах (4.17) - (4.19). Ця постановка дещо відмінна від раніше наведеної. Однак якщо ввести заміну змінних і позначити , то завдання зведеться до відшукання мінімуму лінійної функції

(4.16 ')

при умовах

(4.13 ')

(4.14 ')

(4.15 ')

що з точністю до позначень збігається з раніше сформульованої розподільної завданням.

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