Линейное программирование. Симплекс метод

Линейное  программирование

 

Математическое  программирование занимается изучением экстремальных задач и поиском методов их решений. Задачи математическое программирования формулируется следующим образом: найти экстремум некоторой функции многих переменных при ограничениях , где - функция, описывающая ограничения, * - один из следующих знаков , а - действительное число, i=1,…,m. F – называется целевой функцией.

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

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

Задачу линейного  программирования можно сформулировать так . Найти min  при условии : 

 

Эти ограничения  называются условиями неотрицательности. Если все ограничения заданы в виде строгих неравенств, то данная форма называется канонической.

Для решения  задач данного типа применяются  методы:

• графический;
• табличный ( прямой, простой ) симплекс - метод;
• метод искусственного базиса;
• модифицированный симплекс - метод;
• двойственный симплекс - метод.

 

 

 

 

 

 

 

 

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

 

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Данный метод, имеющий несколько различных форм (модификаций), был разработан в 1947 году Г. Данцигом.

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

 

Рассмотрим  теперь более подробно основы симплекс-метода и сформулируем алгоритм. Для решения  системы все неизвестные произвольно  подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.

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

Последовательность  вычислений симплекс-методом можно  разделить на две основные фазы:

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

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

 

 

 

 

Табличный симплекс-метод

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

 

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

К каждому ограничивающему условию, при переходе от неравенств к равенствам, добавляется дополнительная переменная x_n+m. Дополнительная переменная не будет оказывать влияния на значение целевой функции и на оптимальное решение которое будет получено в результате.

В неравенствах вида « » все дополнительные переменные вводятся со знаком «+», в случае неравенства вида « » дополнительные переменные вводятся со знаком «-».

С помощью дополнительных неотрицательных  переменных перейдем к системе уравнений:

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов  целевой функции F меняются на противоположные a_0n=-a_0n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.

В качестве основных переменных на первом шаге следует выбрать такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений, при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. Следовательно x₁, x₂, x_n - основные переменные, x_n+1, x_n+2, x_n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а основные переменные как небазисные

Выразим базисные переменные через небазисные:

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

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

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

БП	СЧ	x1	x2	…	xn-1	xn	xn+1	…	xn+m	ОО
xn+1	b1	a11	a12	…	a1n-1	a1n	1	…	0
xn+2	b2	a21	a22	…	a2n-1	a2n	0	…	0
…	…	…	…	…	…	…	…	…	…
xn+m	bm	am1	am2	…	amn-1	amn	0	…	1
F	0	-с1	-с2	…	-сn-1	-сn	0	…	0	max

БП-базисные переменные

СЧ-свободные  члены

ОО-оценочные  отношения

 

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

Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент  в последней строке определяет разрешающий  столбец s.

Составим  оценочные ограничения каждой строки по следующим правилам:

Определим min .

Если конечного  минимума нет, то задача не имеет конечного  оптимума.

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

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

Строится новая таблица, содержащая новые названия базисных переменных, по следующим правилам:

1) Разделим каждый элемент разрешающей строки  на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.

2) Строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

3) В новой таблице все элементы разрешающего столбца = 0, кроме самого разрезающего элемента, он всегда равен 1.

• Столбец, у которого в разрешающей строке имеется 0,в новой таблице будет таким же.
• Строка, у которой в разрешающем столбце имеется 0,в новой таблице будет такой же.

Элемент разреш. столбца данной строки

Элемент разреш. строки данного столбца

Разрешающий элемент

Новый элемент

Старый элемент

=

-

*

4) В остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

 

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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