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

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

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

ЗАДАЧА О РАЦИОНАЛЬНОМ ПИТАНИИ.

Имеется четыре вида продуктов питания: П₁, П₂, П₃, П₄.

Известна стоимость единицы каждого продукта с₁, с₂, с₃, с₄.

Из этих продуктов необходимо составить пищевой рацион, который должен содержать не менее

b₁ единиц белков, b₂ единиц углеводов, b₃ единиц жиров.

Причем известно, что в единице продукта П₁ содержится a₁₁ единиц белков, a₁₂ единиц углеводов и a₁₃ единиц жиров и т.д.

Требуется составить пищевой рацион, чтобы обеспечить заданные условия при минимальной стоимости.

Пусть x₁, x₂, x₃, x₄ — количества продуктов П₁, П₂, П₃, П₄, входящих в рацион. Тогда общая стоимость рациона равна

(1)

Запишем ограничения в виде неравенств.

В одной единице продукта П₁ содержится a₁₁ единиц белка.

В x₁ единицах — a₁₁x₁; в x₂ единицах продукта П₂ содержится a₂₁x₂ единиц белка и т.д.

Общее количество белков не должно быть больше b₁. Исходя из этого, получается следующее ограничение:

(2)

Запишем аналогичные условия для жиров и углеводов:

(3)

Принимая во внимание, что x₁, x₂, x₃, x₄ — положительные величины, получаем еще 4 ограничения:

(4)

Таким образом, получилась следующая математическая задача: найти значения переменных x₁, x₂, x₃, x₄, удовлетворяющие системе ограничений (2) - (4), при которых линейная функция (1) обращалась бы в минимум.

В задачах на экстремум функция L называется функцией цели.

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

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

Найти такие значения действительных переменных x ₁, x ₂, …, x_n для которых целевая функция

(5)

принимает максимальное (минимальное) значение на множестве точек, координаты которых удовлетворяют условиям

(6)

Здесь коэффициенты a_ij, b_i, c₀, c_j (i =1.. m, j =1.. n) – действительные числа.

В матричном виде ЗЛП можно сформулировать так. Максимизировать (минимизировать) функцию

F =c₀+ C × x (7)

при условии, что

A×x = b и x ³0, (8)

где

c =(c₀, c₁, c₂, …,c_n) – вектор строка,

x =(x ₁, x ₂, …, x _n) – вектор столбец,

A ={ a_ij } _{m ´ n} – матрица коэффициентов системы ограничений,

b =(b₁, b₂, …,b _m) – вектор столбец системы ограничений.

Если в дополнительных условиях имеется неравенство

,

то его можно свести к равенству, добавив вспомогательную переменную x_{n +1}³0:

Нетрудно установить связь между задачами максимизации и минимизации:

max F =– min (– F).

Поиск по сайту: