Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 59


1 базисных перевозок, а остальные перевозки равны нулю. План (хij) будем называть оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок (L = min).

В силу особой структуры ТЗ при ее решении не приходится долго и нудно разрешать и пере разрешать систему уравнений. Все операции по нахождению оптимального плана сводятся к манипуляциям непосредственно с таблицей, где в определенном порядке записаны условия транспортной задачи: перечень ПО и ПН, заявки и запасы, а также стоимости перевозок сij. По мере заполнения этой таблицы в ее клетках проставляются сами перевозки xij. Транспортная таблица состоит из т строк и п столбцов. В правом верхнем углу каждой клетки мы будем ставить стоимость сij перевозки единицы груза из Аi в Bj, а центр клетки оставим свободным, чтобы помещать в нее саму перевозку xij. Клетку таблицы, соответствующую пунктам Аi Вj будем кратко обозначать (i, j).

Пример транспортной таблицы, где приведены условия задачи и стоимости перевозок, по нет еще самих перевозок, дан в таблице 10.1, где т = 4, п = 5.

Прежде всего займемся составлением опорного плана.. Это в транспортной задаче очень просто: можно, например, применить так называемый «метод северо-западного угла». Продемонстрируем его непосредственно на конкретных данных таблицы 10.1. Начнем заполнение транспортной таблицы с левого верхнего («северо-западного») угла. Пункт В1 подал заявку на 18 единиц груза; удовлетворим ее из запасов пункта

Таблица 10.1

       пн

по

В1

В2

В3

В4

В5

Запасы аi

A1

13

7

14

7

5

30

A2

11

8

12

6

8

48

A3

6

10

10

8

11

20

A4

14

8

10

10

15

30

Заявки bj

18

27

42

15

26

128

А1 После этого в нем остается еще 30 - 18 =12 единиц груза; отдадим их пункту В2. Но заявка этого пункта еще не удовлетворена; выделим недостающие 15 единиц из запасов пункта A2 и т. д. Рассуждая точно таким же образом, заполним до конца перевозками xij транспортную таблицу (таблица 10.2).


Содержание  Назад  Вперед