- •Введение
- •Запишем их в соответствующие клетки (табл. 7). Третья строка и третий столбец становятся закрытыми и их клетки в дальнейших поисках не участвуют.
- •Последовательное улучшение допустимого решения методом потенциалов
- •Для всех небазисных клеток определим невязки:
- •Решение задачи в excel
- •Определение разницы между наилучшим и наихудшим планами перевозок
- •Ответы на вопросы.
- •Решение задачи
Ответы на вопросы.
а) Чтобы определить, имеет ли задача альтернативное решение, следует выполнить повторный поиск. Повторный поиск показал тот же план перевозок. По- видимому, других решений, приводящих к той же самой стоимости перевозок нет.
б) Определить, каким будет план перевозок, если Поставщик 1 сможет поставлять на 10 машин продукции больше, чем планировал.
Вычислим:
суммарное количество продукции на складах:
st =35 + 45 + 30 = 110,
суммарное количество продукции, заказанное клиентами:
4
Y^Pj =30 + 10 + 30 + 30 = 100.
7=1
Тогда
(5),
/=1 у=1
И транспортная задача является открытой (без баланса). В этом случае задачу следует сбалансировать.
Так как Уj , в таблицу транспортных издержек и в таблицу перево-
/=1 7=1
зок надо добавить по одному лишнему столбцу, как будто появился еще один фиктивный потребитель, заказ которого равнялся разности между суммой всех запасов и суммой всех заявок, а издержки перевозок грузов к нему от любого поставщика равны нулю (рис. 7).
|
А |
в |
С |
D |
Е |
F |
G |
1 |
|
ИСХОДНЫЕ ДАННЫЕ |
|
||||
2 |
|
|
Заказы клиентов |
|
|||
з |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
Клиент 5 |
4 |
Запасы продукции |
30 |
10 |
30 |
30 |
10 |
|
5 |
|
|
Стоимости п е р е в оз ки ед. груз а |
|
|||
6 |
Склад 1 |
35 |
300 |
500 |
200 |
200 |
0 |
7 |
Склад 2 |
45 |
600 |
100 |
400 |
300 |
0 |
8 |
Склад 3 |
30 |
200 |
300 |
100 |
400 |
0 |
9 |
|
|
|
|
|
||
10 |
|
|
Требуется ввезти |
||||
11 |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
Клиент 5 |
12 |
i реиушсн выввзш |
3 |
3 |
3 |
3 |
3 |
|
13 |
Склад 1 |
5 |
1 |
1 |
1 |
1 |
1 |
14 |
Склад 2 |
5 |
1 |
1 |
1 |
1 |
1 |
15 |
Склад 3 |
5 |
1 |
1 |
1 |
1 |
1 |
16 |
Стоимость перевозки |
3600 |
|
|
|
|
|
Рис. 8
Затем решим задачу, используя Поиск решения (рис. 9).
|
А |
в |
С |
D |
Е |
F |
6 |
1 |
(ИСХОДНЫЕ ДАННЫЕ |
||||||
2 |
|
Заказв! клиентов |
|
||||
3 |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
Клиент 5 |
4 |
Запасы продукции |
30 |
10 |
30 |
30 |
10 |
|
5 |
|
|
Стоимости перевозки ед.груз а |
|
|||
В |
Склад 1 |
35 |
300 |
500 |
200 |
200 |
0 |
7 |
Склад 2 |
45 |
600 |
—^ О о |
400 |
300 |
0 |
В |
Склад 3 |
30 |
200 |
300 |
100 |
400 |
0 |
9 |
|
|
|
||||
10 |
|
Требуется ввезти |
|||||
11 |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
Клиент 5 |
12 |
i реоуется вывели |
30 |
10 |
30 |
30 |
10 |
|
13 |
Склад 1 |
35 |
30 |
0 |
0 |
5 |
0 |
14 |
Склад 2 |
45 |
0 |
10 |
0 |
25 |
10 |
15 |
Склад 3 |
30 |
0 |
0 |
30 |
0 |
0 |
16 |
Стоимоств перевозки |
21500 |
|
|
|
|
|
Рис. 9
Решение задачи изменилось: минимальная стоимость перевозок стала равной 21500 (у.е.) при объемах перевозок: хц = 30, х]4 = х22 ~ 5, х22 = Ю, х24 - 25, Хзз = 30, а перевозка к фиктивному клиенту х\5 = 10.
в) Определить, каким будет план перевозок, если Поставщик 1 не сможет поставлять на 10 машин продукции больше, чем планировал, а Поставщик 4 сможет поставлять на 5машин меньше.
Вычислим:
суммарное количество продукции на складах:
з
Ylsi =25 + 45 + 30 = 100,
i=i
суммарное количество продукции, заказанное клиентами:
4
Y,Pj =30 + 10 + 30 + 25 = 95.
7=1
Тогда
±*,*±р,
/=1 j=1
и транспортная задача является открытой (без баланса). В этом случае задачу следует сбалансировать.
3 4
Так как 5>,<£ Pj, в таблицу транспортных издержек и в таблицу
/=1 7=1
перевозок надо добавить по одной лишней строке, как будто появился еще один фиктивный поставщик, заказ которого равнялся разности между суммой всех заявок и суммой всех запасов, а издержки перевозок грузов от него к любому поставщику равны нулю (рис. 10).
|
А |
В |
С |
D |
Е |
F |
1 |
|
ИСХОД |
НЫЕ ДАННЫЕ! |
|
|
|
2 |
|
|
Заказы клиентов |
|||
3 |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
4 |
Запасы продукции |
30 |
10 |
30 |
30 |
|
5 |
|
|
Стоимости перевозки ед. груза |
|||
6 |
Склад 1 |
25 |
300 |
500 |
200 |
200 |
7 |
Склад 2 |
45 |
600 |
100 |
400 |
300 |
8 |
Склад 3 |
25 |
200 |
300 |
100 |
400 |
9 |
Склад 4 |
5 |
0 |
0 |
0 |
0 |
10 |
|
|
|
|||
11 |
|
Требуется ввезти |
||||
12 |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
13 |
I [JfeJUye 1 Ln bblbtfJ 1 И |
4 |
4 |
4 |
4 |
|
14 |
Склад 1 |
4 |
1 |
1 |
1 |
1 |
15 |
Склад 2 |
4 |
1 |
1 |
1 |
1 |
16 |
Склад 3 |
4 |
1 |
1 |
1 |
1 |
17 |
Скпад 4 |
4 |
1 |
1 |
1 |
1 |
18 |
Стоимость перевозки |
3600 |
|
|
|
|
Рис. 10 |
||||||
|
А |
В |
С |
D |
Е |
F |
1 |
|
ИСХОД |
НЫЕ ДАННЫЕ |
|
|
|
2 |
|
|
Заказы клиентов |
|||
3 |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
4 |
Запасы продукции |
30 |
10 |
30 |
30 |
|
5 |
|
|
Стоимости п е р е в оз ки ед. груз а |
|||
6 |
Скпад 1 |
25 |
300 |
500 |
200 |
200 |
7 |
Скпад 2 |
45 |
600 |
100 |
400 |
300 |
8 |
Скпад 3 |
25 |
200 |
300 |
100 |
400 |
9 |
Склад 4 |
5 |
0 |
0 |
0 |
0 |
10 |
|
|
|
|
||
11 |
|
Требуется ввезти |
||||
12 |
|
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
13 |
I У I Ln bblbcd I И |
30 |
10 |
30 |
30 |
|
14 |
Скпад 1 |
25 |
25 |
0 |
0 |
0 |
15 |
Склад 2 |
45 |
0 |
10 |
5 |
30 |
16 |
Скпад 3 |
25 |
0 |
0 |
25 |
0 |
17 |
Скпад 4 |
5 |
5 |
0 |
0 |
0 |
18 |
Стоимость перевозки |
22000 |
|
|
|
|
|
|
|
Рис. |
11 |
|
|
Решение задачи изменилось: минимальная стоимость перевозок ] случае будет равной 26500 (у.е.) при объемах перевозок: х, i = 25, х22 Х2з = 5, Х24 = 30, хзз = 25, а перевозка от фиктивного поставщика х4] = 5. Недополучит 5 машин продукции Клиент 1.
ЗАДАЧА 2
УСЛОВИЕ ЗАДАЧИ
Менеджеру транспортного отдела поручено составить план перевозок продукции со склада фирмы в четыре торговые точки области, обеспечивающий минимальные издержки на перевозки (известно, что издержки на перевозки пропорциональны длине пути).
Расстояния от базы до каждого магазина и между магазинами приводятся в таблице 1:
Табл. 1
|
База |
Т1 |
Т2 |
ТЗ |
Т4 |
База |
|
4 |
|
11 |
3 |
Т1 |
4 |
|
6 |
|
6 |
Т2 |
|
6 |
|
2 |
5 |
ТЗ |
11 |
|
2 |
|
9 |
Т4 |
3 |
6 |
5 |
9 |
|
Пустые клетки означают, что дороги или ремонтируются или плохого качества.
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
Сеть дорог, связывающих базу с магазинами области можно представить в виде неориентированного графа, вершинам которого поставлены в соответствие название базы и магазинов, ребрам - связывающие их дороги, и каждому ребру поставлен в соответствие вес - длина дороги. Для удобства обозначим название базы через хь а торговые точки через х2, х3, х3, х5. Расстояния от вершины Х\ до всех остальных и между вершинами представим в виде матрицы весов неориентированного графа (табл. 2). Для наглядности в матрице весов знаки оо (показывающие отсутствие дороги) опустим. Тогда задача сводится к нахождению кратчайших путей от вершины X] до всех остальных. Для ее решения используем метод Дейкстры.
Табл. 2
|
X] |
х2 |
х3 |
х4 |
х5 |
X] |
|
4 |
|
11 |
3 |
х2 |
4 |
|
6 |
|
6 |
Хз |
|
6 |
|
2 |
5 |
х4 |
11 |
|
2 |
|
9 |
Х5 |
3 |
6 |
5 |
9 |
|