Поделиться Поделиться

Умова існування розв’язку транспортної задачі

Теорема . Для того щоб існував розв’язок ТЗ необхідно і достатньо, щоб вона була збалансованою, тобто, щоб Умова існування розв’язку транспортної задачі - Инвестирование - 1 = Умова існування розв’язку транспортної задачі - Инвестирование - 2 .

Для розв’язування транспортної задачі застосовують метод потенціалів.

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

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

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

3. Визначення потенціалів плану ТЗ.

4. Перевірка плану ТЗ на оптимальність. Констатація оптимального плану, якщо умова оптимальності виконується. Перехід до наступного опорного плану за умови, якщо план не є оптимальним.

5. Повторення дій, починаючи з п.3.

Розглянемо кожний з етапів.

Етап 1. Якщо під час перевірки умови збалансованості (8.5) виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. Це виконується введенням фіктивного умовного постачальника Аm+1 у випадку перевищення загального попиту над запасами ( Умова існування розв’язку транспортної задачі - Инвестирование - 3 ) із запасом Умова існування розв’язку транспортної задачі - Инвестирование - 4 . Якщо запаси постачальників перевищують попит споживачів Умова існування розв’язку транспортної задачі - Инвестирование - 5 , то до закритого типу задача зводиться введенням фіктивного умовного споживача Вn+1 з потребою Умова існування розв’язку транспортної задачі - Инвестирование - 6 .

Вартість перевезення одиниці продукції для фіктивного постачальника Аm+1, або фіктивного споживача Вn+1 вважається рівною нулю.

Етап 2. Для побудови початкового опорного плану ТЗ існує декілька методів: північно-західного кута; мінімальної вартості, подвійної переваги та інші. Побудову опорного плану зручно надавати у вигляді т таблиці, в якій постачальники продукції визначаються рядками, а споживачі – стовпчиками.

← Предыдущая страница | Следующая страница →