НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Постановка задачи линейного программирования и двойственная задача линейного программирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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]