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

1.3 Симплекс-метод

Двумерные задачи линейного программирования решаются графически. Для случая n=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

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

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

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

f (x) = c1x1+c2x2+...+cnxn max(min)

a11x1+a12x2+...+a1nxn +х n +1 = b1,

a21x1+a22x2+...+a2nxn+х n +2 = b2,                                                                   

...................................................

am1x1+am2x2+...+amnxn+х n +т = bm,

xi≥0 i = .

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

Выразим в системе ограничений базисные неизвестные через небазисные, т.е. разрешим систему относительно базисных неизвестных:

х n +1 = a11(–x1)+a12(–x2)+...+a1n(–xn) +b1,

х n +2 = a21(–x1)+a22(–x2)+...+a2n(–xn) + b2,                                                                   

...................................................

х n +т = am1(–x1)+am2(–x2)+...+amn(–xn)+bm.

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

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

1.4 Симплексные таблицы

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

Алгоритм решения задач симплексным методом.

1. Математическая модель задачи должна быть канонической. Если в исходной формулировке задача неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу 1.1. Все строки таблицы 1-го шага заполняем по данным системы ограничений и целевой функции. Базисные неизвестные (Б.Н.) запишем в левый заглавный столбец, а небазисные неизвестные (Н.Н.)  – в верхнюю заглавную строку. Числовые значения правой части системы ограничений запишем в правом столбце таблицы (в столбце свободных членов), в месте пересечения верхней заглавной строки и этого столбца поставим единицу. Коэффициенты при небазисных неизвестных запишем под ними. Функцию запишем в последней строке таблицы. В правой клетке этой строки запишем значение функции (Z=0)

Пусть решение в табл. 1.1 неопорное (элемент br,<0). Чтобы получить опорное решение, воспользуемся правилом преобразования таблиц с помощью модифицированных жордановых исключений, в соответствии с которым элементы разрешающей строки делятся на разрешающий элемент и записываются в новой таблице с тем же знаком. Поэтому, чтобы вместо br <0 получить число положительное, необходимо, чтобы разрешающий элемент был в данной строке и имел отрицательный знак.

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

Пусть в r-й строке имеются отрицательные элементы аr2 и аrk. Если за разрешающий момент принять аrk < 0 или  аr2 < 0 и рассчитать новую таблицу, то гарантировано, что вместо элемента br < 0 будет положительное число, равное br/аrk или br/аr2, однако в таблице свободных членов вместо положительных элементов может появится не один, а несколько отрицательных элементов. Чтобы этого не случилось, необходимо разрешающий элемент выбирать по наименьшему симплексному отношению, отношению элементов столбца. За разрешающий столбец выбирается тот, в котором находится отрицательный элемент в строке с отрицательным свободным членом. В данном случае за разрешающий столбец можно выбрать 2-й или k-й, так как  аr2 < 0 и аrk < 0. Выберем за разрешающий столбец k-й. Тогда, обозначив симплексные отношения буквой t, найдем наименьшее из них среди положительных отношений:

t = min (b1/a1k; … bi/aik; ... br/ark; ... bm/amk) = br/ark  > 0.

Это отношение определило разрешающую строку и разрешающий элемент ark. Симплексные отношения удобно рассчитывать в таблице (табл.1.1).

                                                                                                                  Таблица 1.1

Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;

3. Заполняем симплексную таблицу 2-го шага:

– переписываем разрешающую строку, разделив ее на разрешающий элемент;

– заполняем базисные столбцы;

– остальные  коэффициенты таблицы находим по правилу «прямоугольника». Так, например, вместо bi в новой таблице будет элемент bi’:

bi’ = bi – br aik / ark .

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

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

Задача. Транспортное предприятие имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика – 400 млн.руб., пятитонного –500 млн. руб. Предприятие может выделить для приобретения автомашин 14 100 млн.руб. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?

Решить задачу аналитическим способом.

Решение:

Составим математическую модель задачи. Пусть х1 – количество трехтонных автомашин, х2 – количество пятитонных автомашин.

По условию   0 х1 19, 0 х2 17. На приобретение грузовиков необходима сумма 400х1 + 500х2, при этом по условию она не должна превышать 14 100, т.е.  400х1+500 х2 14 100. Теперь введем целевую функцию – грузоподъемность автомашин, которая составляет 3х1+5х2.

Таким образом, задача заключается в следующем: максимизировать целевую функцию:

Z = 3х1+5х2max                     

при ограничениях

400 х1+500 х2 14 100,

0 х1 19,

0 х2 17.

Решим эту задачу симплекс-методом. Приведем задачу к каноническому виду, введя три дополнительные переменные х3, х4, х5:

Z = 3х1+5х2+0х3+ 0х4+0х5max     

400 х1+500 х2+х3 = 14 100,

х1 + х4 = 19,

х2 + х5  = 17,

х1 0,   х2 0.   

Дополнительные неизвестные х3, х4, х5 будут базисными, так как им соответствуют единичные векторы, которые образуют базис в трехмерном пространстве. Разрешив систему относительно базисных неизвестных, получим:

х3 = –400х1 – 500х2 +14 100  0;

          х4 = –х1 + 19  0;

х5 = –х2 + 17  0;

Занесем коэффициенты системы ограничений и функции в симплексную таблицу (таблица 2.1).

                                                                                                            Таблица 2.1