Решение

Пример.

БП	СЧ			CO

	0₊		-5	-
	-3	-2	-1	3
		-4
F			-5

БП	СЧ			CO
		-2	1	0
			-5	-
	3		-1	-
		-6
F			-5

Опорное решение. Т.к. нельзя выбрать разрешающий столбец с двумя отрицательными элементами, то работаем по общим правилам.

БП	СЧ
		-2

	3
		-4	-1
F

Решение опорное и оптимальное.

Ответ:

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

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

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

В ходе преобразований столбцы под “переброшенными” наверх нулями можно вычеркивать. Подлежат вычеркиванию и строки, состоящие из одних нулей.

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

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

Пример. Найти минимум целевой функции: