Розділ 3. Транспортна задача лінійного програмування

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

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

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

Слід зауважити, що і власне транспортні задачі за своїм змістом поділяються на кілька груп. Як правило, критерієм поділу є критерій оптимальності цільової функції задачі, а саме; задачі на мінімізацію вартості перевезень, задачі на мінімізацію строків перевезень, задачі на мінімізацію довжини маршрутів тощо.

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

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

Розглянемо економічну постановку класичної транспортної задачі: нехай маємо m пунктів виробництва чи запасу однорідної продукції з відомими величинами її обсягу у кожному пункті (a₁,a₂…a_m) та n пунктів споживання цієї продукції з відомими величинами попиту на неї (b₁,b₂…b_n). Також відома матриця транспортних витрат С//с_ij//, що необхідно витратити для перевезення одиниці продукції від кожного виробника до кожного споживача.

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

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

Першим кроком розв’язування транспортної задачі є перевірка балансової умови:

(1)

Якщо балансова умова виконується (тобто попит = пропозиції), то задача закритого типу або з правильним балансом.

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

У такому випадку необхідно ввести фіктивного виробника чи споживача (залежно від ситуації) і умовно звести задачу до закритої.

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

ЗАДАЧА. Завод має 3 філії (пункти виробництва), кожна з яких за квартал випускає відповідно 100; 200; 100 одиниць комп’ютерів. Чотири школи (пункти споживання) хочуть придбати ПК для навчання учнів у кількості відповідно 80; 140; 100; 80 шт. Транспортні витрати на перевезення одиниці продукції від виробника до споживача складають:

Скласти такий план перевезення продукції, при якому будуть задоволені і виробники, і споживачі, а сукупна вартість перевезення буде найдешевшою.

Перенесемо умову задачі у транспортну таблицю та знайдемо опорний план транспортної задачі.

Т аблиця 1.

					ai
	2	5	4	6	a1=100
	8	4	3	8	a2=200
	5	1	4	5	a3=100
bj	b1=80	b2=140	b3=100	b4=80	400 400

У даному випадку балансова умова виконується:

Другий крок розв'язку транспортної задачі –знаходження опорного плану.