Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Двойственные задачи по виду системы ограничений и по смыслу экстремума делятся на несимметричные и симметричные.

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

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

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

Несимметричные задачи

(1) Исходная задача Двойственная задача

Ф = С•Х ® min, F = В•Y ® max,

А•Х = В, А^T•Y ≤ C,

Х ³ 0.

(2) Исходная задача Двойственная задача

Ф = С•Х ® max, F = В•Y ® min

А•Х = В, А^T•Y ³ C, (3.24)

Х ³ 0.

Симметричные задачи

(3) Исходная задача Двойственная задача

Ф = С•Х ® min, F = В•Y ® max,

А•Х ³ В, А^T•Y £ C,

Х ³ 0. Y ³ 0.

(4) Исходная задача Двойственная задача

Ф = С•Х ® max, F = В•Y ® min

А•Х £ В, А^T•Y ³ C,

Х ³ 0. Y ³ 0.

Пример 3.10. Дана исходная задача:

максимизировать линейную функцию Ф = 2×х₁ - х₄ ® max

при ограничениях: х₁ + х₂ = 20,

х₂ + 2×х₄ ³ 5,

- х₁ + х₂ + х₃ £ 8,

х_j ³ 0 (j = 1, 2, 3, 4)

Требуется составить задачу, двойственную к исходной.

Решение. Система ограничений задана в смешанном виде. Приведем ее к одному, например, к каноническому виду, введя дополнительные переменные х₅, х₆ х₁ + х₂ = 20,

х₂ + 2×х₄ - х₅ = 5,

- х₁ + х₂ + х₃ + х₆ = 8,

Получили задачу на максимизацию линейной функции с системой ограничений в виде равенств, то есть, имеем несимметричную задачу 2-го типа, которая в матричном форме запишется в виде Ф = С×Х → max

при ограничениях А×Х = В.

Двойственная задача должна иметь вид: F = B×Y → min

при ограничениях A^T×Y ³ C.

В исходной задаче матрица-строка коэффициентов при переменных в целевой функции имеет вид С = (2; 0; 0; -1; 0; 0), матрица-столбец свободных членов и матрица коэффициентов при переменных в системе ограничений имеют вид

20 1 1 0 0 0 0

B = 5 A = 0 1 0 2 -1 0

8 - 1 1 1 0 0 1

Для двойственной задачи матрица-строка коэффициентов при переменных в целевой функции будет иметь вид В = (20; 5; 8), матрица-столбец свободных членов и матрица коэффициентов при переменных системы ограничений будут иметь вид

2 1 0 -1

0 1 1 1

С = 0 А^т = 0 0 1

-1 0 2 0

0 0 -1 0

0 0 0 1

Двойственная задача формулируется в следующем виде:

минимизировать линейную функцию F = 20×y₁ + 5×y₂ + 8×y₃ ® min

при ограничениях y₁ - y₃ ³ 2,

y₁ + y₂ + y₃ ³ 0,

y₃ ³ 0,

2×y₂ ³ -1,

- y₂ ³ 0,

y₃ ³ 0.

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

1. Привести систему ограничений исходной задачи к одному виду: в симметричной задаче на максимизацию линейной функции все неравенства системы ограничений привести к виду «£», в задаче на минимизацию – к виду «³». Для этого неравенства, в которых данное требование не выполняется, нужно умножить на –1. Если в несимметричной исходной задаче в системе ограничений присутствуют неравенства, необходимо преобразовать их в равенства, введя дополнительные переменные.

2. Составить расширенную матрицу А₁ исходной задачи, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений (b_i) и строку коэффициентов при переменных в линейной функции (c_j).

3. Найти матрицу А₁^Т, транспонированную к матрице А₁.

4. Сформулировать двойственную задачу на основании полученной матрицы А₁^Т и условия неотрицательности переменных.

Пример 3.11. Дана исходная задача:

максимизировать линейную функцию Ф = 2×х₁ + 3×х₂ ® max

при ограничениях x₁ + 3×x₂ ³ 18,

2×x₁ + x₂ £ 16,

x₂ £ 5,

3×x₁ £ 21,

x₁ ³ 0, x₂ ³ 0

Требуется составить задачу, двойственную к исходной задаче.

Решение.

1. Имеем симметричную задачу 4-го типа, так как имеем задачу на максимизацию линейной функции и система ограничений задана в виде неравенств.

2. Составим расширенную матрицу исходной задачи

1 3 18

2 1 16

А₁ = 0 1 5

3 0 21

2 3 Ф

3. Найдем матрицу А₁^Т, транспонированную к А₁

1 2 0 3 2

А₁^Т = 3 1 1 0 2

18 16 5 21 F

4. Сформулируем двойственную задачу:

F = 18× y₁ + 16×y₂ + 5× y₃ + 21× y₄ ® min

при ограничениях y₁ + 2×y₂ + 3×y₄ ³ 2,

3×y₁ + y₂ + y₃ ³ 3,

y_i ³ 0, i = 1, 4