Постановка задачи линейного программирования и двойственная задача линейного программирования.
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание изучаемого явления и исследование с помощью математического аппарата.
Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.
В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.
Основные формы задачи ЛП.
Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.
Стандартная задача ЛП.

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

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

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

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

Здесь
.
Ясно, что стандартная
задача получается
как частный
случай общей
при
;
каноническая
— при
.
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении
задач ЛП сложилась
определенная
терминалогия.
Линейная форма
,
подлежащая
максимизации
(или минимизации)
, называется
целевой функцией.
Вектор
,
удовлетворяющий
всем ограничениям
задачи ЛП, называется
допустимым
вектором, или
планом. Задача
ЛП, для которой
существуют
допустимые
векторы, называется
допустимой
задачей. Допустимый
вектор
,
доставляющий
наибольшее
значение целевой
функции по
сравнению с
любым другим
допустимым
вектором
,
т.е.
,
называется
решением задачи,
или оптимальным
планом. Максимальное
значение
целевой
функции называется
значением
задачи.
Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей,
двойственной
к (1) (двойственной
задачей), называется
задача ЛП от
переменных
вида
(3)
или, в матричной записи,
(4)
где
.
Правила
построения
задачи (3) по форме
записи задачи
(1) таковы: в задаче
(3) переменных
столько же,
сколько строк
в матрице
задачи (1). Матрица
ограничений
в (3) — транспортированная
матрица
.
Вектор правой
части ограничений
в (3) служит вектором
коэффициентов
максимизируемой
линейной форме
в (1), при этом знаки
неравенств
меняются на
равенство.
Наоборот, в
качестве целевой
функции в (3)
выступает
линейная форма,
коэффициентами
которой задаются
вектором правой
части ограничений
задачи (1), при
этом максимизация
меняется на
минимизацию.
На двойственные
переменные
накладывается
условие неотрицательности.
Задача (1), в отличии
от двойственной
задачи (3) называется
прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.
Теорема
равновесия.
Пусть
—
оптимальные
планы прямой
(1) и двойственной
(3) задач соответственно.
Тогда если
то
