Задача унификации

Требуется количество изделий — -го типа , а затраты на их производство составляют:

где — количество изделий, — постоянные издержки производства, — переменные издержки.

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

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

,
где — количество изделий -го типа, при которых общая стоимость их производства минимальна:

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

Для минимизации затрат на производство 8 изделий целесообразно применить метод ветвей и границ. Общее число вариантов (при ) и описывается двоичным деревом ветвлений, состоящим из -го уровня.

Ветвление будет производиться следующим образом, множество разбивает на 2 подмножества:

– изготавливает изделия 1 типа,

– заменяем изделия 1 типа на другие,

затем каждая ветвь делиться на 2 подмножества по 2 типу изделий и далее аналогично.

Можно уменьшить количество ветвей в узлах, где , ветви могут быть склеены, сведены в один (в который ведут несколько путей), и для расчета кратчайшего пути всей сети достаточно найти кратчайший путь ведущий в этот «склеенный» узел, и в дальнейшем исходить из этого кратчайшего участка пути. В результате число вариантов не удваивается, а увеличивается на единицу. Узлы дерева имеют двойную нумерацию, первое число дает нам номер подмножества, второе — номер вершины на каждом этапе.

Каждой дуге ставим в соответствующее и соответствующее ему , которое будет считать длиной дуги.

Каждой вершине ставим в соответствие число , которой является нижней границей целевой функции и равной минимуму длин путей ведущих в эту вершину.

На последнем этапе получаем и путь (или несколько путей), дающих этот минимум.

Пример решения задачи унификации.

Исходные данные сведены в таблицу.

i	ai	bi	ci
		1,5
		2,5
		3,5

 

Из условия задачи следует, что необходимо изготовить 18 изделий 5 типов и это обойдется в 86 у.е.