Исследование операций. Линейное, динамическое программирование


Исследование операций - часть 19


Эта задача принадлежит к классу так называемых «вариационных задач», хорошо разработанных в математике. Самые простые из таких задач («задачи на максимум и минимум») знакомы каждому инженеру. Чтобы найти максимум или минимум (короче, «экстремум») функции многих аргументов, надо продифференцировать ее по всем аргументам (в данном случае — элементам решения), приравнять производные нулю и решить полученную систему уравнений. Казалось бы, чего проще? А вот этот классический метод как раз в исследовании операций имеет весьма ограниченное применение. Во-первых, когда аргументов много, задача решения системы уравнений зачастую оказывается не проще, а сложнее, чем непосредственный поиск экстремума. Во-вторых, когда на элементы решения наложены ограничения, экстремум часто достигается не в точке, где производные равны нулю (такой точки может вообще не быть), а где-то на границе области X. Возникают все специфические трудности так называемой «многомерной вариационной задачи при ограничениях», иной раз непосильной по своей сложности даже для современных ЭВМ. Кроме того, в некоторых задачах функция W вообще не имеет производных (например, задана только для целочисленных значений аргументов). Все это делает задачу поиска экстремума далеко не такой простои, как она кажется с первого взгляда.

Метод поиска экстремума и связанного с ним оптимального решения х* должен всегда выбираться исходя из особенностей функции W и вида ограничений, накладываемых на решение. Например, если функция W линейно зависит от элементов решения x1, x2, ..., а ограничения, налагаемые на x1, x2, ..., имеют вид линейных равенств или неравенств, возникает ставшая классической задача линейного программирования, которая решается сравнительно простыми, а главное, стандартными методами (см. главу 3). Если функция W выпукла, применяются специальные методы выпуклого программирования с их разновидностью:

«квадратичным программированием» (см. [8]). Для оптимизации управления многоэтапными операциями применяется метод динамического программирования (см.


Начало  Назад  Вперед



Книжный магазин