49743 (588672), страница 7

Файл №588672 49743 (Блочно-симметричные модели и методы проектирования систем обработки данных) 7 страница49743 (588672) страница 72016-07-29СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

, ;

, ; ; . (1.2.2)

При - задача частично дискретного программирования.

Если - множество всех целочисленных векторов, то при - имеем задачу целочисленного программирования (ЦП). А при - задачу частичного целочисленного программирования (ЧЦП).

В наибольшей степени изучены методы решения задач целочисленного линейного программирования (ЦЛП):

;(1.2.3)

Здесь - множество всех неотрицательных целых чисел, частный случай задач ЦЛП задачи с булевыми переменными, где в (1.2.3):

, ;

В ряде задач ЦП требование целочисленности накладывается и на целевую функцию.

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

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

Обычно эффективное решение задачи тесно связанно с математической моделью задачи, со структурой модели и ее особенностями.

Рассмотрим некоторые математические модели дискретного программирования и методы их решения.

Модели задач ДП. Классическим примером моделей этого класса являются модели целочисленного линейного программирования, в которых переменными являются неделимые величины. Модели этого класса в свою очередь генерировали различные варианты постановки прикладных задач и определены как модели с неделимостями.

В процессе развития теории дискретного программирования выделился класс комбинаторных моделей. [83]

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

Одним из типичных примеров комбинаторной модели является задача о коммивояжере. [84]

В данной задаче имеется кратчайший замкнутый путь, проходящий по одному разу через все города, при условии, что имеется n городов и задана матрица расстояний между ними.

В комбинаторной постановке необходимо определить такую перестановку, которая минимизирует величину целевой функции.

Постановка различных комбинаторных задач может часто формулироваться в виде модели с булевыми переменными, которые принимают только два значения 0 или 1.

К булевым моделям сводятся большое число прикладных задач, что свидетельствует о перспективности моделей этого класса. [85]

В постановках ряда прикладных задач имеются некоторые особенности, касающихся целевой функции либо области ограничений. К примеру, необходимо определить, экстремум неординарной разрывной функции на выпуклом многограннике вида

где

Эти модели образуют класс моделей с неоднородной разрывной целевой функцией.

Модели нахождения экстремума на области, задаваемой не только линейными неравенствам (ограничениями) но и логическими условиями. Такие области оказываются невыпуклыми либо несвязными. Эти задачи образуют модели на не классических областях. [84]

Особый интерес исследователей вызывают многоэкстремальные модели, в которых необходимо определить оптимальные значения более одной целевой функции при наличии (либо отсутствии) систем ограничений. Как правило, модели этого класса сложны в вычислительном отношении. Вместе с тем, постановки целого ряда прикладных задач сводятся к моделям данного класса. Решение указанных задач является актуальным. [103, 105, 107]

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

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

Методы решения задач дискретного программирования (ДП). В задачах ДП методы их решения зачастую связаны с их математической постановкой и особенностями. Имеется большое число методов для решения этих задач. В этой связи целесообразно выделить следующие методы решения задач ДП: точные и приближенные. Среди точных методов наиболее распространены комбинаторные методы и методы отсечения.

Типичным примером комбинаторных методов является метод ветвей и границ [115]. Суть данного метода заключается в направленном переборе допустимых решений на основе вычисления оценок. Основное этапы подхода заключается в следующем:

  1. Исходное множество решений разбиваются не подмножества (процесс ветвления);

  2. Для каждого из подмножеств вычисляется значения оценок (нижние или верхние границы);

  3. На основе выбранного значения оценок вычисляются допустимые решения;

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

Идея метода отсечений заключается в следующем. Решается исходная задача. Если полученное решение удовлетворяет условию целочисленности, то задача решена. В противном случае к ограничениям исходной задачи добавляется новое линейное ограничение. Далее решается задача с дополнительно введенным ограничением. Итеративный процесс повторяется, до тех пор, пока не будет получено целочисленное решение.

Примерами успешной реализации методов отсечения являются алгоритмы Гомори [83] .

Вместе с тем, следует отметить ограниченное использование точных методов для решения прикладных задач большой размерности. Несмотря на использование мощных вычислительных систем с большой памятью, совершенствование и развитие математического аппарата «проклятье дискретности» остается и на сегодняшний день.

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

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

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

В ряде случаев при проектировании систем обработки данных необходимо учитывать вектор критериев, которые могут противоречить друг другу. Такие постановки задач сводятся к многокритериальным задачам дискретного программирования.

Математическая постановка – критериальной задачи предпологает, что задано множество допустимых решений , на котором определена векторная целевая функция (ВЦФ) [98,99].

,(1.2.4)

Причем критерии ВЦФ считаем минимизируемыми:

Fv(x)→min, v=1,2,…,N.(1.2.5)

Элемент называется Парето-оптимальным, если не существует такого допустимого решения , что выполняются неравенства , v=1, 2,…, N, среди которых хотя бы одно является строгим.

Через обозначаем паретовское множество (ПМ), состоящее из всех Парето-оптимальных элементов рассматриваемой задачи с ВЦФ (1) на множестве . Эта задача называется дискретной, если мощность множества ее допустимых решений конечна.

Первоначальная формулировка проблемы многокритериальной (векторной) оптимизации восходит к [98, 99] и состоит в нахождении одного или всех элементов ПМ . Заметим, что в однокритериальном случае ( ) ПМ представляет собой множество всех оптимумов данной оптимизационной задачи. Для последней, однако, более естественной является проблема нахождения какого-либо («первого попавшегося») оптимума. Как обобщение этой проблемы для многокритериального случая в настоящей работе в качестве основной рассматриваем проблему нахождения полного множества альтернатив (ПМА). Подмножество назовем ПМА, если оно удовлетворяет двум условиям: его мощность минимально и выполняется , где , где

.

Множество и будем называть множествами альтернатив (МА). В литературе наряду с МА изучается и другие подмножество паретовского множества.

В системном моделировании, в частности, в теорий выбора и принятия решений наиболее распространенными способами нахождения МА являются следующие.

  1. Построение (определение) детерминированного формального механизма, позволяющего генерировать альтернативы с помощью параметров алгоритма или с помощью параметров формулы . [100-103]

  2. Представление МА в неявном виде с помощью системы соотношений (ограничений ). [104-105]

  3. Перечисление всех элементов МА, т.е. представление каждого элемента МА в явном виде. [108, 109]

В работе [121], именно в контексте алгоритмической проблемы, относящейся к последнему из указанных выше трех способов, осуществляется обоснование оценок мощности МА для таких многокритериальных дискретных задач, как задачи о совершенных паросочетаниях, о коммивояжере, о цепях между парой вершин и другие при этом нахождение МА понимается как перечисления с предъявлением всех его элементов [110, 100]. При определенных условиях нижние оценки мощности ПМ и ПМА перечисленных задач оказывается экспоненциальным. Последнее означает, что для рассматриваемых задач проблема нахождения МА является труднорешаемой [110,111]. Или (в терминологии [112,113]) она имеет экспоненциальную вычислительную сложность.

Следуя, [112], рассматриваемую - критериальную задачу назовем индивидуальной, если все ее параметры имеют фиксированные значения. Говорим о массовой - критериальной задаче или, коротко, о задаче, если для некоторых параметров заданы не фиксированные значения, а диапазоны их изменения.

Анализируя приложения той или другой задачи, нетрудно убедиться, что состав критериев ВЦФ обычно меняется. Например, в системах автоматизированного проектирования электронной техники [114-118] возникает многокритериальные задачи на графах, в которых остовное дерево (связывающая сеть) может оценивается такими критериями, как вес, «узкое место» (минимаксный критерий), степень, диаметр и т.д. [119,120]. При этом по мере необходимости эти критерии входят в состав ВЦФ в разнообразных комбинациях, порождая различные варианты задач об остовных деревьях. Общим у этих задач является лишь множество допустимых решений , каждый элемент которого является связным остовным подграфом данного графа.

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

Тип файла
Документ
Размер
8,2 Mb
Учебное заведение
Неизвестно

Список файлов ВКР

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