Линейное программирование. Задача линейного программирования (ЗЛП)

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

5.1. Задача линейного программирования (ЗЛП)

Линейная функция z = c₁x₁ + c₂x₂ + … + c_nx_n в зависимости от значений переменных x₁, x₂, … , x_n может принимать сколь угодно большие или малые значения. Поэтому нельзя ставить задачу поиска экстремума линейной целевой функции без наложения каких-либо ограничений на область изменения переменных. Если же существуют такие ограничения, то в замкнутой этими ограничениями области экстремумы функции z существуют.

Если целевая функция z и ограничения на область изменения переменных x₁, x₂, … , x_n представлены линейными выражениями, то задача отыскания оптимума целевой функции называется задачей линейного программирования (ЗЛП).

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

Пусть имеется m видов сырья в следующих количествах: b₁, b₂,…, b_m .

Из этого сырья можно изготовить n видов продуктов.

Количество i-го вида сырья (i = 1, 2, … , m), необходимого для получения единицы j-го продукта (j = 1, 2, … , n) обозначим а_ij.

Количество j- го продукта обозначим х_j.

Цена единицы каждого из продуктов соответственно равна с₁, с₂,…, с_n.

Цена j-го продукта равна с_j х_j.

Суммарная цена всей продукции равна . Нужен ее максимум.

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

- целевая функция

;

- условия-ограничения:

1.                    j = 1, 2, … , n;     (5.1)

2.           i = 1, 2, … , m.     (5.2)

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

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

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

                     (5.5)

Каждое из ограничений (5.4) и (5.5) задает полуплоскость возможных значений x₁ и x₂. Неравенства x₁ ³ 0 и x₂ ³ 0 ограничивают значения x₁ и x₂ первой четвертью. Неравенства a_i1x₁ + a_i2x₂ £ b_i тоже делят плоскость на две части. Покажем это.

Рассмотрим прямую a_i1x₁ + a_i2x₂ = b_i. Возьмем на ней какую либо точку. В этой точке равенство соблюдается. Если увеличим x₁, то левая сторона равенства будет больше b_i, что недопустимо. То есть, если левая сторона равенства больше b_i, то мы оказываемся в области недопустимых значений x₁. Если уменьшим x₁, то левая сторона равенства будет меньше b_i , что допустимо. То есть мы попадаем в область допустимых значений x₁.

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

Например, область допустимых решений может быть ограничена многоугольником А₁, А₂ … А₅ (см. рис.).

Рассмотрим целевую функцию

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

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

Направление возрастания целевой функции характеризуется производными:  и . Здесь с₁ и с₂ – скорости возрастания целевой функции Z по направлениям осей х₁ и х₂.

Вектор С = (с₁; с₂) называется градиентом целевой функции. Градиент указывает направление наискорейшего возрастания целевой функции z. Градиент перпендикулярен к линиям уровня.

Вектор, равный градиенту, но направленный в противоположную сторону указывает  направление наискорейшего убывания целевой функции z.

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

Возможные варианты иллюстрируются приведенными ниже рисунками, где обозначено Q - область допустимых решений,  х* = (х₁, х₂) оптимальный план, параллельные линии, сплошные и штриховые, - линии уровня целевой функции. В варианте а - оптимальный план единственный (в точке х*); в варианте б - оптимальных планов бесконечно много (точки х*₍₁₎, х*₍₂₎, х*₍₃₎, …); в вариантах в и г - решения не существует, область допустимых решений не ограничена; в варианте д - область допустимых решений состоит из единственной точки, других решений не существует; в варианте е - система ограничений несовместна, область допустимых решений не существует, задача не имеет решения.