Эксперт по сдаче вступительных испытаний в ВУЗах
Составить математическую модель, найти оптимальный план перевозок и оптимальные издержки в транспортной задаче, заданной таблицами.
| Поставщик |
а i |
|
Потребитель |
b j |
|
Транспортные издержки на маршруте на единицу груза |
| |
j=1 |
j=2 |
j=3 |
| i=1 |
100 |
j=1 |
190 |
i=1 |
4 |
2 |
1 |
| i=2 |
200 |
j=2 |
120 |
i=2 |
1 |
5 |
3 |
| i=3 |
70 |
j=3 |
10 |
i=3 |
1 |
2 |
6 |
Решение
1) Составим математическую модель транспортной задачи.
Введем обозначения:
А
i – поставщики;
B
j – потребители.
Представим исходные данные в виде транспортной таблицы:
| Поставщики |
Потребители |
Запасы груза |
|
|
|
|
4 |
2 |
1 |
100 |
|
1 |
5 |
3 |
200 |
|
1 |
2 |
6 |
70 |
| Потребности в грузе |
190 |
120 |
10 |
|
Обозначим через х
ij – объём перевозки груза от
i-го поставщика к
j-му потребителю. Тогда суммарные транспортные издержки на перевозку груза F(x) составят:
Проверим тип представленной транспортной задачи:
Так как , то суммарные запасы груза у поставщиков больше суммарной потребности потребителей, поэтому данная задача является открытой. Чтобы получить закрытую модель, введем дополнительного (фиктивного) потребителя, объем потребности которого составляет 370-320=50 единиц груза.
Занесем данные в транспортную таблицу:
| Поставщики |
Потребители |
Запасы груза |
|
|
|
|
|
4 |
2 |
1 |
0 |
100 |
|
1 |
5 |
3 |
0 |
200 |
|
1 |
2 |
6 |
0 |
70 |
| Потребности в грузе |
190 |
120 |
10 |
50 |
|
Заданные запасы груза у поставщиков и потребности потребителей накладывают ограничения на значения объемов перевозок груза x
ij.
Ограничения по запасам груза у поставщиков:
Ограничения по потребностям потребителей:
Объемы перевозимого груза не могут быть отрицательными:
Математическая модель представленной транспортной задачи составлена.
2) Построим опорный (базисный) план перевозок методом «минимальной стоимости» («минимального тарифа»).
Выбираем клетку с минимальным тарифом. Искомый элемент равен c
13=1. Для этого элемента запасы равны 100, потребности 10. Поскольку минимальным является 10, то вычитаем его:
x
13 = min(100, 10) = 10.
Далее искомый элемент равен c
21=1. Для этого элемента запасы равны 200, потребности 190. Поскольку минимальным является 190, то вычитаем его:
x
21 = min(200, 190) = 190.
Аналогично определяем остальные элементы:
x
12 = min(90, 120) = 90;
x
32 = min(70, 30) = 30;
x
24 = min(10, 50) = 10;
x
34 = min(40, 40) = 40
В результате получен опорный план, который является допустимым, так как соответствует системе ограничений транспортной задачи:
| Поставщики |
Потребители |
Запасы груза |
|
|
|
|
|
4 |
2[90] |
1[10] |
0 |
100 |
|
1[190] |
5 |
3 |
0[10] |
200 |
|
1 |
2[30] |
6 |
0[40] |
70 |
| Потребности в грузе |
190 |
120 |
10 |
50 |
|
Таким образом, опорный план перевозок груза имеет вид:
Вычислим значение целевой функции для построенного плана:
Число занятых клеток таблицы равно 6. Их должно быть m + n — 1 = 3 + 4 — 1 = 6, поэтому опорный план является невырожденным.
3) Найдем оптимальный план перевозок методом потенциалов.
Итерация 1.
Этап 1. Проверим оптимальность опорного плана.
Для занятых клеток составим систему уравнений потенциалов:
u
1 + v
2 = 2; u
1 = 0; v
2 = 2;
u
3 + v
2 = 2; 2 + u
3 = 2; u
3 = 0;
u
3 + v
4 = 0; 0 + v
4 = 0; v
4 = 0;
u
2 + v
4 = 0; 0 + u
2 = 0; u
2 = 0;
u
2 + v
1 = 1; 0 + v
1 = 1; v
1 = 1;
u
1 + v
3 = 1; 0 + v
3 = 1; v
3 = 1.
| |
v1=1 |
v2=2 |
v3=1 |
v4=0 |
| u1=0 |
4 |
2[90] |
1[10] |
0 |
| u2=0 |
1[190] |
5 |
3 |
0[10] |
| u3=0 |
1 |
2[30] |
6 |
0[40] |
Для каждой свободной клетки найдем оценку:
∆
11 = u
1 + v
1 — с
11 = 0 + 1 — 4 = -3 < 0;
∆
14 = u
1 + v
4 — с
14 = 0 + 0 — 0 = 0;
∆
22 = u
2 + v
2 — с
22 = 0 + 2 — 5 = -3 < 0;
∆
23 = u
2 + v
3 — с
23 = 0 + 1 — 3 = -2 < 0;
∆
31 = u
3 + v
1 — с
31 = 0 + 1 — 1 = 0;
∆
33 = u
3 + v
3 — с
33 = 0 + 1 — 6 = -5 < 0.
Среди оценок нет положительных, поэтому решение оптимально.
Таким образом, оптимальный план перевозок груза:
Минимальные суммарные издержки на транспортировку груза составят:
Ответ. Груз, который находится у первого поставщика, необходимо направить второму потребителю в количестве 90 единиц и третьему потребителю в количестве 10 единиц.
Груз, который находится у второго поставщика, необходимо направить первому потребителю в количестве 190 единиц. При этом у второго поставщика останется невостребованный груз в количестве 10 единиц.
Груз, который находится у третьего поставщика, необходимо направить второму потребителю в количестве 30 единиц. При этом у третьего поставщика останется невостребованный груз в количестве 40 единиц.
При использовании данного плана перевозок груза издержки на транспортировку груза будут минимальными и составят 440 денежных единиц.
