3.3. Решение заданной транспортной задачи

Условия задачи:

Три завода производят однородную продукцию в количествах 600, 800 и 650 единиц соответственно. Четыре потребителя нуждаются в этой продукции в количествах 480, 750, 300 и 520 единиц. Затраты на перевозку единицы продукции (тыс. руб.) от каждого завода к каждому потребителю заданы таблицей:

Поставщики	Потребители
	1	2	3	4
1	40	60	72	20
2	50	60	90	30
3	60	20	40	40

1. Спланируйте перевозку груза так, чтобы суммарные транспортные затраты были минимальными;

2. Повторно решите задачу минимизации суммарных транспортных затрат при дополнительном условии, состоящем в том, что запрещена перевозка груза от 1-го поставщика к 4-му потребителю. Определите, на сколько увеличилось значение суммы затрат.

3. Решите ещё раз задачу минимизации суммарных транспортных затрат при дополнительном условии, что объём перевозки груза от 3-го поставщика к 1-му потребителю не должен превышать 300 единиц ( то есть максимальная поставка груза от 3-го поставщика к 1-му потребителю равна 300 единицам). Оцените удорожание затрат на перевозку из-за этого условия.

Решение задачи¹⁰:

1. Найдем начальное решение методом минимального элемента.

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

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

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

-
	40

-
	60

-
	72

-
	20

600

A ₂

-
	50

-
	60

-
	90

-
	30

800

A ₃

-
	60

-
	20

-
	40

-
	40

650

Потребность

480

750

300

520

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

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

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

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

-
	40

-
	60

-
	72

520
	20

600

A ₂

-
	50

-
	60

-
	90

-
	30

800

A ₃

-
	60

-
	20

-
	40

-
	40

650

Потребность

480

750

300

520

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

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

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

Разместим в ячейку A3B2 значение равное 650

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

-
	40

-
	60

-
	72

520
	20

600

A ₂

-
	50

-
	60

-
	90

-
	30

800

A ₃

-
	60

650
	20

-
	40

-
	40

650

Потребность

480

750

300

520

4). Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 40, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.

Запасы поставщика A1 составляют 80 единиц продукции. Потребность потребителя B1 составляет 480 единиц продукции. (см. таблицу пункта 3)

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

Разместим в ячейку A1B1 значение равное 80

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

-
	50

-
	60

-
	90

-
	30

800

A ₃

-
	60

650
	20

-
	40

-
	40

650

Потребность

480

750

300

520

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

Запасы поставщика A2 составляют 800 единиц продукции. Потребность потребителя B1 составляет 400 единиц продукции. (см. таблицу пункта 4)

От поставщика A2 к потребителю B1 будем доставлять min = { 800 , 400 } = 400 единиц продукции.

Разместим в ячейку A2B1 значение равное 400

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

-
	60

-
	90

-
	30

800

A ₃

-
	60

650
	20

-
	40

-
	40

650

Потребность

480

750

300

520

6). Минимальный элемент матрицы тарифов находится в ячейке A2B2 и равен 60, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B2 наиболее рентабельный.

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

От поставщика A2 к потребителю B2 будем доставлять min = { 400 , 100 } = 100 единиц продукции.

Разместим в ячейку A2B2 значение равное 100

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

100
	60

-
	90

-
	30

800

A ₃

-
	60

650
	20

-
	40

-
	40

650

Потребность

480

750

300

520

7). Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 90, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.

Запасы поставщика A2 составляют 300 единиц продукции. Потребность потребителя B3 составляет 300 единиц продукции. (см. таблицу пункта 6)

От поставщика A2 к потребителю B3 будем доставлять 300 единиц продукции.

Разместим в ячейку A2B3 значение равное 300

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

100
	60

300
	90

-
	30

800

A ₃

-
	60

650
	20

-
	40

-
	40

650

Потребность

480

750

300

520

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

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

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

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

S0 = 40 * 80 + 20 * 520 + 50 * 400 + 60 * 100 + 90 * 300 + 20 * 650 = 79600 ден. ед.

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

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

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

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

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

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

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

Шаг 1. Произведем оценку полученного решения.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем u2 = 0.

v1 + u2 = c21 v1 + u2 = 50 v1 = 50 - 0 = 50

v2 + u2 = c22 v2 + u2 = 60 v2 = 60 - 0 = 60

v3 + u2 = c23 v3 + u2 = 90 v3 = 90 - 0 = 90

v2 + u3 = c32 v2 + u3 = 20 u3 = 20 - 60 = -40

v1 + u1 = c11 v1 + u1 = 40 u1 = 40 - 50 = -10

v4 + u1 = c14 v4 + u1 = 20 v4 = 20 - ( -10 ) = 30

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

u ₁ = -10

A ₂

400
	50

100
	60

300
	90

-
	30

u ₂ = 0

A ₃

-
	60

650
	20

-
	40

-
	40

u ₃ = -40

V _i

v ₁ = 50

v ₂ = 60

v ₃ = 90

v ₄ = 30

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

Λ12 = c12 - ( u1 + v2 ) = 60 - ( -10 + 60 ) = 10

Λ 13 = c13 - ( u1 + v3 ) = 72 - ( -10 + 90 ) = -8

Λ 24 = c24 - ( u2 + v4 ) = 30 - ( 0 + 30 ) = 0

Λ 31 = c31 - ( u3 + v1 ) = 60 - ( -40 + 50 ) = 50

Λ 33 = c33 - ( u3 + v3 ) = 40 - ( -40 + 90 ) = -10

Λ 34 = c34 - ( u3 + v4 ) = 40 - ( -40 + 30 ) = 50

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
10	60

-
-8	72

520
	20

u ₁ = -10

A ₂

400
	50

100
	60

300
	90

-
0	30

u ₂ = 0

A ₃

-
50	60

650
	20

-
-10	40

-
50	40

u ₃ = -40

V _i

v ₁ = 50

v ₂ = 60

v ₃ = 90

v ₄ = 30

Среди оценок свободных ячеек есть отрицательные, следовательно, решение не является оптимальным.

Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A3B3 ( 33 =-10).

Построим цикл для выбранной ячейки A3B3:

Поставьте курсор мыши в выбранную свободную ячейку A3B3. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A3B3. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки образующие цикл для свободной ячейки A3B3 :

A3B3 , A3B2 , A2B2 , A2B3

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

100
	60

300
	90

-
	30

800

A ₃

-
	60

650
	20

-
-10	40

-
	40

650

Потребность

480

750

300

520

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

min = { 650, 300 } = 300

В данном случае, это ячейка A2B3.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

100
	60

300
	90

-
	30

800

A ₃

-
	60

650
	20

-
-10	40

-
	40

650

Потребность

480

750

300

520

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

Что мы делаем?

Мы вводим новый маршрут доставки продукции от поставщика A3 к потребителю B3. По данному маршруту доставим 300 единиц продукции, по цене доставки 40 за единицу продукции. Общие затраты увеличатся на 40 * 300 ден. ед.

Сократим поставку от поставщика A3 к потребителю B2 на 300 единиц продукции, по цене доставки 20 за единицу продукции. Общие затраты уменьшатся на 20 * 300 ден. ед.

От поставщика A2 к потребителю B2 дополнительно поставим 300 единиц продукции, по цене доставки 60 за единицу продукции. Общие затраты увеличатся на 60 * 300 ден. ед.

По маршруту от поставщика A2 к потребителю B3 мы полностью перестаем доставлять продукцию.

Общие затраты уменьшатся на 90 * 300 ден. ед.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

100 + 300
	60

300 - 300
	90

-
	30

800

A ₃

-
	60

650 - 300
	20

+ 300
-10	40

-
	40

650

Потребность

480

750

300

520

Что в итоге?

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

40 * 300 - 20 * 300 + 60 * 300 - 90 * 300 = ( 40 - 20 + 60 - 90 ) * 300 = -10 * 300 ден. ед.

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

ГЛАВНОЕ :

В тот момент, когда мы нашли ячейку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на 33 * 300 = -10 * 300 = -3000 ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 79600 + ( - 3000 ) = 76600 ден. ед. .

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

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

ячейки A1B3, общая стоимость доставки всей продукции изменилась бы на 13 * 80 = -8 * 80 = -640 ден. ед.

Ячейка A2B3 выйдет из базиса, мы перестали доставлять продукцию от поставщика A2 к потребителю B3

Ячейка A3B3 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A3 к потребителю B3 .

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

400
	60

-
	90

-
	30

800

A ₃

-
	60

350
	20

300
	40

-
	40

650

Потребность

480

750

300

520

Шаг 2. Произведем оценку полученного решения.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v2 = 0.

v2 + u2 = c22 v2 + u2 = 60 u2 = 60 - 0 = 60

v2 + u3 = c32 v2 + u3 = 20 u3 = 20 - 0 = 20

v3 + u3 = c33 v3 + u3 = 40 v3 = 40 - 20 = 20

v1 + u2 = c21 v1 + u2 = 50 v1 = 50 - 60 = - 10

v1 + u1 = c11 v1 + u1 = 40 u1 = 40 -(-10)= 50

v4 + u1 = c14 v4 + u1 = 20 v4 = 20 - 50 = - 30

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

u ₁ = 50

A ₂

400
	50

400
	60

-
	90

-
	30

u ₂ = 60

A ₃

-
	60

350
	20

300
	40

-
	40

u ₃ = 20

V _i

v ₁ = -10

v ₂ = 0

v ₃ = 20

v ₄ = -30

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

Λ12 = c12 - ( u1 + v2 ) = 60 - ( 50 + 0 ) = 10

Λ 13 = c13 - ( u1 + v3 ) = 72 - ( 50 + 20 ) = 2

Λ 23 = c23 - ( u2 + v3 ) = 90 - ( 60 + 20 ) = 10

Λ 24 = c24 - ( u2 + v4 ) = 30 - ( 60 + ( -30 ) ) = 0

Λ 31 = c31 - ( u3 + v1 ) = 60 - ( 20 + ( -10 ) ) = 50

Λ 34 = c34 - ( u3 + v4 ) = 40 - ( 20 + ( -30 ) ) = 50

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
10	60

-
2	72

520
	20

u ₁ = 50

A ₂

400
	50

400
	60

-
10	90

-
0	30

u ₂ = 60

A ₃

-
50	60

350
	20

300
	40

-
50	40

u ₃ = 20

V _i

v ₁ = -10

v ₂ = 0

v ₃ = 20

v ₄ = -30

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

Ответ:

X 1 опт =		80	0	0	520
		400	400	0	0
		0	350	300	0

Smin = 40 * 80 + 20 * 520 + 50 * 400 + 60 * 400 + 20 * 350 + 40 * 300 = 76600

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

Замечание:

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

• Построим цикл для ячейки A2B4.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

400
	60

-
	90

-
0	30

800

A ₃

-
	60

350
	20

300
	40

-
	40

650

Потребность

480

750

300

520

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

min = { 400, 520 } = 400

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80
	40

-
	60

-
	72

520
	20

600

A ₂

400
	50

400
	60

-
	90

-
0	30

800

A ₃

-
	60

350
	20

300
	40

-
	40

650

Потребность

480

750

300

520

Общие затраты на доставку всей продукции, по-прежнему, составляют S0 = 76600 + 24 * 400 = 76600 + 0 * 400 = 76600 ден. ед. .

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

A ₁

80 + 400
	40

-
	60

-
	72

520 - 400
	20

600

A ₂

400 - 400
	50

400
	60

-
	90

+ 400
0	30

800

A ₃

-
	60

350
	20

300
	40

-
	40

650

Потребность

480

750

300

520

X 2 опт =		480	0	0	120
		0	400	0	400
		0	350	300	0

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

Решение задачи с ограничительным условием № 1:

«Повторно решите задачу минимизации суммарных транспортных затрат при дополнительном условии, состоящем в том, что запрещена перевозка груза от 1-го поставщика к 4-му потребителю. Определите, на сколько увеличилось значение суммы затрат».

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

F = ∑∑c_ijx_ij, (1)

при условиях:

∑x_ij = a_i, i = 1,2,…, m, (2)

∑x_ij = b_j, j = 1,2,…, n, (3)

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

	1	2	3	4	Запасы
1	40	60	72	-	600
2	50	60	90	30	800
3	60	20	40	40	650
Потребности	480	750	300	520

Поскольку в матрице присутствуют запрещенные к размещению клетки, то для отыскания оптимального плана достаточно заменить их на максимальные тарифы (90 умноженное на 3).

	1	2	3	4	Запасы
1	40	60	72	270	600
2	50	60	90	30	800
3	60	20	40	40	650
Потребности	480	750	300	520

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

∑a = 600 + 800 + 650 = 2050

∑b = 480 + 750 + 300 + 520 = 2050

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	40	60	72	270	600
2	50	60	90	30	800
3	60	20	40	40	650
Потребности	480	750	300	520

Этап I. Поиск первого опорного плана.

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

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630]	90[170]	30	800
3	60	20	40[130]	40[520]	650
Потребности	480	750	300	520

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

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

Значение целевой функции для этого опорного плана равно:

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=40	V2=60	v3=90	v4=90
u1=0	40[480]	60[120]	72	270
u2=0	50	60[630]	90[170]	30
u3=-50	60	20	40[130]	40[520]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (2;4): 30

Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630]	90[170][-]	30[+]	800
3	60	20	40[130][+]	40[520][-]	650
Потребности	480	750	300	520

Цикл приведен в таблице (2,4; 2,3; 3,3; 3,4; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 170. Прибавляем 170 к объемам грузов, стоящих в плюсовых клетках и вычитаем 170 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630]	90	30[170]	800
3	60	20	40[300]	40[350]	650
Потребности	480	750	300	520

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=40	v2=60	v3=30	v4=30
u1=0	40[480]	60[120]	72	270
u2=0	50	60[630]	90	30[170]
u3=10	60	20	40[300]	40[350]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (3;2): 20

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630][-]	90	30[170][+]	800
3	60	20[+]	40[300]	40[350][-]	650
Потребности	480	750	300	520

Цикл приведен в таблице (3,2; 3,4; 2,4; 2,2; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 350. Прибавляем 350 к объемам грузов, стоящих в плюсовых клетках и вычитаем 350 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[280]	90	30[520]	800
3	60	20[350]	40[300]	40	650
Потребности	480	750	300	520

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=40	v2=60	v3=80	v4=30
U1=0	40[480]	60[120]	72	270
U2=0	50	60[280]	90	30[520]
U3=-40	60	20[350]	40[300]	40

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (1;3): 72

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	40[480]	60[120][-]	72[+]	270	600
2	50	60[280]	90	30[520]	800
3	60	20[350][+]	40[300][-]	40	650
Потребности	480	750	300	520

Цикл приведен в таблице (1,3; 1,2; 3,2; 3,3; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 120. Прибавляем 120 к объемам грузов, стоящих в плюсовых клетках и вычитаем 120 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	40[480]	60	72[120]	270	600
2	50	60[280]	90	30[520]	800
3	60	20[470]	40[180]	40	650
Потребности	480	750	300	520

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам, в которых u_i + v_i = c_ij,полагая, что u₁ = 0.

	v1=40	v2=52	v3=72	v4=22
U1=0	40[480]	60	72[120]	270
U2=8	50	60[280]	90	30[520]
U3=-32	60	20[470]	40[180]	40

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij. Минимальные затраты составят:

F(x) = 40*480 + 72*120 + 60*280 + 30*520 + 20*470 + 40*180 = 76840 ден.ед.

Они увеличились на 240 ден. ед.

Решение задачи с ограничительным условием № 2:

«Решите ещё раз задачу минимизации суммарных транспортных затрат при дополнительном условии, что объём перевозки груза от 3-го поставщика к 1-му потребителю не должен превышать 300 единиц ( то есть максимальная поставка груза от 3-го поставщика к 1-му потребителю равна 300 единицам). Оцените удорожание затрат на перевозку из-за этого условия».

В связи с тем, что от 3-го поставщика согласно оптимально найденному решению груз не поставлялся, 2-е условие никак не изменит стоимость затрат и самого решения.

Далее представим решение задачи в Exsel¹¹ (решение приведено только по первому условию, так как задача второго условия элементарна – она просто программируется в поле «Ограничения».

Решение задачи в Exsel.

Для начала вводим все заданные условия:

Далее пишем аналитическое выражение функции цели - формулу

« =СУММПРОИЗВ(B4:E6,B8:E10) в ячейке В14».

Затем мышкой или с помощью клавиатуры переходим к ячейке B14

После этого выполняем команду Сервис / Поиск решения

В диалоговом окне указываем:

• в поле «Равной»: «минимальному значению»;

• в поле «Изменяя ячейки»: «$B$8:$E$10»;

• в поле «Ограничения» - необходимо  добавить заданные ограничения, а именно:

• «$B$8:$E$10>=0»;

• «$F$8:$F$10<=$G$8:$G$10»;

• «$B$11:$E$11=$B$12:$E$12».

И, наконец, нажимаем на кнопку «Выполнить».