Среди чисел есть обязательно наибольшее. Пусть это будет . Тогда

=

= .

Среди чисел есть обязательно наибольшее. Пусть это будет . Тогда

= ( + + …+ )

= .

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

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

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

, , .

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

,

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

Так как

,

то

, (1)

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

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

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

. (2)

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

.

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

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

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

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

§6. Метод последовательного улучшения плана

(симплекс-метод)

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

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

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

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

Целесообразнее оставить x равным нулю, а увеличить х ₂, ибо модуль коэффициента при х ₂ больше модуля коэффициента при x . Увеличить х ₂ можно до тех пор, пока переменные остаются неотрицательными, т.е.:

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

.

Тогда х = 0, х = 8.

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

f = 3 0 + 5 3=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 = - (a _m+ x_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+1x_m+1 + _m+2x_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

Дата добавления: 2015-08-27