Далее выбираются минимальные значения платы за доставку 1 т груза между каждыми двумя корреспондирующими пунктами.

Выбранные минимальные значения d_i сводятся в таблицу 11.

Таблица 11

Минимальные значения плат за доставку 1 тонны груза

Пункты отправления	Пункты назначения
Волгоград	Балахна	Воронеж
Петрозаводск	ПВВ 3128	ПВВ 1651	ПВВ 4099
Шала	ПВВ 3128	ПВВ 1606	ПВВ 4011
Череповец	ПВВ 2628	ПВВ 1189	ПВВ 3597

Общая постановка и решение транспортной задачи.

Общая постановка задачи выглядит следующим образом:

Цель задачи:

,

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

где i – индекс пунктов отправления груза

j – индекс пунктов назначения груза

Х_ij – количество груза, перевозимого от пункта отправления до пункта назначения, т.

При решении задачи должны соблюдаться следующие условия допустимости (ограничения):

1) , j = 1, 2, 3.

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

V₁ = 75 V₂ = 100 V₃ = 25

2) , i = 1, 2, 3.

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

Q₁ = 50 Q₂ = 50 Q₃ = 100

3) Х_ij ≥ 0, i = 1, 2, 3; j = 1, 2, 3.

т.е. объем перевозок между любыми пунктами не должен быть величиной отрицательной.

Кроме того, необходимо, чтобы количество заполненных клеток равнялось m + n – 1 = 5, т.е. 3 + 3 – 1 = 5.

Условия оптимальности:

Схема доставки груза будет оптимальной, если оценочные числа пунктов отправления (а₁, а₂, а₃) и оценочные числа пунктов назначения груза (в₁, в₂, в₃) будут удовлетворять следующим условиям:

1) в_j – а_i = d_ij для X_ij > 0,

т.е. для пунктов, между которыми осуществляются перевозки;

2) в_j – а_i ≤ d_ij для X_ij = 0,

т.е. для пунктов, между которыми перевозок нет.

С помощью первого уравнения условий оптимальности определяются оценочные числа, а с помощью второго – проверяется оптимальность плана доставки грузов.

Исходные данные:

1. 3 пункта отправления груза i = 1, 2, 3

2. 3 пункта назначения груза j = 1, 2, 3

3. Количество груза в пунктах отправления (Q_i), тыс. т.

Q₁ = 50 Q₂ = 50 Q₃ = 100

4. Количество груза в пунктах назначения (V_j), тыс. т.

V₁ = 75 V₂ = 100 V₃ = 25

5. Стоимость доставки 1 т груза (руб/т) d_ij

Алгоритм решения задачи

1. Заполняется матрица (таблица 12) с исходными данными.

Таблица 12

Матрица решения задачи

Пункты отправления	Пункты назначения	аi	Qi
j = 1 Волгоград	j = 2 Балахна	j = 3 Воронеж
i = 1 Петрозаводск
i = 2 Шала
i = 3 Череповец
вj
Vj

Количество заполненных клеток соответствует допустимым условиям и равно m + n – 1 = 5

2. Пользуясь первым условием оптимальности плана в_j – а_i = d_ij, через заполненные клетки определяем оценочные числа а_i и в_j. Следует учесть, что устанавливать оценочные числа можно только через заполненные клетки, где Х_ij > 0.

При этом произвольно принимаем значение a₁ = 1000, тогда

в₂а₁) в₂ – а₁ = 1651

в₂ – 1000 = 1651 в₂ = 2651

в₂а₂) в₂ – а₂ = 1606

2651 – а₂ = 1606 а₂ = 1045

в₃а₂) в₃ – а₂ = 4011

в₃ – 1045 = 4011 в₃ = 5053

в₂а₃) в₂ – а₃ = 1189

2651 – а₃ = 1189 а₃ = 1462

в₁а₃) в₁ – а₃ = 2628

в₁ – 1462 = 2668 в₁ = 4090

Таким образом найденные оценочные числа равны:

в₁ = 4090 в₂ = 2651 в₃ = 5053

а₁ = 1000 а₂ = 1045 а₃ = 1462

3. Проверим оптимальность первоначального плана по второму условию оптимальности:

в_j – а_i ≤ d_ij для X_ij = 0 (для пустых клеток).

1.1 4090 – 1000 =3090 < 3128 нарушений нет

1.2 4090 – 1045 = 3045 < 3128 нарушений нет

3.1 5053 – 1000 = 4053 < 4099 нарушений нет

3.3 5053 – 1462 = 3591 < 3597 нарушений нет

Данный план является оптимальным.

Вывод:

Для найденной конечной схемы грузопотоков подсчитываем сумму транспортных издержек:

D_o= 50*1651 + 25*1606+ 25*4011+ 75*2628+ 25*1189=

= 82550 + 40150 + 100275+ 197100 + 29725 = 449800 тыс.руб.

В соответствии с оптимальной схемой грузопотоков следует, что:

1. из Петрозоводска в Балахну должно быть доставлено 50 тыс. тонн груза в прямом внутреннем водном сообщении;

2. из Шалы в Балахну должно быть доставлено 25 тыс. т. груза в прямом внутреннем водном сообщении;

3. из Шалы в Воронеж должно быть доставлено 25 тыс. т. груза в прямом внутреннем водном сообщении;

4. из Череповца в Волгоград должно быть доставлено 75 тыс. т. груза в прямом внутреннем водном сообщении;

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

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Грузоведение и коммерческая эксплуатация речного транспорта. Краев И.С., Завитаев Е.Ф. Учебник для речных училищ и техникумов. – М.: «Транспорт», 1976.

2. Организация коммерческой работы на речном транспорте. Багров Л.В., Мацвейко А.Н., Чеботарев М.Н. Учебник для институтов водн.трансп.. – М.: «Транспорт», 1977.

3. Прейскурант №10-01. Тарифы на грузовые железнодорожные перевозки. М.: Прейскурантиздат, 1989.

4. Прейскурант №14-01. Тарифы на перевозку грузов и буксировку плотов речным транспортом. М.: Прейскурантиздат, 1989.

5. Тарифное руководство № 4-Р. Расстояние между тарифными пунктами речных пароходств Центрального бассейна / Министерство речного флота РСФСР. – Л.: Транспорт, 1987.

6. Тарифное руководство № 4. Книга 3. Тарифные расстояния между транзитными пунктами железных дорог Российской Федерации / Министерство путей сообщения Российской Федерации. – М.: Транспорт, 1995.