Постановка задачи линейного программирования

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

(9.1)

при условиях

	(9.2)
	(9.3)
	(9.4)

где - заданные постоянные величины и .

Функция (9.1) называется целевой функцией (или линейной формой) задачи (9.1)-(9.4), а условия (9.2)-(9.4) – ограничениями данной задачи.

Канонической или о сновной задачей линейного программирования называется задача, которая состоит в определении максимального значения функции

(9.5)

при выполнении условий:

	(9.6)
	(9.7)

где .

Определение 9.1. Вектор-столбец , координаты которого удовлетворяют всем ограничениям задачи, называется допустимым вектором или планом ЗЛП.

План , при котором целевая функция задачи (9.5) принимает свое максимальное (минимальное значение), называется оптимальным.

Вектор - вектор-строка коэффициентов линейной формы задачи. Вектор - вектор ограничений ЗЛП. Вектора - вектора условий. Матрица - матрица условий размерности .

Каноническая ЗЛП (9.5) - (9.7), может быть записана также в векторной форме:

или более компактно – в матричной форме:

Любую ЗЛП можно привести к канонической форме.

Дата добавления: 2014-01-06