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

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

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

Основной задачей линейного программирования (ОЗЛП) называется задача, которая состоит в определении максимального (минимального) значения функции

(1)

При условиях

(2)

(3)

где - некоторые заданные постоянные величины. Функция (1) называется целевой функцией задачи (1) – (3), а условия (2) – (3) ее ограничениями, где (3) – условия неотрицательности переменных.

Совокупность чисел (x1,x2,...xn ), удовлетворяющая ограничениям задачи (2) – (3), называется допустимым решением (или планом).

План , при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.

Случай, когда F надо обратить не в максимум, а в минимум, легко сводится к простому: изменить знак F на обратный (максимизировать не F, а F`=-F). Оптимальные решения полученных таким образом задач на максимум и минимум совпадают, а значения целевых функций отличаются только знаком. Кроме того, от любых условий – неравенств можно перейти к условиям – равенствам ценой введения некоторых новых «дополнительных» переменных.

Всегда ли эта задача имеет решение? Нет, не всегда.

1. Может оказаться, что уравнения (2) вообще несовместимы (противоречат друг другу).

2. Может оказаться и так, что они совместимы, но не в области неотрицательных решений, т.е. не существует ни одной совокупности чисел x₁0, x₂0, …, x_n0, удовлетворяющей условиям (2).

3. Наконец, может быть и так, что допустимые решения ОЗЛП существуют, но среди них нет оптимального: функция F в области допустимых решений не ограничена сверху.

Характерные черты задач ЛП:

1. Допустимая область всегда является выпуклым многогранником даже в случае, когда она не ограничена.

2. Оптимальное решение всегда достигается в вершинах допустимой области.

3. Если оптимальное решение не одно, то значение функции совпадает во всех точках-решениях.

Графический метод решения задач ЛП

Графический метод основан на геометрической интерпретации задачи ЛП и применяется в основном при решении задач в двухмерном пространстве.

Рассмотрим задачу ЛП: f (X) = c₁x₁+ c₂x₂ min при ограничениях

Каждое неравенство a_ijx₁+ a_ijx₂ b_i определяет в плоскости x₁Оx₂ полуплоскость с граничной прямой a_ijx₁+ a_ijx₂= b_i. Точки, лежащие в полуплоскости, удовлетворяют данному неравенству.

Неравенства x₁0 и x₂0 определяют первый квадрант в системе координат.

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

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

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

Рис.6.1. Многоугольник решений в задаче ЛП

Таким образом, при графическом способе решения задачи ЛП необходимо:

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

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

5. Провести линию уровня функции, перпендикулярную градиенту.

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

Теорема:

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

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

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

Симплекс-метод Данцига

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

Стратегия метода Данцига решения задачи (6.1) - (6.3) основана на особенностях постановки этой задачи. Множество допустимых решений задачи, определяемое ограничениями (6.2) и (6.3), есть выпуклое множество, которое геометрически представляет собой выпуклый политоп, имеющий конечное число крайних точек (вершин).

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

Из курса линейной алгебры известно, что классический метод Гаусса-Жордана решения системы линейных уравнений (6.2) состоит в приведении их к виду:

Переменные x₁,x₂,…,x_m, входящие только в одно из уравнений системы (6.4) с коэффициентами «1», а во все остальные уравнения с коэффициентами, равными нулю, называются базисными, а остальные (n-m) переменных называются небазисными (свободными).

Базисным решением системы (6.4) называется решение

Базисное решение называется допустимым, если x_i ≥ 0, i=1,…,m. Базисное решение называется невырожденным, если x_i> 0, i=1,…,m.

Множество крайних точек политопа X, определяемого ограничениями задачи ЛП, соответствует множеству допустимых базисных решений системы (6.2). При этом одному базисному решению соответствует одна крайняя точка.

Теорема. Если функция f(X) в задаче (6.1) - (6.3) достигает максимума (минимума) на политопе X, определяемом ограничениями (6.2) - (6.3), то она достигает его, по крайней мере, в одной крайней точке этого политопа. Если она достигает его в нескольких крайних точках, то она достигает его на любой выпуклой комбинации этих крайних точек.

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

Однако с ростом числа переменных число вершин резко возрастает. Кроме того, требует­ся в системе ограничений выделять линейно-независимые уравнения.

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

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

Направленность перебора предполагает следующую организацию вычислительного процесса:

1. Нахождение начального базисного решения.

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

На каждой итерации устанавливается один из фактов:

1. базисное решение оптимально,

9. линейная функция f(X) не ограничена сверху (снизу),

10. возможно увеличение (уменьшение) f(X), т.е. переход к новому ба­зису.

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