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

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

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

Второй шаг. На втором шаге необходимо определиться, какую переменную изключить из базиса, а какую включить, для того, что бы произвести перерасчет симплекс-таблицы. Для этого просматриваем столбец со свободными членами и находим в нем отрицательный элемент. Строка с отрицательным элементом будет называться ведущей. В ней находим максимальный по модулю отрицательный элемент, соответсвующий ему столбец - ведомый. Если же среди свободных членов есть отрицательные значения, а в соответсвующей строке нет, то такая таблица не будет иметь решений. Переменая в ведущей строке, находящаяся в столбце свободных членов исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис.

Таблица 1.

базисные переменные Свободные члены в ограничениях Небазисные переменные
x1 x2 ... xl ... xn
xn+1 b1 a11 a12 ... a1l ... a1n
xn+2 b2 a21 a22 ... a2l ... a2n
. . . . . . . .
. . . . . . . .
. . . . . . . .
xn+r b2 ar1 ar2 ... arl ... arn
. . . . . . . .
. . . . . . . .
. . . . . . . .
xn+m bm am1 am2 ... aml ... amn
F(x)max F0 -c1 -c2 ... -c1 ... -cn

 

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

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

Пятый шаг. Если Вы дошли до пятого шага, значит нашли решение, которое допустимо. Однако, это не значит, что оно оптимально. Оптимальным оно будет только в том случае, если положительны все элементы в F-строке. Если же это не так, то необходимо улучшить решение, для чего находим для следующего перерасчета ведущие строку и столбец по следующему алгоритму. Первоначально, находим минимальное отрицательное число в строке F, исключая значение функции. Столбец с этим числом и будем ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они положительны. Минимальное отношение позволит определить ведущую строку. Вновь пересчитываем таблицу по формулам, т.е. переходим к шагу 3.

Шестой шаг. Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена сверху и Fmax->∞. Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

 

На нашем сайте вы также можете:

Решение онлайн

Для ввода исходных данных необходимо указать количество переменных в функции:

и количество ограничений:

ДОБАВИТЬ КОММЕНТАРИЙ