Двойственный задачи линейного программирования

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

1.1.4. Модели целочисленного линейного программирования.

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

Нелинейные модели.

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

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