4.3. Задача о диете.

Рассмотрим задачу о составлении рациона питания. Пусть в рацион входят n видов различных продуктов Р₁,…,Р_n. Данные продукты должны обладать определенными свойствами (иметь определенное количество калорий, белков, жиров, углеводов, витаминов и т.д.). Эти характеристики продуктов обозначим К₁,…,K_m. Обозначим через a_ij , i=1,…,n, j=1,…,m количество j-ой характеристики в единице продукта Р_i , а через х_i – количество продукта Р_i. При этом суммарные характеристики рациона должны удовлетворять некоторым условиям (например, могут накладываться условия на общую калорийность, на суммарное количество витаминов и минеральных элементов и т.д.) Обозначим эти суммарные характеристики (допустимые величины) b₁, b₂,…, b_m.

Составим таблицу характеристик продуктов

	Р1	Р2	…	Рn	Допустимые величины
K1	a11	a12	…	a1n	b1
K2	a21	a22	…	a2n	b2
…	...	…	…	…	…
Km	am1	am2		amn	bm

Общее количество характеристики К₁ в рационе равно

и по физиологическим требованиям эта величина не должна быть менее b₁. Поэтому имеет место условие

(7)

Конечно, возможны и ограничения типа

(например, низкокалорийная диета), однако такие ограничения легко сводятся к виду (7) умножением обеих частей неравенства на (-1).

Кроме того, возможны ограничения типа равенства (например, в лечебных диетах, где как недостаток, так и передозировки некоторых веществ недопустимы). Будем считать, что для характеристик К₁,…,K_s имеются ограничения типа неравенства, а для характеристик К_s+1,…,K_m - ограничения типа равенства. Тогда получим систему ограничений

(8)

Очевидно,

х₁≥0,…, х_n≥0 . (9)

Если с_i – цена единицы продукта Р_i, то общая стоимость рациона питания будет равна

f( (10)

Задачей о диете называют следующую задачу; найти значения переменных удовлетворяющие условиям (8) и (9) и доставляющие функции (10) наименьшее значение.

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

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

• эти значения удовлетворяют некоторой системе, содержащей конечное число линейных уравнений или неравенств;

• при искомых значениях некоторая линейная функция от этих переменных обращается в минимум (максимум);

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

Из рассмотренных нами примеров можно выделить три формы задач линейного программирования.