Построение нижних и верхних оценок минимального значения целевой функции.

Задача коммивояжера и метод ветвей и границ

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

Транспортная задача (ТЗ) ЛП может быть сформулирована следующим образом.

Имеется m пунктов отправления (производства) A₁,..., A_m, в которых имеется товар в количестве a_i,...,a_m соответственно. Кроме того, имеется n пунктов назначения (потребления) B1,..., B_n, в которых имеются заявки на этот товар в количестве b₁,..., b_n соответственно. Предполагается, что

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

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

Математическая модель ТЗ состоит в следующем. Обозначим через x_ij количество товара, перевозимого из A_i в B_j. Составим задачу ЛП:

На практике условие баланса может не выполняться. Что делать? Если

, (производится больше, чем потребляется),

то вводим новый пункт потребления B_n₊₁ с запросом

Полагаем

c_i_,_n+1 = 0, i = 1,... , m.

Если же

, (потребляется больше, чем производится),

то вводим новый пункт производства A_m₊₁ с предложением

Полагаем

c_m_+1,_j =0, j = 1, ... , n.

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

Отметим, что ранг системы ограничений ТЗ равен т + п-1 (на 1 меньше т + п за счет связующего условия баланса). Поэтому количество базисных переменных также равно т + п — 1.

Исходные данные ТЗ удобно представлять в виде транспортной таблицы (ТТ).

A_i/B_j	B₁	B₂	…	B_n	Запасы a_i
A₁	с₁₁	с ₁₂	…	с _1n	a₁
A₂	с ₂₁	с ₂₂	…	с _2n	a₂
…	…	…	…	…	…
A_m	с_m1	с_m2	…	c_mn	a_m
Заявки b_j	b₁	b₂	…	b_n	Σ a_i = Σ b_j

Опорным планомТЗ называется такое распределение объемов перевозок в ТЗ, что

− это распределение является допустимым,

− число базисных переменных равно т + п — 1, все остальные (свободные) переменные равны нулю. Отметим, что некоторые базисные переменные также могут равняться нулю,

− не существует цикла, все вершины которого соответствуют базисным переменным.

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

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

Математическая модель такой ситуации называется задачей коммивояжера,которая состоит в следующем. Задан полныйориентированный или неориентированный граф, для определенности, орграф. Орграф называется полным, если каждая пара вершин i и j соединена дугами (i, j) и (j, i). Известна стоимость с_ij каждой дуги (i,j). Требуется построить гамильтонов цикл (т.е. цикл, проходящий через каждую вершину ровно по одному разу) такой, что суммарная стоимость всех его дуг была минимальной. Отметим, что есть взаимно однозначное соответствие между гамильтоновыми циклами (т.е. маршрутами коммивояжера) в полном графе с п вершинами и перестановками п элементов. Перестановка = (i₁,...,i_n) соответствует маршруту коммивояжера, проходящему через вершины i₁,..., i_n и включающему дуги (i₁, i₂), (i_2,i₃), …, (i_n-₁,i_n),(i_n,i₁).

Основным методом решения задачи коммивояжера является метод ветвей и границ (МВиГ). Этот метод является универсальным и может применяться для решения практически всех дискретных экстремальных задач.

Основные принципы МВиГ для решения задачи минимизации состоят в следующем.

1) Ветвление.

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

Указанный процесс можно представить в виде так называемого дерева ветвлений. Вершины дерева ветвлений соответствуют подзадачам и разбиты на уровни. Исходная задача является вершиной нулевого уровня. Подзадачи, полученные из исходной задачи, являются вершинами первого уровня. Подзадачи, полученные из вершин первого уровня, являются вершинами второго уровня, и т.д. Дуги направлены из вершин уровня i в вершины уровня i + 1. В каждую вершину входит ровно одна дуга.

Для исходной задачи, а также для любой ее подзадачи могут быть найдены числа LB и UB такие, что

LB ≤ F^* ≤ UB,

где F^* - минимальное значение целевой функции в задаче или подзадаче, LB и UB – его нижняя и верхняя оценки соответственно.

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

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

Может оказаться, что задача отыскания нижней и/или верхней оценки сама является сложной. В этом случае соответствующая оценка не используется и можно положить LB =-, UB = .