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

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

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

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

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

 

 

 

 

 

 

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

                                                                                      Таблица 2

	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
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

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

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

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

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

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

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

Если в строке F есть отрицательные элементы, то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b₀) a_0,l=min{a_0,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) включается в базис.

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

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

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

Правила преобразований симплексной таблицы. 

При составлении новой симплекс-таблицы в ней происходят следующие изменения: 

• вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.  
• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l
• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l
• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l
• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,lx a_k,j/ a_k,l

Схему преобразования элементов  симплекс-таблицы (кроме ведущей  строки и ведущего столбца) называют схемой ”прямоугольника”. (Схема 1)        

Схема 1

Преобразуемый элемент a_i,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

1.5 Метод искусственного  базиса

Для применения алгоритма  симплекс-метода система ограничений  должна быть разрешена относительно исходного базиса. Однако в некоторых  задачах линейного программирования базис усматривается не сразу. В  этом случае используется метод «искусственного» базиса. Этот метод заключается в применении правил симплекс-метода к специальной задаче линейного программирования. Она получается из исходной задачи линейного программирования, записанной в канонической форме, добавлением в левые части уравнений системы ограничений, не имеющих предпочтительного вида, «искусственных» неизвестных   В целевую функцию неизвестные   вводят с коэффициентом М [–М] для задачи минимизации [максимизации], где М – достаточно большое положительное число. Составленная таким образом задача называется М–задачей линейного программирования. В процессе решения М–задачи следует вычёркивать из симплекс–таблицы «искусственные» неизвестные   по мере их выхода из базиса. Если все «искусственные» неизвестные вышли из базиса, то получаем исходную задачу линейного программирования. Если оптимальное решение М–задачи содержит хотя бы одну «искусственную» неизвестную или М–задача неразрешима, то исходная задача линейного программирования также неразрешима. Реализацию метода «искусственного» базиса рассмотрим на следующем примере.

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

с системой ограничений

 

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

 

Решение. Задача линейного программирования записана в общей форме.

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

ограничений неотрицательные  балансовые неизвестные   следующим образом:

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

Составим М–задачу линейного программирования, для чего в левые части второго и третьего уравнений системы введём неотрицательные «искусственные» неизвестные   и  :

 

 

 

а в правую часть целевой функции  добавим слагаемые   и  :

 

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

 

Начальным опорным решением будет план

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

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

правой части целевая  функция примет вид:

Заполним начальную  симплекс-таблицу (табл. 3). Последняя строка табл. 8.1 содержит три положительных числа: 3M−3, 8M−2 и 3M−3, следовательно, начальное опорное решение M−задачи линейного программирования не является оптимальным, т. е. не доставляет целевой функции минимальное значение. Выберем столбец, соответствующий наибольшему положительному числу в последней строке.

 

 

Поскольку М – достаточно большое положительное число, выбираем и отмечаем вертикальной стрелкой столбец неизвестной  .

 

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

 

 

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

 

 

Новая симплекс таблица  содержит в последней строке единственное положительное число: M−5/2. Отметим столбец неизвестной   вертикальной стрелкой и убедимся в том, что в его строках есть положительные числа. Найдём частные от деления свободных членов табл. 8.2 на соответствующие положительные числа выделенного столбца (припишем их к табл. 8.2 справа).

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

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

записанную в канонической форме.                                   

                                                                                                             Таблица 5

Базис	Свободные члены
	3/4	13/8	0	1	1	1/8	3/4
	1/4	3/8	1	2	0	−1/8	1/4
	1	0	0	1	0	0	−1
Форма L	7/2	−9/4	0	0	0	−1/4	−5/2

 

 

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

 

 

 

а соответствующее значение целевой функции равно   

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

   

 

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

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

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