Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функц - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Линейное программирование: постановка задач и графическое решение... 1 307.48kb.
Линейное программирование 1 1201.82kb.
Количественные и качественные исследования в менеджменте 7 1370.21kb.
Методические рекомендации по содержанию раздела «Охрана труда» в... 1 177.58kb.
Методы математического моделирования экологических систем 7 1598.52kb.
Лекция №14 Методы оптимизации параметров систем автоматизации 1 120.88kb.
Основные условия, позволяющие строить модели лп 1 196.43kb.
«Производственные функции комплексных переменных в экономическом... 1 17.66kb.
Функции нескольких переменных и их геометрический смысл 1 23.68kb.
Начальная школа является составной частью всей системы непрерывного... 1 56.98kb.
Образовательная программа муниципального бюджетного общеобразовательного... 5 2021.38kb.
3 «А» класс Русский язык – упр. 353 Математика рабочая тетрадь №33... 1 37.11kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Линейное программирование является составной частью раздела математики, который изучает - страница №1/1

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

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

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

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


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

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



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

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



где — матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, — вектором ограничений.

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

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

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



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



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

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



Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая — при .

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

При изучении задач ЛП сложилась определенная терминалогия. Линейная форма , подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор , удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи.


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

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



(1)

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



(2)

Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида



(3)

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



(4)

где .



Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.

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

Теорема равновесия. Пусть — оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда если то









izumzum.ru