Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
методичка ОММ.doc
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
2 Мб
Скачать
☆

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

  1. Визначення типу ТЗ (збалансована чи незбалансована). У другому випадку – збалансувати.

  2. Побудова першого опорного плану ТЗ.

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

  4. Перевірка опорного плану ТЗ на оптимальність. Якщо умова оптимальності не виконується, то повторити дії, починаючи з п.3.

1. Як збалансувати ТЗ було розглянуто раніше. Переходимо до п.2.

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

Метод північно-західного кута.

Таблиця заповнюється починаючи з лівого верхнього кута (північно-західного кута), рухаючись далі по рядку вправо, або по стовпчику вниз. У клітинку (1.1) заноситься менше з чисел та , тобто .

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

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

Заповнивши клітинку (1.2). або (2.1), переходять до заповнення третьої клітинки або по другому рядку, або по другому стовпчику. Цей процес продовжують до повного вичерпування продукції у пунктах, або повного задоволення потреб споживачів. Остання заповнена клітинка виявиться в останньому -му рядку та -му стовпчику.

План, отриманий методом північно-західного кута, буде опорним планом системи обмежень транспортної задачі.

Приклад 4. Методом північно-західного кута знайти опорний план ТЗ, умова якої задається таблицею:

Постачальники

Споживачі

Запаси

1

2

3

4

1

6

7

3

5

100

75

25

2

4

2

5

6

150

55

60

35

3

3

10

20

1

50

50

Потреби

75

80

60

85

Опорний план:

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