Двойственные задачи линейного

Программирования

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

.

.

Данную задачу будем называть исходной.

  Определение 1. Под двойственной задачей (ДЗ) к исходной понимается задача линейного программирования, которая строится по следующим правилам, приведенным в таблице.

 

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

Через  здесь обозначены двойственные переменные.

Замечание 1. Когда целевая функция в исходной задаче минимизируется, таблица прочитывается справа налево.

 Данная таблица позволяет сформулировать несколько общих правил построения двойственных задач.

· Каждому i- м у ограничению исходной задачи соответствует переменная y_i в ДЗ и, наоборот, каждому k -му ограничению ДЗ соответствует переменная x_k исходной задачи.

· Матрицы ограничений в исходной и двойственной задачах взаимно транспонированы.

· Правые части ограничений исходной задачи становятся коэффициентами целевой функции в ДЗ, а коэффициенты целевой функции исходной задачи - правыми частями ограничений в ДЗ.

· Если целевая функция в исходной задаче максимизировалась (минимизировалась), то в ДЗ целевая функция минимизируется (максимизируется);

Используя определение, построим ДЗ к ЗЛП, записанной в симметричной форме. В ДЗ целевая функция минимизируется: .

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

.

     Если использовать определение для построения ДЗ для ЗЛП, записанной в канонической форме, то мы получим задачу вида:

.

     Пример 1. Построить ДЗ к следующей задаче

Решение.

     В ДЗ к исходной задаче будет 3 переменных (в исходной задаче 3 ограничения) и 4 ограничения (в исходной задаче 4 переменных). Поскольку в исходной задаче целевая функция минимизируется, воспользуемся таблицей слева направо. Для иллюстрации построим аналогичную таблицу для данной конкретной задачи.

 

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

 

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

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

                   

                             

                                

Свойство 1. Задача двойственная к двойственной является исходной.

Свойство 2. Для любых  допустимых в исходной задаче и допустимых в двойственной справедливо неравенство

Свойство 3. Если исходная задача не имеет решения из-за неограниченности целевой функции на допустимом множестве, то допустимое множество двойственной задачи пусто.

Свойство 4. Возможен вариант, когда допустимые множества исходной и двойственной задач одновременно пусты.

Пример 2. В качестве примера к свойству 4 рассмотрим следующую двойственную пару

                            

                                    

                                              

                                                           

Свойство 5. Если существует точка , допустимая в исходной задаче и точка , допустимая в двойственной задаче, такие, что , то - решение исходной, а - решение двойственной задачи.

     Теорема 1. (Первая теорема двойственности). Если одна из задач (двойственная или исходная) имеет решение, то и двойственная к ней имеет решение, причем оптимальные значения целевых функций совпадают.

Теорема 2. (Вторая теорема двойственности) Для того, чтобы допустимая в исходной задаче точка  и допустимая в двойственной задаче точка  являлись соответственно решениями исходной и двойственной задач, необходимо и достаточно, чтобы выполнялись равенства (условия дополняющей нежесткости):

или 

или   .

Замечание 2. (Интерпретация симплекс-метода в терминах двойственных задач) В симплекс - процедуре осуществляется перебор базисов  (невырожденных подматриц исходной матрицы ) таким образом, что

1. На каждой итерации метода вектор , где  является допустимым в исходной задаче, т.е. ;

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

или

т.е. вектор  является допустимым в двойственной задаче, кроме того, он является решением двойственной задачи. При этом заметим, что часть ограничений двойственной задачи выполняется в виде равенств , где - множество базисных индексов (так как оценки базисных векторов всегда равны нулю ). Такие точки  называются базисными в двойственной задаче.

     Рассмотрим примеры применения изложенной теории двойственности к решению задач линейного программирования.

 

     Пример 3. На основании графического анализа двойственной задачи исследовать разрешимость следующих задач и в случае разрешимости найти оптимальное значение целевой функции.

 

а)                     б)

                          

                               

                         

 

Решение.

Двойственные к предложенным задачам относятся к задачам линейного программирования в  и поэтому их можно решать описанным в главе 1 графическим методом. Двойственная к задаче а) имеет вид:

 

y1, y2 ≥0

 

                             

 

 

Рис.6

 

Графическое решение данной задачи (Рис. 6) показывает, что  с . В силу первой теоремы двойственности исходная задача также имеет решение, причем оптимальное значение равно 13.

Двойственная задача к задаче б) имеет вид:

 

Рис.7

 

Графический анализ показывает, что двойственная задача неразрешима из-за неограниченности целевой функции, поэтому по свойству 3 исходная задача неразрешима из-за пустоты допустимого множества.

Пример 4. Определить, являются ли данные векторы  и  оптимальными решениями данной задачи и двойственной к ней:

       

Решение. Решение данной задачи осуществляется в несколько этапов: 1) подставим точку  в ограничения исходной задачи. Так как точка

удовлетворяет ограничениям, переходим к следующему этапу;

2) построим двойственную задачу

;

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

4) подставим точку  в целевую функцию исходной задачи, а точку  - в целевую функцию двойственной задачи; полученные значения совпадают, поэтому по свойству 4 данные точки являются соответственно решением исходной и двойственных задач.

Пример 5. Найти решение следующей ЗЛП путем графического анализа двойственной задачи:

.

Решение.

Двойственная задача запишется в виде

 

Графический анализ этой задачи показан на следующем рисунке.

	Рис. 8

 

 Оптимальным решением является вектор  , . На основании второй теоремы двойственности для вектора x*, являющегося решением исходной задачи должны, выполняться равенства     

             .

Подставляя координаты вектора  получаем, что переменные   и  исходной задачи должны обращаться в нуль. Тогда из исходной системы получаем , откуда , и , откуда . Следовательно, решением исходной задачи является вектор . При этом =25.

     Пример 6. Определить решение двойственной задачи к задаче из примера 1 со стр. 22, используя решение исходной задачи.

Решение.

     В соответствии с замечанием 2, решением двойственной задачи является вектор , где матрица  является матрицей обратной к оптимальной базисной матрице .

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

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

 

1)

;

2)              

          

 

 

3)

 

   

 

     .

 

2. На основании графического анализа двойственной задачи исследовать разрешимость следующих задач и в случае разрешимости найти оптимальное значение целевой функции:

1)

  

 

2)

3)

;

 

4)

 

  .

 

3. Для каждой из пары двойственных задач возможны три варианта ответа: задача разрешима (Р), функция не ограничена (Н), область пустая (П). Теоретически, это позволяет рассмотреть 9 ситуаций: РР (обе задачи разрешимы), РН (первая разрешима, во второй целевая функция не ограничена) и т.д. Используя свойства двойственных задач, указать все возможные ситуации.

4. Привести примеры двойственных пар, обладающих следующими свойствами.

1) обе задачи имеют решения;

2) одна задача имеет неограниченное допустимое множество, вторая – пустое множество;

3) допустимые множества обеих задач пустые;

4) допустимые множества обеих задач неограниченные.

5. Определить, являются ли данные векторы  и  решениями данной задачи и двойственной к ней:

.

6. Найти решение двойственных задач, используя решение исходных задач симплексным методом:

1)                                    2)

                                           

                                      

                                         

                                      

3)

  

,

 

1. Постановка транспортной задачи 2. Метод северо-западного угла 3. Метод минимального элемента 4. Вырожденность в транспортной задаче 5. Алгоритм метода потенциалов 6. Открытая транспортная задача

         Глава 4

                                                               

Транспортная задача

 

       Транспортная задача формулируется следующим образом. Имеется  пунктов производства  однородного продукта и  пунктов потребления . Заданы объемы производства  каждого пункта  и размеры спроса каждого пункта  в одних и тех же единицах измерения. Известна также матрица 

 

 

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

Приведенная формулировка предполага- ет наличие равенства (условия баланса):

Такая задача называется закрытой транспортной задачей. Математическая постановка этой задачи имеет следующий вид

                    (1)

при ограничениях

                         (2)   

                                                                     (3)

 

                                ,                        (4)

где  - количество продукта, перевозимое из пункта  в пункт .

     Без ограничения общности всегда можно считать, что  и .

     Задача (1)-(4) является задачей линейного программирования, записанной в канонической форме. Она имеет  переменных и  ограничений. Любая допустимая точка задачи может быть записана в виде матрицы

 

.

 

Как известно, не любая задача линейного программирования имеет решение. Условия разрешимости транспортной задачи формулируются в следующей теореме.

 

     Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно выполнение следующего условия баланса

 

 

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

     Рассмотрим два метода нахождения исходной базисной точки для транспортной задачи: метод "северо-западного угла" и метод минимального элемента.

 

Метод "северо-западного угла"

Алгоритм построения исходной базисной точки складывается из нескольких шагов, на каждом из которых определяется верхний левый элемент матрицы . Сформулируем алгоритм метода "северо-западного угла".

Шаг 0. Полагаем .

Шаг 1. Полагаем . Если , то переходим к шагу 2, в противном случае - к шагу 4.

Шаг 2. Полагаем . Индексу  присваиваем значение . Если , то переходим к шагу 3, в противном случае к шагу 1.

Шаг 3. Полагаем  для всех . Решение закончено.

Шаг 4. Полагаем . Индексу  присваиваем значение . Если , то переходим к шагу 5, в противном случае переходим к шагу 1.

Шаг 5. Полагаем  для всех . Решение закончено.

     Рассмотрим пример использования данного алгоритма.

 

     Пример 1. Исходные данные:

 

	30		36		36		22		56
45		3		4		2		4		5
	30		15
70		3		1		4		2		4
			21		36		13
15		4		3		5		3		6
							9		6
50		2		4		3		6		8
									50

                                                           

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

45+70+15+50=30+36+36+22+56.

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

сo значением целевой функции равным 804.

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

Метод минимального элемента

Шаг 0. Полагаем , где .

Шаг 1. Определяем пару индексов  из условия .

Шаг 2. Полагаем . Если , то переходим к шагу 3, в противном случае - к шагу 6.

Шаг 3. Полагаем .

Шаг 4. .

Шаг 5. Если множество  состоит из элементов одной строки , то полагаем  для всех . Решение закончено. В противном случае переходим к шагу 1.

Шаг 6. Полагаем .

Шаг 7. .

Шаг 8. Если множество  состоит из элементов одного столбца , то полагаем  для всех . Решение закончено. В противном случае переходим к шагу 1.

Данным методом найдем исходную базисную точку для примера 1.

     Пример 2.

	30		36		36		22		56
45		3		4		2		4		5
					36^(2)				9^(5)
70		3		1		4		2		4
			36^(1)				22^(3)		12^(5)
15		4		3		5		3		6
									15^(5)
50		2		4		3		6		8
	30^(4)								20^(5)

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

 

 

со значением целевой функции, равным 545. Данное значение явно меньше, чем значение целевой функции на базисной точке, полученной методом "северо-западного угла".

 

Вырожденность в транспортной задаче

 

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

.

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

     Пример 3. Построим методом "северо-западного угла" исходную базисную точку для следующей задачи

 

	10		4		9		6
6		3		4		2		4
	6
8		3		1		4		2
	4		4
10		4		3		5		3
			0^*		9		1
5		2		4		3		6
							5

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

Метод потенциалов

 

 

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

Задача, двойственная к транспортной задаче имеет вид

,

где  - переменные двойственной задачи, соответствующие ограничениям (2), а  - переменные двойственной задачи, отвечающие ограничениям (3). В соответствии с данным видом двойственной задачи оценки в транспортной задаче будут иметь вид

,

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

                         ,                               (5)

где  - множество базисных пар индексов. Заметим, что система (5) имеет  переменных и  уравнение. Ранг системы равен . Отсюда следует, что одну из переменных можно выбрать произвольно, например, , а все остальные переменные найти по цепочке.

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

.

 

Если существует пара индексов , для которой

,

то существует базисное решение , для которого

                                 ,                                  (6)