Full Text

Введение Одним из важных классов задач комбинаторной оптимизации является задача о назначении целей. Первоначально задача рассматривалась для военных приложений как задача определения оптимального распределения комплекта различного вооружения (средств поражения) по целям для нанесения максимального ущерба противнику [1-7]. В настоящее время область применения таких задач расширилась за счет моделей распределения ресурсов в экономике [8], системах организационного управления [9, 10], планировании производства продукции [11], банковской сфере [12]. Особое внимание распределению ресурсов уделяется при проектном управлении. В статье [13] для решения данной проблемы используется система рейтингов по рабочим задачам и компетенциям. Во многих задачах о назначении целей имеется требование целочисленности переменных. Например, количество ракет, самолетов-перехватчиков, сотрудников, компьютеров. Требование целочисленности переменных существенно усложняет процесс нахождения оптимального решения [14, 15]. Округление нецелочисленных переменных до целых чисел может привести не только к заметным потерям эффективности целочисленного плана, но и к недопустимому решению. Для решения задачи целочисленного распределения средств применяется метод максимального относительного элемента [14]. Данный метод основан на упорядоченном переборе возможных решений и является численным, приближенным. Проблема при его использовании заключается в том, что точного целочисленного решения задачи может не быть, а на поиск наиболее близкого к нему приближенному решению будут тратиться значительные вычислительные ресурсы. Многие задачи оптимизации распределения нецелочисленных ресурсов для непрерывных функций решаются методом неопределенных множителей Лагранжа [9]. Важным и новым является распространение данного метода на решение задач дискретной оптимизации. Целью данной работы является решение задачи распределения целочисленных ресурсов (задачи дискретной оптимизации) методом неопределенных множителей Лагранжа. 1. Постановка задачи Проблема распределения ресурсов (средств) для решения набора заданных задач заключается в следующем. Имеется n задач и m средств для их решения. Заданы важности и вероятности выполнения j-й задачи каждым средством ( ). Обозначим через - количество средств, назначенных для выполнения j-й задачи. Пусть , где - целая часть числа , - дробная часть. Требуется найти такое распределение ресурсов , при котором вероятность выполнения всех задач будет максимальна. В этом случае максимизируемая целевая функция будет иметь вид (1) Коэффициент - это важность выполнения j-й задачи, - нормировка . Для получения критерия целочисленности решения задачи (1) разложим множитель в ряд, ограничиваясь двумя членами, получим При таком разложении абсолютная погрешность вычисления не превосходит величины В самом деле, абсолютная погрешность не превосходит первого отброшенного члена, т.е. члена При максимальном значении вероятности p = 1 покажем, что Имеем т.е. - это верно. Относительная погрешность не превосходит величины т.е. 4,2 %, что близко к повышенной точности. Погрешность в вычислении функции составляет т.е. Система ограничений задачи распределения ресурсов имеет вид (2) 2. Метод решения Для нахождения экстремума функции (1) при ограничениях (2) запишем функцию Лагранжа: (3) Последние два ограничения системы (2) здесь использовать не будем. Они будут учтены в дальнейшем. Найдем частные производные по , , и приравняем их к нулю. Имеем (4) (5) (6) Из формулы (4) для получаем (7) Из формулы (5) при находим Отсюда (8) Из формулы (7) имеем Отсюда с учетом формулы (8) получаем и Следовательно, (9) Допустим, что . Предположим, что В этом случае тогда и только тогда, когда (10) Отсюда следует, что уравнение (10) выполняется тогда и только тогда, когда все равны. Это означает однородность средств. Тогда из формулы (9) следует, что Определим условие выполнения равенства Подставим из уравнения (8) и из уравнения (9) в первое уравнение системы (2), получим (11) Для краткости введем следующие обозначения: в формуле (11) коэффициент при обозначим через a, второе слагаемое - через b, третье - c. Тогда (12) Из уравнения (12) следует, что тогда и только тогда, когда (13) Таким образом, условие (13) является необходимым условием целочисленности ресурсов. При из уравнения (11) имеем (14) При равенство (14) превращается в равенство (15) При выполнении условия с учетом равенства (15) получаем, что . Для целочисленности необходимо и достаточно, чтобы выражение в скобках в уравнении (15) было кратно n. При выполнении однородности из формулы (8) и (15) для имеем (16) Если - целое положительное число, то для положительной целочисленности необходимо и достаточно, чтобы было целым при Итак, точка , координаты которой вычисляются по формулам (15), (16), при этом в (15) выражение в скобках кратно n и второе слагаемое в формуле (16) является целым числом при , является стационарной точкой с целыми положительными координатами. Достаточное условие экстремума сводится к анализу второго дифференциала функции Лагранжа (3) для найденной точки P при условии, что связаны уравнением Второй дифференциал для функции Лагранжа будет иметь вид (17) при этом Поскольку в точке Р имеется максимум. Таким образом, имеем следующее утверждение. Теорема. Для того чтобы задача целераспределения, сводящаяся к максимизации целевой функции (1) при ограничениях (2), имела положительное целочисленное решение, необходимо и достаточно, чтобы выполнялись следующие условия: 1) однородность средств, т.е. все вероятности должны быть равны; 2) если , то и , вычисленное по формуле (15), должно быть целым положительным; 3) выражение ( ) должно быть целым. В самом деле, пусть выполнены условия 1-3. Тогда из условия 1 следует, что все равны, т.е. выполняется равенство (12) и при выполнении условия 3 из с учетом уравнения (12) следует, что . Тогда отсюда вытекает равенство (15), и с учетом выполнения условия 2 получаем, что - целое положительное число, откуда с учетом выполнения условия 3 имеем - целое положительное число. Из равенства (17) следует, что данное решение максимизирует функцию (1) при ограничениях (2). Докажем теорему в обратную сторону. Пусть - целое положительное решение, максимизирующее функцию (1) при ограничениях (2). Тогда при представлении в виде , где - целая, - дробная части числа, имеем , но тогда выполняется равенство (12) и все равны . Значит, выполняется условие 1. Пусть . Тогда, очевидно, вычисленное по формуле (15), будет целым положительным, т.е. выполняется условие 2. При этом будет вычисляться по формуле (16), а так как и - целые, то выполняется условие 3. 3. Результаты и их обсуждение Рассмотрим практическую реализацию разработанного метода. Приведем алгоритм поиска целочисленного решения задачи распределения средств и разберем конкретный пример. Основные этапы алгоритма решения данной задачи заключаются в следующем. 1. Все вероятности должны быть одинаковы. Если это не так, то производится их корректировка. При невозможности такой корректировки положительного целочисленного решения не будет. 2. Ищется . Пусть это будет . 3. Для должно быть известно, что это целое положительное число, т.е. и - целое положительное число. 4. Значение вычисляется по формуле (15). 5. По формуле (16) находятся значения , которые будут целыми положительными. Рассмотрим следующий пример на выполнение вычислений по разработанному алгоритму. Пусть n = 3; m = 11; p = 0,2; По формулам (15) и (16) находим положительное целочисленное решение: , максимизирующее соответствующую целевую функцию (1), которая при данных значениях: Таким образом, алгоритм позволяет аналитически найти решение задачи распределения ресурсов. Заключение В статье разработан новый метод решения оптимизационной задачи распределения целочисленного ресурса. Доказана теорема (критерий существования целочисленного решения), определяющая необходимые и достаточные условия, при выполнении которых решение задачи существует и находится по разработанному в статье алгоритму. К таким условиям относится однородность ресурсов (средств), а также дополнительные условия (ограничения на целочисленность и положительность дополнительных условий задачи). Разработан алгоритм поиска целочисленного решения задачи распределения ресурсов методом неопределенных множителей Лагранжа и разобран конкретный пример.

About the authors

A. V Ganicheva

Tver State Agricultural Academy

A. V Ganichev

Tver State Technical University

References

Statistics

Views

Abstract - 53

PDF (Russian) - 32

Refbacks

• There are currently no refbacks.