Анализ модели. Составление пары симметричных двойственных задач

В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи)

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

1.Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными — в левой.

2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.

3. Если знаки неравенств в ограничениях исходной задачи «≤», то целевая функция Z(X) = с₀ + с₁ · x₁ + с₂ · x₂ + … + с_n · x_n должна максимизироваться, а если «≥», то минимизироваться.

4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче; при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.

5. Целевая функция двойственной задачи имеет вид

где с₀ — свободный член целевой функции Z(X) исходной задачи, b₁, b₂, …, b_m,— свободные члены в ограничениях исходной задачи, при этом b_i— свободный член именно того ограничения исходной задачи, которому соответствует неизвестная y_i, a y₁, y₂, …, y_m— неизвестные в двойственной задаче.

6. Целевая функция F(Y) двойственной задачи должна оптимизиро­ваться противоположным по сравнению с Z(X) образом, т.е. если Z(X) → max, то
F(Y)→ min, и если Z(X) → min, то F(Y) → max.

7. Каждому неизвестному х_j, j = 1, 2, ..., п исходной задачи соответствует ограничение в двойственной задаче. Совокупность этих п ограничений (вместе с условиями неотрицательности неизвестных y_i, соответствующих ограничениям-неравенствам исходной задачи) образует систему ограничений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными y_i у₂, ..., у_т — в левых. Все знаки неравенств имеют вид «≥», если F(Y) → min, и «≤», если
F(Y) → max.

Коэффициенты, с которыми неизвестные y_l у₂, …, у_т входят в ограничение, соответствующее неизвестному x_j, совпадают с коэффициентами при этом неизвестном х. в ограничениях исходной задачи, а именно: коэффициент при y_iсовпадает с тем коэффициентом при х_j с которым х_j входит в ограничение исходной задачи, соответствующее неизвестному y_i.

Двойственность

1) Составляем матрицу из полученной математической модели

7 6 2 1

А = 1 3 6 1

0 2 5 1

1 1 1 F

2) Транспонируем матрицу A

7 1 0 1

А^-1 = 6 3 2 1

2 6 5 1

1 1 1 Z

3) Составляем двойственную задачу

Z = y₁ + y₂ +y₃ → Min

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

F(x) = x₁ + x₂ + x₃ → max Z(x) = y₁ + y₂ +y₃ → min