, . (2.9)
Ограничение по заданному количеству продукции выглядит следующим образом:
,
. (2.10)Задача решается на минимум затрат на производство:
. (2.11)
Необходимо также учесть неотрицательность переменных .
Задача поставлена так, чтобы израсходовать все отведенное время работы машины, т.е. обеспечить полную загрузку машины. При этом количество выпускаемой продукции каждого вида должно быть по крайней мере не менее Nj . Однако в некоторых случаях не допускается превышение плана по номенклатуре, тогда ограничения математической модели изменяются следующим образом:
, (2.12)
,
(2.10)(2.11)
, (2.12)
Пример 2.4. Минимизация дисбаланса на линии сборки.
Промышленная фирма производит изделие, представляющее собой сборку из m различных узлов. Эти узлы изготавливаются на n заводах.
Из-за различий в составе технологического оборудования производительность заводов по выпуску j-го узла неодинакова и равна bij . Каждый i-й завод располагает максимальным суммарным ресурсом времени в течение недели для производства m узлов, равного величине Ti .
Задача состоит в максимизации выпуска изделий, что по существу эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или по нескольким видам узлов.
В данной задаче требуется определить еженедельные затраты времени (в часах) на производство j-го узла на i-м заводе, не превышающие в сумме временные ресурсы 1-го завода и обеспечивающие максимальный выпуск изделий.
Пусть xij - недельный фонд времени (в часах), выделяемый на заводе для производства узла j. Тогда объемы производства узла j будут следующими:
, . (2.15)
Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделии должно быть равно количеству комплектующих узлов, объем производства которых минимален:
(2.16)
Условие рассматриваемой задачи устанавливает ограничение на фонд времени, которым располагает завод i .
Таким образом, математическая модель может быть представлена в следующем виде.
Максимизируем
(2.17)
, (2.18)
для всех i и j.
Эта модель не является линейной, но ее можно привести к линейной форме с помощью простого преобразования. Пусть Y - количество изделий:
(2.19)
Этому выражению с математической точки зрения эквивалентна следующая формулировка: максимизировать Z = Y при ограничениях
, (2.20)
, (2.21)
для всех i и j; .
Пример 2.5. Задача составления кормовой смеси, или задача диете..
Пусть крупная фирма (условно назовем ее «Суперрацион») имеет возможность покупать m различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных компонентов (ингредиентов). Лабораторией фирмы установлено, что продукция должна удовлетворять по крайней мере некоторым минимальным требованиям с точки зрения питательности (полезности). Перед руководством ширмы стоит задана определить количество каждого i-го сырья, образующего смесь минимальной стоимости при соблюдении требований к общему расходу смеси и ее питательности.
Решение
Введем условные обозначения:
xi - количество i-го сырья в смеси;
m - количество видов сырья;
n - количество ингредиентов в сырье;
aij - количество ингредиента j, содержащегося в единице i-го вида сырья;
bj - минимальное количество ингредиента j, содержащегося в единице смеси;
ci - стоимость единицы сырья i;
q - минимальный общий вес смеси, используемый фирмой,
Задача может быть представлена в виде
(2.22)
при следующих ограничениях:
на общий расход смеси:
; (2.23)
на питательность смеси:
, (2.24)
на неотрицательность переменных:
, (2.25)Пример 2.6. Задача составления жидких смесей.
Еще один класс моделей, аналогичных рассмотренным выше, возникает при решении экономической проблемы, связанной с изготовлением смесей различных жидкостей с целью получения пользующихся спросом готовых продуктов.
Представим себе фирму, торгующую различного рода химическими продуктами, каждый из которых является смесью нескольких компонентов. Предположим, что эта фирма планирует изготовление смесей m-видов. Обозначим подлежащее определению количество литров i-го химического компонента, используемого для получения j-го продукта через xij . Будем предполагать, что
, , .Первая группа ограничений относится к объемам потребляемых химических компонентов:
, (2.26)
где Si - объем i-го химического компонента, которым располагает фирма в начале планируемого периода.
Вторая группа ограничений отражает требование, заключающееся в том, чтобы запланированный выпуск продукции хотя бы в минимальной степени удовлетворял имеющийся спрос на каждый из химических продуктов, т.е.
, (2.27)
где Di - минимальный спрос на продукцию у в течение планируемого периода.
Третья группа ограничений связана с технологическими особенностями, которые необходимо принимать во внимание при приготовлении смеси например, простое ограничение, определяемое некоторыми минимально допустимыми значениями, отношения между объемами двух химических компонентов в процессе получения продукта j:
или ,
где r - некоторая заданная константа.
Обозначив через Рij доход с единицы продукции хij запишем целевую функцию:
. (2.28)
Пример 2.7. Задача о раскрое или о минимизации обрезков.
Данная задача состоит В разработке таких технологических планов раскроя, при которых получается необходимый комплекс заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.