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