Допустимые и оптимальные векторы.

Задача линейного программирования называется допустимой, если существует вектор, удовлетворяющий линейным ограничениям задачи. Если такой вектор существует, то он называется допустимым вектором задачи.

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

Значение этого минимума или максимума называется значением задачи линейною программирования.

Обозначим через левые части неравенств системы (II), т. е. положим

ПРЕДЛОЖЕНИЕ 2.1. Если вектор i удовлетворяет

неравенствам

Доказательство. Ввиду (3)

Отсюда в силу (1)

СЛЕДСТВИЕ 2.2. Если у — допустимый вектор стандартной задачи на минимум и Z — допустимый вектор двойственной задачи, то

ПРЕДЛОЖЕНИЕ 2.3. Если вектор удовлетворяет

системе уравнений

Доказательство этого предложения аналогично доказательству предложения (2.1).

СЛЕДСТВИЕ 2.4. Если у — допустимый вектор канонической задачи на минимум и — допустимый вектор двойственной задачи, то

ПРЕДЛОЖЕНИЕ 2.5. Если у — допустимый вектор задачи на минимум (С или К) и Z — допуститый вектор двойственной задачи (С или ), то .

Предложение 2.5 непосредственно следует из следствий 2.2 и 2.4.

ПРЕДЛОЖЕНИЕ 2.6 (КРИТЕРИЙ ОПТИМАЛЬНОСТИ BEKTОPOB). Если у — допустимый вектор задачи на минимум, Z — допустимый вектор двойственной задачи и то у и z являются оптимальными векторами соответствующих задач.

Доказательство. Пусть у — любой допустимый вектор задачи на минимум. Согласно предложению 2.5,

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

Аналогично доказывается, что z является оптимальным вектором задачи на максимум.