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

Метод северо-западного угла

Составление первоначального плана перевозок начнем с перевозки запасов поставщика A1. Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя Bi, затем B2 и так далее. Таким образом, мы будем заполнять таблицу, начиная с клетки (1; 1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика A1 не окажется меньше заказа очередного потребителя. Для выполнения этого заказа используем остатки запаса первого поставщика, а недостающую часть добавим из запасов поставщика A2, то есть переместимся на следующую строку таблицы по столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика A2, затем A3 и так далее.

Пример:

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

1

2

3

Запасы

1

1

2

3

100

2

4

5

6

150

3

7

8

9

50

Потребности

80

120

100

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 100 + 150 + 50 = 300

∑b = 80 + 120 + 100 = 300

Этап I. Поиск первого опорного плана.Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

1

2

3

Запасы

1

1[80]

2[20]

3

100

2

4

5[100]

6[50]

150

3

7

8

9[50]

50

Потребности

80

120

100

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

v1=1

v2=2

v3=3

u1=0

1[80]

2[20]

3

u2=3

4

5[100]

6[50]

u3=6

7

8

9[50]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij. Минимальные затраты составят: F(x) = 1*80 + 2*20 + 5*100 + 6*50 + 9*50 = 1370