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

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

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

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

Условие можно представить в виде таблицы, где – время, в течение которого -ый станок занят изготовлением -го изделия.

Станки	Затраты на единицу изделия, руб., и производительность, шт./ч	Объем имеющихся мощностей, станко-ч.
	…
		…
…	…	…	…	…
		…
Плановое задание, шт.		…

Математически задачу можно сформулировать так: дана система ограничений

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

Левая часть неравенства (4.6) указывает, что суммарная мощность (станко-ч), затраченная i -м станком, не превышает имеющегося объема мощностей на данном станке. Левая часть неравенства (4.7) показывает, что всего должно быть изготовлено k-x изделий не меньше планового задания . Как видно из соотношения (4.7), величина определяет количество -х изделий, изготовляемых на i -м станке. Следует заметить, что ограничения (4.6) и (4.7) могут быть совместными (объем имеющихся мощностей достаточен для выполнения планового задания) и несовместными (объем мощностей недостаточен).

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

Рассмотрим частный случай решения распределительной задачи, когда она приводится к обычной транспортной задаче. Допустим, что производительность любых двух станков пропорциональна. Выбрав один из станков (пусть для определенности первый) в качестве базового, составляем отношение производительностей любого i-го станка к базовому. Следующие отношения будут равны для всех изделий:

где , есть индекс -го станка (по отношению к базовому). Равенства (4.10) позволяют выразить не только производительности всех остальных станков по отношению к производительностям базового станка, но и другие параметры задачи. В этом случае один час работы базового станка принимается за стандартный час.

Тогда мощность -го станка, приведенная к стандартным часам, будет стандартных часов, т. е.

а время, затрачиваемое по плану ('-м станком на производство k-го изделия, выразится в стандартных часах:

-с,иа,=у,А. (4.11)

Плановое задание по А-му изделию составляет &д. Если бы это изделие изготавливалось на базовом станке, то для его производства необходимо было бы стандартных часов

Ь„1К^Ь\ (k^\,...,n). Затраты в расчете на 1 стандартный час составят

С(*^1» -= Oik-

Величины а,, б», сц, называются приведенными к стандартным часам, т. е. мощностями, плановыми заданиями, затратами соответственно.

Приводя системы ограничений (4.6), (4.7) и целевую функцию (4.9) к стандартным часам, получаем

т. с. суммарные приведенные ресурсы должны быть не меньше суммарных приведенных потребностей в стандартных часах. В противном случае план b'=° (&i;...; Ьп) невыполним.

Если условие (4.14) выполняется как равенство, то и неравенства (4.12) и (4.13) превращаются в равенства, и мы приходим к закрытой модели транспортной задачи. После того, как будет найдено оптимальное решение, необходимо с помощью формул (4.11) вернуться к исходным переменным Xik.