Постановка задачи линейного программирования и двойственная задача
линейного программирования.
Линейное программирование является составной частью раздела математики,
который изучает методы нахождения условного экстремума функции многих
переменных и называется математическим программированием. В классическом
математическом анализе рассматривается задача отыскания условного
экстремума функции. Тем не менее, время показало, что для многих задач,
возникающих под влиянием запросов практики, классические методы
недостаточны. В связи с развитием техники, ростом промышленного
производства и с появлением ЭВМ все большую роль начали играть задачи
отыскания оптимальных решений в различных сферах человеческой
деятельности. Основным инструментом при решении этих задач стало
математическое моделирование — формальное описание изучаемого явления и
исследование с помощью математического аппарата.
Искусство математического моделирования состоит в том, чтобы учесть как
можно больше факторов по возможности простыми средствами. Именно в силу
этого процесс моделирования часто носит итеративный характер. На первой
стадии строится относительно простая модель и проводится ее
исследование, позволяющее понять, какие из существенных свойств
изучаемого объекта не улавливаются данной формальной схемой. Затем
происходит уточнение, усложнение модели.
В большинстве случаев первой степенью приближения к реальности является
модель, в которой все зависимости между переменными, характеризующими
состояние объекта, предполагаются линейными. Здесь имеется полная
аналогия с тем, как весьма важна и зачастую исчерпывающая информация о
поведении произвольной функции получается на основе изучения ее
производной — происходит замена этой функции в окрестности каждой точки
линейной зависимостью. Значительное количество экономических,
технических и других процессов достаточно хорошо и полно описывается
линейными моделями.
Основные формы задачи ЛП.
Различают три основные формы задач линейного программирование в
зависимости от наличия ограничений разного типа.
Стандартная задача ЛП.
или, в матричной записи,
— вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных
моделей, сводящихся наиболее естественным образом к этому классу задач
ЛП.
Каноническая задача ЛП.
или, в матричной записи,
Основные вычислительные схемы решения задач ЛП разработаны именно для
канонической задачи.
Общая задача ЛП.
В этой задачи часть ограничений носит характер неравенств, а часть
является уравнениями. Кроме того, не на все переменные наложено условие
неотрицательности:
.
Все три перечисленные задачи эквивалентны в том смысле, что каждую из
них можно простыми преобразованиями привести к любой из двух остальных.
целевой функции называется значением задачи.
Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
вида
(3)
или, в матричной записи,
(4)
.
накладывается условие неотрицательности. Задача (1), в отличии от
двойственной задачи (3) называется прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4)
допустимы, то они обе имеют решение и одинаковое значение.
то
PAGE
PAGE 3
Нашли опечатку? Выделите и нажмите CTRL+Enter
