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

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

В стандартной форме задача линейного  программирования является задачей  на максимум (минимум) линейной целевой  функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны.

 

 

 

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

 

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

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

Особенности симплекс-метода

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

За  прошедшие с тех пор годы было предложено не только много разновидностей симплекс-метода, учитывающих особенности  различных подклассов задачи ЛП (блочные  задачи, задачи со слабо заполненной  матрицей условий A ={a_{i, j}}), но и несколько принципиально иных методов решения задачи ЛП. Некоторые из предложенных методов в теоретическом плане, например, с точки зрения характеристики сложности алгоритма, превосходят симплекс-метод (известно, что симплекс-метод обладает экспоненциальной сложностью, т.е. имеет экспоненциальную оценку трудоемкости на всем классе задач ЛП, тогда как такие алгоритмы, как метод эллипсоидов Хачияна (советского математика) и метод Крамаркара (американского исследователя) характеризуются полиномиальной сложностью). И, тем не менее, по утверждению многих специалистов в теории линейного программирования симплекс-метод и после десятилетий всесторонней апробации с точки зрения алгоритмической реализации и универсальности применимости на классе задач ЛП остается наиболее предпочтительным, а потому наиболее распространенным методом решения задач ЛП.

Основная  идея симплекс-метода достаточно просто иллюстрируется геометрически. Допустимое множество задачи ЛП представляет собой выпуклый многогранник (в случае, если множество не ограничено – выпуклое многогранное множество) с конечным числом вершин этого многогранника, т.е. его крайних точек. В том случае, если задача ЛП имеет единственное решение, то решение находится в одной из этих вершин. Симплекс-метод состоит в таком направленном переборе вершин, при котором значение целевой функции улучшается (не ухудшается) при переходе от вершины к вершине. Каждая вершина многогранника является пересечением плоскостей (в n-мерном случае – гиперплоскостей), каждая из которых задается уравнением, определенным соответствующим ограничением исходной задачи ЛП. Другими словами, каждая вершина определяется системой уравнений, выбираемой специальным образом из системы неравенств. Таким образом, симплекс-метод, по сути дела, представляет собой вычислительную процедуру последовательного решения систем линейных уравнений. Поэтому этот метод содержит в себе правила формирования систем уравнений (правило выбора разрешающего элемента) и схему решения систем линейных уравнений (жордановы исключения).

Так как число вершин в многограннике - на множестве допустимых решений – конечно, и можно показать, что при решении задачи ЛП симплекс-методом значение целевой функции от вершины к вершине улучшается (не ухудшается), то алгоритм метода является конечным. Это означает, что теоретически (без учета вычислительных погрешностей машинной реализации алгоритма) метод сходится за конечное число итераций. Причем считается, что число итераций зависит в основном от числа ограничений m, а не числа переменных n.  В грубом приближении число итераций лежит в пределах от 1,5m до 2m.

 

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ

 

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

 

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

 

Первый шаг.

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

 

Второй шаг.

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

Третий шаг.

На третьем шаге пересчитываем  всю симплекс-таблицу по специальным формулам.

 

Четвертый шаг.

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

 

Пятый шаг.

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

 

Шестой шаг.

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

 

Пример симплекс-таблицы:

1 столбец	2 столбец	3 столбец	Столбцы переменных						5 столбец
			1	1	-1
			x1	x2	x3	x4		x5
-1	x3	38	2	11	1				19
	x4	7	1	1		1			7
	x5	5		-5				1	5/4
		-38	-3	-12

 

Шапка таблицы. Первый столбец предназначен для записи коэффициентов при переменных в функции цели. Второй столбец отображает список базисных переменных в существующем опорном решении. Третий столбец отображает свободные коэффициенты расширенной системы линейных уравнений, т.е. собственно системы линейных уравнений-ограничений и нулевого уравнения, которое записывается последним. Такое расположение столбцов очень удобно – мы можем прочитать список базисных переменных (второй столбец) и их значения в имеющемся решении (третий столбец). Эти же столбцы в последней строке позволяют выписать значение функции цели в данном решении. Например, пусть мы желаем записать из симплекс-таблицы данные текущего решения. Так как переменной x₁ в списке базисных переменных нет, то она – свободная переменная и поэтому x₁ = 0. Переменная x₂ – также свободная, x₂ =0. Читаем значения базисных переменных: x₃ = 38, x₄ = 7, x₅ = 5. Значение функции цели в данном решении f = -38.

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

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

 

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

 

Постановка задачи

 

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

 

Затраты	Партия из 100 плит		Имеющиеся ресурсы  на месяц
	обычных	улучшенных
Материал (фунты)	20	40	4000
Время на прессование (часы)	4	6	900
Время на отделку (часы)	4	4	600
Средства (доллары)	30	50	6000

 

если за каждые 100 обычных  плит фирма получает прибыль, равную 80 долл., а за каждые 100 плит улучшенного  вида - 100 долл.

 

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

 

Введем следующие обозначения. Пусть

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

у - то же для плит улучшенного качества.

Тогда ожидаемую прибыль  можно записать так:

z= 80x + 100y - max.

Для изготовления х партий в 100 плит обычного вида и у партий в 100 плит улучшенного вида требуется

20x+40y

 

 

фунтов дерева. Ясно, что  полученное число не может превосходить количество материала, имеющегося в  наличии, т. е. 4000 фунтов. Тем самым, ограничения  на материал имеют вид:

20x+40<4000

Подобным же образом рассчитываются ограничения на время изготовления и затраты:

прессование: 4x+6y<900,

отделка: 4x+4y<600,

затраты: 30x+50y<6000.

Подведем итог: требуется  найти такие значения х и у, подчиненные условиям

 

20x+40y<4000,

4x+6y<900,

4x+4y<600,

30x+50y<6000,

x>0,

y>0,

 

для которых

z=80x+100y -> max

 

Решение графическим  методом на примере задачи о выпуске продукции

 

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

Для того чтобы найти в  первой четверти плоскости Оху множество точек, координаты (x,y) которых удовлетворяют указанным выше неравенствам, необходимо сначала построить прямые (по точкам их пересечения с координатными осями)

 

	20x+40y<4000,	A(200,0),B(0,100),	(4)
	4x+6y<900,	C(225,0),D(0,150),	(5)
	4x+4y<600,	E(150,0),F(0,150),	(6)
	30x+50y<6000,	G(200,0),H(0,120),	(7)

 

 

а затем, используя точку  начала отсчета О(0,0), определить соответствующие полуплоскости (см. рис.).

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

Напомним, что линейная функция  Z=80x+100y достигает наибольшего значения в одной из вершин этого четырехугольника. Поэтому для ответа на поставленный вопрос необходимо