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

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

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

Методами математического программирования решаются задачи о распределении ресурсов, планировании выпуска продукции, ценообразовании, транспортные задачи и т.п.

Математическое программирование включает в себя такие разделы математики, как линейное, нелинейное и динамическое программирование.

Построение математической модели экономической задачи включает следующие этапы:

·        выбор переменных задачи;

·        составление системы ограничений;

·        выбор целевой функции.

Переменными задачи называются величины x₁, x₂,…, x_n, которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора Х=(x₁, x₂,…, x_n).

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

Целевой функцией называют функцию переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти.

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

Общая математическая формулировка задачи линейного программирования выглядит следующим образом.

Дана система линейных уравнений

a₁₁x₁+a₁₂x₂+…+a_1nx_nb₁,

a₂₁x₁+a₂₂x₂+…+a_2nx_nb₂,

…………………………                                                                   (1.1)

a_m1x₁+a_m2x₂+…+a_mnx_nb_m,

и линейная функция

Z(x) = c₁x₁+c₂x₂+ ... +c_nx_n→max(1.2)

Требуется найти такие неотрицательные решения х₁ 0, х₂0 ... х_n 0 (1.3) системы (1.1) при которых функция принимает наименьшее (наибольшее) значение.

Уравнения (1.1) называются ограничениями данной задачи, уравнение (1.2) называется линейной формой (целевая функция), а уравнение (1.3), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым.

         Наиболее часто встречаются две разновидности задачи линейного программирования:

1.     Каноническая задача линейного программирования. В этом случае система (1.1), помимо тривиальных ограничений (1.3), включает в себя только уравнения.

2.     Стандартная задача линейного программирования. Это означает, что система (1.1), состоит только из неравенств, в число которых входят тривиальные ограничения (1.3)