20. Целочисленные модели исследования операций

Для изучения данного раздела дисциплины необходимо умение решать задачи графическим и симплекс-методом.

Изучив данную тему, студент должен:

– знать методы решения ЗЦЛП;

- уметь решать ЗЦЛП методом ветвей и границ;

- уметь решать задачу коммивояжера

Цель изучения – получить представление о специальных задачах линейного программирования, об особенностях решения ЗЦЛП.

Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения.

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

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

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

Методы решения задач целочисленного линейного (ЗЦЛП) программирования можно классифицировать как (1) методы отсечений и (2) комбинаторные методы.

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

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

< Предыдущая		Следующая >