Постановка задачи линейного программирования и двойственная задача линейного программирования.
Другие рефераты
Постановка задачи линейного программирования и двойственная задача
линейного программирования.
Линейное программирование является составной частью раздела
математики, который изучает методы нахождения условного экстремума функции
многих переменных и называется математическим программированием. В
классическом математическом анализе рассматривается задача отыскания
условного экстремума функции. Тем не менее, время показало, что для многих
задач, возникающих под влиянием запросов практики, классические методы
недостаточны. В связи с развитием техники, ростом промышленного
производства и с появлением ЭВМ все большую роль начали играть задачи
отыскания оптимальных решений в различных сферах человеческой деятельности.
Основным инструментом при решении этих задач стало математическое
моделирование — формальное описание изучаемого явления и исследование с
помощью математического аппарата.
Искусство математического моделирования состоит в том, чтобы учесть
как можно больше факторов по возможности простыми средствами. Именно в силу
этого процесс моделирования часто носит итеративный характер. На первой
стадии строится относительно простая модель и проводится ее исследование,
позволяющее понять, какие из существенных свойств изучаемого объекта не
улавливаются данной формальной схемой. Затем происходит уточнение,
усложнение модели.
В большинстве случаев первой степенью приближения к реальности
является модель, в которой все зависимости между переменными,
характеризующими состояние объекта, предполагаются линейными. Здесь имеется
полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация
о поведении произвольной функции получается на основе изучения ее
производной — происходит замена этой функции в окрестности каждой точки
линейной зависимостью. Значительное количество экономических, технических и
других процессов достаточно хорошо и полно описывается линейными моделями.
Основные формы задачи ЛП.
Различают три основные формы задач линейного программирование в
зависимости от наличия ограничений разного типа.
Стандартная задача ЛП.
[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] то
| |  скачать работу |
Другие рефераты
| 
