Файл: В. А.МАТВЕЕВ.pdf

Выше рассмотрена прямая и двойственная задачи линейного программирования для задачи в стандартной форме. Аналогичные построения для двойственной задачи можно провести для задач в канонической форме (ограничения в форме равенств) и в общей форме (ограничения в форме равенств и неравенств).

Пример 9.1. Для прямой задачи линейного программирования записать двойственную задачу и решить их обе графически

f (x) = x1 + x2 → max,

Двойственную задачу для прямой задачи линейного программирования запишем в матричной форме.

f d ( y) = y1 + y2 → min,

Двойственная задача в матричной форме записи представлена в (9.7), если прямая задача задана в (9.6). Решим прямую задачу. Область допустимых значений X представлена на рис.9.1. Область расположена в первой четверти и ограничена прямыми

На рис.9.1 эта область есть четырёхугольник ОАВС. Через точку В проходит линия уровня, которая определяет решение.

73

x 2

Рис. 9.1.

Отметим, что точка В является пересечением прямых a, b и её координатыаналитическинаходятсякакрешениесистемыуравнений

x1 + 4x2 =1,

5x1 + 2x2 =1.

Тогда В(1/9, 2/ 9). Значит

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

и не содержит начало координат. Область Y не ограничена и изображена на рис.9.2. У этой области только одна касательная из множества линий уровня. Она проходит через точку Е, координаты которой есть решение системы двух уравнений, т.е.

уравнений прямых с, d. Уравнение касательной y1 + y2 = 13 . Тогда двойственная задача имеет решение

74

x 2

0,5 K

Пара двойственных задач линейного программирования имеет общие свойства, представленные в пунктах 1° - 4°. Это свойства связаны с представлением задач. Имеется более глубокая связь, обусловленнаязависимостьюрешений. Приведёмсоответствующую Теорема (теорема двойственности). Рассматривается пара двойственных задач линейного программирования: прямая (8.1)

– (8.3) и двойственная (9.1) – (9.3). Если одна из них имеет оптимальное решение, то и другая имеет решение. Экстремальные значения целевых функций совпадают. Если в одной из задач нет оптимального решения по причине неограниченности области допустимых решений, то в двойственной ей задаче область допустимых решений пуста. Для последнего верно и обратное утверждение.

Свойства прямой и двойственной задачи линейного программирования рассматриваются в учебниках и пособиях по линейномупрограммированию [9, с.239 – 244; 10, с.72 –81]. Вообще теория двойственности является сердцевиной линейного (и более широко – математического) программирования.

Теория двойственности наиболее успешно применяется в задачахлинейногопрограммированиясэкономическимсодержанием. Распространён взгляд на экономику, как науку о “распределении

75

ограниченныхресурсовсцельюполучениямаксимальнойприбыли”. Можно выделить два подхода к её изучению. Один из них связан с максимизациейприбыли. Другойоснованнаминимизациииздержек. Двум этим подходам соответствует пара двойственных задач линейного программирования. Первый подход состоит в том, чтобы составить такой план выпуска продукции x = (x1, x2, …, xm), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдёт имеющихся запасов. Этот взгляд соответствует прямой задаче линейного программирования.

Второй подход состоит в том, что выбирается такая система цен (оценок) для ресурсов y = (y1, y2, …, yn), при которой общие затраты на ресурсы будут минимальны при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этого вида продукции. Этот взгляд соответствует двойственной задаче линейного программирования.

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

Пример 9.2. Решить задачу линейной программирования с использованием двойственной задачи

f (x) = x1 + x2 − x3 − x4 → max; 2x1 + x2 − x3 − x4 ≤1,

x j ≥ 0, j =1,...,4.

Графически эту стандартную задачу решить не удаётся, т.к. число неизвестных n = 4 > 2. Запишем для неё соответствующую двойственную задачу

f d ( y) =1y1 → min;

2y1 ≥1, y1 ≥1,

76

− y1 ≥ −1, − y1 ≥ −1,

y1 ≥ 0.

В этой задаче только одна переменная – y1. более того, здесь область допустимых значений состоит из одной точки, числа y1 = 1. Эта точка определяет оптимальное решение двойственной задачи. Именно,

подобрать допустимое (с неотрицательными координатами) x*

= ( x1* , x2* , x3* , x4* ) X, что 2x1* + x2* − x3* − x4* ≤1. Один из таких

векторов, например, x* = ( x1* , x2* , x3* , x4* ) = (0, 1, 0, 0) X. По

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

fmax = f (x*) =1 при x* = (0,1,0,0).

Отметим, что в этой задаче существуют и другие решения задачи максимизации.

Пример 9.3. Решить задачу линейной программирования с использованием двойственной задачи

f (x) = −6 y1 +10 y2 +9 y3 +8y4 → min;

−2y1 + y2 + y3 ≥ 2, y1 − y2 − y4 ≤ −1, y j ≥ 0, j =1,...,4.

Графически эту стандартную задачу решить не удаётся, т.к. числонеизвестныхn = 4 > 2. Перепишемданнуюзадачувстандартной форме (как задачу минимизации)

f d (x) = −6y1 +10y2 +9y3 +8y4 → min;

77

−2y1 + y2 + y3 ≥ 2, − y1 + y2 + y4 ≥1, y j ≥ 0, j =1,...,4.

В этой задаче по-прежнему четыре переменные, именно y1, y2, y3, y4. Запишем двойственную задачу максимизации (8.1) – (8.3).

f(x) = 2x1 + x2 → max;

−2x1 − x2 ≤ −6, x1 + x2 ≤10,

x1 ≤ 9, x2 ≤ 8,

x j ≥ 0, j =1, 2.

Полученную задачу можно решить графически. Область допустимых значений является шестиугольником ABCDEF и представлена на рис.9.3.

Рассмотрим линии уровня, имеющие вид 2x1 + x2 = с, где с– любое действительное число. Максимальное решение реализуется

x 2

10

E D

8

F

6

Рис. 9.3.

78

в точке С(9, 1). Это общая точка шестиугольника ABCDEF и линии уровня p: 2x1 + x2 = 19. Тогдарешениедвойственнойзадачидлязадачи из данного примера будет

fmax = f (x*) =19 при x* = (9,1).

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

f d (x) = −6y1 +10 y2 +9 y3 +8y4 =19,

−2y1 + y2 + y3 ≥ 2, − y1 + y2 + y4 ≥1, y j ≥ 0, j =1,...,4.

Несложно подобратьрешение y* = (0, 1, 1, 0). Таким образом, получаем решение исходной задачи

fmind = f ( y* ) =19 при y* = (0,1,1,0).

Задачидлясамостоятельногорешения

Задача 9.1 Для прямой задачи линейного программирования записать двойственную задачу и решить их обе графически

Задача 9.2. Решить задачу линейной программирования с использованием двойственной задачи

f (x) = x1 − x2 = 2x3 + x4 → max;

79