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

1.2 Модели и методы решения задач дискретного программирования при проектировании систем обработки данных

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

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

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

Как показал анализ проектирования модульных системы обработки данных в подавляющем большинстве задач анализа и синтеза СОД сводится к задачам дискретного программирования.

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

Определим задачу дискретного программирования следующим образом. [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.  Для каждого из подмножеств  вычисляется значения оценок (нижние или верхние границы);

Похожие работы

Информатика и программное обеспечение ПЭВМ

Скачать

448518

14

55

... также невысока и обычно составляет около 100 кбайт/с. НКМЛ могут использовать локальные интерфейсы SCSI. Лекция 3. Программное обеспечение ПЭВМ 3.1 Общая характеристика и состав программного обеспечения 3.1.1 Состав и назначение программного обеспечения Процесс взаимодействия человека с компьютером организуется устройством управления в соответствии с той программой, которую пользователь ...

Предмет и объект прикладной информатики

Скачать

308601

37

3

... производительных сил, тем быстрее повышается Б. населения. В еще большей степени Б. связано с эффективностью социально-экономической политики в данном обществе. Информатика как наука. Предмет и объект прикладной информатики. Системы счисления Инфоpматика — это основанная на использовании компьютерной техники дисциплина, изучающая структуру и общие свойства информации, а также закономерности и ...

Ответы к экзамену по специальности Информатик-технолог

Скачать

113309

0

0

... . Особо стоит отметить наличие в СЗИ защиты загрузки операционной системы с гибких магнитных дисков и CD-ROM, которая обеспечивает защиту самих средств защиты от "взлома" с использованием специальных технологий. В различных СЗИ существуют программные и аппаратно-программные реализации этой защиты, однако практика показывает, что программная реализация не обеспечивает необходимой стойкости. ...

Автоматизация и диспетчеризация систем электроснабжения

Скачать

129027

5

16

... разных этапах производства (потребления) электроэнергии. Основная цель создания таких систем – дальнейшеё повышение эффективности технических и программных средств автоматизации и диспетчеризации СЭС для улучшения технико-экономических показателей и повышения качества и надёжности электроснабжения ПП. Реформирование электроэнергетики России требует создания полномасштабных иерархических систем ...