Проблема "двух картошек"

Пример 1.2.

Проблема “двух картошек”. Фирма по переработке картофеля производит три вида продукции: картофельные дольки, кубики и хлопья. Анализ загруженности оборудования и спроса на рынке показывает возможность произвести и сбыть до %%1.8%% тонн долек, %%1.2%% тонн кубиков и %%2.4%% тонн хлопьев. Необходимый для переработки картофель фирма закупает у двух поставщиков. Количество готовой продукции и относительная прибыль (доход от реализации готовой продукции за вычетом стоимости сырья), которые можно получить из одной тонны картофеля каждого поставщика, указаны в таблице ниже.

Исходные данные задачи о “двух картошках”

Вид готовой продукции	Выход готовой продукции из %%1%% %%т%% картофеля, %%т%%		Потребности рынка сбыта, %%т%%
	Поставщик 1	Поставщик 2
Дольки	%%0.2%%	%%0.3%%	%%1.8%%
Кубики	%%0.2%%	%%0.1%%	%%1.2%%
Хлопья	%%0.3%%	%%0.3%%	%%2.4%%
Относительная прибыль, ден. ед.	%%5.0%%	%%6.0%%

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

Перейдем от содержательного описания ситуации к формализованному. Введем неизвестные %%x_1%% и %%x_2%% - количество картофеля (в тоннах, %%т%%), закупаемого у поставщиков 1 и 2 соответственно. Используя три первые строки таблицы, составим балансовые соотношения

$$ \begin{array}{ll} 0.2 x_1 + 0.3 x_2 \leq 1.8~~~~~~~~~ \text{(для долек),}\\ 0.2 x_1 + 0.1 x_2 \leq 1.2~~~~~~~~~ \text{(для кубиков),}\\ 0.3 x_1 + 0.3 x_2 \leq 2.4~~~~~~~~~ \text{(для хлопьев).} \end{array} $$

В левой части каждого неравенства записан выход готовой продукции из закупленного картофеля, а в правой части – предельные потребности в продукции на рынке сбыта. Физические размерности сравниваемых величин в балансовых соотношениях одни и те же – %%т%%. Относительная прибыль %%\mathrm{П}%% подсчитывается с помощью последней строки таблицы и в ден. ед. равна $$ \mathrm{П} (x_1, x_2) = 5 x_1 + 6 x_2. $$

По смыслу задачи необходимо найти такие значения неизвестных %%x_1%% и %%x_2%%, которые обеспечивают максимальную относительную прибыль $$ \mathrm{П} (x_1, x_2) = 5 x_1 + 6 x_2 \to \max~~~~~~~~~~~~~~~~(1.6) $$ и удовлетворяют ограничениям типа неравенства (балансовым соотношениям для долек, кубиков и хлопьев) $$ \begin{array}{ll} 0.2 x_1 + 0.3 x_2 \leq 1.8,&~~~~~~~~~~~~~~~~(1.7)\\ 0.2 x_1 + 0.1 x_2 \leq 1.2,&~~~~~~~~~~~~~~~~(1.8)\\ 0.3 x_1 + 0.3 x_2 \leq 2.4,&~~~~~~~~~~~~~~~~(1.9)\\ x_1 \geq 0, x_2 \geq 0. &~~~~~~~~~~~~~~~~(1.10) \end{array} $$

Условия неотрицательности (1.10) добавлены к балансовым соотношениям (1.7) — (1.9), исходя из физического смысла неизвестных.

Полученная задача называется задачей линейного программирования. Отличительная ее особенность состоит в линейности всех функций, задающих целевое условие (1.6), ограничения (1.7) — (1.9) и условия неотрицательности (1.10).