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

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

линейного программирования.

      Линейное   программирование   является   составной   частью    раздела

математики, который изучает методы нахождения условного экстремума  функции

многих  переменных  и   называется   математическим   программированием.   В

классическом  математическом  анализе   рассматривается   задача   отыскания

условного экстремума функции. Тем  не менее, время показало, что  для  многих

задач, возникающих  под  влиянием  запросов  практики,  классические  методы

недостаточны.  В   связи   с   развитием   техники,   ростом   промышленного

производства и с появлением  ЭВМ  все  большую  роль  начали  играть  задачи

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

Основным  инструментом  при  решении   этих   задач   стало   математическое

моделирование — формальное описание  изучаемого  явления  и  исследование  с

помощью математического аппарата.

      Искусство математического  моделирования состоит в  том,  чтобы  учесть

как можно больше факторов по возможности  простыми средствами. Именно в  силу

этого процесс моделирования часто  носит  итеративный  характер.  На  первой

стадии строится относительно простая  модель и  проводится  ее  исследование,

позволяющее понять, какие из  существенных  свойств  изучаемого  объекта  не

улавливаются  данной  формальной   схемой.   Затем   происходит   уточнение,

усложнение модели.

      В  большинстве   случаев  первой  степенью  приближения  к   реальности

является   модель,   в   которой   все   зависимости   между    переменными,

характеризующими состояние объекта, предполагаются линейными. Здесь  имеется

полная аналогия с тем, как весьма важна и зачастую исчерпывающая  информация

о  поведении  произвольной  функции  получается  на   основе   изучения   ее

производной — происходит замена этой  функции  в  окрестности  каждой  точки

линейной зависимостью. Значительное количество экономических, технических и

других процессов достаточно хорошо и полно описывается линейными  моделями.

 

      Основные формы  задачи ЛП.

      Различают  три   основные  формы  задач  линейного  программирование  в

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

      Стандартная задача  ЛП.

                                    [pic]

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

                                    [pic]

где  [pic]—   матрица   коэффициентов.   Вектор   [pic]называется   вектором

коэффициентов линейной формы, [pic]— вектором ограничений.

      Стандартная задача  важна  ввиду  наличия   большого  числа  прикладных

моделей, сводящихся наиболее естественным образом к этому классу задач  ЛП.

      Каноническая задача  ЛП.

                                    [pic]

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

                                    [pic]

      Основные вычислительные  схемы решения задач ЛП разработаны  именно  для

канонической задачи.

      Общая задача ЛП.

      В этой задачи  часть ограничений носит  характер  неравенств,  а  часть

является уравнениями. Кроме того, не  на  все  переменные  наложено  условие

неотрицательности:

                                    [pic]

      Здесь [pic]. Ясно,  что стандартная задача  получается  как частный

случай общей при [pic]; каноническая — при [pic].

      Все три перечисленные  задачи эквивалентны в том  смысле, что каждую  из

них можно простыми преобразованиями привести к любой из двух остальных.

      При изучении задач  ЛП сложилась  определенная  терминалогия.  Линейная

форма [pic], подлежащая максимизации (или минимизации) , называется  целевой

функцией.  Вектор  [pic],  удовлетворяющий всем  ограничениям  задачи   ЛП,

называется  допустимым  вектором,  или  планом.  Задача  ЛП,   для   которой

существуют допустимые векторы,  называется  допустимой  задачей.  Допустимый

вектор [pic], доставляющий наибольшее значение целевой функции по  сравнению

с любым другим допустимым вектором [pic], т.е.  [pic],  называется  решением

задачи, или оптимальным планом. Максимальное значение  [pic]целевой функции

называется значением задачи.