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

Основная задача линейного программирования выглядит следующим образом.

Дана система m линейных уравнений с n неизвестными:

(3.1.1)

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

(3.1.2)

и линейная функция от тех же переменных

(3.1.3)

называемая целевой функцией.

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

Любое неотрицательное решение системы уравнений (3.1.1) называют допустимым решением, а то допустимое решение, при котором целевая функция (3.1.3) принимает наименьшее значение, называют оптимальным 80 решением задачи линейного программирования (3.1.1)—(3.1.3). Кратко задачу формулируют так: найти вектор , минимизирующий целевую функцию (3.1.3) при линейных ограничениях (3.1.1) и (3.1.2).

Стандартная задача ЛП

или, в матричной записи,

где — матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, — вектором ограничений.

Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.

Каноническая задача ЛП

или, в матричной записи,

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

Общая задача ЛП. В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:

Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая — при .

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

При изучении задач ЛП сложилась определенная терминалогия. Линейная форма , подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор , удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи.

Двойственная задача линейного программирования. Рассмотрим задачу ЛП

(1)

или, в матричной записи,

(2)

Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида

(3)

или, в матричной записи,

(4)

где .

Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.

Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.

Теорема равновесия. Пусть — оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда если то