Основные определения и теоремы

Определения

1. Функция F(X) (1) называется целевой функцией, или линейной формой задачи, а условия (2) – (4) – ограничениями данной задачи.

2. Стандартной (или симметричной) задачей ЛП является задача, которая состоит в определении максимального значения функции F(X) при выполнении условий (3), (4).

3. Канонической или основной задачей ЛП называется задача, которая состоит в определении максимального значения функции F при выполнении условий (2), (4).

4. Совокупность чисел Х(х₁ х₂, …х_n), удовлетворяющая ограничениям задачи (1) – (4) называется допустимым решением, или планом.

5. План Х*(х*₁ х*₂, …х*_n), при котором целевая функция задачи принимает максимальное значение, называется оптимальным.

Свойства основной задачи ЛП тесно связаны со свойствами так называемых выпуклых множеств.

Рассмотрим (без доказательства) отражающие свойства основной задачи ЛП, теоремы, предварительно записав ряд определений.

Определение 1. Пусть х₁ х₂, …х_n – произвольные точки евклидова пространства. Выпуклой линейной комбинацией этих точек называется сумма

a₁х₁ + a₂ х₂ +... a_{n ×} х_n,

где a - произвольные неотрицательные числа, сумма которых равна 1.

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

Определение 3. Непустое множество планов основной задачи ЛП называется многогранником решений, а всякая угловая точка многогранника – вершиной.

Совокупность вершин многогранников решений называется опорным планом.