Повна версія

Головна arrow Логістика arrow Проектування логістичних систем

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Моделі оптимізації потоків

Канонічна постановка моделі оптимізації потоків

Завдання відшукання найбільш раціонального способу транспортування деякого продукту досить часто може бути описана наступним чином. Є т пунктів відправлення, в кожному на яких зосереджено певну кількість одиниць однорідного продукту, призначеного до відправки: в першому пункті відправлення є одиниць цього продукту, у другому - одиниць, в i -му - одиниць і, нарешті, в т-му пункті - одиниць продукту. Цей продукт слід доставити в п пунктів призначення (споживання), причому в перший пункт призначення слід доставити одиниць продукту, у другій - одиниць, в j-й - одиниць і, нарешті, в n-й пункт - одиниць продукту. Передбачається, що загальна кількість продукту в пунктах відправлення одно сумарної потреби в цьому продукті у всіх пунктах призначення. Це може бути записано у вигляді рівності, якому повинні задовольняти задані числа і :

Далі передбачається, що кожен пункт відправлення з'єднаний з кожним пунктом призначення деяким маршрутом (число цих маршрутів одно т • п ), причому відома вартість перевезення однієї одиниці продукту за цим маршрутом. Загальна вартість перевезення будь-яким маршрутом пропорційна кількості перевезеного продукту. Вартість перевезення одиниці продукту з i -го пункту відправлення в j- й пункт призначення позначимо числом .

Перераховані дані зручно звести в табл. 4.1, звану таблицею вартостей.

Таблиця 4.1. Таблиця вартостей

У цій таблиці рядкам відповідають пункти відправлення, а стовпцями - пункти призначення. У клітці ij, розташованої на перетині i-го рядка і j-го стовпця, вказана вартість перевезення одиниці продукту за маршрутом, який веде з i -го пункту відправлення в j -й пункт призначення.

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

Позначимо кількість одиниць продукту, плановане до перевезення з i-го пункту відправлення в j-й пункт призначення, через .

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

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

1. З кожного пункту відправлення повинен вивозитися весь наявний там продукт:

(4.1)

2. У кожному пункті призначення повинна бути задоволена вся потреба в розглянутому продукті:

(4.2)

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

(4.3)

Неважко бачити, що, навпаки, будь-яка сукупність чисел х ij, які відповідають умовам (4.1) - (4.3), може розглядатися як певний план перевезень.

Кожен план перевезень може бути наочно зображений у вигляді табл. 4.2.

Таблиця 4.2. План перевезень

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

Звідси сумарна вартість перевезень по всіх маршрутах

(4.4)

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

Математично транспортна задача лінійного програмування формулюється так: знайти значення невідомих ( ), що задовольняють умовам (4.1) - (4.3) і звертають в мінімум лінійну функцію (4.4).

Коло практичних ситуацій, що призводять до цієї математичної задачі, значно ширше кола ситуацій, пов'язаних з різними перевезеннями.

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

У більш загальній постановці цю ж задачу можна сформулювати наступним чином. Нехай стовпці таблиці вартостей означають різні види каналів обслуговування, а рядки - різні класи заявок. Кожне число при цьому показує, скільки каналів містить даний вид, а числа - скільки є заявок класу i. Числа можуть характеризувати час обслуговування заявки i-ro класу каналом обслуговування j- го виду або будь-які інші витрати, пов'язані з цим обслуговуванням. Тоді метою вирішення завдання є розподіл заявок між каналами обслуговування, яке мінімізує сумарні витрати.

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

Слід зазначити, що історично деякі методи рішення транспортної задачі були розроблені не на базі загальних методів лінійного програмування, а безпосередньо з розгляду властивостей транспортної задачі; зв'язок ж цих методів з загальними була з'ясована пізніше. Саме так виник один з найбільш ефективних методів вирішення транспортної задачі - угорський метод, який є з точки зору класифікації, даної у введенні, типовим представником методів послідовного скорочення нев'язок. Ідея методу була висловлена ще в 1931 р угорським математиком Егерварі. На початку 1950-х рр. американський математик Кун, розвинувши цю ідею, розробив метод вирішення задачі вибору, що є окремим випадком транспортної задачі [14, 15]. Пізніше угорський метод був удосконалений і узагальнено на випадок довільної транспортної задачі Манкресом.

 
<<   ЗМІСТ   >>