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

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

Текст из файла (страница 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)

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

F_v(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]. При этом по мере необходимости эти критерии входят в состав ВЦФ в разнообразных комбинациях, порождая различные варианты задач об остовных деревьях. Общим у этих задач является лишь множество допустимых решений , каждый элемент которого является связным остовным подграфом данного графа.

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

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