15инф. Постановка задач исследования операций и их классификация. Основы линейного программирования: постановка задачи, метод решения. Двойственная задача линейного программирования.

Исследование операций — это наука, занимающаяся разработкой и практическим применением методов наиболее эффективного (или оптимального) управления организационными системами.

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

Решение, которое оказывается наиболее выгодным для всей организации, называется оптимальным, а решение, наиболее выгодное одному или нескольким подразделениям, будет субоптимальным. Линейное программирование--раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополни-тельных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на уни-версальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного про-граммирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений. Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с на-хождением экстремумов функции во внутренней точке области допустимых значений. Отсюда -- необходимость разработки новых методов. Симплекс метод задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план.

Двойственная задача.

Двойственность является важным понятием в линейном программировании, имеющим экономическое (практическое) применение. Например, для задачи оптимального распределения ресурсов для производства некоторых видов товаров пара прямой и двойственной задачи принимает следующий экономический смысл:
Прямая задача: Сколько и какой продукции xj необходимо производить, чтобы при заданных доходах Cj и объемах ресурсов bi максимизировать доход от продажи продукции?
Двойственная задача: Какова должна быть "теневая" цена каждого ресурса yi, чтобы при заданных количествах bi и доходах Cj минимизировать затраты?

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы)

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования. Решая одну из

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

Построим ей двойственную задачу по следующим правилам:

Количество переменных в двойственной задаче равно количеству неравенств в исходной.

Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

Столбец свободных членов исходной является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

Условиям неотрицательности переменных исходной задачи соответствуют неравенства ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Транспонированной называется матрица, у которой строки и столбцы меняются местами. Поэтому коэффициенты при переменных y_i в задаче II это, соответственно, коэффициенты i-ого неравенства в задаче I. Неравенства, находящиеся напротив друг друга, называются сопряженными .

Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности.

Теорема 1 (первая теорема двойственности)

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* - оптимальные решения задачи I и II

Теорема 2 (вторая теорема двойственности)

Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задачи I и II соответственно, хотя бы одно из любой пары сопряженных неравенств обращается в равенство.

Геометрический смысл решений неравенств, уравнений и их систем

Рассмотрим решения неравенств.

Утверждение 1. Множество решений неравенства с двумя перемен­ными   a11x1+a12x2<=b1       является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства  a11x1+a12x2>=b1.

Для определения искомой полуплоскости (верхней или ниж­ней) рекомендуется задать произвольную контрольную точку, не лежащую на ее границе – построенной прямой. Если неравенство выполняется в контрольной точке, то оно выполняется и во всех точках полуплоскости, содержащей контрольную точку, и не вы­полняется во всех точках другой полуплоскости. И наоборот, в случае невыполнения неравенства в контрольной точке, оно не выполняется во всех точках полуплоскости, содержащей кон­трольную точку, и выполняется во всех точках другой полуплос­кости. В качестве контрольной точки удобно взять начало координат О (0;0), не лежащее на построенной прямой.