Математика

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


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

      Основные формы задачи ЛП.
      Различают  три  основные  формы  задач  линейного  программирование  в
зависимости от наличия ограничений разного типа.
      Стандартная задача ЛП.
                                    [pic]
или, в матричной записи,
                                    [pic]
где  [pic]—   матрица   коэффициентов.   Вектор   [pic]называется   вектором
коэффициентов линейной формы, [pic]— вектором ограничений.
      Стандартная задача  важна  ввиду  наличия  большого  числа  прикладных
моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
      Каноническая задача ЛП.
                                    [pic]
или, в матричной записи,
                                    [pic]
      Основные вычислительные схемы решения задач ЛП разработаны именно  для
канонической задачи.
      Общая задача ЛП.
      В этой задачи часть ограничений носит  характер  неравенств,  а  часть
является уравнениями. Кроме того, не  на  все  переменные  наложено  условие
неотрицательности:
                                    [pic]
      Здесь [pic]. Ясно,  что  стандартная  задача  получается  как  частный
случай общей при [pic]; каноническая — при [pic].
      Все три перечисленные задачи эквивалентны в том смысле, что каждую  из
них можно простыми преобразованиями привести к любой из двух остальных.
      При изучении задач ЛП сложилась  определенная  терминалогия.  Линейная
форма [pic], подлежащая максимизации (или минимизации) , называется  целевой
функцией.  Вектор  [pic],  удовлетворяющий  всем  ограничениям  задачи   ЛП,
называется  допустимым  вектором,  или  планом.  Задача  ЛП,   для   которой
существуют допустимые векторы,  называется  допустимой  задачей.  Допустимый
вектор [pic], доставляющий наибольшее значение целевой функции по  сравнению
с любым другим допустимым вектором [pic], т.е.  [pic],  называется  решением
задачи, или оптимальным планом. Максимальное значение  [pic]целевой  функции
называется значением задачи.

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



смотреть на рефераты похожие на "Постановка задачи линейного программирования и двойственная задача линейного программирования. "