РАСПРЕДЕЛИТЕЛЬНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ТРАНСПОРТНОГО ТИПА

Многие задачи линейного программирования относятся к классу задач, которые называют распределительными или /v-задачами (лямбда-задачами), а также обобщенными транспортными задачами. В терминах перевозок распределительную задачу можно сформулировать следующим образом: пусть имеются запасы МТС, сконцентрированные в пунктах отправления, причем в различных пунктах имеются различные виды запасов. Все эти запасы или часть их требуется доставить к потребителям, причем для каждого потребителя указано количество запасов МТС. Расходы на перевозку МТС считаются известными. Задача заключается в нахождении плана перевозок, минимизирующего суммарные расходы на транспортировку.

Многопродуктовая транспортная задача

Ранее рассматривалась транспортная задача, в которой фигурировал один вид МТС (один продукт). А как быть, если необходимо спланировать перевозку нескольких видов МТС (несколько продуктов)? Для решения данной задачи можно предложить два пути:

  • 1. Сформировать по каждому виду перевозимых МТС свою транспортную задачу (однопродуктовую). Частные решения этих задач и будут представлять оптимальный план перевозок.
  • 2. Сформировать одну (многопродуктовую) транспортную задачу. Рассмотрим более подробно второй путь.

Пример 7.1. Для трех пользователей необходимо пополнить запасы бензина АИ-76 и АИ-93. Пополнение запасов может производиться из хранилища города (гор.) и области (обл.). Запасы и потребности бензина представлены в табл. 7.1 и 7.2. Возможности поставщиков (гор. и обл.) и спрос потребителей указаны в табл. 7.3.

Таблица 7.1

Склад гор.

Склад обл.

АИ-76

40

60

АИ-93

20

30

Таблица 7.2

1-й потр.

2-й потр.

3-й потр.

АИ-76

25

45

30

АИ-93

15

35

Протяженность маршрутов представлена в табл. 7.3.

Таблица 7.3

1-й потр.

2-й потр.

3-й потр.

Склад гор.

30

50

60

Склад обл.

100

90

120

В целях упрощения вычислений предположим, что Cij = Lij.

Для того чтобы учесть многопродуктовый характер задачи, сформируем транспортную модель следующим образом. Вместо того чтобы рассматривать каждого поставщика как один исходный пункт, разобьем его на несколько пунктов в соответствии с количеством видов перевозимых ГСМ. Аналогично поступим и с пунктами назначения (потребителями). В результате для нашего примера получим 4 поставщика и 5 потребителей.

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

Рис. 7.1. Схема реализации многопродуктовой задачи

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

Транспортная таблица для многопродуктовой транспортной задачи в условиях нашего примера имеет следующий вид (табл. 7.4):

Таблица 7.4

1-й потр.

2-й потр.

3-й потр.

АИ-76

АИ-93

Склад гор.

3

М

5

М

6

40

20

М

3

М

5

М

Склад обл.

10

м

9

9

12

60

30

м

10

М

М

М

АИ-76

25

45

30

АИ-93

15

35

-

Данную транспортную таблицу можно разбить на несколько таблиц по видам продуктов (в нашем случае на две). Следует заметить, что с вычислительной точки зрения небольшие подзадачи решать проще, чем одну сложную. Но разбиение многопродуктовой модели на однопродуктовые можно осуществлять только в том случае, если нет взаимной связи между отдельными видами продуктов. Если такая связь существует, то многопродуктовую модель не удается просто разбить на однопродуктовые.

Пример 7.2. В условиях предыдущего примера предположим, что в 1-й потр. возможна взаимная компенсация АИ-76 и АИ-93 на 100%, во 2-й потр. - на 20%. При построении транспортной таблицы необходимо в 1-й и 2-й потр. добавить по одному потребителю, величины спроса в которых определим из данных о процентном соотношении заменяемых видов ГСМ.

1-йпотр. : 25x0,1=2,5

Z = 4.

  • 15x0,1=1,5
  • 2-й потр. : 45 х 0,2 = 9

> 1=16.

35x0,2 = 7 J

Далее необходимо сформировать транспортную таблицу следующего вида:

Таблица 7.5

1-й потр.

2-й потр.

3-й потр.

76

93

76-93

76

93

76-93

76

Склад гор.

76

3

М

3

5

М

5

6

40

93

м

3

3

М

5

5

М

20

Склад обл.

76

10

м

10

9

М

9

12

60

93

м

10

10

М

9

9

М

30

22,5

13,5

4

36

28

16

30

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >