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

Линейное программирование — это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов. ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравоохранения и даже в социальных науках. Широкое использование этого метода также подкрепляется высокоэффективными компьютерными алгоритмами, реализующими данный метод. На алгоритмах линейного программирования базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач исследования операций (ИО), включая целочисленное, нелинейное и стохастическое программирование.

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

    В самом общем виде задача линейного программирования математически записывается следующим образом:

        (1)

где X = (x₁, x₂ , ... , x_n); W – область допустимых значений переменных x₁, x₂ , ... , x_n ;f(Х) – целевая функция.

    Для того чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать такое, что при любом .

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

    Методы решения оптимизационных задач зависят как от вида целевой функции f(Х), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

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

• показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x₁, x₂, ... , x_n);

• ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

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

        (2)         (3)         (4)         (5)

    При этом система линейных уравнений (3) и неравенств (4), (5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности.

Допустимое решение – это совокупность чисел (план) X = (x₁, x₂, ... , x_n), удовлетворяющих ограничениям задачи. Оптимальное решение – это план, при котором целевая функция принимает свое максимальное (минимальное) значение.

Если математическая модель задачи линейного программирования имеет вид:

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

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

    Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

• если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

• если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

• если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

• если некоторая переменная x_j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x₃ = x₃⁺ - x₃^-, где x₃⁺, x₃^- ≥ 0.

Пример 1. Приведение к канонической форме задачи линейного программирования:

min L = 2x₁ + x₂ - x₃; 2x₂ - x₃ ≤ 5; x₁ + x₂ - x₃ ≥ -1; 2x₁ - x₂ ≤ -3; x₁ ≤ 0; x₂ ≥ 0; x₃ ≥ 0.

   Введем в каждое уравнение системы ограничений выравнивающие переменные x₄, x₅, x₆. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x₄, x₆ вводятся в левую часть со знаком "+", а во второе уравнение переменная x₅ вводится со знаком "-".

2x₂ - x₃ + x₄ = 5; x₁ + x₂ - x₃ - x₅ = -1; 2x₁ - x₂ + x₆ = -3; x₄ ≥ 0; x₅ ≥ 0; x₆ ≥ 0.

   Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x₂ - x₃ + x₄ = 5; -x₁ - x₂ + x₃ + x₅ = 1; -2x₁ + x₂ - x₆ = 3.

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

Алгоритм симплекс-метода находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений. Алгоритм симплекс-метода всегда начинается с некоторого допустимого базисного решения и затем пытается найти другое допустимое базисное решение, "улучшающее" значение целевой функции. Это возможно только в том случае, если возрастание какой-либо нулевой (небазисной) переменной ведет к улучшению значения целевой функции. Но для того, чтобы небазисная переменная стала положительной, надо одну из текущих базисных переменных сделать нулевой, т.е. перевести в небазисные. Это необходимо, чтобы новое решение содержало в точности m базисных переменных. В соответствии с терминологией симплекс-метода выбранная нулевая переменная называется вводимой (в базис), а удаляемая базисная переменная — исключаемой (из базиса).

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

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

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

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

F = с₁х₁+с₂х₂+…+с_nx_nmax

х₁0, х₂0,…, х_n0.

1-й шаг. Вводим добавочные переменные и записываем полученную систему уравнений и линейную функцию в виде расширенной системы.

F–c₁x₁–c₂x₂–…–c_nx_n=0=c_p.

2-й шаг. Составляем первоначальную симплекс-таблицу.

Переменные Базис	Основные и добавочные переменные								свободные члены (решение)	Оценочное отношение
	X1	X2	…	Xn	Xn+1	Xn+2	…	Xn+m
хn+1	a11	a12	…	a1n	1	0	…	0	b1
xn+2	a21	a22	…	a2n	0	1	…	0	b2
…	…	…	…	…	…	…	…	…	…
хn+m	am1	am2	…	amn	0	0	…	1	bm
F	-c1	-c2	…	-cn	-cn+1	-cn+2	…	-cn+m	0

3-й шаг. Проверяем выполнение критерия оптимальности – наличие в последней строке отрицательных коэффициентов. Если таких нет, то решение оптимально и F^*=c_o, базисные переменные равны соответствующим коэффициентам b_j, неосновные переменные равны нулю, т. е. X^*=(b₁,b₂,…, b_m, 0, …, 0).

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

Для определения разрешающей строки, рассчитаем оценочные отношения и заполним последний столбец таблицы.

Оценочное отношение i-ой строки равно

1. , если b_i и a_is имеют разные знаки;

2. , если b_i =0 и а_is<0;

3. , если a_is=0;

4. 0, если b_i=0 и а_is>0;

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

Если минимума нет, то задача не имеет конечного оптимума I и является неразрешимой .

На пересечении разрешающих строки и столбца находится разрешающий элемент а_gs.

5-й шаг. Строим следующую таблицу. Для этого

1. в левом столбце записываем новый базис, в который вместо переменной х_g вводится переменная х_s;

2. элементы разрешающей строки делятся на разрешающий элемент и заполняется строка g в новой таблице;

3. все остальные элементы вычисляются по методу Жордана-Гаусса (по правилу прямоугольника):

Переходим к третьему шагу.

М-метод Иногда при решении ЗЛП в матрице коэффициентов при неизвестных системы ограничений нет единичных столбцов, из которых можно составить единичную матрицу, т.е. возникает проблема выбора базисных переменных, либо первоначальное решение является недопустимым. В таких случаях используют метод искусственного базиса (М - метод). Во все ограничения, где нет базисных переменных, вводятся искусственные переменные. В целевую функцию искусственные переменные вводятся с коэффициентом (- М ) для задач на max и с коэффициентом (+ М ) для задач на min, где М – достаточно большое положительное число.  Затем решается расширенная задача по правилам симплексного метода. Если все искусственные переменные окажутся равными нулю, т.е. будут исключены из базиса, то либо будет получено оптимальное решение исходной задачи, либо исходная задача решается далее и находится ее оптимальное решение или устанавливается ее неразрешимость. Если хотя бы одна из искусственных переменных окажется отличной от нуля, то исходная задача не имеет решения