l1 (1123685), страница 2
Текст из файла (страница 2)
Р
ассмотренная задача целераспределения может быть сведена к задаче линейного программирования. Вводится параметр управления:
Тогда вероятность прорыва к объекту j-й цели через зону действия i-го средства можно представить в виде
П
ри прорыве j-я цель наносит объекту ущерб
Математическое ожидание ущерба, наносимого объекту всеми целями равно сумме ущербов от каждой цели:
Минимизация функции W равносильна максимизации функции:
Функция характеризует предотвращенный ущерб объекту
за счет боевого воздействия по целям средств ПВО. Максимизация функции носит название критерия максимума предотвращенного ущерба. 0кончательно задача целераспределения может быть сформулирована следующим образом.
Найти числа:
которые максимизируют функцию
Сформулированная задача является задачей линейного программирования и известна в литературе, как "задача о назначении".
П
усть в рассмотренной постановке задачи целераспределения вводится допущение о том, что зоны действия средств совпадают, при этом (такая ситуация характерна для группировки истребительной авиации). В этом случае, при прорыве через зону действия группировки, j-я цель наносит объекту ущерб:
Математическое ожидание ущерба, наносимого объекту всеми целями определяется
О
кончательно задача целераспределения, в этом случае, может быть сформулирована следующим образом: Найти числа
Которые минимизируют функцию
при условии
Сформулированная задача не является, в общем виде, задачей линейного программирования, однако ее можно свести к "задаче о назначении", используя следующую теорему (для простоты полагается m=n).
Теорема:
при
Доказательство:
Пусть - множество матриц порядка
, а
Q - допустимое множество матриц, т.е.
Если , то для любого j
найдется единственный индекс i(j), зависящий от X, такой что
при
. Тогда для каждого
, при любом j справедливы равенства:
Следовательно, на множестве Q имеет место равенство
При оптимизации критериев эффективности целераспределения, в поставленных задачах используются методы линейного программирования. Набор параметров управления , максимизирующей (минимизирующей) значения функции M, находится путем преобразования матрицы боевой эффективности элементами которой, являются "веса" целей.
Для решения "задачи о назначении" обычно используется широко распространенный в литературе, т.н. венгерский метод. Метод обеспечивает сходимость процесса, но труден для программирования и требует большого машинного времени.
Ниже рассматриваются без обоснования алгоритмы двух методов, применяемых для максимизации (минимизации) матриц порядка .
Учебный вопрос № 4
МЕТОДЫ ОПТИМИЗАЦИИ МАТРИЦ БОЕВОЙ ЭФФЕКТИВНОСТИ
а) Приближенные методы оптимизации.
На эффективность оптимизации большой значение оказывает точность определения элементов матрицы связей "цель средство". Иногда на практике нет возможности определить эти элементы с достаточной точностью. Например, при решении задачи ЦР в связь "цель средство" входит вероятность маневра цели, которой придается значение равное 0,5. Очевидно, что если элементы матрицы определяются достаточно грубо, то не следует применять точные методы оптимизации, которые требуют выполнения большого объема работы, а результат полученный при этом, довольно приближенный. В подобных случаях применяют приближенные методы оптимизации.
Метод максимума по строке
Находят элемент первой строки, для которой (если таких элементов несколько, то выбирается элемент с наименьшим индексом) . Затем вычеркиваем первую строку и столбец, который содержит максимальный элемент. Далее рассматриваем вторую строку и т. д. до просмотра всех строк.
Метод максимума по столбцу
Процедура заполнения матрицы назначений такая же, как и по методу максимума по строке с той лишь разницей, что строки матрицы заменяются столбцами.
Метод максимального элемента матрицы
Правило заполнения матрицы сводится к выбору максимального элемента и вычеркиванием той строки и столбца, на пересечении которых лежит максимальный элемент. Далее из оставшихся элементов снова выбирается максимальный элемент и так до просмотра всей матрицы.
О
писанные приближенные методы оптимизации могут быть использованы для получения начальных опорных планов.
б) Брэдфордский метод.
Значительно проще Венгерского и обеспечивает быструю сходимость процесса.
Алгоритм:
-
В каждой строке матрицы выбирается максимальный элемент, именуемый основой. Столбец, содержащий основу, называется занятым.
-
Если в каждом столбце есть одна основа, то набор оптимален.
-
Отмечается любой столбец занятый более чем одной основой.
4. Все отмеченные столбцы уменьшаются на минимальную величину необходимую, чтобы какая-то из основ отмеченных столбцов стала равной хотя бы одному элементу в данной строке, но не в отмеченных столбцах. Такой столбец отмечается, элемент именуется основой, а бывшая основа - обычным элементом.
5. Если последняя сформированная основа находится в занятом столбце, то осуществляется переход к пункту 4, иначе все столбцы считаются не отметенными и осуществляется переход к пункту 2.
Пример: Дана матрица боевой эффективности .
Решение:
Получено решение:
Примечание: при минимизации матрицы необходимо пункты 1 и 4 изменить следующим образом:
-
В каждой строке матрицы выбирается минимальный элемент;
4. Все отмеченные столбцы увеличиваются на минимальную величину
При максимизации матрицы (минимизации) матриц порядка необходимо п.2 изменить следующим образом:
-
Если в n столбцах есть одна основа, то набор оптимален (при n>m производится транспонирование матрицы)
ВЕНГЕРСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЦЕЛЕРАСПРЕДЕЛНИЯ
Для решения задачи целераспределения составляется матрица ущербов
Где: - ущерб наносимый атакующим обороняющемуся при назначении i-го средства
на j-ю цель.
Элементы матрицы представляют собой вероятные ущербы в каждом варианте целераспределения (ЦР). Требуется распределить активные средства по целям так, что бы суммарный ущерб был минимальный. Венгерский метод основан на принципе, согласно которому оптимальность решения (или решений) задачи о ЦР не нарушается при уменьшении (или увеличении ) всех выражающих вероятные ущербы элементов строки таблицы (или ее столбца) на одну и ту же величину. В итоге задача ЦР представляется матрицей, элементами которой являются числа 0 и ли 1, причем в каждой строке (или столбце) имеется лишь одна единица.
Процесс решения задачи разбивается на шесть этапов
-
ПОЛУЧЕНИЕ НУЛЕЙ
Среди элементов каждого столбца таблицы выбирается наименьший. Этот наименьший элемент вычитается из всех элементов этого столбца. Составляется матрица, элементами которой являются разности.
Описанный прием позволяет получить хотя бы один нуль в каждом столбце
-
ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ.
С помощью нулевых значений необходимо произвести поиск решения, для которого суммарный ущерб имел бы нулевое значение. Если это возможно то оптимальное решение найдено. В противном случае следует перейти к пункту 3.
Поиск решения начинается с рассмотрения той строки (или тех строк), которая содержит наименьшее число нулей. Обведем квадратиком один из нулей этой строки, а затем вычеркнем нули, которые находятся в той же строке или в том же столбце, что и обведенный нуль. Затем среди оставшихся строк найдем ту (или те), которая содержит меньше всего нулей, и будем повторять тот же процесс до тех пор пока не сможем больше обводить квадратиками новые нули.
-
ПОИСК МИНИМАЛЬНОГО НАБОРА СТРОК И СТОЛБЦОВ СОДЕРЖАЩИХ ВСЕ НУЛИ.
Действия пункта 3 выполняется в такой последовательности:
-
помечаются крестиком (
) все те строки, которые не содержат ни одного обведенного квадратиком нуля;
-
отмечается каждый столбец, содержащий перечеркнутый нуль хотя бы в одной из помеченных строк;
-
отмечается каждая строка, имеющая обведенный квадратиком нуль хотя бы в одном из помеченных столбцов;
-
действия 2) и 3) поочередно повторяются до тех пор, пока не останется строк или столбцов которые еще можно пометить;
Этот процесс позволяет получить минимальное число строк и столбцов, содержащих все перечеркнутые или обведенные нули.
-
ЗАВЕРШЕНИЕ ПУНКТА 3.
П
0
рочеркнем каждую непомеченную строку и каждый помеченный столбец, что позволит выделить минимальное число строк и столбцов, содержащих все перечеркнутые 0 или обведенные нули матрицы.-
ПЕРЕМЕЩЕНИЕ НЕКОТОРЫХ НУЛЕЙ
Рассмотрим часть матрицы, состоящей из непрочеркнутых элементов, и выберем наименьшее число в ней.
- Вычтем это число из элементов непрочеркнутых столбцов и
-
Прибавим к элементам ПРОЧЕРКНУТЫХ строк.
6. ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ИЛИ ПЕРЕХОД К НОВОМУ ЦИКЛУ.
АЛГОРИТМ ВЕНГЕРСКОГО МЕТОДА Дана таблица ущербов