Двойной симплекс метод

Пример решения прямой и двойственной задачи симплекс методом

=== Скачать файл ===

Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования , записанной в форме основной задачи, для которой среди векторов , составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс—метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами при решении задачи симплексным методом эти числа предполагались неотрицательными. Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы т. В данном случае есть решение системы линейных уравнений Однако это решение не является планом задачи 54 — 56 , так как среди его компонент имеются отрицательные числа. Поскольку векторы — единичные, каждый из векторов можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов по векторам служат числа Т аким образом, можно найти. Решение системы линейных уравнений 55 , определяемое базисом , называется псевдопланом задачи 54 — 56 , если для любого. Если в псевдоплане , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то задача 54 — 56 вообще не имеет планов. Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода. Итак, продолжим рассмотрение задачи 54 — Пусть — псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу табл. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи 54 — 56 , поскольку, по предположению, все. Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс—таблицы к другой до тех пор, пока из столбца вектора не будут исключены отрицательные элементы. Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются что мы и предполагаем , то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое— нибудь одно из них: Выбор этого числа определяет вектор , исключаемый из базиса, т. Чтобы определить, какой вектор следует ввести в базис, находим , где. Пусть это минимальное значение принимается при , тогда в базис вводят вектор Р r. Число является разрешающим элементов. Переход к новой симплекс—таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р 0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i — й строке симплекс—таблицы табл. Таким образом, отыскание решения задачи 54 — 56 двойственным симплекс-методом включает следующие этапы: Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален , то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану. Находят новый псевдоплан и повторяют все действия начиная с этапа 2. Найти максимальное значение функции при условиях. Запишем исходную задачу линейного программирования в форме основной задачи: Умножим второе и третье уравнения системы ограничений последней задачи на —1 и перейдем к следующей задаче: Составим для последней задачи двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции. Выбрав в качестве базиса векторы и , составим симплексную таблицу табл. Из этой таблицы видим, что планом двойственной задачи 57 — 59 является. При этом плане Т ак как в столбце вектора Р 0 таблица 16 имеются два отрицательных числа —4 и —6 , а в 4— й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс—метода переходим к новой симплекс—таблице. В данном случае это можно сделать, так как в строках векторов Р 4 и Р 5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р 0. В данном случае это число —6. Следовательно, из базиса исключаем вектор Р 5. Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем. Значит, в базис вводим вектор P 2. Переходим к новой симп л екс—таблице табл. Из этой таблицы видно, что получен новый план двойственной задачи П ри этом плане значение ее линейной формы равно Таким образом, с помощью алгоритма двойственного симплекс—метода произведен упорядоченный переход от одного плана двойственной задачи к другому. Так как в столбце вектора Р 0 таблицы 17 стоит отрицательное число —7, то рассмотрим элементы 2— й строки. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице табл. Как видно из таблицы 18, найдены оптимальные планы исходной и двойственной задач. При этих планах значения линейных форм исходной и двойственной задач равны между собой: Умножая первое и третье уравнения системы ограничений задачи на —1, в результате приходим к задаче нахождения максимального значения функции при условиях. Взяв в качестве базиса векторы Р 3 , Р 4 и Р 5 , составляем симплекс-таблицу табл. В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р 0 не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс—таблице таблица Для этого исключим из базиса вектор Р 5 и введем в базис вектор Р 1. Так как в строке вектора Р 3 нет отрицательных чисел, то исходная задача не имеет решения. Высшая математика Решение контрольных Оплата контрольных Вопросы по Skype Редактор формул Лекции Видео-лекции Учебники on-line Скачать учебники Решатели задач О математике Карта сайта. МЕНЮ Высшая математика Решение контрольных Оплата контрольных Вопросы по Skype Редактор формул Лекции Видео-лекции Учебники on-line Скачать учебники Решатели задач О математике Карта сайта.

Расписание автобусов уфа черкассы

Now or never перевод на русский halsey

Мосгорздрав тесты на категорию

Двойной симплекс метод

Пример решения прямой и двойственной задачи симплекс методом

=== Скачать файл ===

Двойственный симплексный метод

Двойственный симплекс-метод

Двойственный симплекс-метод.

Report Page