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

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

методы недостаточны. Всвязи с развитием техники, ростом промышленного производства и с появлением ЭВМвсе большую роль начали играть задачи отыскания оптимальных решений в различныхсферах человеческой деятельности. Основным инструментом при решении этих задачстало математическое моделирование формальное описание изучаемого явления иисследование с помощью математического аппарата.Искусство математическогомоделирования состоит в том, чтобы учесть как можно больше факторов повозможности

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

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

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

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

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

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

ЛП 1 или, в матричной записи, 2 Задачей, двойственной к 1 двойственной задачей ,называется задача ЛП от переменных вида 3 или, в матричной записи, 4 где .Правила построения задачи 3 по форме записи задачи 1 таковы в задаче 3 переменных столько же, сколькострок в матрице задачи 1 . Матрицаограничений в 3 транспортированная матрица . Вектор правой части ограничений в 3 служит векторомкоэффициентов максимизируемой линейной форме в 1

, при этом знаки неравенствменяются на равенство. Наоборот, в качестве целевой функции в 3 выступаетлинейная форма, коэффициентами которой задаются вектором правой частиограничений задачи 1 , при этом максимизация меняется на минимизацию. Надвойственные переменные накладывается условиенеотрицательности. Задача 1 , в отличии от двойственной задачи 3 называетсяпрямой.Теорема двойственности. Если взаимодвойственныезадачи 2 ,

4 допустимы, то они обе имеют решение и одинаковое значение.Теорема равновесия. Пусть оптимальные планы прямой 1 и двойственной 3 задачсоответственно. Тогда если то