Тема 2.6. Основные теоремы линейного программирования

Определение. Линейная комбинация

точек называется выпуклой, если

> 0, > 0,…, > 0 и + + …+= 1.

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

Теорема 1. Множество всех планов задачи ЛП является выпуклым множеством.

Доказательство. Пусть – произвольные планы задачи ЛП. Это значит, что выполняются равенства:

…,

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

.

Таким образом, является планом задачи ЛП. Теорема доказана.

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

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

Теорема 2. Если оптимальный план задачи ЛП существует, то, по крайней мере, одна из вершин является оптимальным планом.

Доказательство. Обозначим через оптимальный план. Будем считать, что – не вершина. Для конкретности рассуждений будем считать, что – наибольшее значение целевой функции. Представим в виде выпуклой линейной комбинации вершин , т.е.

,

где

> 0, > 0,…, > 0 и + + …+= 1.

Тогда:

М = )

=

= .

Пусть - наибольшее из чисел

.

Тогда:

=

(+ + …+)=.

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

Теорема 3. Каждое невырожденное базисное решение системы ограничений задачи ЛП является вершиной.

Доказательство. Пусть – невырожденное базисное решение системы ограничений (уравнений): , где

, , .

Эту систему уравнений можно записать в виде:

,

где: – -й столбец матрицы (.

Так как

,

то

, (1)

при этом векторы линейно независимые, коэффициенты положительные.

Допустим, что Х не является вершиной. Тогда – выпуклая линейная комбинация k вершин (> 1). Очевидно, что все координаты этих вершин, начиная с (-й, равны нулю, ибо в противном случае, учитывая, что все > 0 и что каждая координата точки Х является линейной комбинацией соответствующих координат этих вершин, точка X имела бы положительных координат больше m. Так как точка

удовлетворяет системе ограничений, то справедливо равенство:

. (2)

Вычтем из равенства (1) равенство (2). Получим равенство:

.

Но так как векторы линейно независимые, то

Таким образом, Х совпадает с вершиной Х. Теорема доказана.

Теорема 4. Каждая вершина области ограничений задачи ЛП является базисным решением ее системы ограничений.

Доказательство этой теоремы опускаем.

Тема 2.7. Метод последовательного улучшения плана (симплекс-метод)

Задача. Найти наибольшее значение функции f = 3 x + 5 x , если переменные величины x , x неотрицательные и удовлетворяют системе неравенств:

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

Балансовые переменные х , x примем в качестве базисных, а переменные x , х - в качестве свободных переменных. Выразим базисные переменные через свободные переменные:

Целевую функцию f запишем в виде: f = 0 - (- З х - 5 х ). Приравняв свободные переменные к нулю, получим первое базисное решение (0;0;12;14). Ему соответствует значение

f = . Увеличение значения целевой функции

f = 0- (-3- 5) можно получить путем увеличения либо , либо . Целесообразнее оставить равным нулю, а увеличить ибо модуль коэффициента при больше модуля коэффициента при . Увеличить можно до тех пор, пока переменные остаются неотрицательными, т.е.:

Положим, что:

.

Тогда = 3, = 8. Получим второе базисное решение (0;3;0;8). Теперь , -базисные переменные, , - свободные переменные. Второму базисному решению соответствует значение целевой функции

f = 30 = 15.

Выразим базисные переменные х₂, x и целевую функцию через свободные переменные х , х₃.

4 x = 12 - 3 x - х_3, x = 3-

x = 14-7 x ₁ - 2

f = 3 x + 5 x = 3 x +5

Итак, имеем:

f = 15 -

Видим, что увеличение x или х ₃ с нулевого значения повлечет только уменьшение достигнутого ранее значения целевой функции. Таким образом, f _max = 15 и (0;3) – оптимальный план (значение балансовых переменных опускаем).

Теперь сформулируем алгоритм симплекс- метода.

I шаг. Приводим систему ограничений к виду:

x= - (ax_m+1 +a _m+2x_m+2 +...+ a _nx_n),

х₂ = - (а₂ + x + а₂ x _m+2 +...+а_{2 n} х _n),

….........................................................................

х_m = - (a x +a x + +a x ),

где x , x₂,..., x _m - базисные переменные, x , ,x - свободные переменные, , ,..., .

II шаг. Полагая свободные переменные равными нулю, получаем первое базисное решение

( , ,..., ,0,...,0). Находим также первое значение целевой функции, т.е. значение

f ( , ,..., ,0,...,0) = f .

III шаг. Выражаем целевую функцию f через свободные переменные:

f = f - ( _m+1 x_m+1 + _m+2 x_m+2+...+ +...+ _nx_n).

Если среди коэффициентов _m+1,...,,...,_n нет отрицательных,

то f= f_max и ( , ,..., ,0,...,0) – оптимальный план, и задача решена.

Допустим, что среди чисел _m+1,…,…,_n имеются отрицательные, например, . Если при этом среди коэффициентов ,,..., нет положительных, то х можно увеличивать неограниченно (переменные x , x₂,..., х _m не станут от этого отрицательными) и, следовательно, f_max = +

Пусть < 0, но среди коэффициентов а, a,...,a есть положительные. Без потери общности будем считать, что

a>0, a>0,..., a>0.

Если

min

то переменную х выводим из состава базисных переменных, полагая x = 0, а переменную вводим в состав базисных переменных, полагая =. Таким образом, приходим к новым базисным переменным и новым свободным переменным. Разрешаем систему ограничений относительно новых базисных переменных и переходим снова к шагу II.

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

Дата добавления: 2014-10-31