Другие предметы \ Методы оптимизации

Общая постановка задачи оптимизации металлургических процессов, страница 11

Оптимальный план поставок газет по областям.

Пункты
отправления

(печатания)

Пункты назначения (области)

Запасы

1

2

3

4

А

1,0

1,0

1,2

3,0

40

40

Б

0,8

3,0

1,3

0,9

110

30

40

40

В

4,0

2,5

1,8

1,3

30

20

10

Потребности

30

60

40

50

Поиск опорного плана задачи методом минимального элемента.

Пункты
отправления

(печатания)

Пункты назначения (области)

Запасы

1

2

3

4

А

1,0

1,0

1,2

3,0

40

40

Б

0,8

3,0

1,3

0,9

110

30

30

50

В

4,0

2,5

1,8

1,3

30

20

10

Потребности

30

60

40

50

Затраты на перевозку составят:

30×0,8 + 40×1,0 + 20×2,5 + 10×1,8 + 30×1,3 + 50×0,9 = 216

Поиск опорного плана методом аппроксимации Фогеля:

на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности заносят в специально отведенные для этой цели строку и столбец в таблице условий задачи. В строке (или столбце), которой соответствует максимальная разность, находят минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

Пункты
отправления

(печатания)

Пункты назначения (области)

Разности по строкам

1

2

3

4

А

1,0

1,0

1,2

3,0

0

–

–

–

40

40

Б

0,8

3,0

1,3

0,9

0,1

0,1

0,4

2,1

110

30

40

40

В

4,0

2,5

1,8

1,3

0,5

0,5

0,5

1,2

30

20

10

Разности по столбцам

0,2

1,5

0,1

0,4

3,2

0,5

0,5

0,4

–

0,5

0,4

–

0,5

–

0,4

30

60

40

50

Общая стоимость перевозок составит:

30×0,8 + 40×1,0 + 20×2,5 + 40×1,3 + 40×0,9 + 10×1,3 = 215.

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

Скачать файл