Розподільна завдання
Багато задач лінійного програмування, що зустрічаються при вирішенні питань планування, можуть бути зведені до задачі, одна з численних економічних інтерпретацій якої така. Є т видів сировини в кількостях одиниць. Існують п пунктів виробництва, у яких будь-який вид цієї сировини може перероблятися в готовий продукт, причому на виготовлення одиниці готового продукту в 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 ')
що з точністю до позначень збігається з раніше сформульованої розподільної завданням.
В даний час розроблений ряд алгоритмів розв'язання розподільної задачі, більшість з яких реалізують ідею послідовного поліпшення плану.
|