Каноническая и многомерная задачи о ранце и их интерпретации.

ОГЛАВЛЕНИЕ

1. Рабочая программа курса......................стр. 4

2. Краткий конспект лекций......................стр. 8

3. Задачник с решением типовых задач...стр. 53

4. Домашние контрольные задания..........стр. 114

5. Вопросы к экзамену.................................стр. 117

1. РАБОЧАЯ ПРОГРАММА КУРСА " МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ"

Часть 3.

Специальность:

" Прикладная информатика"

Специализация:

" Информационные системы обеспечения финансово-кредитной, юридической, управленческой и издательской деятельности"

Форма обучения: очно-заочная.

2/2

ПРЕДИСЛОВИЕ

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

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

СОДЕРЖАНИЕ КУРСА

3 семестр

МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ

2. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПЕРЕБОРНОГО ТИПА.

Задачи целочисленного булева программирования. Каноническая и многомерная задачи о ранце и их интерпретации. Задача коммивояжера и ее интерпретации. Задачи о назначениях и их интерпретации. Задача целочисленного линейного программирования в общей постановке. Метод ветвей и границ. Общая схема метода ветвей и границ Джеффриона-Марстена. Решение канонической задачи о ранце методом ветвей и границ. Решение многомерной задачи о ранце методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ. Решение задачи целочисленного линейного программирования методом ветвей и границ. Решение задачи о ранце с использованием табличной схемы. Решение задачи о ранце с использованием рекуррентных соотношений динамического программирования. Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования. Задачи теории расписаний. Задачи теории расписаний с одним обслуживающим прибором. Перестановочный прием в задачах теории расписаний. Теорема Лившица-Кладова. Задачи теории расписаний в общей постановке. Задача Джонсона. Графики Ганта. Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования. Сетевые модели. Расчет временных характеристик сетевых моделей. Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потоке. Алгоритм Форда-Фалкерсона поиска максимального потока в транспортной сети. Алгоритмы решения задач о назначениях. Минимаксные задачи о назначениях. Задачи о назначениях с индивидуальными предпочтениями.

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПЕРЕБОРНОГО ТИПА.

1.Решение канонической и многомерной задач о ранце методом ветвей и границ.

2.Решение задачи коммивояжера методом ветвей и границ.

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

4.Задачи теории расписаний.

5.Расчет временных характеристик сетевой модели.

6.Потоки в сетях. Алгоритм Форда-Фалкерсона.

7.Решение задачи о назначениях алгоритмом Куна.

8.Минимаксные и максиминные задачи о назначениях. Задачи о назначениях с индивидуальными предпочтениями.

ЛИТЕРАТУРА (основная)

1.Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М. Наука, 1969.

2.Таха Х. Введение в исследование операций. М. Мир, 1985, Том 1.

3.Вагнер Г. Основы исследования операций. М. Мир, 1972, том 1.

ЛИТЕРАТУРА (дополнительная)

1.Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М.Наука, 1975.

2.Форд Л., Фалкерсон Д., Потоки в сетях. М. Мир, 1966.

3.Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М. Мир, 1984.

4.Сергиенко И.В." Математические модели и методы решения задач дискретной оптимизации" Киев, Наукова думка, 1988.

5.Батищев Д.И., Прилуцкий М.Х." Оптимизация управленческих решений в сетевых моделях" Учебное пособие. Горький, ГГУ, 1985.

6.Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Учебное пособие. Изд. ННГУ, Н.Новгород, 1994.

К РАТКИЙ КОНСПЕКТ ЛЕКЦИЙ.

2.1.Задачи целочисленного булева программирования.

Под задачей математического программирования понимается задача (1):

extr f ( x ), (1)

x D

где D = {х (x) 0, j=1, 2,..., n, x Q, Q }.

Здесь ( x ), j=1, 2,..., n, и f( x ) - произвольные функции, а extr - max или min. Функция f( x ) называется целевой функцией, функционалом или критерием задачи (1), а D - множеством или областью допустимых решений задачи (1).

Среди задач типа (1) выделяют задачи, которые называют регулярными.

Для них:

- для каждого допустимого вектора x, x D, может быть определена непустая окрестность;

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

-локальный оптимум целевой функции совпадает с глобальным.

Примерами регулярных задач являются задачи выпуклого программирования (функция f( x ) - вогнута, а функции g( x ) -выпуклые). Если функции f( x ) и g ( x ) - линейные, то задача называется задачей линейного программирования.

Если область Q не является связной, то задача (1) называется дискретной задачей математического программирования или задачей дискретного программирования. Если функции f( x ) и g ( x ) при этом являются линейными, то такая задача называется задачей целочисленного линейного программирования. Если компоненты вектора x могут принимать лишь значения 0 или 1, то такая задача называется задачей целочисленного булева программирования.

Метод ветвей и границ.

Впервые этот метод был предложен в 1960 году для решения задачи целочисленного линейного программирования.

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

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

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

Основные понятия метода ветвей и границ.

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

Свойства, связывающие исходную задачу с ее релаксацией:

- если релаксация задачи не имеет решения, то и исходная задача решения не имеет,

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

- значение оптимума ( значение критерия на оптимальном решении) исходной задачи на минимум (максимум) не меньше (не больше) значения оптимума релаксационной задачи.

Ветвление - разбиение всего множества допустимых решений на непересекающиеся подмножества.

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

Потомок - подзадача, полученная в результате ветвления кандидата.

Стратегия - порядок выбора задач кандидатов.

Рекорд -значение критерия, соответствующее наилучшему решению, полученному к данному этапу вычислений.

Задачи теории расписаний.

Изучением вопросов оптимального планирования и управления на сетевых структурах занимается теория расписаний - раздел дискретного программирования. Задачи теории расписаний как правило трудноразрешимы, хотя для некоторых из них существуют эффективные алгоритмы решения. К задачам теории расписаний относятся:

- задачи упорядочения - минимизации функций на перестановках,

- задачи согласования - определение длительностей выполнения работ при конфликтующих потребностях работ в ресурсах,

- задачи распределения - при альтернативных технологиях выполнения работ.

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

Теорема Лившица-Кладова.

Следующие классы функций:

- f(i, t) = c(i) t + b(i), a> 0, i=1, 2,..., m,

- f(i, t) = c(i) exp(at) + b(i), i=1, 2,..., m, (a> 0),

- f(i, t) - монотонно-возрастающие функции, i=1, 2,..., m,

являются единственной совокупностью функций, для которых применим перестановочный прием.

Лемма.

Мощность любого потока не больше пропускной способности любого сечения.

Доказательство.

Надо доказать, что F(X) K(S(u), S(s)), для любого потока X и любого сечения (S(u), S(s)).

Из условий (4), просуммировав его по всем i, i S(u)\{u}, получим

(i, j) =0, (7)

(здесь суммирование производится, соответственно, по i S(u)\{u} и j V).

Из условий (2) следует, что

x(i, j) =0, (8)

если суммирование берется по одному и тому же произвольному подмножеству S множества V.

Рассмотрим величину

F(X) = x(u, j) = x(u, j) + x(i, j), где во втором слагаемом суммирование берется, соответственно, по i S(u)\{u} и i V, т.е. по условию (7) второе слагаемое равно 0. Преобразуем полученное выражение

x(i, j) + x(i, j), где в первом слагаемом суммирование берется, соответственно, по i S(u) и по i S(s), т.е. оно определяет величину потока через (S(u), S(s)) - сечение, а во втором слагаемом суммирование берется по одному и тому же множеству S(u), т.е. по условию (8), второе слагаемое равно нулю. Учитывая условия (1) математической модели, получаем доказательство леммы.

Теорема Форда-Фалкерсона “О максимальном потоке в транспортной сети”.

Если для некоторого потока найдется сечение такое, что величина потока через него равна пропускной способности этого сечения, то этот поток максимален.

Доказательство.

Пусть X(0) - поток, для которого существует сечение (S(u), S(s)), такое, что величина потока X(0) через него равна величине K(S(u), S(s)) - пропускной способности (S(u), S(s)) сечения.

Из доказательства леммы следует, что x(u, j) = x(i, j) = L(X)

где суммирование берется, соответственно, по i S(u) и по j S(s).

Будем доказывать теорему от противного.

Пусть существует поток X’, такой, что F(X’) > F(X(0)), т.е.

F(X’) = x’(u, j) = L(X’) > L(X(0)) = K(S(u), S(s)), что противоречит лемме.

Теорема доказана.

Вопросы к экзамену.

1.Задачи математического программирования в общей перестановке.

2.Общий подход к решению оптимизационных задач.

3.Задачи целочисленного булева программирования.

4.Каноническая задача о ранце и её интерпретации.

5.Многомерная задача о ранце и её интерпретации.

6.Задача коммивояжера и ее интерпретации.

7.Задача о назначениях и её интерпретации.

8.Задача целочисленного линейного программирования в общей постановке.

9.Метод ветвей и границ. Общая схема метода ветвей и границ Джеффриона-Марстена. 10.Решение задач о ранце методом ветвей и границ.

11.Решение задачи коммивояжера методом ветвей и границ.

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

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

14.Решение задачи о ранце с использованием рекуррентных соотношений динамического программирования.

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

16.Задачи теории расписаний. Задачи теории расписаний с одним обслуживающим прибором. Перестановочный прием в задачах теории расписаний.

17. Теорема Лившица-Кладова. Задачи теории расписаний в общей постановке. Задача Джонсона. Графики Ганта.

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

19. Сетевые модели. Расчет временных характеристик сетевых моделей.

20. Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потоке. Алгоритм Форда-Фалкерсона поиска максимального потока в транспортной сети.

21.Алгоритм Куна решения задач о назначениях.

22.Минимаксные задачи о назначениях.

23.Задачи о назначениях с индивидуальными предпочтениями.

ОГЛАВЛЕНИЕ

1. Рабочая программа курса......................стр. 4

2. Краткий конспект лекций......................стр. 8

3. Задачник с решением типовых задач...стр. 53

4. Домашние контрольные задания..........стр. 114

5. Вопросы к экзамену.................................стр. 117

1. РАБОЧАЯ ПРОГРАММА КУРСА " МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ"

К РАТКИЙ КОНСПЕКТ ЛЕКЦИЙ.

2.1.Задачи целочисленного булева программирования.

Под задачей математического программирования понимается задача (1):

extr f ( x ), (1)

x D

где D = {х (x) 0, j=1, 2,..., n, x Q, Q }.

Среди задач типа (1) выделяют задачи, которые называют регулярными.

Для них:

- для каждого допустимого вектора x, x D, может быть определена непустая окрестность;

-локальный оптимум целевой функции совпадает с глобальным.

Каноническая и многомерная задачи о ранце и их интерпретации.

Содержательное описание.

Есть несколько “предметов”, о которых известны их “веса” и “полезности”. Задан “ранец” определённой грузоподъёмности. Требуется поместить в “ранец” “предметы” таким образом, чтобы они все “убрались” в “ранец” и суммарная “полезность” от них была максимальна.

Математическая модель.

Исходные параметры модели.

Пусть i=1, 2,..., m - номера предметов, v(i) - “вес” “предмета” с номеров i, c(i) - “полезность” “предмета” с номером i, i=1, 2,..., m, v(0) - “вместимость” “ранца”.

Варьируемые параметры модели.

Обозначим через x - m мерный вектор, элементы которого x(i)=1, если “предмет” с номером i будет помещен в “ранец” и x(i)=0, если “предмет” с номером i не будет помещен в “ранец”.

Ограничения математической модели.

v(i) x(i) v(0), (1)

x(i) {0, 1}, (2)

Постановка оптимизационной задачи.

Критерий оптимальности для задачи о “ранце” имеет вид:

F( x ) = c(i) x(i ) max. (3)

Здесь ограничение (1) связано с вместимостью “ранца”, а условия (2) - естественные условия на введенные переменные.

Критерий (3) связан с максимализацией суммарной “полезности” от предметов, помещенных в “ранец”.

Задача (1) - (3) называется задачей о ранце (канонический случай).

Если кроме ограничения (1) по “весу” в задаче присутствуют подобные ограничения по другим характеристикам “предметов”, т.е. ограничения (1) преобразуются в (4):

v(i, j) x(i) b(j), j=1, 2,..., m, (4)

где v(i, j) - есть j-ая характеристика “предмета” с номером i, i=1, 2,..., m, j=1, 2,..., n, а b(j) -”вместимость “ранца” по j-той характеристике, то задача (2), (3), (4) называется многомерной задачей о ранце.

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

- задача загрузки уникального оборудования,

- задача формирования портфеля заказов, обеспеченного ресурсами,

- задача объемного планирования для предприятия,

- задачи загрузки контейнеров и др.

12 3 4 5 6 7 8 Следующая ⇒