Постановка задачі. На попередніх лекціях ми розглянули загальні методи рішення задач лінійного програмування

На попередніх лекціях ми розглянули загальні методи рішення задач лінійного програмування. Проте існують частинні типи задач лінійного програмування, які, в силу особливості своєї структури, допускають рішення більш простішими методами. Одним з таких типів задач лінійного програмування є задачі найбільш раціональної організації (тобто оптимальної) перевезення однорідного продукту з пунктів відправлення (ПВ) до пунктів призначення (ПП), які мають задані ресурси і потреби. Скорочено цей тип задач має назву – транспортна задача.

Критерієм якості плану перевезення може бути їх вартість, або термін (час). Відповідно вирішується транспортна задача за критерієм вартості, або критерієм часу.

В лекції розглянемо задачу при умові мінімальної вартості перевезення.

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

(1)

Крім того, відома вартість перевезення одиниці продукту від кожного ПВ до кожного ПП . Загальна вартість перевезення по будь-якому маршруту пропорційна кількості продукту, що перевозиться.

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

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

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

Перш ніж розглянути математичну модель задачі та її рішення зробимо кілька зауважень.

Транспортна задача може бути закритого чи відкритого типу. Умова (1) показує, що задача відноситься до закритого типу. Якщо умова (1) не виконується, тобто

або ,

то задача відкритого типу. Але у всякому разі таку задачу можна звести до задачі закритого типу введенням фіктивного ПВ або ПП ( або ) з нульовою вартістю транспортування .