Универсальный метод решения линейных

Задач оптимизации

Графический метод решения ЗЛП целесообразно использовать только для задач с двумя переменными. В случае большего числа переменных используют универсальный метод решения ЗЛП – симплекс-метод.

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

Алгоритм симплекс-метода решения ЗЛП

1. Определение начального опорного плана ЗЛП.

2. Построение симплексной таблицы.

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

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

5. Повторение действий, начиная с п.3.

Рассмотрим алгоритм симплекс-метода на примере.

Пример 2.3.1. Решить ЗЛП (2.2.1), (2.2.5) симплекс-методом.

Решение.Для решения ЗЛП необходимо, чтобы все свободные члены системы ограничений (2.2.1) были неотрицательными. Для этого первое неравенство системы умножим на (–1):

(2.3.1)

Перейдем к минимуму в нашей задаче:

min(–z) = – x₁ – 4x₂

Приведем задачу к канонической форме, вводя дополнительные переменные x₃ , x₄, x₅ в систему ограничений (2.3.1).

Замечание.

Если неравенство имеет знак “ ”, то дополнительную переменную вводят со знаком “+”; если неравенство имеет знак “ ”, то дополнительную переменную вводят со знаком “– ”.

ЗЛП (2.3.1) в канонической форме имеет следующий вид:

min(–z) = – x₁ – 4x₂ .

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

(2.2.2)

min(–z) = – x₁ – 4x₂ + Мx₆ + Мx_7.

В векторной форме система ограничений (2.2.2) имеет вид

р₁x₁ + р₂x₂ + р₃x₃ + р₄x₄ + р₅x₅ + р₆x₆ + р₇x₇ = р₀,

где р₁ = , р₂ = , р₃ = , р₄ = , р₅ = , р₆ = , р₇ = , р₀ =

Переменные x₁ и x₂ являются основными, x₃, x₄, x₅ – дополнительными, x₆, x₇ – искусственными. Векторы р₆, р₄, р₇ образуют единичный базис, причем р₆ – первый базисный вектор.

Заполним первую симплекс-таблицу. Исходная симплекс-таблица заполняется следующим образом. В первой строке записывают коэффициенты целевой функции. В столбец “Базис” записывают базисные векторы. В столбце “С” записывают коэффициенты целевой функции при базисных векторах. В столбцах “р₀”, “р₁”, “р₂”, “р₃”, “р₄”, “р₅”, “р₆”, “р₇” записывают компоненты соответствующих векторов.

Для заполнения клеток таблицы, которые находятся в двух последних строках, нужно элементы столбца “С” умножить на соответствующие элементы рассчитываемого столбца и отнять число, стоящее в первой строке (за исключением столбца “р₀”). Например, для заполнения клеток столбца “р₂” умножим элементы столбца “С” на соответствующие элементы столбца “р₂” и отнимем число – 4: М·5 + 0·1 + М·1 – (– 4) = 4 + 6М. Коэффициент при М записывают в М-строку, число без М вносят в z–строку.

Таблица 2.3.1

Первая симплексная таблица

Последние две строки симплекс-таблицы называются индексными. В них, начиная со второго столбца “р₁”, содержатся оценки оптимальности, с помощью которых проверяют оптимальность опорного плана, соответствующего данной таблице. Значение составляющих опорного плана расположено в столбце “р₀”, причем небазисным переменным присваивают нулевые значения.

Первой симплекс-таблице 2.3.1 соответствует опорный план:

x₁ = 0, x₂ = 0, x₃ = 0, х₄ = 6, x₅ = 0, x₆ = 5, x₇ = 7.

Критерий оптимальности проверяют по М-строке, а если она отсутствует, то по z-строке.

Критерий оптимальности опорного плана

· Если в индексной строке среди оценок оптимальности есть хотя бы одна положительная, то опорный план не является оптимальным.

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

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

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

Для перехода к следующей симплекс-таблице в М-строке выбирают наибольшую положительную оценку, начиная со столбца “р₁”. В нашем случае – это число 8 в столбце “р₁”.

В нашем случае вектор “р₁” следует ввести в базис.

Найдем симплексноеотношение оптимальности : элементы столбца “р₀” разделим на положительные элементы разрешающего столбца.

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

В нашем случае . Таким образом, вектор р₇ следует вывести из базиса. Кроме того вектор р₇ можно исключить из рассмотрения, поскольку он является искусственным.

В нашем случае это число 7.

Переход к следующей симплекс-таблице осуществляют по правилам:

· все элементы разрешающей строки делят на генеральныйэлемент;

· разрешающий столбец дополняют нулями;

· если в разрешающей строке есть нули, то соответствующие столбцы переписывают без изменений;

· все другие элементы рассчитывают с помощью метода прямоугольников: если г – генеральный элемент, с – старый элемент, а и b – элементы разрешающей строки и разрешающего столбца,топ – новый элемент находят по формуле:

а		с
г		b

Таким образом, вторая симплекс-таблица имеет вид:

Таблица 2.3.2

Вторая симплексная таблица

Этой симплексной таблице соответствует опорный план:

x₁ = 1, x₂ = 0, x₃ = 0, х₄ = 5, x₅ = 0, x₆ = 4.

Он не является оптимальным, так как в М-строке есть положительные оценки.

По правилам, описанным выше, перейдем к третьей симплексной таблице:

Таблица 2.3.3

Третья симплексная таблица

Базис	С	р0	– 1	– 4
р1	р2	р3	р4	р5
р2	– 4	14/17			–7/34		1/34
р4		73/17			3/17		2/17	(73/17)/(3/17)=73/3
р1	– 1	15/17			1/34		–5/34	(15/17)/(1/34)=30
z-строка	–71/17			27/34		1/34

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

Третьей симплексной таблице соответствует опорный план:

x₁ = 15/17, x₂ = 14/17, x₃ = 0, х₄ = 73/17, x₅ = 0.

Он не является оптимальным, так как в z-строке есть положительные оценки.

Перейдем к четвертой симплексной таблице:

Таблица 2.3.4

Четвертая симплексная таблица

Этой симплекс-таблице соответствует опорный план:

x₁ = 1/6, x₂ = 35/6, x₃ = 73/3, х₄ = 0, x₅ = 0.

Он является оптимальным и единственным, так как в z-строке нет положительных оценок. Значение целевой функции min (– z) = – 47/2, значит,

max z = – min (– z) = 47/2.