Симплекс-алгоритм решения задачи ЛП

из "Экономико-математические модели и методы "

Существует несколько форм симплекс-алгоритма с короткой матрицей, с расширенной матрицей, двойственный алгоритм, модифицированный. [c.48]
При рассмотрении алгоритма с короткой матрицей будем считать, что задача дана на максимум целевой функции. Если задача дана на минимум, то ее можно привести к задаче на максимум, изменив знак целевой функции. [c.48]
Для применения симплекс-алгоритма ЗЛП должна быть представлена в канонической форме (4.5). Если в системе ограничений (4.5) т п и все уравнения линейно независимы, то эту систему можно разрешить относительно тех т переменных, которым в матрице ограничений соответствуют линейно независимые столбцы. [c.48]
Переменные Хь Х2,. .., Хт будут базисными, а переменные Хт + 1, Хт + 2,. ..,Х -свободными. [c.48]
Симплекс-алгоритм носит итеративный характер и состоит в построении и последовательном преобразовании симплексной таблицы, в результате которого от начального плана можно за конечное число шагов получить оптимальный план, либо установить, что ЗЛП не имеет решения. [c.48]
Задачу (4.8), (4.9), разрешенную относительно базисных переменных, удобно представить в виде симплексной таблицы. [c.48]
В / -строке записаны коэффициенты модифицированной целевой функции с обратными знаками, Ь0 - это значение функции при нулевых значениях свободных переменных. [c.49]
Если в столбце свободных членов все коэффициенты bio О, то вектор Х= (Xj = Ъю, Х2 = Ь2о, -., Хт = Ьт0, Хт + 1 = 0,. .., Х = 0) называется начальным опорным планом. Значение целевой функции равно элементу 5-столбца в F-строке. [c.49]
Решение задачи линейного программирования симплексным методом проводится в два этапа. Сначала находится начальное базисное решение, а затем проводится направленный перебор базисных решений для получения оптимального плана. [c.49]
В столбце свободных членов отыскивается отрицательный элемент. Если такого нет, текущее решение является опорным. Далее переходят к алгоритму нахождения оптимального плана. [c.49]
Если среди элементов столбца свободных членов несколько отрицательных, то выбирается минимальный из них. По минимальному отрицательному элементу этой строки выбирается разрешающий столбец (г). Если просматриваемая строка не содержит отрицательных элементов, задача несовместна и не имеет решения. [c.49]
Находятся симплексные отношения элементов столбца свободных членов к элементам разрешающего столбца (кроме F-строки). Рассматриваются только положительные отношения. По наименьшему положительному симплексному отношению определяется разрешающая строка (s). [c.49]
На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент (asr). [c.49]
В результате выполнения этого шага переменная хг становится базисной, а переменная xs выводится из базиса и становится свободной. После чего переходят к шагу 1. [c.50]
Если все элементы F-строки неотрицательны, то базисное решение оптимально. В противном случае оно может быть улучшено. [c.50]
Если все элементы F-строки положительны, то полученный оптимальный план будет единственным, если в F-строке есть нулевые элементы, то существует бесконечно много оптимальных планов. [c.50]
Разрешающий столбец выбирают по минимальному отрицательному элементу F-строки. Пусть г — номер разрешающего столбца. [c.50]
Если в F-строке есть отрицательный элемент, в столбце которого нет положительных элементов, то целевая функция неограниченна и решения ЗЛП не существует. [c.50]
Пусть s - номер разрешающей строки. [c.50]
Выполняется точно так же, как и в предыдущем алгоритме. После чего осуществляется переход к шагу 1. [c.50]

Вернуться к основной статье