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

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

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

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

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

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

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

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

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

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

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


Скачиваний: 1
Просмотров: 0
Скачать реферат Заказать реферат