Меню
Главная
Авторизация/Регистрация
 
Главная arrow Техника arrow Автоматизация технологических процессов и производств

Оптимизация задачи распределения грузов с помощью метода потенциалов

Математическая модель задачи оптимизации с помощью линейного программирования может быть представлена в табличной форме, для которой применяют специальный метод потенциалов, который является разновидностью симплекс-метода. Метод потенциалов в ряде случаев позволяет упростить решение задачи поэтапного достижения экстремума целевой функции. Этот метод широко применяется при решении транспортной задачи, результатом которой является определение оптимальной схемы перевозок грузов от поставщиков к потребителям. Обычно задача формулируется следующим образом.

Пусть имеется т пунктов хранения однородного продукта (например, заготовок одного типа), в каждом из которых находится соответственно а 1, а2, ..., ат количеств продукта. Имеется п пунктов потребления этого продукта, в каждый из которых требуется доставить Ьх, Ь2, ..., Ьп количеств продукта. Известны удельные затраты с,у на перевозку единицы продукта из каждого /-го пункта хранения (/ = 1, т) в каждый у'-й пункт потребления (/=1, п). Оптимальным является план перевозок, при котором суммарные транспортные затраты минимальны. Данные транспортной задачи представляют в виде таблицы.

Таблица 4.12. Данные транспортной задачи для решения методом потенциалов

Пункты

хранения

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

в

В2

ВЗ

Вп

А

с

С2

с13

Сп

а

X

11

X

12

X

13

X

1/7

А2

С21

с22

с23

с2п

а2

*21

х22

х23

х2п

. . .

Ат

Ст

Ст2

СтЗ

с

^ пт

ат

хт

хт2

х,»3

х

Лтп

Ь1

ь

Ь2

ьг

Ьп

щ=

= 1а,

В табл. 4.12 содержатся все уравнения математической модели задачи линейного программирования. Сумма произведений с^Ху каждой клетки дает выражение целевой функции

/=1 ;=1

где Ху — количество продукта, доставляемого из /-го пункта хранения ву'-й пункт потребления.

Система ограничений имеет вид равенств:

X хи = ЬР X *(/=*»»

у=1 /=1

где Ху > 0.

Уравнение баланса (правая нижняя клетка таблицы):

п т

ХЛ.-Х‘'•

7=1 1=1

Пример решения задачи методом потенциалов

Пусть из двух накопителей Н1 и Н2 автоматического склада АС необходимо доставить заготовки одного типа на 3 производственных участка ГПС: У1, У2, УЗ (табл. 4.13).

Таблица 4.13. Исходные данные к примеру транспортной задачи

АС

ГПС

я/

У1

У2

УЗ

Н1

20

20

30

1800

X

11

X

12

X

13

Н2

30

40

20

2600

X

21

X

22

*23

1000

1200

2200

4400

Баланс: ^Ьу = X, а, = 4400.

7=1 /=1

Требуется определить количество единиц Груза Ху .

Этап № 1

Для определения первоначального допустимого базисного плана сначала заполняем верхнюю левую клетку, по возможности удовлетворяя полностью запрос потребителя У1, т. е. назначаем хи = 1000. При этом учитывается, чтобы величина затрат сп была минимальной. В нашем примере сп = си = 20, поэтому можно заполнять как клетку (1.1), так и клетку (1.2). После заполнения клетки (1.1) остаток заготовок из Н1 запишем в клетку (1.2), т. е. х12 - 1800 - 1000 = 800 заготовок пойдет на участок У2. Для потребителя УЗ останется х13 = 0.

Во второй строке клетка с минимальными затратами с23 = 20 соответствует участку УЗ, поэтому туда записываем всю потребность х23 = 22 0 0. Остаток из Н2 запишем в соседнюю клетку (2.2), т. е. х22 = = 2600 - 2200 = 400. Для потребителя У1 останется х21 = 0.

Заполненные клетки соответствуют базисным переменным, а незаполненные — свободным. После заполнения клеток получим табл. 4.14. Проверим начальный опорный план на оптимальность. Для свободных клеток (х,у = 0) оптимального плана должно выполняться условие

- и, < с,р

где Vj — потенциалу-го столбца (/=1,2,3 — номер столбца); и і — потенциал /-й строки (/=1,2 — номер строки).

Таблица 4.14. Распределение грузов на первом этапе

АС

гпс

а,

УІ

У2

УЗ

Н1

20

20

30

1800

1000

800

0

Н2

30

40

20

2600

0

400

2200

Ьі

1000

1200

2200

4400

Значения потенциалов находим из условия: у- - и1 - с,у для базисных клеток (х,у > 0). Напишем эти равенства:

  • (кл. 1.1): V, - их = 20;
  • (кл. 1.2): у2- и1 = 20;
  • (кл. 2.2): у2 - и2 - 40;
  • (кл. 2.3): v3- и2 = 20.

Так как переменных здесь больше, чем уравнений, то принимаем, например, и| = 0. Тогда получим: и2 = -20; У| = 20; у2 = 20; у3 = 0. Теперь проверим неравенства для свободных клеток:

  • (кл. 1.3): у3 - их < 30, 0 - 0 < 30 (условие выполняется);
  • (кл. 2.1): у, — и2 < 30, 20 -г 20 < 30 (условие не выполняется).

Следовательно, начальный план не оптимален. Необходимо его улучшить.

Этап № 2

В клетку (2.1), для которой не выполняется контрольное неравенство, перенесем поставку груза из соседней клетки (2.2) и получим: х2 - 400, х22 = 0. Затем, двигаясь по часовой стрелке, с целью сохранения баланса цифру 400 вычтем из клетки (1.1) и добавим 400 в клетку (1.2). В результате цикла пересчета новые значения базисных переменных будут: хп = 1000 - 400 = 600; х12 = 800 + 400 = 1200. Значения переменных в столбце УЗ остались прежними. После заполнения на втором этапе получаем табл. 4.15.

Таблица 4.15. Распределение грузов на втором этапе

АС

гпс

/7 .

У1

У2

УЗ

С11

Н1

20

20

30

1800

600

1200

0

Н2

30

40

20

2600

400

0

2200

ь

1000

1200

2200

4400

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

Проверим новый допустимый план на оптимальность.

Сначала найдем значения потенциалов, полагая их = 0: и2 = -10; V] = 20; v2 = 20; у3 = 10. Затем проверим неравенства:

  • (кл. 1.3): у3их < 30, 10 - 0 < 30 (условие выполняется);
  • (кл. 2.2): у2 - и2 < 40, 20 + 10 < 40 (условие выполняется). Следовательно, данное решение оптимально.

Сравним значения целевой функции для исходного и оптимального планов:

I, = 20 • 1000 + 20 • 800 + 40 • 400 + 20 • 2200 = 96 000 ед.

Ь2 = 1опт = 20 • 600 + 20 • 1200 + 30 ? 400 + 20 • 2200 = 92 000 ед.

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы