Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Порядок выполнения задания

  • 2.4.1. Изучить алгоритмы 2.1-2.3. Оценить вычислительную сложность алгоритмов. Реализовать один из них - тот, что указан в варианте задания (табл. 2.3), в виде программной процедуры. Оформление процедуры должно допускать ее автономное тестирование. Осуществить тестирование с помощью примеров 2.1-2.3.
  • 2.4.2. Написать и отладить программу решения оптимизационной задачи, используя метод исчерпывающего поиска (табл. 2.3). Найти условия, при которых задача не имеет решения. Проверку этих условий предусмотреть в программе. Определить способы внешнего и внутреннего представления исходных, промежуточных и результирующих данных. Указать набор тестов для контроля правильности работы программы. Использовать рекомендации, приведенные в прил. 2. Оценить сложность решения задачи по времени и памяти.

Варианты

Согласно табл. 2.3 вариант задания определяет номер алгоритма, генерирующего все «-разрядные двоичные вектора, и название оптимизационной задачи, которую требуется решить. Каждая из предлагаемых оптимизационных задач является NP-трудной и может быть сформулирована как задача целочисленного линейного программирования с двоичными (или булевыми) переменными [10,20]. Одним из методов, возможно, не самым лучшим, решения NP-трудных задач является метод исчерпывающего поиска - полный перебор всех возможных наборов значений двоичных переменных и выбор среди них тех, которые обладают требуемым свойством в наибольшей или наименьшей степени. Именно так следует решать задачу, указанную в варианте задания. Для организации исчерпывающего поиска необходимо использовать разработанную процедуру генерации двоичных векторов.

Таблица 2.3

Номер варианта

Номер алгоритма

Название задачи

1

2.1

Задача размещения баз

2

2.2

Задача выбора проектов

3

2.3

Задача о доставке

4

2.1

Задача о доставке

5

2.3

Задача выбора проектов

6

2.2

Задача размещения баз

Задача размещения баз. Некоторая территория разделена на п районов. Предполагается, что военная база, расположенная в каком- то районе, может контролировать не только этот район, но и соседние, граничащие с ним районы. Каждый район характеризуется определенными убытками, связанными с расположением в нем военной базы. Требуется найти такие места размещения военных баз, чтобы суммарные убытки были минимальные и вся территория была под контролем.

Формализуем постановку задачи. Пусть с, - размер убытков, связанных с размещением военной базы в районе /, и А = {ау} - матрица, отражающая отношение соседства между районами территории:

Введем двоичные переменные:

Требуется найти значения переменных х,...,хп, при которых минимизируются суммарные убытки

и выполняются условия

Если С = с2 = ... = с„ = 1, то рассматриваемая задача сводится к отысканию наименьшего числа военных баз, способных контролировать всю территорию, и мест размещения этих баз.

Пример 2.4. Пусть некоторая территория разделена на районы, которым присвоены номера 1, 2, ..., 9 (рис. 2.1). Тогда матрица А, отражающая отношение соседства между районами этой территории, имеет вид, указанный на рис. 2.2.

Рис. 2.1

Рис. 2.2

При С = С2 = ... - Сд- 1 военные базы можно разместить в районах с номерами {1, 6, 7}. Существуют и другие оптимальные решения. Минимальное число баз, контролирующих всю территорию, неизменно равно 3.

Задача выбора проектов. Имеются п проектов S = {sb ..., s„} и т ресурсов R = {г,гт). Для каждого проекта st е S задано множество ресурсов Rj с R, необходимых для его реализации. Считается, что всякий проект может быть реализован за один и тот же промежуток времени. Если два различных проекта sh Sj е S используют один и тот же ресурс rk е Rt n Rj Ф 0, то они не могут выполняться одновременно. Требуется найти в S = {si, ..., л„} максимальное (по включению) множество независимых проектов, т. е. таких проектов, которые могут выполняться одновременно.

Пусть матрица А = {ау} отражает отношение «проект-ресурс»:

Заметим, что строки этой матрицы являются битовыми шкалами для Rt сЛ (г - 1,и), a R играет роль универсального множества. Определим двоичные переменные:

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

и выполняются условия

для любых 1 при которых Xj = xk= 1. Эти условия отражают требования независимости выбранных проектов.

Пример 2.5. Пусть S — {si, s2, Si, s4, s5}, R = {гь г2, г3, г4}. Потребность проектов в ресурсах описывает матрица А, приведенная на рис. 2.3. Здесь максимальные множества независимых проектов: {s2, s3, ^4}, {-?2, ^з, ^5}.

Рис. 2.3

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

Введем двоичные переменные:

Пусть стоимость затрат, связанных с маршрутом у, равна с;, и матрица А = {а^} отражает отношение «клиент-маршрут»:

Г1, если клиент/обслуживается маршрутом /',

аи =

[О в противном случае (/ = 1, «; j = 1, т).

Необходимо найти значения двоичных переменных хь хт, при которых достигается минимум суммарных затрат

и выполняются условия

Если с j = с2 - ... - ст 1, то задача сводится к поиску наименьшего числа маршрутов, позволяющих обслуживать каждого клиента один раз в день.

Пример 2.6. Пусть число клиентов равно 5, а число маршрутов равно 4. Матрица А, описывающая отношение «клиент-маршрут», приведена на рис. 2.4.

Рис. 2.4

Рис. 2.5

Если С - 15, с2 15, Сз = 20, С = 10, то множество маршрутов {1,4} - оптимальное решение задачи о доставке. Поскольку в А второй и четвертый столбцы совпадают, то существует и другое оптимальное решение {1,2}. Однако если матрицу А изменить так, как указано на рис. 2.5, то задача о доставке не имеет решения.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>