Вычисление нового базисного решения

Исключаемой (из базисных) переменных является .

Именно ее следует ввести в состав базисных переменных

Пример

Определение базисных решений

Преобразование задачи в стандартную форму

1. Преобразовать неравенства в равенства;

2. Преобразовать свободные переменные в неотрицательные;

3. Целевая функция должна минимизироваться или максимизироваться.

Пример:

 

- свободная переменная (без ограничений).

 

Свободную переменную можно представить как разность двух неотрицательных переменных:

Далее выполним следующие действия:

1. Вычтем из левой части первого неравенства дополнительную переменную х₄ и затем умножим все неравенство на -1, для того, чтобы правая часть неравенства стала положительной.

2. Добавим дополнительную переменную х₅ к левой части второго неравенства.

3. Т.к. третье ограничение изначально записано в виде равенства, то оставляем его без изменений.

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

 

 

 

 

 

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

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

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

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

Количество базисных решений не превосходит .

 

 

 

Приведем к стандартной форме

 

 

 

 

 

ЗЛП в стандартной форме можно представить в виде след. таблицы.

базис								Решение
		-5	-4
		-1

Допустимое решение , ,

Базисное решение , , ,

Какая переменная дает наибольший рост функции ?

базис			Точка пересечения	Комментарий
			24/6 = 4 > 0	минимум
			6/1 = 6 > 0
	-1		1/(-1) = -1	не подходит
			2/0 = ∞	не подходит

 

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

Ведущий столбец, ведущая строка и ведущий элемент.

базис
		-5	-4
		-1

 

1. Вычисление элементов ведущей строки

- заменяем на ;

- все элементы ведущей строки (теперь это ) делим на ведущий элемент (6)

базис
	0/6	6/6	4/6	1/6	0/6	0/6	0/6	24/6

 

 

2. Вычисление элементов остальных строк (включая )

- вычисление -строки

новая -строка = текущая -строка - (пересечение -строки с ведущим столбцом) × (новая ведущая строка)

 

базис
			-2/3	5/6
	0/6		2/3	1/6

- вычисление -строки

новая -строка = текущая -строка - (пересечение -строки с ведущим столбцом) × (новая ведущая строка)

 

базис
			-2/3	5/6
	0/6		2/3	1/6
			4/3	-1/6

- вычисление -строки

новая -строка = текущая -строка - (пересечение -строки с ведущим столбцом) × (новая ведущая строка)

 

базис
			-2/3	5/6
	0/6		2/3	1/6
			4/3	-1/6
			5/3	1/6

- вычисление -строки

новая -строка = текущая -строка - (пересечение -строки с ведущим столбцом) × (новая ведущая строка)

 

базис
			-2/3	5/6
	0/6		2/3	1/6
			4/3	-1/6
			5/3	1/6

Новое базисное решение , , ,

Новое уравнение

 

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

Определим исключаемую переменную

базис			Точка пересечения	Комментарий
	2/3		4/(2/3) = 6 > 0
	4/3		2/(4/3) = 3/2 > 0	минимум
	5/3		5/(5/3) = 3
			2/1 = 1

 

базис
			-2/3	5/6
			2/3	1/6
			4/3	-1/6
			5/3	1/6

 

Перерасчет таблицы