Математические методы решения задачи о получении оптимального плана перевозок (транспортной задачи)

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

Условимся отмечать знаком «плюс» те вершины цикла, в которых перевозки необходимо увеличить, а знаком «минус» – те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть означенным. Перенести какое-то количество единиц груза по означенному циклу – это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по-прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце – заявке этого столбца.

Полученный  новый опорный план транспортной задачи снова проверяют на оптимальность.

 

2 РЕШЕНИЕ ЗАДАЧИ О ПОЛУЧЕНИИ  ПЛАНА ГРУЗОПЕРЕВОЗОК

2.1 Математическая модель

У поставщиков  сосредоточено соответственно 60, 40, 20 единиц некоторого однородного груза, который необходимо добавить потребителям ,,, в количестве 40, 30, 30 и 50 единиц. Данные о стоимости перевозок единицы груза от поставщиков к потребителям приведены в таблице. Составить такой план перевозок от поставщиков к потребителям, при котором суммарные затраты на перевозку груза будут минимальны.

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	2	3	5	1	60
A2	3	4	9	4	70
A3	2	5	2	5	20
Потребности	40	30	30	50	150

Обозначим через  количество единиц груза, перевозимого из пункта в пункт

Тогда

2 ден. ед. – стоимость перевозки груза из в ,

3 ден. ед. – стоимость перевозки груза из в ,

5 ден. ед. – стоимость перевозки груза из в ,

  ден. ед. – стоимость перевозки груза из в ,

3 ден. ед. – стоимость перевозки груза из   в

4 ден. ед. – стоимость перевозки груза из в ,

9 ден. ед. – стоимость перевозки груза из в ,

2_ден. ед. – стоимость перевозки груза из в ,

2_ден. ед. – стоимость перевозки груза из в ,

5 ден. ед. – стоимость перевозки груза из в ,

2_ден. ед. – стоимость перевозки груза из в ,

5 ден. ед. – стоимость перевозки груза из в .

Суммарная стоимость перевозок  равна:

(2₊3₊5_{++3+4+9+2+2+5+2+5)} ден. ед.

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

2₊₃₊5_{++3+4+9+2+2+5+2+5}

Опишем систему ограничений:

1)         (2 + 3_{+ 5} + ₎ ед. груза – мощность поставщика ,

(3 + 4_{+ 9} + 2₎ ед. груза – мощность поставщика ,

(2 x₃₁ + 5 x₃₂ + 2 x₃₃ + 5 x₃₄) ед. груза – мощность поставщика .

Так как мощности поставщиков ограничены и заданы условием задачи, то:

 

 

2)         (2 + + ) ед. груза – потребность пункта ,

( + + ) ед. груза – потребность пункта ,

( + + ) ед. груза – потребность пункта ,

( + + ) ед. груза – потребность пункта .

Так как потребности пунктов ,,, в грузе ограничены и заданы условием задачи, то:

 

3) Условие неотрицательности

 

Таким образом, математическая модель задачи имеет вид:

=(2_+3+5++3+4+9+

+2_+2+5+2+5)

при ограничениях:

 

.

Суммарная мощность поставщиков равна: 60+70+20=150 (ед. груза)

Суммарный спрос потребителей равен: 40+30+30+50=150 (ед. груза)

Это закрытая модель.

2.2 Получение опорного плана грузоперевозок

Для составления исходного плана  перевозов используем метод северо-западного  угла:

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	2 40	3 20	5	1	60
A2	3	4 10	9 30	4 30	70
A3	2	5	2	5 20	20
Потребности	40	30	30	50	150

 

 

 

Стоимость перевозок по этому  плану

 

 

 

 

 

 

 

 

2.3 Получение оптимального плана грузоперевозок

 

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

 

 

,

 

 

 

 

 

Полагая, например, , найдем:

 

 

 

 

 

 

Для каждой свободной клетки вычислим относительные оценки:

 

 

 

 

 

 

 

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

Определим новое базисное решение.

Минимальной разностью является для клетки (3, 3). Отрицательная оценка показывает, что при включении в данную свободную клетку каждой единицы груза общая стоимость уменьшается на 8 единицы. Для определения количества груза , подлежащего распределению, построим замкнутый цикл (указан пунктиром в таблице). Одна из вершин цикла находится в незанятой клетке (3, 3), которую отмечаем знаком «плюс». Все остальные вершины цикла находятся в базисных клетках, с чередующимися знаками «минус» и «плюс».

	Пункты	B1	B2	B3	B4	Запасы
	A1	2 40	3 20	5	1	60
	A2	3	4 10	9   – 30	4 + 30	70
	A3	2	5	2   +	5 – 20	20
	Потребности	40	30	30	50	150

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

 

	Пункты	B1	B2	B3	B4	Запасы
	A1	2 40	3   – 20	5 +	1	60
	A2	3	4   + 10	9 – 10	4 50	70
	A3	2	5	2 20	5	20
	Потребности	40	30	30	50	150

Стоимость перевозок по этому плану

 

Исследуем базисное решение на оптимальность.

Вычислим потенциалы и , исходя из базисных переменных:

 

 

,

 

 

 

 

 

Полагая, например, , найдем:

,
,
,

Для каждой свободной клетки вычислим относительные оценки:

 

 

 

 

 

 

 

 

Условие оптимальности плана перевозок  не выполняется, так как одна из оценок отрицательна.

Определим новое базисное решение.

Построим замкнутый цикл пересчета для свободной клетки (1, 3), для которой не выполняется неравенство, и перераспределим поставки согласно этому означенному циклу, аналогично п.3.

В клетку (1, 3) поместим груз .

После преобразований получаем новый  план перевозок:

	Пункты	B1	B2	B3	B4	Запасы
	A1	2 40	3   – 10	5 10	1 +	60
	A2	3	4   + 20	9	4 – 50	70
	A3	2	5	2 20	5	20
	Потребности	40	30	30	50	150

Стоимость перевозок по этому плану

 

Исследуем базисное решение на оптимальность.

Вычислим потенциалы и , исходя из базисных переменных:

 

 

,

 

 

,

.

 

Полагая, например, , найдем:

,
,
,

Для каждой свободной клетки вычислим относительные оценки:

 

 

 

 

 

 

 

 

Условие оптимальности плана перевозок  не выполняется, так как одна из оценок отрицательна.

Определим новое базисное решение.

Построим замкнутый цикл пересчета для свободной клетки (1, 4), для которой не выполняется неравенство, и перераспределим поставки согласно этому означенному циклу, аналогично п.3.

В клетку (1, 4) поместим груз .

После преобразований получаем новый  план перевозок:

	Пункты	B1	B2	B3	B4	Запасы
	A1	2   – 40	3	5 10	1 + 10	60
	A2	3   +	4 30	9	4 – 40	70
	A3	2	5	2 20	5	20
	Потребности	40	30	30	50	150