Симплексный метод с использованием М- базиса

б). существует номер  такой, что , тогда выполняется пункт 9.

9. Пусть – множество всех индексов , для которых : . Номер определяется из условия: Коэффициент – называется разрешающим элементом симплекс-таблицы, строка – разрешающей строкой, а столбец – разрешающим столбцом.

 

 

10. Переходим к следующей симплекс-таблице по правилам:

а). в левом столбце записываем новый базис: вместо старой базисной переменной – переменную ;

б). в столбцах, соответствующих  базисным переменным, проставляем нули и единицы: 1 – против «своей»  базисной переменной, 0 – против «чужой»  базисной переменной, 0 – в нижней строке (где  ) для всех базисных переменных;

в). новую строку с номером  (для новой базисной переменной ) получаем из старой разрешающей строки делением ее на разрешающий элемент : , ;

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

Затем переходим к пункту 7 и  т. д.

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

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

 

 

Первая симплекс-таблица (таблица 7) имеет вид:

 

	св. чл.						оценка
	27	3	0	1	0	0	9
	30	0	2	0	1	0
	20	1	1	0	0	1	20
	0	-2	-1	0	0	0

 

Таблица 7.

 

 

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

1). в новой симплекс-таблице в  первом столбце вместо переменной  пишем новую базисную переменную ;

2). расставляем единицы и нули  по правилу, описанному в п. 10 б);

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

4). вторую строку переписываем  без изменений, так как в  разрешающем столбце уже стоит  ноль;

5). в старой симплекс-таблице  разрешающую строку  умножаем на коэффициент и складываем с третьей строкой – получаем третью строку новой симплекс-таблицы;

6). в старой симплекс-таблице  разрешающую строку  умножаем на коэффициент и складываем с нижней строкой – получаем нижнюю строку новой симплекс-таблицы (таблица 8).

 

	св. чл.						оценка
	9	1	0	1/3	0	0
	30	0	2	0	1	0	15
	11	0	1	-1/3	0	1	11
	18	0	-1	2/3	0	0

 

Таблица 8.

 

 

Аналогичным образом строим третью симплекс-таблицу (таблица 9).

 

	св. чл.
	9	1	0	1/3	0	0
	8	0	0	2/3	1	-2
	11	0	1	-1/3	0	1
	29	0	0	1/3	0	1

 

Таблица 9.

Так как все элементы нижней строки симплекс-таблицы неотрицательны, выписываем решение задачи: ;   

 

 

 

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

 

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

Алгоритм выбора начального базиса.

1. Задача ЛП в канонической форме

,

 (1)

 

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

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

,

 (2)

. 

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

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

 

 

 

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

а). если , то допустимое множество исходной задачи (1) пусто;

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

5. Процедурой симплекс-метода получаем искомое решение задачи (1).

 

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

 

Пример 1 . Решить задачу ЛП:

Рассмотрим вспомогательную задачу ЛП:

Найдем  . Тогда

 

	2	2	-1	-1	1	1	0	2
	1	-1	-3	1	1	0	1	1
	5	2	3	2	3	0	0
	-3	-1	4	0	-2	0	0

 

 

	1	3	2	-2	0	1
	1	-1	-3	1	1	0
	2	5	12	-1	0	0
	-1	-3	-2	2	0	0

 

	1/3	1	2/3	-2/3	0
	4/3	0	-7/3	1/3	1
	1/3	0	26/3	7/3	0
	0	0	0	0	0

 

  ;  .

 

 

 

Пример 2. Решить задачу ЛП:

Рассмотрим вспомогательную задачу ЛП:

 

Найдем  . Тогда

 

	1	-1	1	-1	0	0	1	1
	3	-1	1	0	1	0	0	3
	3	1	0	0	0	1	0
	0	-1	-2	0	0	0	0
	-1	1	-1	1	0	0	0

 

	1	-1	1	-1	0	0
	2	0	0	1	1	0
	3	1	0	0	0	1
	2	-3	0	-2	0	0
	0	0	0	0	0	0

 

	4	0	1	-1	0	1
	2	0	0	1	1	0
	3	1	0	0	0	1
	11	0	0	-2	0	3

 

 

	6	0	1	0	1	1
	2	0	0	1	1	0
	3	1	0	0	0	1
	15	0	0	0	2	3