Вариант 13
Сельскохозяйственные предприятия А1, А2, A3, A4, А5 произвели соответственно x1, х2, х3, х4, х5 тонн картофеля, который должен быть доставлен в овощехранилища В1, В2, В3, В4, B5 в количествах у1; у2, у3, y4, y5 тонн соответственно.
Расстояние доставки картофеля от поставщика А1 к указанным потребителям равно s1, s2, s2, s4, s5 (км).
Расстояние доставки картофеля от поставщика А2 к указанным потребителям равно s1, s2, s2, s4, s5 (км).
Расстояние доставки картофеля от поставщика A3 к указанным потребителям равно s1, s2, s2, s4, s5 (км).
Расстояние доставки картофеля от поставщика А4 к указанным потребителям равно s1, s2, s2, s4, s5 (км).
Расстояние доставки картофеля от поставщика А5 к указанным потребителям равно s1, s2, s2, s4, s5 (км).
Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие объем транспортных работ (ткм).
Решение:
Составим из исходных данных распределительную таблицу:
Сельскохозяйственные предприятия Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2 10 5 15 3 250
А2
7 5 14 3 8 200
А3 4 3 12 9 5 200
А4
2 8 3 5 5 100
А5 5 12 3 8 4 250
Потребности 300 150 200 200 150

Математическая модель:
Целевая функция – объем транспортных работ:
F(X)= 2×11 + 10×12 + 5×13 + 15×14 + 3×15 +
+ 7×21 + 5×22 + 14×23 + 3×24 + 8×25 +
+4×31 + 3×32 + 12×33 + 9×34 + 5×35 +
+2×41 + 8×42 + 3×43 + 5×44 + 5×45 +
+5×51 + 12×52 + 3×53 + 8×54 + 4×55 → min
Ограничения по запасам:
x11 + x12 + x13 + x14 + x15 ≤ 250
x21 + x22 + x23 + x24 + x25 ≤ 200
x31 + x32 + x33 + x34 + x35 ≤ 200
x41 + x42 + x43 + x44 + x45 ≤ 100
x51 + x52 + x53 + x54 + x55 ≤ 250
Ограничения по потребностям:
x11 + x21 + x31 + x41 + x51 ≥ 300
x12 + x22 + x32 + x42 + x52 ≥ 150
x13 + x23 + x33 + x43 + x53 ≥ 200
x14 + x24 + x34 + x44 + x54 ≥ 200
x15 + x25 + x35 + x45 + x55 ≥ 150
где xij – количество тонн картофеля перевозимого с Ai сельскохозяйственного предприятия на Bj овощехранилище.
Проверим условие разрешимости задачи: ∑х = 250 + 200 + 200 + 100 + 250 = 1000, ∑y = 300 + 150 + 200 + 200 + 150 = 1000 . Поскольку ∑х =∑y, то задача сбалансирована и разрешима.
Составим опорный план методом минимальной стоимости:
Шаг 1

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3 8 200
А3 4 3 12 9 5 200
А4
2 8 3 5 5 100
А5 5 12 3 8 4 250
Потребности 300 150 200 200 150

Шаг 2

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3 8 200
А3 4 3 12 9 5 200
А4
2
50 8 3 5 5 100
А5 5 12 3 8 4 250
Потребности 300 150 200 200 150

Шаг 3

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3
200 8 200
А3 4 3 12 9 5 200
А4
2
50 8 3 5 5 100
А5 5 12 3 8 4 250
Потребности 300 150 200 200 150

Шаг 4

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5 200
А4
2
50 8 3 5 5 100
А5 5 12 3 8 4 250
Потребности 300 150 200 200 150

Шаг 5

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5 200
А4
2
50 8 3
50 5 5 100
А5 5 12 3 8 4 250
Потребности 300 150 200 200 150

Шаг 6

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5 200
А4
2
50 8 3
50 5 5 100
А5 5 12 3
150 8 4 250
Потребности 300 150 200 200 150

Шаг 6

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5 200
А4
2
50 8 3
50 5 5 100
А5 5 12 3
150 8 4
100 250
Потребности 300 150 200 200 150

Шаг 6

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10 5 15 3 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5
50 200
А4
2
50 8 3
50 5 5 100
А5 5 12 3
150 8 4
100 250
Потребности 300 150 200 200 150

Шаг 7.
Поскольку n+m-1=5+5-1=9 не равно числу заполненных клеток, то введем нулевую поставку

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
250 10
0 5 15 3 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5
50 200
А4
2
50 8 3
50 5 5 100
А5 5 12 3
150 8 4
100 250
Потребности 300 150 200 200 150

Проверим план на оптимальность:
Считаем потенциалы строк и столбцов через базисные ячейки по формуле:
ui + vj = cij
u1 + v1 = 2
u4 + v1 = 2
u4 + v3 = 3
u5 + v3 = 3
u5 + v5 = 4
u3 + v5 = 5
u3 + v2 = 3
u2 + v4 = 3
u2 + v4 = 3
Решая систему получим:
v1 = 2 u4 = 0 v3 = 3 u5 = 0 v5 = 4 u3 = 1 v2 = 2 u2 = 3 v4 = 0
Найдем оценки не заполненных клеток по формуле:
∆сij= cij -(ui + vj)
∆С=
v1=2 v2=2 v3=3 v4=0 v5=4

u1=0 0 8 2 15 -1

u2=3 2 0 8 0 1

u3=1 1 0 8 8 0

u4=0 0 6 0 5 1

u5=0 3 10 0 8 0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых
∆15 = — 1 <0
Добавляем поставку через клетку (1, 5) обменяв по циклу 1,5 → 1,1 → 4,1 → 4,3 → 5,3 → 5,5 50 тонн груза:

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
200 10
0 5 15 3
50 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5
50 200
А4
2
100 8 3 5 5 100
А5 5 12 3
200 8 4
50 250
Потребности 300 150 200 200 150

Проверим план на оптимальность:
∆С=
v1=2 v2=10 v3=11 v4=0 v5=12

u1=0 0 0 -6 15 -9

u2=3 2 -8 0 0 -7

u3=-7 9 0 8 16 0

u4=0 0 -2 -8 5 -7

u5=-8 11 10 0 16 0
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Добавляем поставку через клетку (1, 5) обменяв по циклу 1,5 → 1,2 → 3,2 → 3,5 0 тонн груза:

Овощехранилища Запасы

В1
В2
В3 В4
В5
А1
2
200 10 5 15 3
50 250
А2
7 5 14 3
200 8 200
А3 4 3
150 12 9 5
50 200
А4
2
100 8 3 5 5 100
А5 5 12 3
200 8 4
50 250
Потребности 300 150 200 200 150

Проверим план на оптимальность:
∆С=
v1=2 v2=1 v3=2 v4=0 v5=3

u1=0 0 9 3 15 0

u2=3 2 1 9 0 2

u3=2 0 0 8 7 0

u4=0 0 7 1 5 2

u5=1 2 10 0 7 0

Опорный план является оптимальным, так все оценки свободных клеток не отрицательны.
Минимальный объем транспортных работ:
F(X)= 2*200+3*50 + 3*200 + 3*150 + 5*50 + 2*100 + 3*200 + 4*50 = 2850ткм.
Ответ:
С предприятия А1 необходимо направить в 1-е овощехранилище 200 тонн картофеля, в 5-е овощехранилище 50 тонн картофеля.
С предприятия А2 необходимо направить в 4-е овощехранилище 200 тонн картофеля.
С предприятия А3 необходимо направить во 2-е овощехранилище 150 тонн картофеля, в 5-е овощехранилище 50 тонн картофеля.
С предприятия А4 необходимо направить в 1-е овощехранилище 100 тонн картофеля.
С предприятия А5 необходимо направить во 3-е овощехранилище 200 тонн картофеля, в 5-е овощехранилище 50 тонн картофеля.

Вариант 13 Сельскохозяйственные предприятия А1 А2 A3 A4