.

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

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 289
Скачать документ

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

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

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

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

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

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

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

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

— вектором ограничений.

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

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

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

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

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

В этой задачи часть ограничений носит характер неравенств, а часть
является уравнениями. Кроме того, не на все переменные наложено условие
неотрицательности:

.

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

целевой функции называется значением задачи.

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

Рассмотрим задачу ЛП

(1)

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

(2)

вида

(3)

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

(4)

.

накладывается условие неотрицательности. Задача (1), в отличии от
двойственной задачи (3) называется прямой.

Теорема двойственности. Если взаимодвойственные задачи (2), (4)
допустимы, то они обе имеют решение и одинаковое значение.

то

PAGE

PAGE 3

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат
UkrReferat.com. Всі права захищені. 2000-2019