Задача унификацииТребуется количество изделий — -го типа , а затраты на их производство составляют: где — количество изделий, — постоянные издержки производства, — переменные издержки. Будем считать, что изделия взаимозаменяемые, они отсортированы по возрастанию мощности и изделия с меньшим порядковым номером можно заменить на изделие с большим порядковым номером. Задача состоит в том, чтобы минимизировать затраты на производство необходимых изделий за счет уменьшения количества их типов, т. е. требуется найти: , Для минимизации затрат на производство 8 изделий целесообразно применить метод ветвей и границ. Общее число вариантов (при ) и описывается двоичным деревом ветвлений, состоящим из -го уровня. Ветвление будет производиться следующим образом, множество разбивает на 2 подмножества: – изготавливает изделия 1 типа, – заменяем изделия 1 типа на другие, затем каждая ветвь делиться на 2 подмножества по 2 типу изделий и далее аналогично. Можно уменьшить количество ветвей в узлах, где , ветви могут быть склеены, сведены в один (в который ведут несколько путей), и для расчета кратчайшего пути всей сети достаточно найти кратчайший путь ведущий в этот «склеенный» узел, и в дальнейшем исходить из этого кратчайшего участка пути. В результате число вариантов не удваивается, а увеличивается на единицу. Узлы дерева имеют двойную нумерацию, первое число дает нам номер подмножества, второе — номер вершины на каждом этапе. Каждой дуге ставим в соответствующее и соответствующее ему , которое будет считать длиной дуги. Каждой вершине ставим в соответствие число , которой является нижней границей целевой функции и равной минимуму длин путей ведущих в эту вершину. На последнем этапе получаем и путь (или несколько путей), дающих этот минимум. Пример решения задачи унификации. Исходные данные сведены в таблицу.
Из условия задачи следует, что необходимо изготовить 18 изделий 5 типов и это обойдется в 86 у.е.
|