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

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

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

Пример

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

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

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

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