Лекция № 6. Тема: Распределение машин по объектам строительства

Тема: Распределение машин по объектам строительства

Венгерским методом.

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

Пусть для монтажа j = 4 объектов требуется i = 4 крана, Из отчетных данных известно какое время необходимо каждому крану А i для монтажа объекта В j. Необходимо так распределить краны по объектам, чтобы суммарное время на монтаж этих объектов было минимальным. Исходные данные представлены в табл. 1 (Оценочным критерием могут служить и суммарные затраты на монтаж объектов).

Таблица 1.

Машины А i	Затраты времени на монтаж С i j по объектам В j	аi	d j
В1	В2	В3	В4
А1
А2
А3
А4
b j					-	-

Где: аi – число машин на объекте

d j -минимальный элемент в строке

b j -на объекте машин.

Введем переменные Х i j (i, j = 1….n), имеющее следующий смысл:

m = 4

∑ Х i j = Х i1 + Х i2 + Х i3 + Х i 4 = 1

b = 1

n = 4

∑ Х i j = Х 1 j + Х 2 j + Х 3 j + Х 4 j = 1

i = 1

первое равенство - на каждом объекте работает только один кран и

второе равенство – каждый кран работает на одном объекте.

Критерий оптимизации - суммарное время монтажа четырех объектов записывается математически так:

n = 4 m = 4

У = С 11 ∙ Х11 + … + С i j ∙ Х i j + … С 44 ∙ Х44 = ∑ ∑ С i j ∙ Х i j

i = 1 j = 1

Таким образом, задача свелась к нахождению чисел Х ij которые удовлетворяют двум вышеперечисленным условиям и минимизируют время монтажа объектов.

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

Решение задачи считается оптимальным, если все измененные затраты С i j ≥ 0 и можно отыскать такой набор Х i j при которых:

n = 4 m = 4

У = ∑ ∑ С i j ∙ Х i j ------ min.

i = 1 j = 1

Алгоритм данного метода имеет следующие этапы.

1. Получение нулей в каждой строке: Для этого найдем наименьший элемент в каждой строке d j табл.1 и вычтя его из всех элементов получим новую матрицу табл. 2.

Аналогично выполняем операции по столбцам и получаем табл. 3

Таблица 2

Машины А i	Затраты времени на монтаж С i j по объектам В j	аi
В1	В2	В3	В4
А1
А2
А3
А4
b j					-
d j					-

Таблица 3

Машины А i	Затраты времени на монтаж С i j по объектам В j	аi
В1	В2	* В3	В4
А1	0 *1
А2	0	0 *3		0
* А3	2		0 *2	3
* А4		2	0
b j					-

Дата добавления: 2014-01-05