Определение разницы между наилучшим и наихудшим планами перевозок
В результате решения задачи оптимизации был найден оптимальный (наилучший) план перевозки продукции - такой план, при котором достигается минимальная стоимость перевозок.
Чтобы определить, насколько полученный при оптимизации план лучше, чем другие возможные планы, надо найти план, приносящий максимум издержек. Для этого следует запустить Поиск решения еще раз и поменять цель поиска на максимум - выбрать направление изменения целевой функции: установить переключатель в положение Максимальному значению (рис. 5). Получим решение (рис. 6)
Рис.5
|
ИСХОДНЫЕ ДАННЫЕ |
|
|
|
|
|
|
Недельные портебности завода |
|||
Max отгрузка маш/нед. |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
|
50 |
30 |
45 |
40 |
||
Стоимости перевозки ед груза |
|||||
Поставщик 1 |
50 |
1600 |
1400 |
1100 |
1250 |
Поставщик 2 |
55 |
1300 |
1350 |
1500 |
1200 |
Поставщик 3 |
60 |
1000 |
1250 |
900 |
1400 |
|
|
|
|
|
|
|
|
Требуется Получить |
|||
Требуется поставить |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
|
50 |
30 |
45 |
40 |
||
Поставщик 1 |
50 |
50 |
7,34E-11 |
0 |
0 |
Поставщик 2 |
55 |
0 |
10 |
45 |
0 |
Поставщик 3 |
60 |
0 |
20 |
0 |
40 |
Стоимость перевозки |
242 000 |
|
|
|
|
Рис. 6
В полученном решении суммарная стоимость перевозок возрастет на 55 250 (у.е.). Таким образом, наихудший план отличается от наилучшего на 29,6%.
Ответы на вопросы.
а) Чтобы определить, имеет ли задача альтернативное решение, следует выполнить повторный поиск. Повторный поиск показал тот же план перевозок. По-видимому, других решений, приводящих к той же самой стоимости перевозок нет.
б) Определить, каким будет план перевозок, если Поставщик 4 сможет поставлять на 5 машин продукции больше, чем планировал.
Вычислим:
суммарное количество продукции на складах: (4)
суммарное количество продукции, заказанное клиентами:
Тогда (5)
И транспортная задача является открытой (без баланса). В этом случае задачу следует сбалансировать.
Так
как
,
в таблицу транспортных издержек и в
таблицу перевозок надо добавить по
одному лишнему столбцу и строке, как
будто появился еще один фиктивный
потребитель и поставщик, заказ которого
равнялся разности между суммой всех
запасов и суммой всех заявок, а издержки
перевозок грузов к нему от любого
поставщика равны нулю (рис. 7).
|
ИСХОДНЫЕ ДАННЫЕ |
|
|
|
|
|||||
|
|
Недельные портебности завода |
|
|||||||
Max отгрузка маш/нед. |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
Завод 5 |
|||||
50 |
30 |
45 |
40 |
5 |
||||||
Стоимости перевозки ед груза |
||||||||||
Поставщик 1 |
50 |
1600 |
1400 |
1100 |
1250 |
0 |
||||
Поставщик 2 |
55 |
1300 |
1350 |
1500 |
1200 |
0 |
||||
Поставщик 3 |
60 |
1000 |
1250 |
900 |
1400 |
0 |
||||
Поставщик 4 |
5 |
0 |
0 |
0 |
0 |
0 |
||||
|
|
|
|
|
|
|
||||
|
|
Требуется Получить |
|
|||||||
Требуется поставить |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
Завод 5 |
|||||
4 |
4 |
4 |
4 |
4 |
||||||
Поставщик 1 |
5 |
1 |
1 |
1 |
1 |
1 |
||||
Поставщик 2 |
5 |
1 |
1 |
1 |
1 |
1 |
||||
Поставщик 3 |
5 |
1 |
1 |
1 |
1 |
1 |
||||
Поставщик 4 |
5 |
1 |
1 |
1 |
1 |
1 |
||||
Стоимость перевозки |
15 250 |
|
|
|
|
|
||||
Рис. 7
Затем решим задачу, используя Поиск решения (рис. 8).
|
ИСХОДНЫЕ ДАННЫЕ |
|
|
|
|
||
|
|
Недельные портебности завода |
|
||||
Max отгрузка маш/нед. |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
Завод 5 |
||
50 |
30 |
45 |
40 |
5 |
|||
Стоимости перевозки ед груза |
|||||||
Поставщик 1 |
50 |
1600 |
1400 |
1100 |
1250 |
0 |
|
Поставщик 2 |
55 |
1300 |
1350 |
1500 |
1200 |
0 |
|
Поставщик 3 |
60 |
1000 |
1250 |
900 |
1400 |
0 |
|
Поставщик 4 |
5 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Требуется Получить |
|
||||
Требуется поставить |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
Завод 5 |
||
50 |
30 |
45 |
40 |
5 |
|||
Поставщик 1 |
50 |
0 |
0 |
35 |
10 |
5 |
|
Поставщик 2 |
55 |
0 |
25 |
0 |
30 |
0 |
|
Поставщик 3 |
60 |
50 |
0 |
10 |
0 |
0 |
|
Поставщик 4 |
5 |
0 |
5 |
0 |
0 |
0 |
|
Стоимость перевозки |
179 750 |
|
|
|
|
|
|
Рис. 8
Решение задачи изменилось: минимальная стоимость перевозок стала равной 179 750(у.е.)
в) Определить, каким будет план перевозок, если Поставщик 4 не сможет поставлять на 5 машин продукции больше, чем планировал, а Поставщик 1 сможет поставлять на 10 машин меньше.
Вычислим:
суммарное количество продукции на складах:
суммарное количество продукции, заказанное клиентами:
Тогда
и транспортная задача является открытой (без баланса). В этом случае задачу следует сбалансировать.
Так
как
,
в
таблицу транспортных издержек и в
таблицу
перевозок надо добавить по одной лишней строке, как будто появился еще один фиктивный поставщик, заказ которого равнялся разности между суммой всех заявок и суммой всех запасов, а издержки перевозок грузов от него к любому поставщику равны нулю (рис. 9).
|
ИСХОДНЫЕ ДАННЫЕ |
|
|
|
|||
|
|
Недельные портебности завода |
|||||
Max отгрузка маш/нед. |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
|||
50 |
30 |
45 |
40 |
||||
Стоимости перевозки ед груза |
|||||||
Поставщик 1 |
40 |
1600 |
1400 |
1100 |
1250 |
||
Поставщик 2 |
55 |
1300 |
1350 |
1500 |
1200 |
||
Поставщик 3 |
60 |
1300 |
1350 |
1500 |
1200 |
||
Поставщик 4 |
10 |
0 |
0 |
0 |
0 |
||
|
|
|
|
|
|
||
|
|
Требуется Получить |
|||||
Требуется поставить |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
|||
50 |
30 |
45 |
40 |
||||
Поставщик 1 |
40 |
1 |
1 |
1 |
1 |
||
Поставщик 2 |
55 |
1 |
1 |
1 |
1 |
||
Поставщик 3 |
10 |
1 |
1 |
1 |
1 |
||
Поставщик 4 |
10 |
1 |
1 |
1 |
1 |
||
Стоимость перевозки |
16050 |
|
|
|
|
||
Рис. 9
|
ИСХОДНЫЕ ДАННЫЕ |
|
|
|
|||
|
|
Недельные портебности завода |
|||||
Max отгрузка маш/нед. |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
|||
50 |
30 |
45 |
40 |
||||
Стоимости перевозки ед груза |
|||||||
Поставщик 1 |
40 |
1600 |
1400 |
1100 |
1250 |
||
Поставщик 2 |
55 |
1300 |
1350 |
1500 |
1200 |
||
Поставщик 3 |
60 |
1300 |
1350 |
1500 |
1200 |
||
Поставщик 4 |
10 |
0 |
0 |
0 |
0 |
||
|
|
|
|
|
|
||
|
|
Требуется Получить |
|||||
Требуется поставить |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
|||
50 |
30 |
45 |
40 |
||||
Поставщик 1 |
40 |
0 |
0 |
0 |
40 |
||
Поставщик 2 |
55 |
0 |
20 |
35 |
0 |
||
Поставщик 3 |
10 |
50 |
0 |
10 |
0 |
||
Поставщик 4 |
10 |
0 |
10 |
0 |
0 |
||
Стоимость перевозки |
209 500 |
|
|
|
|
||
Рис.10
Решение задачи изменилось: минимальная стоимость перевозок в этом случае будет равной 209 500 (у.е.), а перевозка от фиктивного поставщика х42 = 10. Недополучит 10 машин продукции Завод 2.
ЗАДАЧА 2
УСЛОВИЕ ЗАДАЧИ
Менеджеру транспортного отдела поручено составить план перевозок продукции со склада фирмы в четыре торговые точки области, обеспечивающий минимальные издержки на перевозки (известно, что издержки на перевозки пропорциональны длине пути).
Расстояния от базы до каждого магазина и между магазинами приводятся в таблице 1:
Табл. 1
|
база |
Т2 |
Т3 |
Т4 |
Т5 |
Т6 |
база |
- |
10 |
6 |
15 |
9 |
11 |
Т2 |
10 |
- |
10 |
12 |
21 |
14 |
Т3 |
6 |
10 |
- |
15 |
18 |
12 |
Т4 |
15 |
12 |
15 |
- |
21 |
17 |
Т5 |
9 |
21 |
18 |
21 |
- |
16 |
Т6 |
11 |
14 |
12 |
17 |
16 |
- |
Пустые клетки означают, что дороги или ремонтируются или плохого качества.
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
Сеть дорог, связывающих базу с магазинами области можно представить в виде неориентированного графа, вершинам которого поставлены в соответствие название базы и магазинов, ребрам - связывающие их дороги, и каждому ребру поставлен в соответствие вес - длина дороги. Для удобства обозначим название базы через хьа торговые точки через х2, х3, х3, х5. Расстояния от вершины Х\ до всех остальных и между вершинами представим в виде матрицы весов неориентированного графа (табл. 2). Для наглядности в матрице весов знаки оо (показывающие отсутствие дороги) опустим. Тогда задача сводится к нахождению кратчайших путей от вершины X] до всех остальных. Для ее решения используем метод Дейкстры.
Табл. 2
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
Х1 |
- |
10 |
6 |
15 |
9 |
11 |
Х2 |
10 |
- |
10 |
12 |
21 |
14 |
Х3 |
6 |
10 |
- |
15 |
18 |
12 |
Х4 |
15 |
12 |
15 |
- |
21 |
17 |
Х5 |
9 |
21 |
18 |
21 |
- |
16 |
Х6 |
11 |
14 |
12 |
17 |
16 |
- |