Название: Постановка задачи линейного программирования и двойственная задача линейного программирования.
Вид работы: реферат
Рубрика: Математика
Размер файла: 34.34 Kb
Скачать файл: referat.me-216993.docx
Краткое описание работы: Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции.
Постановка задачи линейного программирования и двойственная задача линейного программирования.
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание изучаемого явления и исследование с помощью математического аппарата.
Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.
В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.
Основные формы задачи ЛП.
Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.
Стандартная задача ЛП.
или, в матричной записи,
где — матрица коэффициентов. Вектор
называется вектором коэффициентов линейной формы,
— вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
Каноническая задача ЛП.
или, в матричной записи,
Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
Общая задача ЛП.
В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:
Здесь
. Ясно, что стандартная задача получается как частный случай общей при
; каноническая — при
.
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении задач ЛП сложилась определенная терминалогия. Линейная форма , подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор
, удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор
, доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором
, т.е.
, называется решением задачи, или оптимальным планом. Максимальное значение
целевой функции называется значением задачи.
Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных
вида
(3)
или, в матричной записи,
(4)
где .
Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице
задачи (1). Матрица ограничений в (3) — транспортированная матрица
. Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные
накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
Теорема двойственности . Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение .
Теорема равновесия
. Пусть — оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда если
то
Похожие работы
-
Риск в задачах линейного программирования
Лабораторная работа №3 Риск в задачах линейного программирования. Задание Предприятие выпускает 2 вида продукции в объмах Н1 и Н2. Известен случайный вектор ограничений -
-
Вычисление наибольшего, наименьшего значения функции в ограниченной области
Правило нахождения точек абсолютного или глобального экстремума дифференцируемой в ограниченной области функции. Составление и решение системы уравнений, определение всех критических точек функции, сравнение наибольшего и наименьшего ее значения.
-
Решение военно-логистических задач по выбору оптимального маршрута для военно-транспортных средств
Обоснование выбора оптимального маршрута по критерию минимума времени на его прохождение. Словесная постановка маршрутной задачи. Математическая постановка задачи. Оптимизация маршрута с города Рязановский до города Королева. Оценка его вариантов выбора.
-
Экстремумы функций многих переменных
Понятие экстремума. Необходимые и достаточные условия экстремума.
-
Экзаменационные билеты по методам оптимизации за весенний семестр 2001 года
примерный перечень экзаменационных вопросов методы оптимизации Сформулируйте понятие «оптимизации». Приведите примеры сфер деятельности, где можно использовать методы оптимизации.
-
Задача линейного программирования
Юридический техникум Рассмотрено и одобрено ПЦК г. Кропоткин программирования Председатель ПЦК Покалицына О.В. План чтения лекции по учебной дисциплине
-
Задачи по Математике 3
Задача 1 Решить графическим методом задачу линейного программирования А) найти область допустимых значений многоугольник решений Б) найти оптимумы целевой функции
-
Линейное программирование 3
БАЛТИЙСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ РЫБОПРОМЫСЛОВОГО ФЛОТА РФ ИНСТИТУТ ПРИКЛАДНОЙ ЭКОНОМИКИ И МЕНЕДЖМЕНТА КАФЕДРА «МЕНЕДЖМЕНТ» Контрольная работа
-
Математические методы методы
Общая задача линейного программирования Общей задачей линейного программирования называется задача, которая состоит в определении максимального или минимального значения функции
-
Линейное и нелинейное программирование
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ Севастопольский национальный технический университет Кафедра кибернетики и вычислительной техники Пояснительная записка