Методы последовательного улучшения допустимого решения (МПУ) 26, 196 [c.473]
Применение описанных методов улучшения плана чередуется с проверкой условий оптимальности, т. е., получив новый план, мы прежде всего, определяя оценки, выясняем, не оптимален ли он. Если да, то решение заканчивается. Если же нет, то снова применяется метод последовательного улучшения плана. Доказано, что с помощью этого метода за конечное число улучшений можно прийти от любого допустимого плана [c.21]
Использование теоремы двойственности и связанного с ней признака оптимальности допустимого плана лежит в основе большинства эффективных методов решения задач линейного программирования. В 2 было продемонстрировано решение задачи о раскрое с помощью метода последовательного улучшения плана. Близко к нему примыкает симплекс-метод, разработанный американским математиком. Дж. Данцигом. Здесь мы приведем лишь краткое описание этого метода. [c.31]
Прямой симплекс- метод. Изложение этого алгоритма будет проведено по следующему плану. Сначала качественно разъясняется основная идея метода. Затем эта идея получает четкое математическое оформление. И, наконец, приводятся расчетные формулы. Последний вопрос практически важен, он связан со стремлением свести к минимуму необходимые вычисления. Алгоритм представляет собой процедуру последовательного улучшения так называемых допустимых решений (планов). Допустимым решением называется точка sga, для которой [c.419]
Понятие базисного множества и базисного решения. Допустимые и двойственно допустимые базисы. Общая схема последовательного улучшения, конкретизация для прямой и двойственной задачи в канонической несимметричной форме. Получение начального решения. Связь с симплекс методом. Проблема вырожденности. [c.47]
Здесь нами построена последовательность вершип x(l x(z х(3) таких, что каждые два соседних элемента последовательности являются соседними вершинами множества допустимых решений, причем при движении вдоль последовательности значение критерия возрастает. В последней точке достигается максимум. Подобные методы, основанные на последовательном переходе от одной вершины к другой, соседней с большим (или в крайнем случае не меньшим) значением критерия, получили название методов последовательного улучшения допустимого решения. Их использование определяется следующими преимуществами. Во-первых, переход в соседнюю вершину требует значительно меньшего объема вычислений, чем поиск некоторой [c.52]