Лабораторне заняття №9

 

Тема заняття: Розв’язання транспортної задачі методом потенціалів.

Мета: сформувати вміння та навички розв’язання транспортної задачі методом потенціалів.

Методичні рекомендації: Вивчити лекцію №4 та ознайомиться з наступною літературою [1 с. 159-189], [2 с.134-158], [3 с.129-168], [4 с.134-175]

Постановка транспортної задачі:

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

Математична модель транспортної задачі має такий вигляд:

(1)

за обмежень

; (2)

; (3)

, (4)

де х_ij — кількість продукції, що перевозиться від і -го постачальника до j -го споживача; с_ij — вартість перевезення одиниці продукції від і -го постачальника до j -го споживача; а_i — запаси продукції і -го постачальника; b_j — попит на продукцію j -го споживача.

Якщо в транспортній задачі загальна кількість продукції постачальників дорівнює загальному попиту всіх споживачів, тобто

, (5)

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

Планом транспортної задачі називають будь-який невід’єм­ний розв’язок системи обмежень (2)—(4) транспортної задачі, який позначають матрицею .

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

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

МЕТОД ПОТЕНЦІАЛІВ

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

Алгоритм методу потенціалів складається з таких етапів.

1. Визначення типу транспортної задачі (відкрита чи закрита).

2. Побудова першого опорного плану транспортної задачі.

3. Перевірка плану транспортної задачі на оптимальність.

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

5. Новий план знову перевіряють на оптимальність, тобто повторюють дії п. 3, і т. д.

Задача 1

Розв’язати методом потенціалів транспортну задачу:

1.1. ;

1.2. ; 1.3. ;

 

 

ДОДАТКОВІ ЗАВДАННЯ:

Задача 2

Розв’язати методом потенціалів транспортну задачу:

2.1. ; 2.2. ;