l1 (1123685), страница 2

Файл №1123685 l1 (Методичка и она же лекции) 2 страницаl1 (1123685) страница 22019-05-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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. ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ИЛИ ПЕРЕХОД К НОВОМУ ЦИКЛУ.

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

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

Тип файла
Документ
Размер
309,5 Kb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6489
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее