Общая распределительная задача

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

Как и в предыдущих примерах, исходные данные задачи можно представить в виде таблицы, где C_ij – доход, прибыль или затраты при выделении единицы ресурса i -го вида на j -ю работу (табл. 4.4):

Таблица 4.4

Виды ресурсов	Работы (операции)	Количество ресурсов
		…	n
	С 11	С 12	…	С 1 n	a 1
	С 21	С 22	…	C 2 n	a 2
…	…	…	…	…	…
m	Cm 1	Cm 2	…	Cmn	am
Потребность	b 1	b2	…	bn

Если C_ij – прибыль или выигрыш, то имеем задачу максимизации, если же C_ij – затраты или убытки, то задачу минимизации.

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

Другим важным частным случаем задачи распределения (и транспортной задачи) является задача о назначениях или задача выбора. Она отличается от общего случая тем, что по условиям задачис каждым ресурсом можно оперировать только как с единым целым, он либо направляется на работу, либо нет. Работе также требуется только один вид ресурса, причем целиком. Иначе говоря,. потребности и ресурсы неделимы. Следовательно, в задаче о назначениях всегда a_i =1, b_j =1 и x_ij – булевы, " ij.

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

Рассмотрим пример общей распределительной задачи.

Пусть с железнодорожной станции необходимо отправить n видов грузов в количестве b_j, j =1, 2, …, n. Станция может использовать m видов вагонов в количестве a_i, i =1, 2, …, m. Для каждого вида вагона известна норма загрузки i –го вагона j – м грузом - B_ij. Известны затраты на погрузку i -го вагона j -м грузом - С_ij. Необходимо организовать отправку груза наилучшим образом, т.е. с минимальными затратами на погрузку.

Как видно, здесь ресурсы – вагоны разных типов (единицы измерения - штуки), а потребность – груз (тонны или м³). Единицы измерения разные, следовательно, это задача общего вида.

Введем переменные x_ij – количество вагонов i- го типа, отводимых под j -й груз. В качестве критерия берем суммарные затраты на погрузку всего груза.

Тогда приходим к модели задачи, которая включает:

критерий

ограничения-равенства, отражающие необходимость отправить все виды грузов в полном объеме,

ограничения-неравенства, учитывающие ограниченное число вагонов каждого вида,

и условия неотрицательности переменных

x_ij ³0, " i,j.

Размерность задачи определяется значениями n и m.

Принципиальное отличие данной модели от транспортной содержится в первой группе ограничений – это наличие коэффициентов B_ij. Если бы все B_ij равнялись единице, мы имели бы модель несбалансированной транспортной задачи (и тогда размерности x_ij, b_j и a_i совпадают).

Задача планирования работы оборудования

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

Очевидно, что за критерий следует принять время выполнения заказа, и чем оно меньше, тем лучше. Введем переменные x_ij – количество продукции i -го вида, произведенного на j -м оборудовании.

Ограничившись тремя видами продукции и двумя видами оборудования, представим исходные данные и все переменные в таблице (табл. 4.5).

Таблица 4.5

Продукция	Оборудование	Заказ
	х 11	х 12
	х 21	х 22
	х 31	х 32

Цифры в правом верхнем углу клеток второго и третьего столбцов показывают норму времени на производство единицы продукции.

Составим модель задачи. Требование обязательного выполнения заказа порождает 3 ограничения-равенства:

x ₁₁ + x ₁₂=70,

x ₂₁ + x ₂₂=90, (*)

x ₃₁ + x ₃₂=45.

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

4 х ₁₁+7 х ₂₁+3 х ₃₁

и время работы второго оборудования

10 х ₁₂+5 х ₂₂+6 х ₃₂.

Время выполнения заказа T будет определяться максимальным из них. Таким образом, целевая функция задачи принимает вид

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

4 х ₁₁+7 х ₂₁+3 х ₃₁£ T,

10 х ₁₂+5 х ₂₂+6 х ₃₂£ T. (**)

Рассматривая T как переменную, запишем критерий следующим образом:

L = T →min.

Этот линейный критерий совместно с условиями (**) эквивалентен исходной нелинейной целевой функции.

В итоге мы пришли к линейной модели, которая включает критерий L, ограничения (*), (**) и условия неотрицательности

x_ij ³0, " i, j.