3.5. Другие методы оптимизации

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

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

Основное содержание этих методов составляют динамическое программирование и совокупность способов решения, объединенных общим термином – метод “ветвей и границ”.

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

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

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

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

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

16