Демонстрационный пример решения задачи о ранце
Для задачи о ранце определим, что ранец имеет грузоподъёмность W = 12. Количество грузов n = 5. Значения весов грузов W зададим в виде таблицы 3.
Таблица 3. Определение весов грузов
Для данного множества грузов максимальная мощность подмножеств грузов М = 3.
Согласно моего метода, для получения оптимального решения задачи о ранце, необходимо чтобы:
m = (М+1) /2 для M для нечётных;
m = M/2+1 для M для чётных.
Для данного примера задачи о ранце: М = 3, m = 2.
Значения цены грузов P зададим в виде таблицы 4.
Таблица 4. Определение цены грузов
С помощью метода неявного перебора был получен оптимальный результат для данного примера задачи о ранце:
W = W2 + W4 = 4 + 8 = 12
P = P2 + P4 = 6 + 7 = 13
Занесём определённый упорядоченный вектор грузов относительно значений весов грузов и их цены в таблицу 5.
Произведём объединение грузов из множества грузов в подмножества грузов по два и по три.
Полученные упорядоченные вектора подмножества грузов по два и по три и их значений суммарных весов грузов и цен занесём в таблицу 5.
Таблица 5. Определённый и полученные упорядоченные вектора грузов
Из таблицы 5 видно, что для определения глобального оптимального результата в данном примере задачи о ранце: для данного метода достаточно чтобы Nуг = 3. Искомый результат:
W = W1 + W2 + W3 = 3 + 4 + 5 = 12
P = P1 + P2 + P3 = 1 + 6 + 4 = 11
Таким образом, без перебора вариантов решения задачи о ранце, находим данным методом глобальный оптимальный результат данного примера задачи о ранце.
Основываясь на данных из таблицы, определим зависимость числа подмножеств по три (Kw3) с суммарным весом грузов больше или равно W = 12, от числа угадывания (N) на шкале угадывания (Nm) для данного метода.
Рис. 4.13. Выявленная зависимость между Кw3 и Nm.
Где Кw3 – количество подмножеств грузов по три, с суммарным весом грузов больше или равно W.
Nm – шкала угадывания количества подмножеств грузов.
Nуг – количество угаданных подмножеств грузов.
Согласно данного метода определим локальное оптимальное решения задачи о ранце для значений:
М = 2 и Nуг = 4.
Рассмотрим таблицу 6 для значений М = 2 и Nуг = 4.
Таблица 6. Определённый и полученный упорядоченный вектор грузов для М = 2 и Nуг = 4.
Из таблицы 6 определим локальное оптимальное решения задачи о ранце:
W = W2 + W4 = 4 + 8 = 12
P = P2 + P4 = 6 + 7 = 13
Согласно метода, определим локальное оптимальное решения задачи о ранце для значений М = 1 и Nуг = 5 согласно таблицы 7.
Таблица 7. Определённый вектор грузов для
М = 1 и Nуг = 5
Из таблицы 7 определим локальное оптимальное решения задачи о ранце для М = 1 и Nуг = 5 :
W = W4 = 8
P = P4 = 7
Исходя из вышеизложенного выбираем локальный оптимальный результат данного примера задачи о ранце:
W = W2 + W4 = 4 +8 = 12
P = P2 + P4 = 6 + 7 = 13.
Таким образом, без перебора вариантов решения задачи о ранце, находим данным методом локальный оптимальный результат и глобальный оптимального результат для данного примера задачи о ранце с помощью моего метода. Определение лучшего результата требует выполнение дополнительных условий. Необходимо определить, что для нас является более важным, число грузов или их ценность.
Что и требовалось доказать.
Задача о назначениях
Введение
Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой одной работы, но с неодинаковыми затратами. Нужно распределить работы так чтобы выполнить работы с минимальными затратами.
В настоящее время неизвестен эффективный точный метод решения задачи о назначениях.
Постановка задачи
Для задачи о назначениях даны два множества А и Т одного размера и задана функция стоимости
С: А × Т → R
Необходимо найти биекцию ƒ: А → Т такую, что целевая функция
Метод решения задачи о назначениях
Определяется в качестве числа угадывания (Nуг) определённое числа исполнителей и подмножеств исполнителей различной мощностью.
Первоначально осуществляется объединение исполнителей по два и упорядочение по затратам подмножеств исполнителей. В дальнейшем проводиться поэтапное объединение исполнителей в конечные подмножества исполнителей, с увеличением мощности подмножества с упорядочением этих подмножеств по возрастанию затрат, до получения подмножества исполнителей мощностью m, где
m = (М+1)/2 для нечётной мощности множества исполнителей (M) и
m = M/2+1 для M чётных.
Осуществляется итерационное угадывание количества этих подмножеств с различной мощностью.
В результате поиска, согласно данного метода путём увеличения значения Nуг, после получении первого подмножества с мощностью М процесс поиска заканчивается.
Индикатором нахождения оптимального решения является само появление первого подмножества исполнителей мощностью М.
Для данного метода существует зависимость, согласно закономерности, присущей задачам комбинаторной оптимизации, которая является объективной.
В общем виде её можно представить в виде положительного градиента со сдвигом относительно начала координат.
Рис. 4.15. Выявленная зависимость между Ки и Nm.
Где Ки – количество подмножеств исполнителей для всех работ, Nm – количество подмножеств исполнителей а Nуг – количество угаданных подмножеств исполнителей.
Алгоритм решения задачи о назначениях
Шаг 1) Определяем в качестве числа угадывания (Nуг) определённое числа исполнителей и подмножеств исполнителей различной мощностью.
Шаг 2) Производится сортировка и запоминание исполнителей в соответствии с их затратами.
Шаг 3) Выбирается значение Nуг, и запоминается…
Шаг 4) Выбирается множество исполнителей с мощностью согласно Nуг с соответствующими им наилучшими затратами.
Шаг 5) Производится объединения исполнителей в подмножества исполнителей по два и запоминание этих подмножеств исполнителей, с учётом их затрат.
Шаг 6) Осуществляется сортировка и запоминание подмножеств исполнителей по два с соответствующими им наименьшими затратами.
Шаг 7) Выбирается множество подмножеств исполнителей по два с мощностью согласно Nуг с соответствующими им наименьшими затратами
Шаг 8) Производится объединения исполнителей по два в подмножества исполнителей по три и запоминание этих подмножеств с их наименьшими затратами.
Рис.4.16. Объединение исполнителей по 3.
Данная процедура объединения подмножеств исполнителей меньшей мощности в подмножества исполнителей большей мощности, по различным правилам, должна повторятся до получения подмножеств исполнителей с числом исполнителей m = (М+1) /2 для М нечётных и с числом исполнителей m = M/2+1 для M чётных (пример объединения исполнителей в подмножество показан на рис.4.17.), где М является мощностью множества исполнителей.
Рис. 4.17. Пример объединения исполнителей в подмножество.
После каждого объединения, производится сортировка подмножеств исполнителей большей мощности в соответствии с их наименьшими затратами и запоминание этих подмножеств исполнителей большей мощности с их затратами, а затем выбор подмножеств исполнителей большей мощности с их наименьшими затратами согласно Nуг. Если множество подмножеств исполнителей большей мощности в результате объединения на каком-то этапе данного объединения будет пусто то увеличиваем Nуг
Конец ознакомительного фрагмента.
О проекте
О подписке