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

Модели линейного программирования

Лекции

по дисциплине:

“МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ”

Модели линейного программирования находят широкое применение при решении плановых задач в различных сферах хозяйственной деятельности.

Задача линейного программирования (ЗЛП) в общем виде формулируется следующим образом. Требуется найти экстремум (минимум или максимум) целевой функции

n

Z(x) = ∑ c_j x_jàmax (min) (1)

i=1

при ограничениях:

n

∑ a_ij x_j ≤ (≥) b_i i=1,2, …,m (2)

i=1

x_j ≥ 0, j= 1,2,…,n. (3)

где c_j – затраты в случае минимизации и доход в случае максимизации;

a_ij - удельные затраты i-го ресурса на единицу выпуска j-го продукта;

b_i - лимиты ресурсов или количественное выражения спроса в зависимости от смыслового наполнения величины b_i;

x_j – искомые количества j-го продукта.

Система ограничений (2) говорит о том, что в случае ограниченности ресурсов их расход не может быть превышен (ограничения со знаком ≤), и в случае трактовки b_i как характеристик спроса (ограничения со знаком ≥) означает, что потребности (спрос) должны быть полностью удовлетворены или превышены.

Ограничение (3) – традиционное ограничение на неизвестные с экономическим смыслом, т.е. либо искомые объемы продукции выпускаются (x_i≥0), либо нет (x_i=0).

Упорядоченная совокупность чисел (x₁, x₂, …,x_n), которая удовлетворяет ограничениям (2-3), называется допустимым решением или допустимым планом задачи линейного программирования.

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

Кроме того, множество допустимых решений является выпуклым. Множество называется выпуклым, если вместе с двумя точками ему принадлежит и отрезок, их соединяющий. Не все точки выпуклого множества равнозначны между собой. Точки, которые не являются внутренними точками ни одного из отрезков, соединяющих две точки выпуклого множества, называются угловыми точками.

Справедлива теорема: на множестве допустимых решений линейная функция цели задачи линейного программирования достигает экстремума в угловой точке.

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

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

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

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