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

В общем виде модель записывается следующим образом:

· целевая функция:

= c1x1 + c2x2 +... + cnxn → max(min);

(2.1)

· ограничения:

a11x1 + a12x2 +... + a1nxn {≤ = ≥ } b1, a21x1 + a22x2 +... + a2nxn {≤ = ≥ } b2, ... am1x1 + am2x2 +... + amnxn {≤ = ≥ } bm;

(2.2)

· требование неотрицательности:

xj ≥ 0,

(2.3)

При этом a_ij, b_i, c_j ( ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3).

Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми.

Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

46. Теоремы об оптимальности плана ЗЛП. Симплексный метод.

Теорема: Если для некоторого вектора Ā _j в системе

Х₁ + а_{1 m +1} X_{m +1} + а_{1 m +2} X_{m +2} + … + а_{1 n} X_n = a₁

Х₂ + а_{2 m +1} X_{m +1} + а_{2 m +2} X_{m +2} + … + а_{2 n} X_n = a₂

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

X_m + а_{mn +1} X_{m +1} + а_{mn +2} X_{m +2} + … + а_mn X_n = a_m

Выполняется соотношение Z_j – c_j > 0, то план Х_Б0 не является оптимальным и можно перейти к плану Х_Б1 такому, что Z (Х_Б1) ≤ Z (Х_Б0).

Здесь Z_j = (С, Ā _j) – скалярное произведение векторов.

С – вектор, состоящий из коэффициентов при базисных переменных целевой функции Z

Ā _j – вектор, состоящий из коэффициентов разложения соответствующего вектора по векторам базиса.

c_j – коэффициент целевой функции Z при переменной Х_j

Следствие из теоремы: Если для всех векторов Ā ₁, Ā ₂, …, Ā _n некоторого опорного плана Х выполняется соотношение Z_j – c_j < 0, то опорный план Х является оптимальным. Величины (Z_j – c_j) – называются оценками оптимальности соответствующих векторов.

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

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

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

Симплексный метод:

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