yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Исследование операций

7. Транспортная задача

 

Задача. Имеется три поставщика груза и четыре потребителя. Запасы груза у поставщиков  и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары “поставщик – потребитель” сведены в таблицу поставок (Таблица 7.1).

Таблица 7.1.

Поставщики

Мощность поставщиков

Потребители

1

2

3

4

20

110

40

110

1

60

1

2

5

3

2

120

1

6

5

2

3

100

6

3

7

4

 

В каждой клетке для каждой пары “поставщик - потребитель” указаны коэффициенты затрат на перевозку груза от i-того поставщика к j-тому потребителю.

Задача ставится следующим образом:

Найти объёмы перевозок груза для каждой пары “поставщик-потребитель” чтобы:

    1. запасы груза поставщиков были реализованы;

    2. спросы всех потребителей были удовлетворены;

    3. суммарные затраты на перевозку были минимальными.

 

7.1. Экономико-математическая модель задачи

Обозначим через хij-объём перевозки от i-того поставщика к j-тому потребителю и назовём его поставкой клетки (і, j).

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

                                                                            (7.1)

Для того чтобы спрос каждого потребителя был удовлетворён, подобные уравнения баланса составим для каждого столбца таблица поставок

                                                                                                 (7.2)

Очевидно, что объём перевозимого груза не может быть  отрицательным, поэтому следует дополнительно предположить, что

                    хij (і = 1,2,3;  j = 1,2,3,4).

Суммарные затраты F на перевозку груза  должны быть минимальными.

 

Особенности экономико-математической модели транспортной задачи:

1.     Система ограничений есть уравнение;

2.     Коэффициенты при переменных системы ограничений равны единице или нулю;

3.     Каждая переменная входит в систему ограничений два раза – один раз в систему (7.1) и один раз – в систему (7.2).

В рассматриваемой транспортной задаче суммарные запасы груза поставщиков (280) равны суммарному спросу  потребителей (280). Такие транспортные задачи называются закрытыми. Если обозначить через m – число поставщиков, через n – число потребителей, то ранг системы ограничений будет равен m + n – 1.

Так же как и при решении любой задачи  ЛП  при решении Т.З. переменные хij должны быть разбиты на основные (базисные) и неосновные (свободные). Базисная переменная хij в транспортной задаче равна поставке в клетку с номером (і;j), которая называется базисной клеткой или заполненной клеткой. Число базисных переменных (базисных клеток) в закрытой Т.З. должно быть равно рангу системы, т.е. числу m + n – 1. Остальные незанятые (пустые) клетки соответствуют свободным (неосновным) переменным.

На первом шаге решения Т.З. как и в симплексном методе необходимо  найти исходное базисное распределение поставок (опорный план).

 

 

17