Теория графов 3 (стр. 2 из 3)

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

Условие въезда в пункт 1 аналогично условию въезда из пункта 1 (Рис.7). Требование минимальной продолжительности маршрута запишется в виде целевой функции:

min L= t₁₁

₁₁+ t_{12 12}+ t_{13 13}+ t_{14 14}+ t_{15 15}+ t_{21 21}+ t_{22 22}+…+ t_{55 55} ,

где t_ij берутся из исходной таблица, а

_ij - искомые переменные.

Тогда всю задачу можно сформулировать:

min L =

tij ij,

(*)

В результате решения системы (*) получим (Рис.8) следующие значения

остальные =0;

min L = 10+8+10+20+14=62

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

min L = tij ij,

1.3. Транспортная задача

Транспортная задача – это задача о выборе плана перевозок однородного продукта из пунктов производства в пункты потребления. Пусть имеется m продуктов отправления и n пунктов назначения. Запасы продукта в пунктах отправления обозначим через a_i , потребность в продукте в пункте потребления – b_{j .} Расходы на доставку единицы продукта из i-го пункта отправления в j-й пункт назначения равняются C_ij.

Балансовое условие производства и потребления имеет вид

Требуется определить x_ij – количество продукта, доставляемого от i-го пункта отправления к j-му пункту потребления. При этом обязательными условиями являются: необходимость удовлетворения всех потребителей, оптимальный план доставки продукта должен обеспечить минимум общей суммы затрат на доставку. Экономико-математическая модель задачи:

min L =

В рассмотренной ЭММ предполагается, что суммарные запасы равны суммарным потребностям. Такая модель называется закрытой. Если это условие не выполняется, то модель называется открытой. Для сведенья открытой модели к закрытой вводится или фиктивный пункт отправления, или фиктивный пункт назначения.

Транспортная задача может быть решена методами линейного программирования. Однако благодаря особенностям переменных задачи разработаны специальные методы ее решения. Наиболее применяемый из них метод потенциалов.

Согласно методу потенциалов, каждому i-му пункту отправления устанавливается потенциал U_i, который можно интерпретировать как цену продукта в пункте отправления, а каждому j-му пункту назначения устанавливается потенциал V_j, который можно условно принять как цену продукта в пункте назначения равна его цене в пункте отправления плюс транспортные расходы на его доставку, т.е. V_j= U_i+c_ij.

Алгоритм решения транспортной задачи методом потенциалов включает следующие этапы:

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

2. построение системы потенциалов на основе равенства V_j= U_i+c_ij;

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

Третий этап повторяется до тех пор, пока план перевозок не станет оптимальным.

Пример. Пусть имеется 3 поставщика и 4 потребителя. Запасы продукта у поставщиков, спрос потребителей и транспортные расходы на доставку единицы продукта от i-го поставщика к j-му потребителю заданы в таблице:

Поставщик	Потребитель				Запас
	1	2	3	4
1	3	5	6	2	170
2	6	4	7	5	250
3	5	4	6	5	180
Спрос	180	230	160	60	600

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

Решение. Обозначим x_ij – количество продукта, доставляемого от i-го поставщика к j-му потребителю. Тогда модель:

min L = 3x₁₁+5x₁₂+6x₁₃+2x₁₄+6x₂₁+4x₂₂+7x₂₃+5x₂₄+5x₃₁+4x₃₂+6x₃₃+5x₃₄

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

таблица 2

Поставщики		Потребитель				Запас
		1	2	3	4
		V1=3	V2=5	V3=8	V4=7
1	U1=0	3 150	5 20	6 6	2 2	170
2	U2=1	6 7	4 210	4 70	5 6	250
3	U3=2	5 7	4 6	6 120	5 60	180
Спрос		150	230	160	60	600

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

Первоначальный план содержит шесть перевозок: от первого поставщика – 150 ед. к первому потребителю и 20 ед. ко второму; от второго поставщика – 210 ед. ко второму и 40 ед. к третьему; от третьего поставщика – 120 ед. к третьему потребителю и 60 ед. к четвертому.

Построим систему потенциалов на основе равенства:

V_j= U_i+c_ij.