Основные факты теории двойственности.

Пусть дана задача линейного программирования в канонической форме

Метод исключения переменных.

f(x)=

а_ij x_j =b_i,i=1:m, (7.8)

x_j ≥0.

где число переменных на два больше числа ограничений-равенств, т.е. n-m=2,

причем ранг матрицы А=m. Тогда две переменные в указанной системе уравнений, скажем х₁ и х₂, являются свободными, т.е. через них можно выразить все остальные переменные:

, (7.9)

где…- некоторые числа. Подставляя эти выражения в целевую функцию, получаем

………………, 7.10)

где - некоторые числа.

Рассмотрим задачу линейного программирования с двумя переменными:

…

Используя геометрические построения, находим ее решение (). Подставляя эти числа в (7.9), (7.10), получаем решение и значение исходной задачи (7.8).

Пример 7.2. Найти максимальное значение функции

f = —16x₁ — x₂ + x₃+5x₄ + 5x₅

при условиях:

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

Выше было показано (см. § 1.2), что исходная задача записана в форме основной для задачи, состоящей в нахождении максимального значения функции

f = 2x₁ + Зx₂;

при условиях:

Из целевой функции исходной задачи переменные x₃, x₄,x₅ исключены с помощью подстановки их значений из соответствующих уравнений системы ограничений.

Построим многоугольник решений полученной задачи (рис. 7.1.). Как видно из рис. 7.1., максимальное значение целевая функция задачи принимает в точке С пересечения прямых I и II. Вдоль каждой из граничных прямых значение одной из переменных, исключенной при переходе к соответствующему неравенству, равно нулю. Поэтому в каждой из вершин полученного многоугольника решений последней задачи по крайней мере две переменные исходной задачи принимают нулевые значения. Так, в точке С имеем x₃ =0 и x₄ =0. Подставляя этизначения в первое и второе уравнения системы ограничений исходной задачи, получаем систему двух уравнений

,

решая которую, находим x*₁ = 3, x*₂ = 4.

Подставляя найденные значения x₁ и x₂ в третье уравнение системы ограничений исходной задачи, определяем значение переменной x₅ равное14.

Следовательно, оптимальным планом рассматриваемой задачи является x*=(3, 4, 0, 0, 14). При этом плане значение целевой функции есть F_max=18.

7.1.3. Двойственность в линейном программировании

Каждой задаче ЛП можно поставить в соответствие другую задачу ЛП, называемую двойственной. Их совместное изучение составляет предмет теории двойственности, являющейся важным разделом линейного программирования. Более эффектной теория двойственности является в тех случаях, когда двойственная задача решается проще, чем прямая.

Для удобства выпишем еще раз общую задачу ЛП:

f(x)=,

а_ij x_j =b_i,i=1:l;

а_ijx_j£ b_i , i=(l+1):m; (7.11)

x_j³0

Двойственной к задаче (7.11) называется следующая задача:

(7.12)

При этом задача (7.11) называется прямой.

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

 

 

х₁≥0 … х_s≥0 х_s+1 … х_n

y1≥0 . . . yl≥0 yl+1 . . . ym	а11 … а1s а1,s+1 … а1n       аl1 … аls аl,s+1 … аln аl+1, 1 … аl+1,s аl+1,s+1 … аl+1,s . . . am1 … ams am,s+1 … amn	≤       ≤ =       =	b1 . . . bk bk+1 . . . bm
≥ … ≥ = … =
с1 … cs cs+1 … cn

 

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

1) если прямая задача решается на максимум, то двойственная – на минимум, и наоборот;

2) в задаче на максимум ограничения – неравенства имеют смысл ≤, а в задаче минимизации – смысл ≥;

3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи ;

4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием ;

5) свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот ;

6) если на переменную прямой задачи наложено условие не отрицательности (≥), то соответствующее ограничение двойственной задачи записывается как ограничение – неравенство , если же нет, то как ограничение равенство ;

7) если i-e ограничение исходной задачи является неравенством, то i –я переменная двойственной задачи y_i³0. Если же i-е ограничение есть уравнение, то переменная y_i может принимать как положительные, так и отрицательные значения, т.е. условие не отрицательности не налагается.

 

Сначала в таблицу заносится вся информация о прямой задаче: значения параметров a_ij ,b_i, и с_j, знаки неравенств или равенств в ограничениях (справа), условия неотрицательности соответствующих переменных (сверху). Затем каждой i - й строке (i-му ограничению прямой задачи) ставится в соответствие двойственная переменная y_i, на которую накладывается условие неотрицательности, если справа в этой строке стоит знак неравенства. Внизу проставляются знаки неравенства или равенства в зависимости от того, наложено или не наложено усло­вие неотрицательности на соответствующую переменную прямой задачи. После этого двойственная задача «считывается» путем умножения вектора у=(y_i) на столбцы матрицы А =(а_ij) и вектор b =(b_i).

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

Таблица 7.1

Формы записи прямой и двойственной задач

 

Форма записи прямой задачи ЛП	Форма записи соответствующей двойственной задачи ЛП
Основная: <c,x> max, Ax≤b	Каноническая: : <b,y> min, yA=c, y≥0
Стандартная: <c,x> max, Ax≤b, х≥0	Стандартная: <b,y> min, yA≥c, y≥0
Каноническая:c,x> max, Ax=b, х≥0	Основная: <b,y> min, yA≥c

 

Теорема 7.1. Задачи (7.11) и (7.12) взаимодвойственны, т. в. двойственной к задаче (7.12) является задача (7.11).

Ниже под Х и У понимаются допустимые множества задач (7.11) и (7.12) соответственно.

Теорема 7.2. Для любых хÎХ и yÎY выполняется неравенство <с, х> £ <b, у>.

Теорема 7.3. Пусть х*Î X, у*Î У. Тогда

1) если

<с, х*>=<b,у*>, (7.13)

то х* есть решение задачи (7.11), а у* — решение задачи (7.12);

2) равенство (7.13) равносильно совокупности условий

(7.14)

(7.15)

Равенство (7.13) принято называть соотношением двойственности, условия (7.14), (7.15)— условиями дополняющей нежесткости.

Теорема 7.4 (теорема двойственности). Прямая задача (7.11) имеет решение в том и только том случае, если двойственная задача (7.12) имеет решение; при этом значения данных задач совпадают, т. е. для любых их решений х* и у* выполнено соотношение двойственности (7.12).

При практическом применении теории двойственности особенно полезным является следующее утверждение, непосредственно вытекающее из теорем 7.3 и 7.4.

Теорема 7.5 (о дополняющей нежесткости). Точки x*Î Х и у*Î Y являются решениями взаимодвойственных задач (7.11) и (7.12) соответственно в том и только том случае, если выполняются условия (7.14), (7.15).

Итак, взаимодвойственые задачи ЛП имеют или не имеют решения одновременно. Следующая теорема показывает, что уже по их допустимым множествам можно отличить первый случай от второго.

Теорема 7.6. Если допустимые множества взаимодвойственных задач (7.11) и (7.12) непусты, то обе они имеют решение. Если же только у одной из них допустимое множество непусто, то ее значение бесконечно, т. е.

Пример 7.2. Построить задачу двойственную к следующей задаче ЛП.

17х₁ – 5 х₂ + х₃+ х₄ – 8х₅max

3х₁ – х₂ – х₃ + 4х₄ + 7х₅ ≤11

х₁ – 5 х₂ – 7х₃ + х₄ + 2х₅ ≥-8

х₁ + х₂ + х₃ + 3х₄ – х₅=4

х₁≥0, х₄≥0.

Решение. Составим таблицу перехода к двойственной задаче (табл. 7.1).

Отсюда получаем ответ:

Таблица 7.1

х₁≥0 х₂ х₃ х₄≥0 х₅

11y₁ +8y₂ + 4y₃ min,

3y₁ – y₂ + y₃ ≥17

–y₁ + 5y₂ + y₃ = –5

–y₁ + 7y₂ + y₃ =1

4y₁ – y₂ + 3y₃ ≥1

7y₁ – 2y₂ – y₃= –8

Симплексный метод