Принцип двойственности

 

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

 

Для того чтобы показать, как принцип двойственности может упростить процесс решения приведем следующий пример:

 

 

max(f)-?                                                  min(φ)-?                                  

 

 

Из данного примера легко просматривается взаимосвязь между исходной и двойственной задачами.

 

Введя в рассмотрение следующие элементы:

 

 

 

Эту связь можно обозначить следующим образом:

 

 

max(f)-?                                                  min(φ)-?           

 

В двойственной задаче всего 2 переменных. Её можно легко решить графическим методом и, используя вторую теорему двойственности, найти решение исходной.

 

Пропустим процесс решения двойственной ЗЛП, записав только результаты:

 

Y1=2 Y2=4     min(φ)=150

 

Т.к max(f)=min(φ), решение исходной задачи уже известно. Остаётся только найти значения X1, X2, X3, при которых это значение достигается. Здесь мы применим вторую теорему двойственности, которая устанавливает следующее соответствие:

 

 

В нашем примере получается следующая вполне тривиальная система линейных уравнений:

 

 

Решение данной системы легко находится методом Гаусса и окончательный ответ таков:

 

Функция f достигает максимума при X₁=0, X_2­=5, X₃=10 и max(f)=150

Список использованной литературы

 

1. Учебник: «Математика в экономике»; А.С. Солодовников, В.А. Бабайцев, А.В. Браилов: Финансы и статистика 1999г.

2. Сборник задач по курсу математики; под редакцией А.С. Солодовникова и А.В. Браилова; ФА 2001г.

3. «Линейные неравенства»; С.Н. Черников; Наука 1968

4. «Краткий очерк развития математики»; Д.Я. Стройк; Наука 1984.

[1] Вектор нормали имеет координаты (С1;С2), где C1 и C2 коэффициенты при неизвестных в целевой функции f=C1◦X1+C2◦X2+C0.

[2]при нахождении минимума выбираем положительные коэффициенты

[3] Если положительных элементов не оказалось то данная ЗЛП не имеет решения, т.е max(f)=+∞ (при задаче на нахождение максимума) или min(f)=- ∞ (нахождение минимума)

[4] Если есть несколько одинаковых отношений можно выбрать любую строку