Мощности предприятий

Задача размещения с ограничениями по

Задача размещения без ограничений

Модели размещения производства

Модели этого типа имеют несколько приложений в экономической практике, например:

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

Постановка задачи размещения предприятий, производящих некоторую однородную продукцию, имеет такой вид.

Задано множество пунктов возможного размещения предприятий (или других объектов размещения) . При этом известны затраты на размещение предприятия в каждом из этих пунктов - .

Известно множество потребителей - и соответствующие им объемы потребностей в продукции на интервале времени . Заданы и затраты на производство и доставку продукции потребителю в пределах интервала времени .

Задача размещения заключается в выборе множества пунктов размещения таким образом, чтобы суммарные издержки были минимальными. При этом подмножество предприятий из множества может быть любым в количестве от 1 до . Ограничения на мощность предприятий не накладываются.

Целевая функция имеет вид:

Отсюда критерий:

.

Параметры и данные задачи можно представить и в табличном виде:

Первое слагаемое в ЦФ – это единовременные издержки, а второе – издержки производства (и логистики), где суммируются издержки по всем потребителям, а каждое слагаемое соответствует издержкам того предприятия из множества , для которого они минимальны.

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

Пример. Пусть имеется 3 места размещения, т.е. и 2 потребителя, т.е. . Вектор единовременных затрат . Матрица издержек производства и логистики:

.

Решим эту задачу перебором вариантов. Все варианты подмножеств следующие:

.

Вычислим все значения ЦФ:

Наименьшим суммарным издержкам соответствует вариант .

▲

Для этого варианта задачи кроме данных предыдущей модели вводятся следующие элементы:

- вектор максимально возможных объемов производства (предельной производительности) в пунктах размещения;

- матрица потребностей j-го потребителя в продукции i-го предприятия.

Вводятся также следующие переменные:

ЦФ для этой задачи имеет вид:

Тогда задача оптимального размещения примет вид:

при ограничениях:

1. каждый потребитель может обслуживаться только одним производством:

;

2. суммарный объем потребностей всех потребителей любого j-го производства не должен превышать его предельной производительности:

;

3. искомые переменные могут принимать только булевы значения:

.

Эта задача относится к классу задач целочисленного (булева) линейного программирования и может быть решена одним из методов условной оптимизации.