Методы решения транспортной задачи.

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

Тогда:

При транспортная задача называется несбалансированной.

Случаи несбалансированности транспортной задачи

1. - предложение больше спроса. В задачу вводим фиктивного -й потребителя со спросом и с нулевыми затратами на доставку. Тогда задача становится сбалансированной.

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

Алгоритм решения сбалансированной транспортной задачи

1. Строим начальный допустимый план доставки товара. Транспортную задачу записываем в виде таблицы. Поставщиков записываем в строках, потребителей – в столбцах, запас товара – справа, спрос на товар – внизу, в каждую клетку таблицы записываем :

		…
		…
…	…	…	…	…
		…
		…

Пример 5.1. Имеется три топливохранилища , , (m=3) и пять АЗС (автозаправочных станций, n=5). Суточные возможности хранилища: , потребности АЗС: 80, 170, 150, 180, 70 ед. соответственно. Затраты на доставку записаны в таблице 1.

Методы построения допустимого плана поставок

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

В северо-западную клетку (левый верхний угол) доставляем максимально возможное количество единиц товара: . Если весь товар с -го склада вывезен, то в других клетках -ой строки ставим прочерки. Аналогично поступаем с клетками -го столбца, если -ый потребитель удовлетворён. Заполняем северо-западные оставшиеся клетки, пока не вывезем весь товар и не удовлетворим всех потребителей. Заполните таблицу 1.

Таблица 1

Значение целевой функции .

Б) Метод минимального элемента

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

Замечание. Если добавлены фиктивные поставщики или потребители, то их при нахождении минимума не учитывать. Заполните таблицу.

 

Начальный план доставки методом минимального элемента:

.

2. Проверяем начальный план доставки на невырожденность.

План доставки товара называется невырожденным, если число заполненных клеток равно , иначе план называется вырожденным.

В этом примере .

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

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

В рассматриваемом примере начальный план доставки, построенный по методу минимального элемента, является вырожденным, так как заполнены только шесть клеток. Фиктивную доставку осуществим в клетку (3;1).

3. Находим оптимальное решение методом потенциалов (существуют и другие методы). Присваиваем каждому поставщику и каждому потребителю потенциалы. Потенциал -го поставщика – , потенциал -го потребителя :

	0

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

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

считаем . Тогда

Для всех незанятых клеток вычисляем их потенциалы: .

Критерий оптимальности

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

Иначе выбираем и в ту клетку, в которой достигается максимум, завозим товар, ставим в ней знак «+» и строим цикл перераспределения доставки товара. В вершинах цикла ставим знаки «+» или «–», чередуя их, начиная от клетки, где мы поставили первый «+». Если максимум достигается не в одной клетке, то выбираем из них любую.

т.к. (план не оптимален), ставим в клетку (2;2) знак «+» и начинаем строить цикл:

		+
	0

Находим минимальное значение доставки по всем клеткам со знаком «–». После этого в клетки со знаком «+» добавляем данное значение, а из клеток со знаком «–» вычитаем. Строим новый план доставки и возвращаемся на шаг 2 и т.д., пока не будет выполнен критерий оптимальности.

		150
	0

Новое значение целевой функции: . Количество занятых клеток 7, следовательно, план невырожденный, переходим к шагу 3.

Критерий оптимальности выполняется, следовательно, получено оптимальное решение .

 

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

 

Таблица 1.2

 

Исходные данные транспортной задачи

Тарифы, руб./шт.	1-й магазин	2-й магазин	3-й магазин	Запасы, шт
1-й склад
2-й склад
3-й склад
4-й склад
Потребности, шт

 

Целевая функция и ограничения данной задачи имеют вид

 

 

 

 

Экранные формы, задание переменных, целевой функции, ограничений и граничных условий двухиндексной задачи (1.5) и ее решение представлены на рис.1.15, 1.16, 1.17 и в табл.1.3.

 

 

Рис.1.15. Экранная форма двухиндексной задачи (1.5)(курсор в целевой ячейке F15)

 

Таблица 1.3

 

Формулы экранной формы задачи (1.5)

Объект математической модели

Выражение в Excel

 

Переменные задачи

C3:E6

 

Формула в целевой ячейке F15

=СУММПРОИЗВ(C3:E6;C12:E15)

 

Ограничения по строкам

 

в ячейках F3, F4, F5, F6

=СУММ(C3:E3)

 

=СУММ(C4:E4)

 

=СУММ(C5:E5)

 

=СУММ(C6:E6)

 

Ограничения по столбцам

 

в ячейках С7, D7, E7

=СУММ(C3:C6)

 

=СУММ(D3:D6)

 

=СУММ(E3:E6)

 

Суммарные запасы и потребности

 

в ячейках H8, G9

=СУММ(H3:H6)

 

=СУММ(C9:E9)

 

Рис.1.16. Ограничения и граничные условия задачи (1.5)

 

 

Рис.1.17. Экранная форма после получения решения задачи (1.5)(курсор в целевой ячейке F15)

Задача о назначениях

Постановка задачи. Имеется n видов работ и n исполнителей. Известны затраты , необходимые для того, чтобы -й исполнитель выполнил -ю работу. Нужно назначить исполнителей на работы таким образом, чтобы суммарные затраты на проведение всех работ были минимальными. Каждый исполнитель делает одну работу.

Запишем экономико-математическую модель:

 

 

Целевая функция     Сумма элементов каждого столбца =1(одна единица, остальные нули) Сумма элементов каждой строки =1 (одна единица, остальные нули)

 

 

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