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

МЕТОДИ ПОБУДОВИ ОПОРНОГО ПЛАНУ.

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

ПОСТАНОВКА ТРАНСПОРТНОЇ ЗАДАЧІ

План

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

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

(1)

за обмежень

; (2)

; (3)

, (4)

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

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

, (5)

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

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

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

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

Дата добавления: 2014-10-31