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

 

1. Каждому му неравенству системы ограничений исходной задачи ставится в соответствие переменная .

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

3. Составляют систему ограничений по правилу: коэффициенты новой сис­темы ограничений образуют транспонированную матрицу коэффици­ентов исходной системы ограничений; при этом знаки неравенств из­меняют на противоположные.

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

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

 

Реализовав перечисленные в правилах действия, получим математическую модель двойственной задачи в виде:

 

Если модель исходной задачи имеет канонический вид, то при составлении математичес­кой модели двойственной задачи используют все правила, приведенные выше, с добавлением еще одного правила:

 

6. Ограничениями двойственной задачи будут неравенства, причем, если в целевой функции составляемой двойственной задачи требуется найти минимум, то ставится знак неравенства «больше или равно», если же – максимум, то знак «меньше или равно».

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

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

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

Если же одна из двойственных задач не имеет решения, ввиду того, что: , или: , то другая задача не имеет допустимых ре­шений.

Теорема 2. Для оптимальности допустимых решений и  пары двойст­венных задач необходимо и достаточно, чтобы они удовлетворяли системе урав­нений:

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

Обе сформулированные теоремы позволяют определить опти­мальное решение одной из задач двойственной пары по оптимальному решению другой.

 

ПРИМЕР: Математическая модель задачи линейного программи­ро­вания имеет вид:

Составьте математическую модель двойственной задачи и по оптимальному решению одной из задач найдите оптимальное решение другой.

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

 

Если решить исходную задачу графическим методом, то полу­чим:  и при этом: . На основании первой теоремы двойственности зак­лючаем, что: . Поскольку полученные оптимальные решения исходной задачи положительны, по второй теоре­ме двойственности систему ограничений двойст­венной задачи можно записать в виде равенств или уравнений:

 

 

Теперь подставим значения  и  в систему ограничений исходной зада­чи и получим:

 

На этом основании система ограничений двойственной задачи примет вид:

Решая ее, окончательно находим:  и при этом: .

Теперь решим обратную задачу. Пусть дано опти­мальное решение двойственной задачи: . По первой теореме двойственности имеем: . Так как , то по второй теореме двойственности заключаем, что второе и третье неравен­ства исходной задачи обращаются в равенства, или в уравнения:

 

Решив эту систему, находим:  и при этом: .

 

Тема 2. Транспортная задача