Некоторые проблемы решения оптимизационных задач на ЭВМ

Как это получается, можно увидеть на следующем примере. Предположим, надо вычислить выражение [(1/3+2/9)-9]2. Допус­тим, вычисления производятся с точностью до второго знака, т.е. числа округляются до второго знака после запятой. Тогда полу­чится: 1/3=0,33; 2/9=0,22; 1/3+2/9=0,55; 0,55-9=4,95, 4,952=24,50, в то время, как точное значение равно 25. Ошибка произошла на пол-единицы, т.е. на 2%.

Разумеется, ЭВМ вычисляет значения с гораздо большей точ­ностью — например, до 16-го знака. И все же результирующая ошибка при большом числе операций, выполняемых современ­ными компьютерами (иногда миллиарды операций в секунду), может сказаться не только на точных значениях оптимального решения, но и на качественном результате!

Рис. 13.2 иллюстрирует, как при совсем незначительных изме­нениях чисел, входящих в условие задачи, может качественно измениться результат.

На рис. 13.2 область допустимых решений системы ограниче­ний конечна и имеет конечный оптимум. Но при незначительном изменении параметров (на тысячные доли) область становится неограниченной, и целевая функция может неограниченно воз­растать (рис. 13.3).

Аналогичные (и более разнообразные) ситуации возникают при рассмотрении нелинейных задач. Таким образом, при раз­работке алгоритма решения задач математического программи­рования требуется оценить ошибку округления и в случае необ­ходимости модифицировать алгоритм так, чтобы уменьшить ее. С этой целью создан, например, модифицированный симплексный метод (МСМ). Основное внимание в вычислительных процеду­рах МСМ сосредоточено именно на минимизации ошибок ок­ругления.

Другие проблемы связаны с большой размерностью задач. На­пример, если задача линейного программирования содержит до 1500 строк в матрице системы ограничений, то современный компьютер позволяет реализовать симплексный метой. Однако порой встречаются задачи от 8000 до 16000 строк. В этом случае требуются модификации известных алгоритмов. Такие модифика­ции рассматриваются, например в [9].

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

13.1.