|
Задача заключается в минимизации (3.4) при ограничениях (3.5). М ы б удем рассматривать вспомогательную задачу следую щ его вида: З а д а ч а 2. Ф иксируем допустим ы й вес каж дой гр у п п ы Т и сформулируем следую щ ую задачу: максимизировать сум м у весов размещ енных в ящ ики вместимостью Т камней: Ф = Е а , х , ^ > т а х . (3.6) при ограничениях (3.5) и (3.6): X a .x.j < Т , j = l,m . (3.7) I Связь между задачами (3.4)-(3.5) и (3.5)-(3.7) очевидна. М иним альное Т, при котором в оптимальном реш ении задачи 2 размещены все кам ни, определяет оптимальное решение задачи 1. Сначала получим сетевое представление задачи 2. О но представлено на рис. 3.1 для случая п = 3, m = 2. 125 П оскольку структура сетевого представления имеет вид сети, а не дерева, то для построения оценочной задачи разделяем ка ж д ую верш ину, ниж него уровня на две верш ины. Преобразованная структура приведена на рис. 3.2. |
Рассмотрим постановку «задачи о камнях». Имеется и «камней» разного веса. Требуется разбить их на m групп (куч) так, чтобы максимальный вес камней в группе был минимален. Задача о камнях имеет многочисленные варианты применения (равномерное распределение работ между исполнителями, функций по подразделениям организационной структуры и т.д.). Дадим формальную постановку задачи. Задача I.Обозначим через а г вес 1-го камня, Хц =1если камень i попал в j -ю кучку, Ху = О в противном случае. Суммарный вес камней в j -й группе равен т, = Е = ,*,(3-3.3) I Максимальный вес группы Т = т а х ^ а ,Х у -> m in. (3.3.4) 1 I Поскольку каждый камень должен быть помещен только в одну группу, имеем ограничения: 90 2 х ц = 1 , i = l,n . (3.3.5) J Задача заключается в минимизации (3.3.4) при ограничениях (3.3.5). Мы будем рассматривать вспомогательную задачу следующего вида: Задача 2. Фиксируем допустимый вес каждой группы Т и сформулируем следующую задачу: максимизировать сумму весов размещенных в ящики вместимостью Т камней: Ф=2®Хц -> т а х . (3.3.6) I.J при ограничениях (6.5) и (6.6): 2а,Х у<Т, (3.3.7) i Связь между задачами (3.3.4)-(3.3.5) и (3.3.5)-(3.3.7) очевидна. Минимальное Т, при котором в оптимальном решении задачи 2 размещены все камни, определяет оптимальное решение задачи 1. Сначала получим сетевое представление задачи 2 [23]. Оно представлено на рис. 3.3.1 для случая п = 3, m = 2. 91 Поскольку структура сетевого представления имеет вид сети, а не дерева, то для построения оценочной задачи разделяем каждую вершину, нижнего уровня на две вершины. Преобразованная структура приведена на рис. 3.3.2. Все также делим на 2 части и v,, для каждой вершины нижнего уровня так, что и„+ Уц=а,, для всех i,j. Рассмотрим следующие две задачи. Первая задача. Определить Хц так, чтобы максимизировать (3.3.8) (3.3.9) при ограничениях (3.3.5), Вторая задача. Максимизировать I.J (3.3.10) при ограничениях (3.3.7). |