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

 

Питательное вещество	Продукт
F1	F2	…	Fn
N1	α11	α12	…	α1n
N2	α21	α22	…	α2n
…	…	…	…	…
Nm	αm1	αm2	…	αmn

 

Предположим, что диетолог уже выбрал диету, т.е. определил, что человек должен за месяц потреблять η₁ кг продукта 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

 

Потребовав его неотрицательности наряду с остальными неизвестными, получим, что условие x_{n + 1} ≥ 0 превращает (7.84) в (7.83). Введя по отдельному дополнительному неизвестному для каждого из неравенств, получим систему уравнений, равносильную исходной системе неравенств. Пример. Дана система неравенств

Сведем ее к системе уравнений. Получим

После оптимизации значениями дополнительных неизвестных следует пренебречь.