Автор admin | Рубрика Современные оконные системы | Posted 21-07-2009
Tags: задачи, метод
Все методы линейного программирования делятся на две группы: конечные и итеративные. Методы первой группы обеспечивают решение задачи за конечное число шагов, методы второй связаны с бесконечным числом итераций и позволяют получить лишь приближенное решение. В настоящем учебном пособии рассматриваются только конечные методы линейного программирования.В зависимости от идеи, которая положена в основу того или иного конечного метода, он может быть отнесен к одному из следующих трех направлений линейного программирования: 1) последовательного улучшения плана; 2) последовательного уточнения оценок; 3) последовательного сокращения невязок (рис. 23).
Рассмотрим принципы, положенные в основу каждого направления, состав шагов и порядок перехода от одного шага к другому.
При решении задач конечными методами линейного программирования отправные планы задачи могут быть составлены с использованием: а) планов прямой задачи, б) планов сопряженной (двойственной) задачи; в) совместным использованием прямой и двойственной задач.Метод последовательного улучшения плана следует отнести к методам первой группы, в которых оптимальный план достигается при движении по опорным планам, составленным для прямой задачи.
В тех случаях, когда при решении задач начальный план составляют с учетом ограничений, обусловленных в задаче, а затем путем последовательных улучшений исходного плана приходят к удовлетворению условий целевой функции, мы имеем дело с методами последовательного улучшения плана.
Метод последовательного улучшения плана складывается из следующих этапов, необходимых для решения задач: способа вычислений опорного плана; установления критерия, позволяющего проверить оптимальность плана на каждом шаге; способа, позволяющего получить план, более близкий к оптимальному.