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