Признак оптимальности в развернутой форме

Для оптимальности допустимого вектора х=(х₁,х₂…,х_n,) в задаче 1 достаточно существование m-мерного вектора у=(у₁,…,у_m), удовлетворяющего условиям:

а) у_i і 0, i I₂

б) еa_ijy_i + c_j = 0, j J_1,

i I

в) еa_ijy_i + c_j, £ 0, j J_2,

i I

г) еa_ijy_i + c_j, = 0, если х_j >0 для j J_2,

i I

д) у_i = 0, если еa_ijx_j + b_i >0, i I₂ ,

^{j J}

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

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

И ее следствия

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

Теорема двойственности. Каковы бы ни были исходные данные, для задач 1 и 1* имеет место один из следующих взаимоисключающих случаев.

1. В задачах 1 и 1* имеются оптимальные векторы х и у и , т.е. обе задачи разрешимы.

2. В задаче 1 существуют допустимые векторы, но линейная функция на множестве этих векторов не ограничена сверху, тогда в задаче 1* нет допустимых векторов.

3. В задаче 1* существуют допустимые векторы, но функция не ограничена снизу на множестве этих векторов, тогда в задаче 1 нет допустимых векторов.

4. В задачах 1 и 1* нет допустимых векторов.

Критерий разрешимости задачи ЛП

Теорема существования

Для того чтобы в двойственных задачах 1 и 1* существовали оптимальные векторы х и у, т.е. имел место случай 1 теоремы двойственности, достаточно выполнения одного из следующих условий:

1. в задаче 1 существует оптимальный вектор х

2. в задаче 1* существует оптимальный вектор у

3. в задаче 1 существует допустимый вектор х и функция ограничена сверху

4. в задаче 1* существует допустимый вектор у и функция ограничена снизу

5. в задачах 1 и 1* существуют допустимые векторы х и у

Необходимый признак оптимальности

Допустимый признак оптимальности в краткой и развернутой форме является также и необходимым признаком.

Доказательство: Пусть имеется оптимальный вектор х в задаче 1 и оптимальный вектор у в задаче 1*. Тогда на основании условий 2 теоремы о существовании имеет место случай 1 теоремы двойственности, то есть .

Прямые задачи линейного программирования в канонической форме