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

Тема 2. Симплекс-метод решения задачи линейного программирования Рассмотренный выше геометрический метод решения задач ЛП никак не может удовлетворить ни математиков, ни экономистов. Возможны «технические» погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов производства, избыток питательных веществ и т.п.), не выявляются при геометрическом решении задач. Но самое главное – геометрический метод неприемлем для решения практических задач. Его можно применять только в том случае, когда число переменных равно двум. Поэтому, необходимы аналитические методы, позволяющие решать задачи линейного программирования с любым числом переменных и выявлять экономический смысл входящих в них величин. Один из таких методов – это симплексный алгоритм, который представляет собой алгебраический метод, позволяющий найти решение задач ЛП с помощью итеративной процедуры. Симплекс-метод впервые был сформулирован в работе Данцига в 1949г. Для реализации симплексного метода – последовательного улучшения решения, необходимо знать три основных элемента: • способ определения какого-либо первоначального допустимого базисного решения задачи; • правило перехода к лучшему решению; • признак проверки оптимальности найденного решения. Для использования симплексного метода задача ЛП должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений. Если линейное неравенство с п неизвестными имеет вид а1х1+а2х2+…+апхп  в, то для приведения его к равенству необходимо к его левой части прибавить некоторую неотрицательную величину xn+10. Переменная xn+10, с помощью которой неравенство преобразуется в уравнение, называется дополнительной переменной. Если неравенство имеет вид а1х1+а2х2+…+апхп  в, то для приведения его к равенству из левой его части необходимо вычесть неотрицательную величину xn+10. Существует две разновидности симплексного метода: 1) симплекс-метод с естественным базисом; 2) симплекс-метод с искусственным базисом (М-метод). Практические расчеты при решении реальных задач симплексным методом выполняются в настоящее время с помощью компьютеров. Однако, если расчеты осуществляются без ЭВМ, то удобно использовать симплексные таблицы. Рассмотрим алгоритм решения задачи ЛП. Для определенности рассмотрим задачу на отыскание максимума. 1. Приведем задачу к каноническому виду. После введения добавочных переменных, записывают в виде расширенной системы. Предположим, что все добавочные переменные имеют тот же знак, что свободные члены; в противном случае, используется М-метод, который будет рассмотрен ниже. 2. Исходную расширенную систему занесем в первую симплексную таблицу. Последняя строка таблицы, в которой приведено уравнение для целевой функции, называется оценочной. В ней указаны коэффициенты целевой функции с противоположенными знаками. В левом столбце таблицы записываем основные переменные (базис). Во втором столбце таблицы записываем свободные члены расширенной системы. Последний столбец подготовлен для оценочных отношений. В первой строке таблицы записываем все переменные. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты из расширенной системы. Далее таблица преобразуется по определенным правилам. 3. Проверяем выполнение критерия оптимальности при решении задачи на максимум – наличие в последней строке отрицательных коэффициентов. Если отрицательных коэффициентов нет, то решение оптимально, и достигнут максимум функции F (в левом нижнем углу таблицы). 4. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент в последней строке определяем как разрешающий (разрешающий столбец S). Составляем оценочные отношения по следующим правилам: 1) ∞, если bi и ais имеют разные знаки; 2) ∞, если bi =0 и ais  0; 3) ∞, ais=0; 4) 0, если bi =0 и ais  0; 5) , если bi и ais имеют одинаковые знаки. Определяем min . Если конечного минимума нет, то задача не имеет конечного оптимума. Если минимум конечен, то выбираем строку, на которой он достигается. Эта строка называется разрешающей. На пересечении разрешающих строки и столбца находится разрешающий элемент aqs . 5. Переходим к следующей таблице по правилам: 1) в левом столбце записываем новый базис, вместо основной переменной xq – переменную xs. 2) в столбцах, соответствующих основным переменным проставляем 0 и 1: 1 – против «своей» основной переменной; 0 – против «чужой» основной переменной; 0 – в последней строке для всех основных переменных. 3) новую строку с номером q получаем из старой строки делением на разрешающий элемент aqs . 4) все остальные элементы находим по правилу: ; . Далее переходим к пункту 3. Задача 1. Решить задачу ЛП симплекс-методом. F= 2x1+3x2 max х1+3х2  18; 2х1+х2  16; х2  5; 3х1  21; х1  0, х2  0. Решение. 1. Приведем систему к каноническому виду, введя дополнительные переменные х3 , х4 , х5 , х6 и запишем расширенную систему задачи: F- 2x1-3x2 =0 х1+3х2 + х3 =18; 2х1+х2 + х4 = 16; х2 + х5 = 5; 3х1+ х6 =21; х1,2,…,6  0. 2.Заполним первую симплексную таблицу. базис Свободный член х1 х2 х3 х4 х5 х6 Оценочное отношение х3 18 1 3 1 6 х4 16 2 1 1 16 х5 5 1 1 5 х6 21 3 1 ∞ F -2 -3 3. Проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выберем из них наибольший по модулю (-3). Второй столбец будет разрешающим, переменная х2 перейдет в основные (в базис). 4. Найдем оценочные отношения по правилу пункта 4. min{6, 16, 5, ∞}=5. Третья строка будет разрешающей, элемент а32 =1 будет разрешающим. 5. Перейдем к следующей симплексной таблица. базис Свободный член х1 х2 х3 х4 х5 х6 Оценочное отношение х3 3 1 1 -3 3 х4 11 2 1 -1 5,5 х2 5 1 1 ∞ х6 21 3 1 7 F 15 -2 3 Критерий оптимальности вновь не выполнен. Разрешающий столбец – первый. min{3; 5,5; ∞; 7}=3. Разрешающая строка – первая, разрешающий элемент – а11=1. Составим новую симплексную таблицу. базис Свободный член х1 х2 х3 х4 х5 х6 Оценочное отношение х1 3 1 1 -3 ∞ х4 5 -2 1 5 1 х2 5 1 1 5 х6 12 -3 9 1 12/9 F 21 2 -3 Критерий оптимальности не выполнен, разрешающий столбец – пятый, разрешающий элемент – а25=5. Составим новую симплексную таблицу. Критерий оптимальности выполнен, значит, наибольшее значение целевой функции равно 24 и достигается это оптимальное значение при х=(6; 4; 0; 0; 1; 3). Ответ: при х1= и х2=.