Используя двойственный симплекс-метод, находят решение задачи, получающейся в результате присоединения дополнительного ограничения. [c.470]
Двойственный симплекс-метод. Начнем с анализа геометрической картины, связанной с задачей линейного программирования. На рис. 76 изображен (качественно) многогранник Р, причем одна ось — прямая е, в качестве второй оси на рис. 76 принято иг-мерное пространство. Граница Р состоит из т мерных граней (на рис. 76 они изображены отрезками). Каждая грань определяется вектором g, ортогональным данной грани. Мы будем считать этот вектор нормированным условием (g, е) = 1. Такие векторы определяют нижние грани Р, при нормировке (g, e) =—1 получим верхние. Это следует понимать так коль скоро задан вектор g, соответствующая ему грань определяется как совокупность точек х вида [c.426]
Заметим сразу же, что произвольному вектору g обычно соответствует вершина, т. е. нет ни одного индекса га, для которого С ) )—0. Однако при реализации двойственного симплекс-метода [c.427]
ДВОЙСТВЕННЫЙ СИМПЛЕКС- МЕТОД [c.68]
Основные идеи двойственного симплекс-метода. [c.68]
Здесь следует подчеркнуть, что двойственный симплекс-метод непосредственно нацелен на нахождение решения прямой задачи. [c.72]
По аналогии со стандартным симплекс-методом вычислительную процедуру двойственного симплекс-метода удобно оформлять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с формальной стороны их структура остается неизменной. Иногда считается целесообразным добавить к двойственной симплекс-таблице строку, содержащую строку со значениями А,у, [c.74]
Таким образом, при решении задачи вида (1.66)-(1.68) двойственный симплекс-метод имеет несомненные преимущества по сравнению с прямым. [c.76]
Другое важное направление использования двойственного симплекс-метода связано с поиском оптимальных планов в тех задачах, условия которых претерпели некоторые изменения после того, как они уже были решены с помощью стандартной симплекс-процедуры. Типичными примерами таких изменений являются [c.76]
В первом случае, т. е. при изменении вектора 6, достоинства двойственного симплекс-метода очевидны, так как ранее найденный оптимальный базис можно использовать в качестве исходного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотрении методов решения целочисленных задач. [c.76]
Двойственный симплекс-метод — метод последовательного уточнения оценок. [c.79]
Перечислите основные идеи, на которых базируется алгоритм двойственного симплекс-метода. [c.81]
Сформулируйте критерий оптимальности, используемый в алгоритме двойственного симплекс-метода. [c.81]
По каким признакам можно определить, что множество допустимых планов задачи, решаемой двойственным симплекс-методом, пусто [c.81]
В каких ситуациях могут быть реализованы преимущества двойственного симплекс-метода [c.81]
В соответствии с алгоритмом двойственного симплекс-метода переходим к следующему базису Af(p(2 2)) = 0, 2, 3 . [c.149]
Для любой задачи линейного программирования можно сформулировать задачу-двойник, или, иначе, двойственную задачу. Эта задача-двойник является своеобразным "зеркальным отражением" исходной задачи, поскольку ее формулировка использует те же параметры, что и исходная задача, а ее решение может быть получено одновременно с решением исходной задачи. Фактически при решении исходной задачи симплекс-методом одновременно решается и двойственная задача, и наоборот. Следует также заметить, что исходная и двойственная задачи совершенно симметричны. Если двойственную задачу рассматривать как исходную, то исходная будет для нее двойственной. [c.65]
Перейдя к вектору — g, получим вторую точную грань Р, соответствующую данному набору индексов М. В настоящее время разработано большое число алгоритмов точного решения задачи Л. Все они объединяются общим термином симплекс-метод, однако различают прямые и двойственные варианты симплекс-метода. С этими двумя вариантами связаны две основные качественные идеи, в той или иной мере лежащие в основании большинства алгоритмов как точного, так и приближенного решения задачи линейного программирования. [c.419]
Симплекс-метод двойственный 426 [c.486]
Задачи линейного программирования (7.61 — 7.90) решите симплекс-методом и проведите анализ моделей на чувствительность, сформулируйте двойственную задачу к исходной и решите ее. [c.265]
Использование теоремы двойственности и связанного с ней признака оптимальности допустимого плана лежит в основе большинства эффективных методов решения задач линейного программирования. В 2 было продемонстрировано решение задачи о раскрое с помощью метода последовательного улучшения плана. Близко к нему примыкает симплекс-метод, разработанный американским математиком. Дж. Данцигом. Здесь мы приведем лишь краткое описание этого метода. [c.31]
Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (оценок) и по существу близкий к описанному выше методу последовательного улучшения плана. [c.35]
Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как прямой, так и двойственной задачи. [c.63]
В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в [1]. Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод. [c.77]
Понятие базисного множества и базисного решения. Допустимые и двойственно допустимые базисы. Общая схема последовательного улучшения, конкретизация для прямой и двойственной задачи в канонической несимметричной форме. Получение начального решения. Связь с симплекс методом. Проблема вырожденности. [c.47]
Двойственный симплекс-метод основан на том, что, исходя из некоторого вектора g, устраивают последовательные его повороты, причем каждый поворот (переход от g к g ) сопровождается ростом F (g). Этим обеспечивается сходимость g ->g , признаком того, что текущий вектор g уже есть g, служит невозможность его изменения. Однако, после того как встретилась неулучшаемая грань М, следует еще решить систему (т+1) линейных уравнений [c.428]
Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г. [c.68]
В процессе изложения идей, положенных в основу двойственного симплекс-метода, еще раз воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (1.48). На рис. 1.11 изображен конус К положительных линейных комбинаций расширенных векторов условий а1 для случая т = 2, п = 6, а на рис. 1.12 — (для большей наглядности) — поперечное сечение данного конуса некоторой плоскостью L, проходящей параллельно оси аппликат. [c.68]
Описанные выше свойства пары двойственных задач линейного программирования являются идейной основой двойственного симплекс-метода, который представляет собой итеративный процесс целенаправленного перебора сопряженных (двойственно допустимых) базисов и соответствующих псевдопланов. В этом и заключено его принципиальное отличие от обычного симплекс-метода, в котором последовательно рассматриваются допустимые базисные планы прямой задачи1. Нетрудно догадаться, что при определенной структуре задачи путь, предлагаемый двойственным алгоритмом, может оказаться более коротким. [c.71]
Критерий оптимальности псевдоплана х в двойственном симплекс-методе заключается в том, что х одновременно должен являться допустимым планом прямой задачи, т. е. все его компоненты должны быть неотрицательны Ц>0). [c.71]
Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у решаемой КЗЛП является неотрицательность каких-либо r-х компонент во всех столбцах а1, представленных в текущем базисе р (аг/(р)>0, е п),если 6г(р)<0 1. [c.72]
Алгоритм и табличная реализация двойственного симплекс-метода. Обобщая сказанное в предыдущем пункте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП. [c.73]
Особенности применения двойственного симплекс-метода. Алгоритм двойственного симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исходного сопряженного базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей, сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев исходный псевдоплан может быть определен достаточно легко. [c.75]
Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном примере процесс решения КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений 6, в результате которых [c.77]
Поскольку в начальном псевдоплане имеется только одна отрицательная компонента (- 6с, ), то из базиса должен быть выведен соответствующий ей вектор an+l. Далее, следуя рекомендациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то описанные действия итеративно повторяются. [c.147]
Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану. [c.147]
Проведенные преобразования системы ограничений D q позволили явно выделить сопряженный базис, образуемый столбцами с номерами 1,. .., т, п+1, и соответствующий ему псевдоплан (alf. .., dm, 0,. .., О, 4dJ), т. е. для решения задачи (Д(< ),/) может быть применен алгоритм двойственного симплекс-метода. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5. [c.155]
Какую роль играет алгоритм двойственного симплекс-метода при решении целочисленной линейной задачи методом Гомори [c.157]
Как уже отмечалось, при решении симплекс-методом исходной задачи сразу же решается и двойственная. Если "Поиск решения" MS-Ex el получил решение задачи об оптимальном плане продукции, то он нашел и теневые цены ресурсов. Никаких дополнительных операций по решению двойственной задачи на практике делать не нужно. Полученные нами значения двойственных цен ресурсов мебельного цеха У, = 40 Y2 = 0 У3 = 60 можно найти в колонке "Теневые цены" таблицы "Ограничения" отчета об устойчивости для прямой задачи об оптимальном плане выпуска продукции (рис. 14). [c.75]
Если среди внебазисных переменных нет ни одной, которую можно проварьировать с убыванием л, это свидетельствует о том, что данное допустимое решение — оптимально. Этот факт нам будет удобно доказать несколько ниже, в связи с двойственным вариантом симплекс-метода. [c.422]
Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (о. о. оценок). Существуют и другие методы решения задач линейного программирования. Упомянем и коротко поясним один из них — метод блочного программирова- [c.42]
Связь матричных игр с линейным программированием и нахождение NEm. Доказательство Сл. 1.1 для антагонистических (матричных) игр двух лиц можно проводить и независимо от теоремы Нэша, через линейное программирование, что дает также способ поиска NEm для этих игр. Для этого задачу 1-го игрока записывают в форме максимизации (неизвестной ему заранее) цены игры //0 по переменным //о,/А при ограничениях ц, > О, Sf li/ = lr fJ-ak > ц0 (k = 1,...,п2), где ak e Rni — столбцы матрицы платежей (а ) = (MI(X ,X )). Здесь ограничения типа > выражают гипотезу 1-го о неблагоприятном поведении противника (максимин). Легко проверить, что задача противника есть двойственная к описанной задаче. Таким образом симплекс методом можно найти седловую пару в игре Gm, она является и Нэшевской парой. Для случая биматричной игры 2x2 также легко найти NEm графически, строя функции (или отображения) NRi(x i) отклика игроков на действия партнеров. [c.7]
Смотреть страницы где упоминается термин Двойственный симплекс-метод
: [c.468] [c.438] [c.147] [c.53] [c.290]Смотреть главы в:
Математические исследования операций в экономике -> Двойственный симплекс-метод