Решение транспортной задачи методом северо-западного угла

Требуется составить план перевозок, при котором общая стоимость перевозок минимальная.

Решение: Найдем начальное решение методом северо-западного угла.

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

Запасы поставщиков:

• 60 + 30 + 50 =
• 140 единиц продукции.

Потребность потребителей:

• 40 + 80 + 80 =
• 200 единиц продукции.

Разница в 60 единиц продукции.

Введем в рассмотрение фиктивного поставщика A₄, с запасом продукции равным 60 единиц.

Стоимость доставки единицы продукции от поставщика A₄ ко всем потребителям примем равной нулю. (см. таблицу 1).

Теперь суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.

Согласно условию задачи составим таблицу. (тарифы маршрутов располагаются в нижнем правом углу ячейки) Начинаем заполнять таблицу от левого верхнего угла и постепенно «двигаемся» к правому нижнему.

От северо-запада к юго-востоку.

От поставщика A₁ к потребителю B₁ будем доставлять min = { 60, 40 } = 40 единиц продукции.

От поставщика A₁ к потребителю B₂ будем доставлять min = { 20, 80 } = 20 единиц продукции.

От поставщика A₂ к потребителю B₂ будем доставлять min = { 30, 60 } = 30 единиц продукции.

От поставщика A₃ к потребителю B₂ будем доставлять min = { 50, 30 } = 30 единиц продукции.

От поставщика A₃ к потребителю B₃ будем доставлять min = { 20, 80 } = 20 единиц продукции.

От поставщика A₄ к потребителю B₃ будем доставлять 60 единиц продукции.

Мы израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Мы нашли начальное решение.

Стоимость доставки продукции, для начального решения, не сложно посчитать.

S = 40 * 1 + 20 * 13 + 30 * 3 + 30 * 8 + 20 * 6 + 60 * 0 = 750 ден. ед.

Полученное начальное решение является оптимальным?

Для того, чтобы иметь возможность ответить на этот вопрос, количество задействованных маршрутов должно равняться 4 + 3 — 1 = 6, где.

• 4 — количество строк в таблице.
• 3 — количество столбцов в таблице.

Количество задействованных маршрутов не может получиться больше 6, меньше — возможно.

Посчитайте. Количество задействованных маршрутов равно 6, что и требовалось.

В противном случае, мы не сможем найти потенциалы поставщиков и потребителей. Дальнейшие наши действия будут состоять из однотипных шагов, каждый из которых состоит в следующем:

Находим потенциалы поставщиков и потребителей.

Зная потенциалы, находим оценки незадействованных маршрутов.

Если оценки всех незадействованных маршрутов неотрицательные, то уменьшить общую стоимость доставки нельзя. Задача решена.

Если хотя бы один незадействованный маршрут имеет отрицательную оценку, тогда мы можем найти новое решение, как минимум, не хуже имеющегося.

Вводим незадействованный маршрут, с отрицательной оценкой, в схему доставки продукции.

Один, ранее задействованный маршрут, исключаем.

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

Шаг 1.

Каждому поставщику A _i ставим в соответствие некоторое число — u _i, называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число — v _j, называемое потенциалом потребителя.

Найдем потенциалы поставщиков и покупателей. (поверьте, это очень просто). Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.

Примем v₂ = 0.

A₁B₂ :

v₂ + u₁ = 13.

u₁ = 13 — 0 = 13.

A₂B₂ :

v₂ + u₂ = 3.

u₂ = 3 — 0 = 3.

A₃B₂ :

v₂ + u₃ = 8.

u₃ = 8 — 0 = 8.

A₃B₃ :

v₃ + u₃ = 6.

v₃ = 6 — 8 = -2.

A₄B₃ :

v₃ + u₄ = 0.

u₄ = 0 — (-2) = 2.

A₁B₁ :

v₁ + u₁ = 1.

v₁ = 1 — 13 = -12.

Найдем оценки незадействованных маршрутов.

Оценка незадействованного маршрута = тариф маршрута.

A₁B₃: ₁₃ = 8 — (13 + (-2)) = -3.

A₂B₁: ₂₁ = 2 — (3 + (-12)) = 11.

A₂B₃: ₂₃ = 4 — (3 + (-2)) = 3.

A₃B₁: ₃₁ = 4 — (8 + (-12)) = 8.

A₄B₁: ₄₁ = 0 — (2 + (-12)) = 10.

A₄B₂: ₄₂ = 0 — (2 + 0) = -2.

Введение

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

Будем использовать новый маршрут доставки продукции от поставщика A₁ к потребителю B₃.

Построим цикл для нового маршрута.

моделирование математический транспортный задача Пусть ячейка A₁B₃, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.

min = { 20, 20 } = 20.

От ячеек цикла с четными номерами отнимает 20. К ячейкам с нечетными номерами прибавляем 20.

Достаточно взглянуть на таблицу и Вы увидите, что баланс не нарушится. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.

А вот общие затраты на доставку всей продукции изменятся на величину.

8 * 20 — 13 * 20 + 8 * 20 — 6 * 20 = (8 — 13 + 8 — 6) * 20 =.

= -3 * 20 = ₁₃ * 20.

Выражение стоящее в скобках равно оценке нового маршрута!

Поэтому новая стоимость доставки вычисляется именно так:

S = 750 + ₁₃ * 20 = 750 — 3 * 20 = 690 ден. ед.

Один маршрут из построенного цикла, по которому ничего не доставляется, мы должны исключить.

У нас есть 2 таких маршрута. Тариф маршрута от поставщика A₁ к потребителю B₂ наибольший.

Исключим именно его. Второй маршрут будем считать задействованным.

Шаг 2.

Каждому поставщику A _i ставим в соответствие некоторое число — u _i, называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число — v _j, называемое потенциалом потребителя.

Найдем потенциалы поставщиков и покупателей.

Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.

Найдем оценки незадействованных маршрутов Оценка незадействованного маршрута = тариф маршрута.

A1B2: 12 = 13 — (8 + 2) = 3.

A2B1: 21 = 2 — (1 + (-7)) = 8.

A2B3: 23 = 4 — (1 + 0) = 3.

A3B1: 31 = 4 — (6 + (-7)) = 5.

A4B1: 41 = 0 — (0 + (-7)) = 7.

A4B2: 42 = 0 — (0 + 2) = -2.

Введение

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

Будем использовать новый маршрут доставки продукции от поставщика A₄ к потребителю B₂.

Построим цикл для нового маршрута.

Пусть ячейка A₄B₂, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.

min = { 60, 50 } = 50.

От ячеек цикла с четными номерами отнимает 50. К ячейкам с нечетными номерами прибавляем 50.

Достаточно взглянуть на таблицу и Вы увидите, что баланс не нарушится.

Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.

А вот общие затраты на доставку всей продукции изменятся на величину.

0 * 50 — 0 * 50 + 6 * 50 — 8 * 50 = (0 — 0 + 6 — 8) * 50 = -2 * 50 = ₄₂ * 50.

Выражение стоящее в скобках равно оценке нового маршрута!

Поэтому новая стоимость доставки вычисляется именно так:

S = 690 + ₄₂ * 50 = 690 — 2 * 50 = 590 ден. ед.

Один маршрут из построенного цикла, по которому ничего не доставляется, мы должны исключить.

Это маршрут от поставщика A₃ к потребителю B₂. Теперь данный маршрут незадействованный.

Шаг 3.

Каждому поставщику A _i ставим в соответствие некоторое число — u _i, называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число — v _j, называемое потенциалом потребителя.

Найдем потенциалы поставщиков и покупателей.

Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.

Найдем оценки незадействованных маршрутов Оценка незадействованного маршрута = тариф маршрута Примем v3 = 0.

A1B3: v3 + u1 = 8 u1 = 8 — 0 = 8.

A3B3: v3 + u3 = 6 u3 = 6 — 0 = 6.

A4B3: v3 + u4 = 0 u4 = 0 — 0 = 0.

A1B1: v1 + u1 = 1 v1 = 1 — 8 = -7.

A4B2: v2 + u4 = 0 v2 = 0 — 0 = 0.

A2B2: v2 + u2 = 3 u2 = 3 — 0 = 3.

A₁B₂: ₁₂ = 13 — (8 + 0) = 5.

A₂B₁: ₂₁ = 2 — (3 + (-7)) = 6.

A₂B₃: ₂₃ = 4 — (3 + 0) = 1.

A₃B₁: ₃₁ = 4 — (6 + (-7)) = 5.

A₃B₂: ₃₂ = 8 — (6 + 0) = 2.

A₄B₁: ₄₁ = 0 — (0 + (-7)) = 7.

Оценки всех незадействованных маршрутов неотрицательные. Следовательно, уменьшить общую стоимость доставки мы не сможем.

Ответ:

Решение транспортной задачи средствами MS Excel

F = -4x₁+5x₂ > min, при системе ограничений:

7x₁+9x₂?63(1)

x₁-2x₂?6(2)

• 7x₁+2x₂?14(3)
• -x₁+x₂?5(4)

x₁?0(5)

x₂?0(6)

F = -4x₁+5x₂ > min, при системе ограничений:

7x₁+9x₂?63(1)

x₁-2x₂?6(2)

• 7x₁+2x₂?14(3)
• -x₁+x₂?5(4)

x₁?0(5)

x₂?0(6)