Матрица питательности

Предположим, что диетолог уже выбрал диету, т.е. определил, что человек должен за месяц потреблять η₁ кг продукта F₁,..., η_n кг продукта F_n. Полное количество питательного вещества N₁ будет

По условию требуется, чтобы его, по крайней мере, хватило

η₁α₁₁ + η₂ α₁₂ +…+ η_n α_1n ≥ γ₁

Точно то же и для остальных веществ. В целом

η₁α_i1 + η₂ α_i2 +…+ η_n α_in ≥ γ_i (i = 1, 2,… m)

Эти условия определяют наличие минимума необходимых питательных веществ. Диета, для которой выполнены условия (7.78) - допустимая диета. Предположим, что из всех допустимых диет должна быть выбрана самая дешевая. Пусть π_i - цена 1 кг продукта F_i. Полная стоимость диеты, очевидно,

S = π₁η₁ + π₂η₂ +… + π_nη_n. (7.79)

Таким образом, мы пришли к задаче: найти неотрицательное решение η₁, …, η_n системы неравенств (7.78), минимизирующее выражение (7.79).

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

1) все эти значения были неотрицательны;

2) удовлетворяли системе линейных уравнений или линейных неравенств;

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

Запишем это с помощью формул: дана система линейных уравнений и неравенств

(7.80)

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

f = c₁x₁ + c₂x₂ + … + c_nx_n (7.81)

Требуется найти такое неотрицательное решение

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0

системы (7.80), чтобы функция f принимала наименьшее (или наибольшее) значение.

Условия (7.80) называют ограничениями данной задачи, а функцию f - целевой функцией (или линейной формой). В приведенных выше примерах ограничения имели вид не уравнений, а неравенств. Заметим, что ограничения в виде неравенств всегда можно свести к системе в виде равенств (способом введения добавочных неизвестных).

Так, для неравенства

a_i1x₁ + a_i2x₂ + … + a_inx_n ≥ b_i

вводя добавочное неизвестное x_{n +1}, получаем

x_{n +1} = a_i1x₁ + a_i2x₂ + … + a_inx_n - b_i