Реализация метода Искусственного Базиса

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

1) если целевая функция исходной задачи формулируется на максимум, то целевая функция двойственной задачи – на минимум, и наоборот. При этом в задаче на максимум во всех неравенствах в функциональных ограничениях используется знак « », а в задаче на минимум − знак « »;

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

3) число неизвестных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе у двойственной задачи – числу неизвестных в исходной;

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

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

при этом ограничению, записанному  в виде неравенства со знаком « »,

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

6) задача, двойственная двойственной, совпадает с исходной;

7) базисным неизвестным прямой задачи линейного программирования соответствуют свободные неизвестные двойственной, и наоборот.

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

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

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

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

Запишем пару симметричных взаимодвойственных задач линейного  программирования в соответствии с  перечисленными выше правилами (табл. 6)                                                     

 

 

 

 

                                                                                      

                                                                                                  Таблица 6

Прямая задача линейного программирования	Двойственная задача линейного программирования

 

 

Основные утверждения  о взаимодвойственных задачах линейного  программирования  содержатся в следующих теоремах.

Первая теорема двойственности.

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

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

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

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

 

 

 

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

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

Вторая теорема двойственности (принцип дополняющей нежёсткости).  

Пусть   допустимое решение прямой задачи линейного программирования, а   допустимое решение двойственной задачи линейного программирования. Для того чтобы эти решения были оптимальными решениями соответствующих взаимодвойственных задач линейного программирования, необходимо и достаточно того, чтобы выполнялись следующие равенства:

                    

 

                            

 

Замечание.

Условия (29) и (30) позволяют, зная оптимальное решение одной из взаимодвойственных задач линейного программирования, найти оптимальное решение другой задачи. 

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

 

 

 

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

с ограничениями

при условиях неотрицательности 

 

Составить двойственную задачу и записать её оптимальное  решение. 

 

Решение. 

Составим задачу, двойственную данной, пользуясь сформулированными выше правилами (или табл. 9.1).

Поскольку прямая задача линейного программирования − задача минимизации, то двойственная задача −  это задача максимизации; её целевая  функция имеет вид:

 

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

 

а  неизвестные удовлетворяют условиям неотрицательности: 

 

Приведём прямую и двойственную задачи линейного программирования к каноническому виду, вводя дополнительно в их системы ограничений неотрицательные балансовые неизвестные   (в прямую задачу): 

  

и   (в двойственную задачу):

 

В прямой и двойственной задачах базис усматривается  сразу:

− для задачи минимизации:   

− для задачи максимизации:  .

Следует отметить, что  задача минимизации не имеет предпочтительного вида в базисе   

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

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

учитывая установленное  соответствие неизвестных.

 

 

 

Свободные неизвестные               Базисные неизвестные

Базисные неизвестные                   Свободные неизвестные       

 

Соответствие неизвестных прямой и двойственной задач линейного программирования 

 

Методом, описанным в  пункте 7, получим следующую последовательность симплекс-таблиц (табл. 8, 9).

 
 
 

Оптимальное решение задачи максимизации, записанной в канонической форме, имеет вид:

Оптимальное решение  этой задачи линейного программирования найдено в базисе

Следовательно, двойственная ей задача минимизации имеет оптимальное  решение в базисе 

Оптимальное решение задачи минимизации  запишем по последней строке табл. 9.4:

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

Соответствующее оптимальное  значение целевых функций:

 

2. Разработка и описание алгоритма решения задачи

Алгоритм

Приводим задачу ЛП  к каноническому виду

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n+x_n+2=b₂

.........................................

a_i,1x₁+a_i,2x₂+...a_i,nx_n+R_i=b_i

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов  целевой функции F меняются на противоположные a_0,n=-a_0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, x_n+m , к каждому i-му условию-равенству добавляем искусственную переменную R_i.

 

 

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче (Табл. 10).

                                                                                              Таблица 10

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
Ri	ai,1	ai,2	...	ai,n-1	ai,n	bi
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm
M	-∑ai,1	-∑ai,2	...	-∑ai,n-1	-∑ai,n	-∑bi

Шаг 1. Проверка на допустимость.

Проверяем на положительность  элементы столбца b (свободные члены), если среди них нет отрицательных  то найдено допустимое решение (решение  соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.

Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.

Если после перерасчета  в столбце свободных членов остались отрицаетельные элементы, то переходим  к первому шагу, если таких нет, то ко второму.

Шаг 2. Проверка на оптимальность. 

На предыдущем этапе  найдено допустимое решение. Проверим его на оптимальность Если среди  элементов симплексной таблицы, находщихся в строках M и F(не беря в  расчет элемент b₀- текущее значение целевой функции и элемент -∑b_i) нет отрицательных, то найдено оптимальное решение.

2.1 Положительность строки M

Если в строке M есть отрицательные элементы то решение  требует улучшения. Выбираем среди  отрицательных элементов строки M максимальный по модулю (исключая -∑b_i)

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для которой  это отношение минимально - ведущая.  Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2.

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

Если в строке M и  в столбце свободных членов все  элементы положительные, то переходим  к шагу 2.2.