5. Транспортна задача лiнiйного програмування

5.1. Змiстовна постановка та формальна модель транспортної задачi лiнiйного програмування

Нехай є m пунктів виробництва однорiдної або взаємозамінної продукції. Кожний з пунктів виробництва позначимо через , деi= 1, …, m. Через будемо позначати обсяг продукції, що виробляють у пункті. Нехай єn пунктів споживання (призначення) цієї продукції, кожний з яких позначимо через , деj=1, ..., n, а обсяг споживання (попиту) продукції в пункті – через. Вартість перевезення одиниці продукції відi-го виробника j-го споживача складає (i=1, ..., m, j=1, …, n). Припускається, що транспортні витрати на перевезення між будь-якою парою пунктів пропорційні обсягу продукту, який перевозять.

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

Математична модель задачі така:

(5.1)

(5.2)

(5.3)

(5.4)

У (5.1) являє собою сумарні транспортні витрати.

Задача (5.1) – (5.4) є ЗЛП і називається транспортною задачею лінійного програмування (ТЗЛП). Така назва пов’язана зі структурою задачі, а не зі змістовною постановкою. До моделі вигляду (5.1) – (5.4) може привести задача, за своїм змістом ніяк не пов’язана з транспортом та плануванням перевезень. У такому разі кажуть, що задачу можна сформулювати в термінах транспортної задачі.

5.2. Умова iснування розв’язку транспортної задачі лінійного програмування

Необхідною умовою існування розв’язку задачі (5.1) – (5.4) є

.

Якщо

, (5.5)

то кажуть, що мають збалансовану транспортну модель; умова (5.5) має назву умови балансу.

Збалансована транспортна модель має вигляд:

(5.6)

(5.7)

(5.8)

(5.9)

Теорема 1

Для того, щоб задача (5.6) – (5.9) мала допустимий розв’язок, необхідно і достатньо, щоб виконувалась умова балансу.

5.3. Побудова формальної моделi транспортної задачі лінійного програмування при порушеннi умов балансу в змiстовiй постановцi

1.Нехай у змістовній постановці є таке співвідношення:

.

Введемо фіктивний пункт споживання з обсягом споживання

і покладемо . Після цього будуємо задачу (5.6)–(5.9), для якої виконується умова балансу. Тоді – неперевезена (надлишкова) продукція пункту.

2. Нехай у змістовій постановці .

Введемо фіктивний пункт виробництва з обсягом виробництва:

Далі будуємо задачу (5.6) – (5.9), для якої виконується умова балансу. Тоді - це обсяги нестачі продукції в пунктах.

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

Побудуємо вектори , які відповідають зміннимi=1,…, m, j=1,…, n, та вектор

правих частин обмежень :

Якщо змінні упорядковано так:

,

то матриця Р коефіцієнтів лівої частини системи обмежень матиме вигляд:

Розглянемо деякі властивості транспортної задачі, обумовлені цими особливо­стями.

Матриця Р має розмірність (m+n)(mn). Очевидно, що ранг матриці Р не може перевищувати m+n, оскільки ТЗЛП має зміст, якщо m>1 та n>1, і в цьому разі m+n  mn.

Легко помітити, що якщо від суми перших m рядків обмежень (5.7) відняти суму останніх n рядків, то одержимо нульовий рядок. Отже, ранг матриці Р r(Р)  m+n–1 і кожен з рядків матриці Р можна виразити як лінійну комбінацію інших рядків.

Теорема 2

Ранг матриці Р дорівнює m + n — 1.

Теорема 3

Якщо всі іу транспортній задачі — цілі, то всіу будь-якому ДБР (включаючи й оптимальний) також будуть цілими числами.