XV Международная студенческая научная конференция Студенческий научный форум - 2023

Симплексный метод – это метод последовательного улучшения плана. Этим методом можно решать задачи линейного программирования с любым количеством переменных и ограничений [1].

Симплексный метод или симплекс метод состоит из следующих этапов:

привести задачу линейного программирования (далее – ЗЛП) к каноническому виду, это подготовительный этап прежде чем перейти к решению задачи;

после того как сделали подготовительный этап, переходим к вычислительному этапу, он заключатся в последовательном построении симплекс-таблиц;

когда мы закончили вычислительный этап, переходим к заключительному этапу, в него входит запись оптимальных значений переменных и оптимального значение целевой функции.

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

Симплексный метод был впервые представлен американским математиком Джорджем Бернардом Данцигом в 1947 году. С этого момента симплекс метод считается наилучшим методом использующих линейное программирование. По причине его многочисленного экономического влияния и широкого применения симплекс метод стал объектом множества исследований. Именно из-за исследований симплексный метод стал эффективным вычислительным средством.

Двойственный симплекс метод – вначале симплексным методом решается двойственная задача, а затем оптимальное решение исходной задачи находят с помощью теорем двойственности [2].

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

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

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

Вычислительная процедура двойственного симплекса состоит из следующих этапов вычисления:

Этап 1. Найдем псевдоплан данной задачи. Псевдоплан - план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных x_i имеются отрицательные числа.

Этап 2. Проверяем его на оптимальность. Если в полученном опорном плане не выполняется условие оптимальности, то задача решается с помощью симплексного метода.

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

Этап 4. Найдем новый псевдоплан и продолжим действовать со 2 этапа.

Замечания.

1) Задача неразрешима при условии, что в разрешающей строке нет ни единого отрицательного элемента;

2) Искусственные переменные не надо вводить, при условии, что ограничения задачи заданы неравенства вида «≥».

Особенности двойственного симплекс-метода используются при решении методом Гомори для нахождения целочисленного решения в задачах линейного программирования.

Двойственный симплекс-метод «выгодно» применять, когда легко находится какая-нибудь симплексная таблица, удовлетворяющая условию оптимальности.

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

Рассмотрим практический пример применение двойственного симплекс метода на примере.

Найти при условиях

Решение примера:

Ведем дополнительные переменные , далее запишем пример чтобы коэффициенты при базисных были равны 1.

Получаем следующие результат:

Полученные данные представим в виде симплекс-таблице 1.

Таблица 1

Симплекс-таблица

Б. н.	С. ч.
	8	1	1	1	0	0
	-4	-1	1	0	1	0
	-6	-1	-2	0	0	1
	16	1	1	0	0	0

Самое большое отрицательное число по модулю -6, следовательно убираем из базиса переменную

Чтобы определить новый разрешающий столбец, найдем

Выполним элементарное преобразование строк, и получаем следующую симплекс-таблице 2.

Таблица 2

Симплекс-таблица

Б. н.	С. ч.
	5	1/2	0	1	0	1/2
	-7	-3/2	0	0	1	1/2
	3	1/2	1	0	0	-1/2
	13	1/2	0	0	0	1/2

По данным таб. 2, видно, что наибольший отрицательный элемент –7, следовательно, рассматривать мы будем элементы второй строки.

Далее сделаем преобразование таблицы, занесем полученные значения в симплекс-таблицу 3.

блица 3

Симплекс-таблица

Б. н.	С. ч.
	8/3	0	0	1	1/3	2/3
	14/3	1	0	0	-2/3	-1/3
	2/3	0	1	0	1/3	-1/3
	32/3	0	0	0	1/3	2/3

По данным в таб. 3, мы видим, что в последней строке отсутствуют отрицательные элементы, вследствие чего план является оптимальным, так же

Оптимальный план можно записать так:

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

Список литературы

Симплексный метод решения задач линейного программирования // StudFiles– URL: https://studfile.net/preview/4085841/page:4/;

Мастяева И.Н., Горемыкина Г.И. Методы оптимальных решений – znanium.com, 2022;

Богданов С. И. Методы оптимальных решений – znanium.com, 2018;

 Бардаков В. Г., Мамонов О. В. Методы оптимальных решений – znanium.com, 2013.

Код для цитирования: Скопировать