Навігація
Посилання


Менеджмент підприємства

Транспортна задача


Вартість перевезень 1 т вантажу в гривнях із кожного пункту відправлення А1 та А2 в кожний пункт призначення В1, В2 та В3 задана у такому вигляді (цифри умовні):

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

Позначимо через Х1, Х2 та Х3 кількість вантажів, які потрібно перевезти з пункту А1 відповідно в пункти В1, В2 та В3 , а через Y1, Y2 та Y3 – кількість вантажів, які потрібно перевезти з пункту А2 в пункти В1, В2 та В3. Запишемо це в такому вигляді:

У зв’язку з тим, що потреба у вантажі в пункті В1 становить

200 т, то Х1 + Y1 = 200. Аналогічно одержуємо, що

Х2 + Y2 = 600 і Х3 + Y3 = 200.

З другого боку, загальна кількість вантажу, відправленого зі станції А1, повинна збігатися з його запасами або Х1 + Х2 + Х3 = 400. Аналогічно Y1 + Y2 + Y3 = 600.

Із умов задачі випливає, що загальна вартість усіх перевезень

F = 8X1 + 18X2 + 6X3 + 8Y1 + 16Y2 + 24Y3 .

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

і лінійної форми

Необхідно серед усіх позитивних розв’язків системи (а) обрати такий, за якого лінійна форма (b) досягає найменшого значення.

ГЕОМЕТРИЧНЕ РОЗВ’ЯЗАННЯ ТРАНСПОРТНОЇ ЗАДАЧІ

Розглянемо систему (а). Якщо скласти почленно перші три рівняння і відняти четверте, то одержимо п’яте рівняння. Це означає, що в системі (а) п’яте рівняння зайве. Про таке рівняння кажуть, що воно – результат чотирьох рівнянь, а про всю систему кажуть, що вона лінійно залежна. Якщо виключити п’яте рівняння, то чотири рівняння, що залишилися, є лінійно незалежними. Таким чином, одержуємо чотири лінійно незалежні рівняння першого ступеня з шістьома невідомими. В цих рівняннях чотири невідомі можна виразити через два останні. У цьому випадку кажуть, що система має чотири залежні невідомі і два вільні невідомі. Оберемо вільними невідомими Х1 та Х2 і отримуємо:

Підставляючи знайдені значення Y1, Y2, X3, Y3 в лінійну функцію (b), одержуємо

Згадаємо, що величини X1, X2, X3, Y1, Y2, Y3 не можуть набувати негативних значень. Це означає, що мають місце такі нерівності:

Таким чином, транспортна задача може бути сформульована і так: дана система лінійних нерівностей (а’) та лінійна форма

Серед розв’язків системи (а’) потрібно знайти такий, за якого лінійна форма F набуває найменшого значення. Для розв’язання цієї задачі візьмемо на площині прямокутну систему координат і побудуємо багатокутник abcd можливих розв’язків системи нерівностей а’ (рисунок 5.21). Запишемо цільову функцію у матричному вигляді:

Таким чином, мінімальне значення функції досягається за максимального значення Х1 та Х2.

Рисунок 5.21. Графічне розв’язання транспортної задачі

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

ачення вона має в точці перетину прямих (І) та (ІІІ). Це відповідає оптимальному розв’язку: Х1 = 200, Х2 = 200 (точка С). При цьому F = 12000. З рівнянь (а) знаходимо, що Х3 = 0, Y1 = 0, Y2 = 400, Y3 = 200. Таким чином, оптимальним планом перевезення вантажів є такий: перевезти з пункту А1 по 200 т в В1 і в В2, а з пункту А2 400 т в В2 і 200 т в В3. Вартість перевезень при цьому найменша (12000 грн.).

Недоліком графічного (ручного) методу розв’язання моделі лінійного програмування є те, що він придатний для задач лише з двома або, максимум, з трьома змінними. Для більшої кількості змінних потрібно використовувати, так званий, симплекс-метод.


загрузка...