Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Р
ассмотренная задача целераспределения может быть сведена к задаче линейного программирования. Вводится параметр управления:

Тогда вероятность прорыва к объекту j-й цели через зону действия i-го средства можно представить в виде

П
ри прорыве j-я цель наносит объекту ущерб

Математическое ожидание ущерба, наносимого объекту всеми целями равно сумме ущербов от каждой цели:

Минимизация функции W равносильна максимизации функции:

Функция характеризует предотвращенный ущерб объекту
за счет боевого воздействия по целям средств ПВО. Максими­зация функции носит название критерия максимума пре­дотвращенного ущерба. 0кончательно задача целераспределения может быть сформулирована следующим образом.

Найти числа:

которые максимизируют функцию

при условии

Сформулированная задача явля­ется задачей линейного програм­мирования и известна в литературе, как "задача о назначе­нии".

П
усть в рассмотренной постановке задачи целерас­пределения вводится допущение о том, что зоны действия средств совпадают, при этом (такая ситуация харак­терна для группировки истребительной авиации). В этом слу­чае, при прорыве через зону действия группировки, j-я цель наносит объекту ущерб:

Математическое ожидание ущерба, наносимого объекту всеми целями определяется

О
кончательно задача целераспределения, в этом случае, может быть сформулирована следующим образом: Найти числа

Которые минимизируют функцию

при условии

Сформулированная задача не явля­ется, в общем виде, задачей линейного програм­мирования, однако ее можно свести к "задаче о назна­­чении", используя следующую теорему (для простоты полагается m=n).

Теорема:

при

Доказательство:

Пусть - множество матриц порядка , а

Q - допустимое множество матриц, т.е.

Если , то для любого j найдется единственный индекс i(j), зависящий от X, такой что при . Тогда для каждого , при любом j справедливы равенства:

Следовательно, на множестве Q имеет место равенство

При оптимизации критериев эффективности целераспределения, в по­ставленных задачах используются методы линейного программирова­ния. Набор параметров управления , максимизирующей (минимизи­рующей) значения функции M, находится путем преобразования мат­рицы боевой эффективности элементами которой, являются "веса" целей.

Для решения "задачи о назначении" обычно используется широко распространенный в литературе, т.н. венгерский метод. Метод обес­печивает сходимость процесса, но труден для программирования и требует большого машинного времени.

Ниже рассматриваются без обоснования алгоритмы двух методов, применяемых для максимизации (минимизации) матриц порядка .

Учебный вопрос № 4

МЕТОДЫ ОПТИМИЗАЦИИ МАТРИЦ БОЕВОЙ ЭФФЕКТИВНОСТИ

а) Приближенные методы оптимизации.

На эффективность оптимизации большой значение оказывает точ­ность определения элементов матрицы связей "цель средство". Иног­да на практике нет возможности определить эти элементы с доста­точной точностью. Например, при решении задачи ЦР в связь "цель средство" входит вероятность маневра цели, которой придается значение равное 0,5. Очевидно, что если элементы матрицы определяют­ся достаточно грубо, то не следует применять точные методы оптимизации, которые требуют выполнения большого объема работы, а результат полученный при этом, довольно приближенный. В подобных случаях применяют приближенные методы оптимизации.

Метод максимума по строке

Находят элемент первой строки, для которой (если та­ких элементов несколько, то выбирается элемент с наименьшим ин­дексом) . Затем вычеркиваем первую строку и столбец, который со­держит максимальный элемент. Далее рассматриваем вторую строку и т. д. до просмотра всех строк.

Метод максимума по столбцу

Процедура заполнения матрицы назначений такая же, как и по ме­тоду максимума по строке с той лишь разницей, что строки матрицы заменяются столбцами.

Метод максимального элемента матрицы

Правило заполнения матрицы сводится к выбору максимального элемента и вычеркиванием той строки и столбца, на пересечении ко­торых лежит максимальный элемент. Далее из оставшихся элементов снова выбирается максимальный элемент и так до просмотра всей матрицы.

О

писанные приближенные методы оптимизации могут быть использованы для получения начальных опорных планов.

б) Брэдфордский метод.

Значительно проще Венгерского и обеспечивает быструю сходимость процесса.

Алгоритм:

1. В каждой строке матрицы выбирается максимальный элемент, именуемый основой. Столбец, содержащий основу, называется занятым.

2. Если в каждом столбце есть одна основа, то набор оптимален.

3. Отмечается любой столбец занятый более чем одной основой.

4. Все отмеченные столбцы уменьшаются на минимальную величину необходимую, чтобы какая-то из основ отмеченных столбцов стала равной хотя бы одному элементу в данной строке, но не в отмечен­ных столбцах. Такой столбец отмечается, элемент именуется основой, а бывшая основа - обычным элементом.

5. Если последняя сформированная основа находится в занятом столбце, то осуществляется переход к пункту 4, иначе все столбцы считаются не отметенными и осуществляется переход к пункту 2.

Пример: Дана матрица боевой эффективности .

Решение:

Получено решение:

Примечание: при минимизации матрицы необходимо пункты 1 и 4 изменить следующим образом:

1. В каждой строке матрицы выбирается минимальный элемент;

4. Все отмеченные столбцы увеличиваются на минимальную величину

При максимизации матрицы (минимизации) матриц порядка необходимо п.2 изменить следующим образом:

1. Если в n столбцах есть одна основа, то набор оптимален (при n>m производится транспонирование матрицы)

ВЕНГЕРСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЦЕЛЕРАСПРЕДЕЛНИЯ

Для решения задачи целераспределения составляется матрица ущербов

Где: - ущерб наносимый атакующим обороняющемуся при назначении i-го средства

на j-ю цель.

Элементы матрицы представляют собой вероятные ущербы в каждом варианте целераспределения (ЦР). Требуется распределить активные средства по целям так, что бы суммарный ущерб был минимальный. Венгерский метод основан на принципе, согласно которому оптимальность решения (или решений) задачи о ЦР не нарушается при уменьшении (или увеличении ) всех выражающих вероятные ущербы элементов строки таблицы (или ее столбца) на одну и ту же величину. В итоге задача ЦР представляется матрицей, элементами которой являются числа 0 и ли 1, причем в каждой строке (или столбце) имеется лишь одна единица.

Процесс решения задачи разбивается на шесть этапов

1. ПОЛУЧЕНИЕ НУЛЕЙ

Среди элементов каждого столбца таблицы выбирается наименьший. Этот наименьший элемент вычитается из всех элементов этого столбца. Составляется матрица, элементами которой являются разности.

Описанный прием позволяет получить хотя бы один нуль в каждом столбце

1. ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ.

С помощью нулевых значений необходимо произвести поиск решения, для которого суммарный ущерб имел бы нулевое значение. Если это возможно то оптимальное решение найдено. В противном случае следует перейти к пункту 3.

Поиск решения начинается с рассмотрения той строки (или тех строк), которая содержит наименьшее число нулей. Обведем квадратиком один из нулей этой строки, а затем вычеркнем нули, которые находятся в той же строке или в том же столбце, что и обведенный нуль. Затем среди оставшихся строк найдем ту (или те), которая содержит меньше всего нулей, и будем повторять тот же процесс до тех пор пока не сможем больше обводить квадратиками новые нули.

1. ПОИСК МИНИМАЛЬНОГО НАБОРА СТРОК И СТОЛБЦОВ СОДЕРЖАЩИХ ВСЕ НУЛИ.

Действия пункта 3 выполняется в такой последовательности:

1. помечаются крестиком ( ) все те строки, которые не содержат ни одного обведенного квадратиком нуля;

2. отмечается каждый столбец, содержащий перечеркнутый нуль хотя бы в одной из помеченных строк;

3. отмечается каждая строка, имеющая обведенный квадратиком нуль хотя бы в одном из помеченных столбцов;

4. действия 2) и 3) поочередно повторяются до тех пор, пока не останется строк или столбцов которые еще можно пометить;

Этот процесс позволяет получить минимальное число строк и столбцов, содержащих все перечеркнутые или обведенные нули.

1. ЗАВЕРШЕНИЕ ПУНКТА 3.

П

0

рочеркнем каждую непомеченную строку и каждый помеченный столбец, что позволит выделить минимальное число строк и столбцов, содержащих все перечеркнутые 0 или обведенные нули матрицы.

1. ПЕРЕМЕЩЕНИЕ НЕКОТОРЫХ НУЛЕЙ

Рассмотрим часть матрицы, состоящей из непрочеркнутых элементов, и выберем наименьшее число в ней.

- Вычтем это число из элементов непрочеркнутых столбцов и

• Прибавим к элементам ПРОЧЕРКНУТЫХ строк.

6. ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ИЛИ ПЕРЕХОД К НОВОМУ ЦИКЛУ.

АЛГОРИТМ ВЕНГЕРСКОГО МЕТОДА Дана таблица ущербов

Характеристики

Список файлов учебной работы