18. Задача линейного программирования. Понятия допустимого и оптимального плана.

Наиболее разработанными являются методы решения задач линейного программирования¹. В общем виде задача линейного программирования заключается следующем: найти значения переменных х1, х2, …, хn, доставляющие оптимальное значение целевой функции:

F=c1x1+c2x2+ ... +сnхnmin (max) (9.3)

при выполнении ограничений:

а11х1+а12х2+ …+а1nхn{, =, }b1

а21 х1+а22х2+ …+а2nхn{, =, }b2

……… (9.4)

аm1х1+аm2x2+ …+аmnхn{, =, }bm

xj>=0, (i=1…n) (9.5)

где аij, bi , cj –заданные постоянные величины, m – число уравнений, n – число переменных.

Ограничения (9.5) с математической точки зрения являются необязательными, но в моделях экономических задач они, как правило, всегда присутствуют. Это связано с экономическим смыслом переменных х1, х2, …, хn. Например, если под xi понимается количество продукции вида i, которое необходимо выпускать на предприятии, то очевидно, что оно не может быть отрицательным.

Систему ограничений (9.4) называют функциональными ограничениями, а ограничения (9.5) – прямыми. Вместе ограничения (9.4) и (9.5) определяют область допустимых решений.

Набор значений переменных х1, х2,…,хn, при котором выполняются все ограничения, называется допустимым решением или планом. Допустимое решение, при котором функция F принимает оптимальное значение, называется оптимальным.