Глава II. Двойственность и целочисленность в линейном программировании. Транспортная задача.

§1. Теория двойственности

1.1. Задача, приводящая к паре двойственных задач

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

c₁x₁+c₂x₂+…+c_nx_n  max

(1.1)

Предположим, производитель продукции отказался производить продукцию и решил продать сырьё (например, производитель продукции продаёт своё производство). Пусть y₁, y₂, …, y_m  стоимость единицы сырья соответственно 1-го, 2-го, …, m-го видов. Тогда выручка (прибыль) от продажи всех видов сырья составит b₁y₁+b₂y₂+…+b_my_m. Покупатель заинтересован в том, чтобы купить сырьё как можно дешевле:

b₁y₁+b₂y₂+…+b_my_m  min.

Сырьё всех видов, ранее предназначенное для выпуска единицы продукции первого вида, оценивается в a₁₁y₁+a₂₁y₂+…+a_m1y_m. Продавец сырья заинтересован в том, чтобы эта оценка была не меньше, чем прибыль за единицу продукции первого вида. От производства которого он отказался:

a₁₁y₁+a₂₁y₂+…+a_m1y_m≥c₁.

Аналогично рассуждая относительно всех видов сырья, предназначенных ранее для выпуска единицы j-го вида продукции, получаем неравенство

a_1jy₁+a_2jy₂+…+a_mjy_m≥c_j (j=1, 2, …, n).

Наконец, стоимость единицы любого вида сырья неотрицательная:

y_j≥0 (i=1, 2, …, m).

Таким образом, мы приходим к следующей математической модели этой ситуации:

b₁y₁+b₂y₂+…+b_my_m  min

(1.2)

1.2. Пара симметричных двойственных задач

Сравним задачи (1.1) и (1.2). Эта пара задач обладает следующими свойствами:

1. Матрицы систем ограничений задач транспонированы по отношению к друг другу.

2. Каждому ограничению одной задачи соответствует переменная во второй задаче; все переменные удовлетворяют условию неотрицательности.

3. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами соответствующих ограничений другой. При этом свободные члены целевых функций задач совпадают.

4. Целевые функции задач оптимизируются противоположным образом: если одна из задач  на максимум, то вторая  на минимум, а если одна из задач на минимум, то вторая  на максимум.

5. Если целевая функция задачи максимизируется, то знаки неравенств в ограничениях задачи имеют вид «», а если минимизируется, то имеют вид «».

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

Такая пара задач называется парой симметричных двойственных задач. Одна задача пары двойственных называется двойственной к другой.

1.3. Пара несимметричных двойственных задач

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

1. Матрицы систем ограничений задач транспонированы по отношению к друг другу.

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

3. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами соответствующих ограничений другой. При этом свободные члены целевых функций задач совпадают.

4. Целевые функции задач оптимизируются противоположным образом, то есть если одна из задач  на максимум, то вторая  на минимум, а если одна из задач на минимум, то вторая  на максимум.

5. Если целевая функция задачи максимизируется, то знаки неравенств в ограничениях задачи имеют вид «», а если минимизируется, то имеют вид «».

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

Наконец, условия 1  6 называются условиями двойственности.

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

Пример 1. Составить двойственные к задачам:

а) 2x₁+2x₂5x₃  max(min); б) 2x₁+2x₂5x₃  min

Решение. а) Сначала составим двойственную к задаче на максимум (max). Двойственная  следующая:

12y₁2y₂+24y₃  min

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

2x₁+2x₂5x₃  max 12y₁2y₂+24y₃  min

задач выполнены все условия двойственности.

1. Матрицы систем ограничений задач транспонированы по отношению к друг другу:

= .

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

3. Коэффициенты 2, 2, 5 при переменных в целевой функции первой задачи являются свободными членами соответствующих ограничений второй и, наоборот, коэффициенты 12, 2, 24 при переменных в целевой функции второй задачи являются свободными членами соответствующих ограничений первой. При этом свободные члены целевых функций задач совпадают (оба равны 0).

4. Целевые функции задач оптимизируются противоположным образом: исходная задача  на максимум, а вторая  на минимум.

5. Выдержаны требования к соответствию типа экстремума целевой функции к типам неравенств в ограничениях: если целевая функция задачи максимизируется, то знаки неравенств в ограничениях задачи имеют вид «», а если минимизируется, то имеют вид «».

Теперь составим двойственную к задаче на минимум (min). Тогда исходную необходимо переписать согласно виду экстремума целевой функции  минимума. Это означает, что все нетривиальные неравенства в исходной задаче должны принять вид «». Для этого достаточно эти неравенства умножить на 1:

а) 2x₁+2x₂5x₃  min

Двойственная  следующая:

12y₁+2y₂24y₃  max

Убеждаемся в этом точно так же, как и в предыдущем случае.

б) Двойственная  следующая:

12y₁2y₂+24y₃  max

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

2x₁+2x₂5x₃  min 12y₁2y₂+24y₃  max

задач выполнены все условия двойственности.

1. Матрицы систем ограничений задач транспонированы по отношению к друг другу:

=

2. В каждой задаче по три ограничения и три переменные, то есть каждому ограничению одной задачи соответствует переменная в другой задаче. При этом переменные x₁, x₂, x₃, y₁, y₂, соответствующие ограничениям-неравенствам в одной задаче, удовлетворяет условиям неотрицательности в другой, а переменная y₃, соответствующая ограничению-равенству в первой, может быть любого знака (на неё ограничение неотрицательности не накладывается).

3. Коэффициенты 2, 2, 5 при переменных в целевой функции первой задачи являются свободными членами соответствующих ограничений второй и, наоборот, коэффициенты 12, 2, 24 при переменных в целевой функции второй задачи являются свободными членами соответствующих ограничений первой. При этом свободные члены целевых функций задач совпадают (оба равны 0).

4. Целевые функции задач оптимизируются противоположным образом: исходная задача  на минимум, а вторая  на максимум.

5. Выдержаны требования к соответствию типа экстремума целевой функции к типам неравенств в ограничениях: если целевая функция задачи максимизируется, то знаки неравенств в ограничениях задачи имеют вид «», а если минимизируется, то имеют вид «».

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