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

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

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

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

(1)

(2)

(3)

где A-mxn-матрица, rank(A)=m, b− неотрицательный вектор столбец длины m (b∈ R^m, b≥0), c − вектор строка длины n (c∈Rⁿ), x − вектор столбец длины n (x∈Rⁿ).

Определение 1. Допустимым планом или планом задачи линейного программирования (1)−(3) называется вектор , удовлетворяющим ограничениям (2)−(3).

Определение 2. Опорным планом задачи линейного программирования (1)−(3) называется план , если среди соотношений (2)−(3), которым он удовлетворяет как точным равенствам, имеется n линейно независимых.

Из определения 2 следует, что понятие опорный план совпадает с понятием вершины выпуклого многогранного множества, определяемого условиями (2)−(3).

Определение 3. Опорный план задачи линейного программирования (1)−(3) называется невырожденным , если число его положительных компонент в точности равен m.

Определение 4. Задача линейного программирования называется невырожденным , если все ее опорные планы невырождены.

Определение 5. Целевой функцией задачи линейного программирования (1)−(3) называется линейная функция cx, которую нужно максимизировать (в данном случае) на заданном выпуклом многогранном множестве (2)−(3).

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

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

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

Начнем рассмотрение метода со второго этапа. Мы будем предполагать, что ЗЛП невырождена (Определение 4).

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

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

где

Очевидно, что является опорным планом ЗЛП (4)-(6). Действительно, x⁰ удовлетворяет уравнениям (5)-(6), и ровно m координат вектора x⁰ положительны, а остальные нули.

Запишем ЗЛП (4)-(6) в векторном виде:

(4')

(5')

(6')

где E−единичная матрица порядка m×m,

Разделим x на базисные и свободные компоненты (базисные компоненты − это положительные компоненты вектора, а свободные компоненты − это нулевые компоненты):

(7)

где

,.

(7')

Тогда (5') можно записать так:

.

(8)

или

.

(9)

Отсюда

(10)

Представим c в виде объединения базисных и свободных компонент:

,

(11)

где

,.

Тогда, учитывая (7), (10) и (11), получим

.

(12)

Обозначим

.

(12')

Тогда (12) можно записать так:

.

(12'')

В выражении (12) ничего не изменится, если к правой части добавить нулевой элемент:

.

(13)

где − нулевая вектор-строка длины m.

Обозначим

.

(14)

Выражение (14) эквивалентно следующему выражению:

(14')

или

,.

(14'')

Тогда (13) можно записать так:

.

(15)

или

.

(16)

Заметим, что первые m элементы вектора Δ и последние n−m элементы вектора x нулевые (;).

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

Учитывая (7') перезапишем (5) следующим образом:

(17)

где −p-ый элемент вектора x, которую нужно ввести в базис (т.е сделать положительным).

Постепенно увеличивая из нуля нужно следить, чтобы новый вектор x удовлетворял уравнениям (17). Поэтому нужно уменьшить при , при этом нужно следить, чтобы не стал отрицательным. (В случае , увеличивается, а в случае , не изменяется).

Другими словами нужно решить систему линейных неравенств

(18)

Из (18) следует

,.

Тогда

,.

(19)

Подставляя в (18), получим:

.

(20)

Тогда при имеем

а при имеем

.

Из вышеизложенного можно сформулировать следующие теоремы:

Теорема 1 (признак оптимальности опорного плана). Опорный план задачи (4)-(6) является оптимальным, если для любого j (j=1,...,n).

Теорема 2. Если для некоторого j=k, и среди чисел (i=1,...,m) нет положительных, целевая функция (4) задачи (4)-(6) не ограничена на множестве (5)-(6).

Теорема 3. Если опорный план x задачи (4)-(6) не вырожден и для некоторого j=k, и среди чисел (i=1,...,m) есть положительные, то существует опорный план x' такой, что cx' >cx.

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

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

В таблице 1, в первом столбце записвыаются базисные элементы текущего опорного плана. Во втором столбце записываются элементы правой части ограничений. С правой стороны второго столбца записываются элементы матрицы A. В нижней части таблицы записываются соответствующие элементы вектора Δ, а − значение целевой функции в данной точке.

Далее рассматривают элементы , . Если среди них нет отрицательных элементов, то данный план является оптимальным (Теорема 1).

Пусть . Тогда рассматривают . Если среди них нет положительных элементов, то задача неограничена сверху, т.е. неразрешима (теорема 2).

Пусть среди есть положительные элементы. Тогда вычисляют для всех тех i, для которых

Тогда из базиса выходит k-я переменная, а в базис входит p- я переменная, значение которой равно .

Далее делают исключение Гаусса для столбца p выбирая в качестве ведущего элемента . Т.е. обнуляются все элементы данного столбца, кроме . Для этого нужно сложить строку i со строкой k, умноженной на . Затем строку k делят на . В результате получают следующую симплекс таблицу:

Здесь

,

,

,

.

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

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

Метод искусственного базиса

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

Пусть требуется найти максимум функции

(21)

при условиях

(22)

(23)

где и среди векторов

нет mединичных и линейно независимых.

Определение 7. Задача, состоящая в определении максимального значения функции

(24)

при условиях

где M − некоторое достаточно больное положительное число (конкретное значение обычно не задается), называется расширенной задачей по отношению к (21)−(23).

Расширенная задача (24)−(26) имеет опорный план

,

(27)

где первы n элементы нули. Переменные называются искусственными. Векторы столбцы

(28)

образуют так называемый искусственный базис m-мерного векторного пространства.

Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом.

Теорема 4. Если в оптимальном плане расширенной задачи (24)−(26) значения искусственных переменных , то является оптимальным планом задачи (21)−(23).

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

Значение целевой функции при опорном плане (27):

(29)

Значения вычисляются из выражения (14''):

(30)

Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M, а другая − нет.

После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m+1)-ю строку помещают коэффициенты, не содержащие M, а в (m+2)-ю строку − коэффициенты при M.

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

Итерационный процесс ведут по m+2 строке до тех пор, пока элементы m+2 строки, соответствующие переменным не станут неотрицательными. При этом, если искусственные переменные исключены из базиса, то найденный план расширенной задачи отвечает некоторому опорному плану исходной задачи.

Если же не все искусственные переменные исключены из базиса и элемент m+2 строки, столбца x₀ отрицателен, то исходная задача не имеет решения.

Если же не все искусственные переменные исключены из базиса и элемент m+2 строки, столбца x₀ равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.

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

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

Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:

• Составляют расширенную задачу (24)−(26).
• Находят опорный план расширенной задачи.
• Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
• Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.

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