Типы распределительных задач

1. Простые распределительные задачи:

2. Задачи с однородными ресурсами и разнородными потребностями:

(столбцы матрицы с элементами l_ij одинаковы)

3. Задачи с разнородными взаимозаменяемыми ресурсами и однородными потребностями:

(строки матрицы одинаковы)

4. Задачи с пропорциональными ресурсами:

, где – элементы строки матрицы , принятой за единичную.

Ресурсы и потребности неоднородны (строки матрицы , элементы которой устанавливают связь между единицами ресурсов и потребностей, пропорциональны). Числа называют индексами i-тых ресурсов.

5. Распределительные задачи общего вида.

Приведение к ТЗ

2.

3.

4. .

Подставим в модель:

Обозначим

5. В этом случае распределительная задача не можетбыть приведена к транспортной. Для ее решения может быть использованы методы, предназначенные для решения распределительных задач (например, обобщенный метод потенциалов).

Таким образом задача о назначениях – частный случай ТЗ, а распределительная задача – ее обобщение.

Пример

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

А) Пусть имеется m видов оборудования с ресурсами а₁ … а_m станко/ч, и n видов выпускаемых изделий с плановыми заданиями на выпуск b₁ … b_n. l_ij – производительность i-того оборудования при изготовлении j-го изделия (руб/ч).

Модель:

(ограничения по ресурсам)