Метод Фогеля - Транспортная задача линейного проектирования

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

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

Таблица 4

Телефон. станции

Районы

Свободн номера

I

II

III

IV

V

1

1

2

6

3
    2 25

25

1

1

1

1

-

-

-

-

2

6

2
    2 25
    1 5

3

30

1

1

1

1

1

1

-

-

3

2
    1 25
    2 5

1
    3 10

40

1

1

1

1

1

1

1

2

4
    2 30

5

6
    4 25

6

55

2

1

2

-

-

-

-

-

5

0

0
    0 15

0

0

15

0

0

0

0

0

0

0

0

Заявки

30

25

45

30

35

1

1

0

0

0

-

1

0

0

0

-

-

0

0

0

-

-

0

0

0

-

-

0

0

0

-

-

0

-

0

-

-

2

-

3

-

-

2

-

-

Алгоритм метода включает следующие основные этапы:

    1. Вычисление разностей в каждой строке и в каждом столбце матрицы между наименьшим расстоянием и ближайшим к ней величиной. Разности по строкам записываются справа в столбце разностей, разности по столбцам - внизу в строке разностей. У нас для строки 4 разность равна 1I-1IV =4-2=2 и т. д. 2. Находим из всех разностей максимальную. В примере это 2 в строке 4 (если их несколько, то берем любую из них). 3. Помещаем в клетку в строке с наибольшей разностью максимально возможного количества ресурсов, где находится наименьшее расстояние C4I=2, количество заявок 30. Поскольку при этом все запросы первого района удовлетворены, то этот столбец исключаем из дальнейшего рассмотрения. 4. Вычисляем разность по столбцам и строкам, не принимая во внимание расстояния в клетках, имеющих ресурсы, и в клетках исключенной строки или столбца, и определяем максимальную разность в столбце или строке. 5. Находим минимальный элемент в строке или столбце с максимальной разностью помещаем в эту клетку максимально возможное количество ресурса. Затем возвращаемся к этапу 4.

Далее за максимальную разность принимаем 1 в столбце II. В клетку 2III c наименьшим расстоянием помещаем имеющееся количество заявок 25. И исключаем второй столбец из рассмотрения. Следующая максимальная разность 2 в четвертой строке. Для четвертой телефонной станции необходимо еще 25 номеров, их мы записываем в клетку 4IV и исключаем четвертую строку из рассмотрения. Далее за максимальную разность принимаем 1 в первой строке. Т. к. первый столбец исключен из рассмотрения, записываем количество свободных номеров в пятый столбец первой строки и исключаем ее из рассмотрения. Далее за максимальную разность принимаем 1 во второй строке. В клетке 2IV, имеющей минимальное расстояние записываем 5 номеров. Заявки четвертого столбца удовлетворены, исключаем его из рассмотрения. Далее за максимальную разность принимаем опять разность во второй строке. В клетке 2III пишем 25. Во второй строке свободных номеров больше нет, исключаем ее из рассмотрения. Далее максимальная разность у нас получилась в пятом столбце - 3. В клетке 3V пишем оставшиеся 10 заявок и исключаем столбец V из рассмотрения. Далее максимальная разность получается в третьей строке, равная 2. Записываем в клетке 3III оставшиеся свободными 5 номеров. Третьему столбцу не хватает еще 15 номеров. Их мы записываем в клетку 5III. Заявки все удовлетворены, свободных номеров больше нет. Рассчитываем стоимость плана.

Стоимость плана составляет:

S=2*25+2*25+1*5+1*25+2*5+3*10+2*30+4*25+0*15=330

Похожие статьи




Метод Фогеля - Транспортная задача линейного проектирования

Предыдущая | Следующая