Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 13

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 7 8 9 10 11 12 < 13 > 14 15 16 17 18 19 .. 84 >> Следующая


max CijXij —>• min . (2.1.14)

Если ограничиться указанными условиями (2.1.11)-(2.1.13), то получим задачу о назначении, в оптимальном решении которой может быть несколько циклов.
Гл. 2. Модели дискретного программирования

35

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

Ui — Uj + nxij < п — I; Ui > 0 г, j = 1, 2,..., п; г ф j.

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

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

T = . . . 5 5 H ) •

Выпишем для каждого звена цикла т приведенное выше условие:

Uil - Ui2 + п < п - 1,

Ui2 — Ui3 + п < п — 1,

щк - Uil + Г1 < п - 1.

Сложим эти неравенства. Получим кп < к(п—1), что невозможно при кф 0.

Если существует цикл, не проходящий через город 0, то указанное условие не выполнено.

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

Положим Ui = р, если і-й город посещается на р-м шаге; тогда Ui-Uj < п — 1. Отсюда следует, что указанное условие выполняется, ЄСЛИ Xij = 0.

Пусть Xij = 1; тогда если щ = р, то Wj = р + 1, р — (р + 1) + + п < п — 1, п — 1 = п — 1.

В силу единственности цикла в условиях (2.1.11) и (2.1.12) і и j должны изменяться от 1 до п.

Рассмотрим соотношение между значениями целевых функций для оптимальных решений задач назначения и коммивояжера для одной и той же матрицы С. Пусть ро — оптимальное решение (подстановка) задачи о назначении, f(po) — значение целевой функции, и Zo — оптимальное решение задачи коммивояжера, l(zо) — длина оптимального маршрута. Покажем, что f(po) ^ Kzo)-

Задача о назначении определена на множестве А матриц х = (xij) с числом циклов, большим или равным 1; задача коммивояжера определена на множестве матриц S с одним циклом. Поэтому S С А; тогда f(po) < l(zo), т-е- оптимальное решение задачи о назначении дает нижнюю оценку для оптимального решения задачи коммивояжера. Покажем, что эта оценка может быть сколь угодно плохой, т.е. существуют матрицы (7, для которых разность l(zo) — f(po) может быть сколь угодно большой.

3*
36 Разд. I. Предмет и модели дискретного программирования

Пусть оптимальное решение задачи о назначении состоит из двух циклов, все элементы матрицы (7, входящие в цикл, равны р, а все остальные элементы матрицы С равны q, q > р. Представим ситуацию графически (рис. 2.3).

Чтобы перейти к оптимальному решению задачи коммивояжера, т.е. к одному циклу, необходимо разорвать первый и второй циклы в отмеченных местах, удалить два звена с длиной 2р и добавить два звена с длиной 2q. Если в первом цикле к звеньев, а во втором s, т0 /(Po) = p(k + s). В оптимальном решении задачи коммивояжера получаем l(zo) = (к — I)р + (s — I)р + 2q = (к + s — 2)р + 2q. Поэтому l(zo) - f(po) = (к + s—2)p + 2q — (к + s)p = 2(q - p). Отсюда следует, что при фиксированном значении р величина q может быть выбрана так, что разность l(zo) — f(po) может быть сколь угодно большой.

Сформулируем задачу коммивояжера на языке теории графов. Рассмотрим неориентированный (симметричный) полный п-вершин-ный граф, каждая из вершин которого соответствует одному из городов и каждый город — одной вершине, сц — Cji. Необходимо найти гамильтонов цикл кратчайшей длины. Если граф не является полным, то возникает задача о существовании гамильтонова цикла. Для ориентированного полного графа Cij ф Cji возникает задача о поиске гамильтонова контура минимальной длины. Если граф не является полным (как и в симметричном случае), то неизвестно, разрешима ли задача. Приведем без доказательства достаточные условия существования гамильтонова цикла в n-вершинном графе *).

Теорема Оре. Если п > 3 и для любой пары Uj v несмежных вершин выполнено условие du + dv > п, то гамильтонов цикл существует (du, dv — степени вершин и, v).

Теорема Дирака. Если п > 3 и для любой вершины и выполнено условие du > п/2, то гамильтонов цикл существует.

*)Емеличев В. А, Мельников А. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, 1990. — С. 199, 200.
Гл. 2. Модели дискретного программирования

37

Рассмотренная задача коммивояжера называется замкнутой. Можно рассмотреть задачу, в которой возврат в начальный город не предполагается. Такая задача называется открытой. Можно также рассмотреть открытую задачу, у которой начальный и конечный города не фиксированы. Обе эти задачи легко сводятся к стандартной задаче, т.е. к замкнутой задаче, у которой начальный город фиксирован и совпадает с конечным.

Задача многих коммивояжеров. Пусть имеется п городов; множество городов обозначим через P = (1,2,..., гг). Пусть сц >0 — «расстояние» от города г до города j. Пусть т <С п — число коммивояжеров, каждый из которых находится в одном из городов. Требуется разбить множество из п городов на т непересекающихся подмножеств так, чтобы суммарная длина путей всех коммивояжеров была минимальна.
Предыдущая << 1 .. 7 8 9 10 11 12 < 13 > 14 15 16 17 18 19 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100