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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 .. 84 >> Следующая


Будем также считать, что

Ai >0, А2 > 0, Ai + А2 = 1.

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

Ii (z°) = min Ii (z) = /?, і = I, 2.

Z Є Zq

Процесс оптимизации каждой свертки критериев сводится к решению задачи коммивояжера для функций fi(z), і = I, 2,..., 9.

В качестве начального выбирается тот из маршрутов zJ и z\, для которого значение оптимизируемой свертки меньше.

Для улучшения начального решения используются модифицированные для оптимизации свертки комбинированные алгоритмы локальной оптимизации.

Подробное описание алгоритмов и результатов эксперимента содержится в [37].
Задачи

Предлагаемые ниже задачи носят теоретический характер и

связаны с доказательством некоторых утверждений, разработкой

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

1. Привести пример матрицы расстояний с неотрицательными элементами, для которой разность между значениями целевых функции для оптимальных решений задач коммивояжера и назначений сколь угодно велика. Для каких матриц эти значения совпадают?

2. Привести пример симметричной матрицы расстояний с неотрицательными элементами, для которой разность между значением целевой функции оптимального решения задачи коммивояжера и длиной кратчайшего 1-дерева сколь угодно велика. Для каких матриц эти значения совпадают?

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

4. Привести примеры матриц расстояний с неотрицательными элементами, для которых алгоритм типа «greedy» перехода в ближайшую точку, начиная с первой, дает:

— оптимальное решение;

— сколь угодно плохое решение.

5. Описать множество матриц расстояний, для которых алгоритм типа «greedy» перехода в ближайшую точку, начиная с первой точки, дает единственное оптимальное решение.

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

7. Указать способ сведения открытой задачи коммивояжера к замкнутой.

8. Сформулировать задачу обхода конем всех полей шахматной задачи как симметричную открытую задачу коммивояжера*).

*)Мудрое В.И. Задача коммивояжера. — М.: Знание, 1969.
Задачи

225

9. Доказать асимптотическую формулу (2.1.17) для задачи т > 1 коммивояжеров.

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

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

12. Предположим, что коммивояжер должен посетить вершину X сразу после посещения вершины у. Как это можно учесть в алгоритме ветвей и границ решения задачи коммивояжера?

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

14. Пусть известен некоторый алгоритм решения линейной задачи о назначении. Описать алгоритм решения задачи о назначении на «узкие места» с применением алгоритма решения линейной задачи о назначении.

15. Пусть известен некоторый алгоритм решения линейной задачи коммивояжера. Описать алгоритм решения задачи коммивояжера на «узкие места» с применением алгоритма решения линейной задачи коммивояжера.

16. Сформулировать задачу о кратчайших расстояниях на графе как задачу целочисленного линейного программирования с булевыми переменными *).

17. Привести пример связного графа без петель и кратных ребер, для которого алгоритм типа «greedy» с выбором на каждом шаге вершины с наибольшей степенью дает оптимальное вершинное покрытие с числом вершин > 2.

18. Привести пример взвешенного по ребрам графа с четным числом вершин без изолированных вершин, для которого неразрешима задача о паросочетании минимального веса (задача о реберном покрытии разрешима всегда).

19. Привести пример задачи об одномерном целочисленном ранце, для которой достигается оценка є = 1 /2 в алгоритме гарантированного функционирования, или показать, что это оценка недостижима.

20. Свести общую задачу линейного целочисленного программирования к задаче с булевыми переменными.

*) Зуховицкий С. И., Авдеева JI. И. Линейное и выпуклое программирование: Справ, руководство. — М.: Наука, 1964.

15 И.Х. Сигал, А.П. Иванова
Упражнения

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

1. 17xi + 9x2 + Ижз + 13^4 + 15ж5 + 7xq + 2^7 —>¦ max,

7xi H- 3x2 4жз + 5^4 H- 6^5 H- 2xq H- Ж7 ^ 15,

Xj Є {0; 1}, j = I, 2,..., 7.

2. бОжі + 60^2 + 40жз + 10^4 + 20^5 + Южб + 3^7 —>• max,

Зхі H- 5^2 H- 4жз + Х4. H- 4ж5 H- Зжб H- Ж7 ^ 10,

Xj Є {0; 1}, J = 1,2,...,7.

3. 2хі H- 3x2 4жз H- 5^4 + ЗЖ5 -|- 4жб H- 7^7 -I- —У max,

Зхі + Х2 + Зжз + 2ж4 + Ж5 + 3^6 + Ж7 + Xs < 15,

жі Є {0; 1}, j = 1,2,...,8.

4. 4жі + 28^2 H- 5жз -|- 9^4 -|- 6ЗЖ5 -|- ІІЖб —^ max,
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100