ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5527
Скачиваний: 27
41
в) задачи отыскания алгоритма получения конфигурации, а
также выделения из заданной совокупности конфигураций таких,
которые обладали бы избранным свойством в наибольшей или наи-
меньшей степени, или задачи оптимизации.
Элементы комбинаторных суждений появились еще в глубо-
кой древности, на заре формирования математической науки. В ходе
истории они развивались совместно с другими разделами математи-
ки, Нетрудно увидеть, что в ряде областей современной математики:
теории чисел, алгебре, геометрии, математической логике и др. мно-
гие основные понятия и методы имеют дискретную природу и обла-
дают устойчивыми связями. Это позволяет рассматривать задачи
комбинаторного анализа в различных интерпретациях, исследовать
проблемы различной природы с единой точки зрения, В наше время
в связи с развитием вычислительной техники возможности дискрет-
ных методов исследования и их значение резко возросли. Наряду с
исторически сложившейся комбинаторной теорией (комбинаторным
анализом) в современной математике существуют: теория графов,
геометрия чисел, дискретный и конечный анализы, исследование
операций.
3.1
Постановка
задач
комбинаторного
программирования
Изучение основ комбинаторного анализа полезно начать с рас-
смотрения нескольких примеров, содержащих постановки задач оп-
тимизации, типичных для АСУ и относящихся к области комбина-
торного программирования. Комбинаторное программирование –
это подраздел математического программирования, включающий
чисто дискретные задачи и специфические методы их исследования.
Началом развития комбинаторного программирования считают 40-
50-е годы, первыми объектами исследования явились простые идеа-
лизированные модели, такие как задача коммивояжера, задача обра-
ботки деталей на двух станках и т.д.
Задачи комбинаторного программирования возникают во мно-
гих областях практической деятельности: организация и размещение
производства, планирование транспортных перевозок, распределе-
ние ресурсов и др. Задачи этого типа можно интерпретировать как
задачи оптимизации функций, определенных на заданном множест-
42
ве выборок (комбинаций) из конечного числа элементов.
При рассмотрении примеров особое внимание уделим форма-
лизации задач, т.к. уже этот этап часто вызывает трудности на прак-
тике.
3.1.1
Задачи
определения
очередности
выпол
-
нения
заданий
Проблема. Для заданного множества заданий (работ, опера-
ций) исполнителю требуется выбрать наилучшую последователь-
ность их выполнения. Понятие «наилучшей» последовательности
зависит от конкретных условий и чаще всего определяется дирек-
тивными сроками окончания отдельных заданий.
Введем следующие обозначения:
{
}
N
I
N
,...,
2
,
1
=
– множество номеров заданий, число кото-
рых равно
N
;
(
)
N
π
π
π
π
,...,
,
2
1
– перестановка элементов множества
I
N
, определяющая очередность выполнения заданий (например,
3
5
=
π
означает, что третье задание выполняется пятым по поряд-
ку);
)
( j
τ
– время выполнения
j
-го задания;
)
( j
T
– директивный срок окончания
j
-го задания;
)
( j
a
– штраф, налагаемый на исполнителя за невыполнение
j
-го задания к сроку
)
( j
T
;
⎭
⎬
⎫
⎩
⎨
⎧
>
≤
=
0
,
1
0
,
0
)
(
x
x
x
Q
− функция скалярной переменной.
Множество возможных решений рассматриваемой задачи
составляют всевозможные перестановки
π
из элементов множества
N
I
. Обозначим это множество перестановок
N
Π
. На множестве
N
Π
ищется наилучшее в некотором смысле, т.е. оптимальное,
решение. Формализация понятия оптимальности осуществляется в
задачах математического программирования заданием на множестве
возможных решений так называемой целевой функции. Для любой
43
пары возможных решений лучшим считается то, для которого зна-
чение целевой функции «лучше». Если смысл выбранного критерия
таков, что «лучше» означает больше (или меньше), то задача сво-
дится к отысканию среди возможных решений такого, на котором
целевая функция принимает наибольшее (наименьшее) значение.
В нашей задаче цель – возможно меньшее (с учетом штрафов)
отклонение от директивных сроков. Поэтому целевой функцией
может быть функция
:
)
(
1
π
F
∑
∑
=
∈
−
=
j
K
j
k
I
j
T
Q
j
a
F
N
1
1
)].
(
)
(
[
)
(
)
(
π
τ
π
π
π
(1)
Для каждой очередности
π
функция (1) определяет величину
суммарного штрафа за нарушение директивных сроков.
Таким образом, задача сводится к нахождению минимума функции
)
(
1
π
F
на множестве
N
Π
. Рассмотрим конкретный вариант решения
данной задачи. Пусть
N
I
j
j
a
∈
= ,
1
)
(
. В этом случае функция
)
(
1
π
F
определяет количество невыполненных к сроку заданий для данной оче-
редности
π
. Исходные данные к задаче приведены в табл. 3.1.
Таблица 3.1 – К решению задачи о заданиях
j
1 2 3 4 5 6 7 8
)
( j
τ
10 6 3 1 4 8 7 6
)
( j
Τ
35 20 11 8 6 25 28 9
Пусть
π
′
=(1,2,3,4,5,6,7,8),
π
′′
=(5,4,3,2,7,1,8,6).
Соответствующие
значения
целевой
функции:
6
)
(
1
=
′
π
F
,
2
)
(
1
=
′′
π
F
, т.е. значения
1
F
существенно зависят
от выбранной очередности
π
. Общее же число возможных реше-
ний равно 8! = 40320.
3.1.2
Задачи
определения
порядка
обработки
деталей
Проблема. При заданных временах и последовательностях об-
44
работки деталей найти такой порядок их запуска, при котором сум-
марное время обработки минимально.
Пусть
N
I
– множество номеров деталей, подлежащих обработке
π
– перестановка из элементов множества
N
I
, задающая по-
рядок запуска деталей в производство;
}
,...,
2
,
1
{
M
I
M
=
– множество номеров станков.
Сделаем следующие, естественные во многих случаях предпо-
ложения:
1)
каждая из деталей должна быть обработана на каждом из М
станков;
2)
начавшись, обработка любой детали идет без перерывов;
3)
последовательность прохождения деталей по станкам
должна быть одинакова для всех деталей (для определенности при-
мем, что нумерация станков соответствует последовательности об-
работки деталей;
4)
заданы времена
)
,
( j
i
τ
обработки
j
-й детали на
i
-м
станке
).
,
(
N
M
I
j
I
i
∈
∈
Определим время
)
,
(
π
π
j
k
T
завершения обработки детали
на первых
k
станках (для данной перестановки
π
):
∑
=
=
j
i
i
j
T
1
1
),
,
1
(
)
,
(
π
π
π
τ
(2)
∑
=
=
k
i
k
i
T
1
1
1
)
,
(
)
,
(
π
π
π
τ
(3)
Время
)
,
(
π
π
j
k
T
получим, воспользовавшись следующими
соображениями. Обработка детали
j
π
на
k
-м станке может на-
чаться только после окончания ее обработки на
)
1
(
−
k
-м станке и
по окончании обработки на
k
-м станке детали
1
−
j
π
. Тогда для оп-
ределения
)
,
(
π
π
j
k
T
имеем рекуррентное соотношение
)}.
,
(
),
,
(
max{
)
,
(
)
,
(
1
1
π
π
π
π
π
π
π
τ
−
−
+
=
j
k
j
k
j
j
k
T
T
k
T
(4)
45
Критерий оптимальности в задачах такого типа – время обра-
ботки всех деталей на всех станках, которое стремятся уменьшить.
Поэтому в качестве целевой функции
)
(
2
π
F
можно выбрать время
окончания обработки детали
N
π
на станке
:
M
).
,
(
)
(
2
π
π
π
N
M
T
F
=
(5)
Множеством возможных решений является множество
N
Π
,
на котором с помощью соотношений (2) – (5) определена целевая
функция
)
(
2
π
F
.
Формальная постановка задачи.
На множестве
N
π
найти перестановку, минимизирующую
функцию
)
(
2
π
F
.
Проиллюстрируем постановку на конкретном примере. Пусть
5
=
N
,
2
=
M
. Значения
)
,
(
j
i
τ
приведены в табл. 3.2.
Таблица 3.2 – К задаче о деталях
i
j
1 2 3 4 5
1
4 3 1 5 2
2
1 2 5 2 4
Рассмотрим
очередности
)
5
,
4
,
3
,
2
,
1
(
=
′
π
и
).
1
,
2
,
4
,
5
,
3
(
=
′′
π
Соответствующие значения целевой функции
20
)
(
2
=
′
π
F
,
16
)
(
2
=
′′
π
F
можно получить из соотношений
(6.2 – 6.5) или построив диаграмму обработки деталей для данных
перестановок.
3.1.3
Задачи
распределения
заданий
Проблема. Для заданного множества заданий и заданного
множества исполнителей распределить задания наиболее рацио-
нально (с точки зрения затрат ресурсов или времени на их выполне-