Задача о смесях

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

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

Пусть х_i – количество i-го вида сырья в смеси; т – количество видов сырья; п – количество ингредиентов в смеси; а_ij – количество ингредиента j-го вида, содержащегося в единице i-го вида сырья; b_j – минимальное количество ингредиента j-го вида, содержащегося в единице смеси; с_i – стоимость единицы сырья i-го вида; q – минимальный общий вес смеси, используемый фирмой.

Для построения экономико-математической модели условие задачи удобно представить в таблице 2.3.

Таблица 2.3

В единице сырья первого вида содержится а₁₁ единиц первого ингредиента, а во всем сырье первого вида этого ингредиента будет а₁₁х₁. Этого же ингредиента в единице сырья второго вида содержится а₁₂ единиц, а во всем сырье второго вида этого ингредиента будет а₁₂х₂ и так далее, а_1nх_n – количество первого ингредиента в п-м виде сырья. Общее количество сырья первого вида, содержащегося во всех смесях равно

а₁₁х₁ + а₁₂х₂ + … + а_1nх_n.

Поскольку известно, что минимальное количество ингредиента первого вида, содержащегося в единице смеси, должно быть b₁ , имеем следующее ограничение

а₁₁х₁ + а₁₂х₂ + … + а_1nх_n b₁ .

Рассмотрим второй вид ингредиента. Необходимо учесть содержание этого ингредиента во всем количестве смеси первого сырья, второго и т.д. до п-го вида сырья. Суммируя отдельные значения количества единиц второго вида ингредиента во всех смесях, получим общее количество второго вида ингредиента. Она должно быть не меньше минимального количества ингредиента второго вида, содержащегося в единице смеси b₂. Аналогично предыдущим рассуждениям, можно установить соотношения между содержанием ингредиента любого вида во всех смесях и минимальным количеством этого ингредиента в смеси. В результате придем к системе ограничений на питательность смеси:

а11х1 + а12х2 + … + а1nхn b1. а21х1 + а22х2 + … + а2nхn b2, ………………………………. ат1х1 + ат2х2 + … + атnхn bт.

Переменные х₁, х₂, …, х_n , представляющие собой количества ингредиента первого, второго и т.д., до п-го вида, не могут быть отрицательными. В случае, если какой-либо ингредиент не входит в состав смеси, то соответствующая переменная будет равно нулю. Таким образом, придем к системе ограничений на неотрицательность переменных

х₁ 0, х₂ 0, …, х_n 0.

В связи с тем, что известен минимальный общий вес смеси q, используемый фирмой, придем к ограничению на расход смеси

х₁ + х₂ + … + х_n q.

Зная, что цена единицы сырья первого вида с₁, можем вычислить стоимость всего сырья первого вида – с₁х₁. Аналогично стоимость всего сырья второго вида – с₂х₂ и т.д., стоимость всего сырья п-го вида – с_nх_n. Суммарная стоимость всех видов сырья, используемых в приготовлении смеси, равна сумме всех этих стоимостей.

Таким образом задача о смесях заключается в нахождении величин , , …, х_n , удовлетворяющих ограничениям

а11х1 + а12х2 + … + а1nхn b1. а21х1 + а22х2 + … + а2nхn b2, ………………………………. ат1х1 + ат2х2 + … + атnхn bт. х1 + х2 + … + хn q. х1 0, х2 0, …, хn 0

и дают минимум целевой функции

z = с₁х₁ + с₂х₂ +…+ с_nх_n.