Линейное программирование

Линейное программирование – это раздел математики, ориентированный на нахождение экстремума (максимума или минимума) в задачах, которые описываются линейными уравнениями. Причем, линейным уравнением описывается как сама целевая функция, так и переменные (входные параметры).

Необходимым условием задач линейного программирования является обязательное наличие ограничений на ресурсы (сырье, материалы, финансы, спрос).

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

Критерий оптимальности дожжен удовлетворять следующим требованиям:

1) Быть единственным для данной задачи;

2) Измеряться в единицах количества;

3) Линейно зависеть от входных параметров.

Стандартная задача линейного программирования – задача, в которой требуется определить максимальное либо минимальное значение целевой функции при ограничениях неравенств и условиях.

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

Сформулируем задачу линейного программирования в общем виде:

1) Найти экстремум целевой функции:

F(x)= ) (1)

2) При ограничениях в виде равенств:

(2)

3) При ограничениях в виде неравенств:

(3)

4) При условиях неотрицательности входных параметров:

(4)

5) В краткой форме задача линейного программирования может быть записана:

(5)

При условии:

при j=1,2,…,m; (6)

где – входные переменные,

– числа положительные, отрицательные, равные нулю.

В матричной форме эта задача может быть записана:

Cx→max, при Ax≤bили Ax ≥ b, x≥ 0 (7)

		…
		…
		…
		…
		…