Теория ЛП. 1 Теория ЛП. Теория линейного программирования (ЛП) Двойственные задачи линейного программирования со смешанными ограничениями

• Название: Теория линейного программирования (ЛП) Двойственные задачи линейного программирования со смешанными ограничениями
• Анкор: Теория ЛП
• Дата: 10.11.2020
• Размер: 56.05 Kb.
• Имя файла: 1 Теория ЛП.docx
• Тип: Задача; #149380

ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЛП)
Двойственные задачи линейного программирования со смешанными ограничениями
Для задач ЛП характерно то, что

• 
  Целевая функция  (показатель эффективности) линейно зависит от элементов решения х₁,х₂, …х_n
  
• 
  Ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно х₁,х₂, …х_n.
  

В качестве основной обычно рассматривается задача ЛП в следующей форме.

Пусть заданы два множества I={1,2…m} и J={1,2…n}, а также их разбиение на попарно непересекающиеся подмножества, т.е.

I= I₁U I₂, причем I₁  I₂ = 

J= J₁UJ₂, J₁J₂ = 

Заданы вещественные числа а_ij, iI, jJ

b_i , iI,

с_j , jJ.

ЗАДАЧА 1. Максимизировать линейную функцию

(1),

на множестве векторов Х=( х₁,х₂, …х_n) (2),

удовлетворяющих условиям:

х_{j }0 для jJ₂ (3),

2 (4).

Определение.

Вектор (2), удовлетворяющий условиям (3) и (4) называется допустимым для задачи 1. Допустимый вектор (2), доставляющий максимум функции (1) называется оптимальным.

Говорят, что задача 1 является задачей ЛП со смешанными ограниче-ниями. Наряду с этой задачей, которая именуется ПРЯМОЙ, рассматри-вается так называемая ДВОЙСТВЕННАЯ к ней задача - задача 1*.


ЗАДАЧА 1*. Минимизировать линейную функцию

(5)

на множестве векторов Y=(y₁,y₂,…..y_n) (6),

удовлетворяющих условиям:

1 y_{j } 0 для iI₂ (7),
2 (8)

Вектор (6), удовлетворяющий условиям (7) и (8) называется допустимым в задаче 1*. Допустимый вектор (6), доставляющий минимум функции (5), называется оптимальным в этой задаче.

Двойственная задача составляется по следующему ПРАВИЛУ:

В задаче 1 требуется максимизировать целевую функцию. В задаче 1* требуется минимизировать целевую функцию.
В задаче 1 имеется n-переменных и m- ограничений типа (4). В задаче 1* имеется m –переменных и n-ограничений типа (8). Это значит, что каждой переменной в задаче 1 соответствует ограничение в задаче 1* и каждому ограничению в задаче 1 соответствует переменная в задаче 1*.

1. 
   Коэффициенты с_j линейной функции (1) в задаче 1 являются свободными членами ограничений (8) задачи 1*, свободные члены bi ограничений (4) в задаче 1 являются коэффициентами линейной функции (5) задачи 1*.
   

1. 
   Коэффициенты при неизвестных а_ij в задачах 1 и 1* одни и те же, но матрицы из этих коэффициентов транспонированы по отношению друг к другу.
   

В задаче 1 все неравенства типа  , а в задаче 1* все неравенства типа .
Если на переменную задачи 1 налагается условие неотрицательности, то соответствующее ограничение в двойственной задаче является неравенством, а если условия неотрицательности на переменную нет, то соответствующее ограничение в задаче 1* является уравнением. И наоборот.
Определение задачи 1 как ПРЯМОЙ, а задачи 1* как ДВОЙСТВЕННОЙ, условно. Обе задачи взаимодвойственны.

Изучение двойственных задач оправдано тем, что в практике различных исследований иногда легче решать ДВОЙСТВЕННУЮ задачу, чем ПРЯМУЮ. Решив двойственную задачу, можно дать ответ – имеет ли оптимальное решение прямая задача.
Пример. Записать двойственную задачу к следующей задаче линейного программирования.
ЗАДАЧА 1. Найти удовлетворяющие условиям:



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

ЗАДАЧА 1*. Найти удовлетворяющие условиям:


Предварительный анализ двойственных задач
Некоторую связь между парой двойственных задач устанавливает следующая лемма.

ЛЕММА.

Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства

m(х)n(у) , (9)

причем это неравенство выполняется как равенство в том и только в том случае, если имеют место следующие соотношения:
(10) (11)


Доказательство:



(1) (8) (4) (5)

Следствие из леммы:
Признак оптимальности в краткой форме
Для оптимальности допустимого вектора х в задаче 1 необходимо и достаточно существования допустимого вектора у в задаче 1^* такого, что

m(х)= n(у) (12)

При этом допустимый вектор у является оптимальным в задаче 1*.

Теорема двойственности

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

1. 
   В задачах 1 и 1* имеются оптимальные векторы х и у и .
   
2. 
   В задаче 1 существуют допустимые векторы , но линейная функция на множестве этих векторов не ограничена сверху, т.е. , тогда в задаче 1* нет допустимых векторов.
   
3. 
   В задаче 1* существуют допустимые векторы , но функция не ограничена снизу на множестве этих векторов, т.е. , тогда в задаче 1 нет допустимых векторов.
   
4. 
   В задачах 1 и 1* нет допустимых векторов, то есть
   

Экономическая интерпретация двойственных задач
Пример. С внедрением новой технологии на некотором предприятии появилась возможность использовать три вида отходов производства, получаемых в количестве 70, 30, 15 единиц в сутки, для производства двух видов изделий, пользующихся большим спросом. Известно, что для производства одного изделия первого вида требуется 4, 3, 0 единиц отходов 1, 2, 3-го видов соответственно; для производства одного изделия второго вида требуется 3, 4, 3 единиц отходов 1, 2, 3-го видов. Ожидаемая прибыль от реализации продукции I и II-го видов 12 и 15 у.е. соответственно. Требуется составить план производства продукции I и II-го видов , обеспечивающий наибольшую прибыль, т.е. требуется решить следующую задачу линейного программирования.
Задача I. Найти , удовлетворяющие условиям:


Это же предприятие получило возможность продавать отходы производства, для чего ему необходимо определить их цену. Пусть - цена единицы отходов 1,2,3 - го видов. Естественно, что покупатель стремится к тому, чтобы суммарная цена всех отходов была наименьшей, а предприятию выгодно продавать их лишь в том случае, если выручка от продажи не меньше, чем прибыль от реализации готовых изделий, т.е. математическая модель задачи выглядит следующим образом:

Задача II. Найти , удовлетворяющие условиям:



Задачи I и II являются парой двойственных задач.