Дипломная работа: Блочно-симметричные модели и методы проектирования систем обработки данных
Приведем краткий обзор
моделей и методов задач дискретного программирования (ДП), используемых в
процессе проектирования систем обработки данных.
Определим задачу
дискретного программирования следующим образом. [83]
Задачей дискретного
программирование (ДП) будем называть задачу отыскания экстремума (max, min)
скалярной функции, заданной на дискретном (несвязном) множестве, т.е. такую
задачу математического программирования (МП), у которой на все или на часть
переменных, определяющих область допустимых решений, наложено требование
дискретности. Запишем задачу МП в виде:
, (1.2.1)
где - -мерный вектор; - скалярный функция; -некоторое множество в , .
Если - конечное (или счетное)
множество или декартово произведение конечного (счетного) множества на
множество мощности континиума, то будет иметь место задача ДП. В этом случае
условие принадлежности некоторому
множеству может быть записано в виде:
, ;
, ;
; . (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] .
Вместе с тем, следует
отметить ограниченное использование точных методов для решения прикладных задач
большой размерности. Несмотря на использование мощных вычислительных систем с
большой памятью, совершенствование и развитие математического аппарата
«проклятье дискретности» остается и на сегодняшний день.
Поэтому для эффективного
решения прикладных задач и преодоления вычислительной сложности точных методов
возникла необходимость разработки приближенных и эвристических методов, которые
тесно связаны со структурой и особенностями постановки этих задач.
В отличие от точных
методов, приближенные позволили решать задачи большой размерности и полученные
решения удовлетворяют потребностям практики. При этом в ряде случаев появилась
возможность оценить отклонение от оптимального решения либо определить
ближайшие окрестности от оптимального решения.
Все это позволило
использовать приближенные методы в качестве эффективного инструментария для
решения практических задач.
В ряде случаев при
проектировании систем обработки данных необходимо учитывать вектор критериев,
которые могут противоречить друг другу. Такие постановки задач сводятся к
многокритериальным задачам дискретного программирования.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 |