Математическая модель транспортной задачи

3)

Минимальный элемент  матрицы тарифов находится в  ячейке A₃B₁ и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₁ наиболее рентабельный.

Запасы поставщика A₃ составляют 15 единиц продукции. Потребность потребителя B₁ составляет 20 единиц продукции. (см. таблицу пункта 2)

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

Разместим в ячейку A₃B₁ значение равное 15

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

4)

Минимальный элемент  матрицы тарифов находится в  ячейке A₂B₁ и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₂ к потребителю B₁ наиболее рентабельный.

Запасы поставщика A₂ составляют 25 единиц продукции. Потребность потребителя B₁ составляет 5 единиц продукции. (см. таблицу пункта 3)

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

Разместим в ячейку A₂B₁ значение равное 5

Мы полностью  удовлетворили потребность потребителя B₁. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

5)

Минимальный элемент  матрицы тарифов находится в  ячейке A₂B₃ и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₂ к потребителю B₃ наиболее рентабельный.

Запасы поставщика A₂ составляют 20 единиц продукции. Потребность потребителя B₃ составляет 15 единиц продукции. (см. таблицу пункта 4)

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

Разместим в ячейку A₂B₃ значение равное 15

Мы полностью  удовлетворили потребность потребителя B₃. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

6)

Минимальный элемент  матрицы тарифов находится в  ячейке A₂B₂ и равен 5, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₂ к потребителю B₂ наиболее рентабельный.

Запасы поставщика A₂ составляют 5 единиц продукции. Потребность потребителя B₂ составляет 5 единиц продукции. (см. таблицу пункта 5)

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

Разместим в ячейку A₂B₂ значение равное 5

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

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

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.

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

S₀ = 1 * 30 + 4 * 5 + 5 * 5 + 4 * 15 + 2 * 15 = 165 ден. ед.

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

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

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

·  Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

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

·  Находим новое решение, как минимум, не хуже предыдущего.

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

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.