Материал: 5462
41
|
|
|
|
План Х2 |
|
|
|
|
|
Таблица 4 |
||
|
63 |
34 |
43 |
|
50 |
65 |
|
70 |
||||
|
|
|
1,5 |
|
3 |
2,5 |
1 |
+ |
|
2 |
1,8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
75 |
|
|
|
|
|
|
|
50 |
|
|
|
25 |
|
|
|
|
|
|
|
|
|
|
|||
100 |
|
|
1 |
|
3,5 |
2 |
3 |
|
|
4 |
1 |
|
55 |
|
|
|
|
|
|
|
|
|
|
45 |
|
|
|
|
|
|
|
|
|
|
|
|
||
150 |
|
|
1,2 |
|
2 |
2,2 |
2,5 |
|
|
2,5 |
3 |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
+ |
34 |
43 |
|
|
65 |
|
|
|||
|
|
|
|
|
|
|||||||
Для плана Х2 T2 |
max tij |
t35 |
2,5. |
|
|
|
|
|||||
Для нового плана Х2 проводим аналогичную итерацию, т.е. повторяем действия 2,3,4.
По маршруту (3,5)-(3,1)-(2,1)-(2,6)-(1,6)-(1,5) перемещаем поставку 
min 25;65;55 25 (план Х3, табл. 5), что не оказывает влияния на общую продолжительность реализации плана перевозок. Все другие маршруты, исходящие из 3-й клетки (3,5), имеют пустую клетку со знаком «минус», поэтому полная разгрузка клетки (3,5) невозможна. Следовательно, T min Tk min 3;2,5 2,5 (час).
Легко видеть, что планов со временем реализации Т = 2,5 можно построить несколько. Для этого не нужно вычеркивать клетки с tij 2,5 . Рассмотрим
план Х3 (табл. 5) и план Х4 (табл. 6), который используем в следующей задаче.
|
|
|
План Х3 |
|
|
|
|
Таблица 5 |
|
63 |
34 |
43 |
50 |
65 |
70 |
||
|
1,5 |
|
2,5 |
1 |
2 |
1,8 |
||
75 |
|
|
|
50 |
25 |
|
||
100 |
1 |
|
2 |
|
|
|
|
1 |
30 |
|
|
|
|
|
|
70 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
150 |
1,2 |
2 |
2,2 |
|
2,5 |
|
2,5 |
|
33 |
34 |
43 |
|
|
40 |
|
||
|
|
|
|
|||||
42
|
План Х4 |
|
|
|
Таблица 6 |
|
|
63 |
34 |
43 |
50 |
65 |
70 |
|
1,5 |
|
2,5 |
1 |
2 |
1,8 |
75 |
|
|
|
10 |
65 |
|
100 |
1 |
|
2 |
|
|
1 |
30 |
|
|
|
|
70 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
150 |
1,2 |
2 |
2,2 |
2,5 |
2,5 |
|
33 |
34 |
43 |
40 |
|
|
|
|
|
|
||||
Вопросы для самопроверки
1.В чем смысл транспортной задачи по критерию минимума времени?
2.Чем отличается маршрут от контура?
3.Как определяется время реализации полученного плана перевозок?
4.Считают ли в этой задаче число занятых клеток в таблице и почему?
5. Почему в таблице зачеркивают клетки, для которых tij tплан ?
6.Чем отличается опорный план от допустимого, и какой план находится в задаче по критерию минимума времени?
Задачи для самостоятельного решения
Найти два плана, для которых выполняется минимальное время реализации при следующих данных:
|
|
|
3 |
1 |
2 |
1,8 |
2,5 |
1,5 |
1. ai |
(85; 105; 155); |
T |
3,5 |
3 |
4 |
1 |
2 |
1 |
|
|
|
2 |
2,5 |
2,5 |
3 |
2,2 |
1,2 |
b j |
(75; 80; 35; 48; 52; 55). |
|
|
|
|
|
|
|
|
|
|
1 |
2 |
1,8 |
1,5 |
3 |
1,5 |
2. ai |
(47; 63; 120); |
T |
3 |
4 |
1 |
1 |
3,5 |
2 |
|
|
|
2,5 |
2,5 |
3 |
1,2 |
2 |
2,2 |
b j |
(60; 54; 26; 40; 28; 22). |
|
|
|
|
|
|
|
|
|
|
43 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1,5 |
1,8 |
|
3 |
2,5 |
1 |
|
2 |
|
3. |
ai |
(87; 53; 60); |
T |
1 |
1 |
3,5 |
2 |
|
3 |
|
4 |
|
|
|
|
|
1,2 |
3 |
|
2 |
2,2 |
2,5 |
|
2,5 |
|
|
b j |
(54; 46; 32; 28; 19; 21). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
2,5 |
|
1 |
1,5 |
1,8 |
|
2 |
|
4. |
ai |
(125; 75; 50); |
T |
3,5 |
2 |
|
3 |
1 |
|
1 |
|
1 |
|
|
|
|
2 |
2,2 |
2,5 |
1,2 |
|
3 |
2,5 |
||
|
b j |
(70; 55; 40; 45; 25; 15). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,8 |
2 |
|
1 |
2,5 |
3 |
|
1,5 |
|
5. |
ai |
(62; 37; 91); |
T |
1 |
4 |
|
3 |
2 |
|
3,5 |
|
1 |
|
|
|
|
3 |
2,5 |
2,5 |
2,2 |
2 |
|
1,2 |
||
|
b j |
(35; 45; 50; 36; 10; 14). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1,8 |
2,5 |
3 |
1,5 |
|
1 |
||
6. |
ai |
(83; 47; 63); |
T |
4 |
1 |
|
2 |
3,5 |
1 |
|
3 |
|
|
|
|
|
2,5 |
3 |
|
2,2 |
2 |
1,2 |
|
2,5 |
|
|
b j |
(35; 45; 60; 20; 20; 13). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2,5 |
1 |
2 |
1,8 |
1,5 |
3 |
|||
7. |
ai |
(34; 86; 70); |
T |
2 |
3 |
4 |
1 |
1 |
|
3,5 |
||
|
|
|
|
2,2 |
2,5 |
2,5 |
3 |
1,2 |
2 |
|||
|
b j |
(55; 45; 32; 28; 14; 16). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,8 |
1,5 |
3 |
2 |
2,5 |
1 |
|||
8. |
ai |
(69; 71; 82); |
T |
1 |
1 |
3,5 |
4 |
2 |
3 |
|||
|
|
|
|
3 |
1,2 |
2 |
2,5 |
2,2 |
2,5 |
|||
|
b j |
(57; 33; 42; 34; 29; 27). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,8 |
2 |
2,5 |
1 |
|
3 |
1,5 |
||
9. |
ai |
(77; 63; 84); |
T |
1 |
|
4 |
2 |
|
3 |
3,5 1 |
||
|
|
|
|
3 |
2,5 |
2,2 |
2,5 |
2 |
1,2 |
|||
|
b j |
(52; 38; 26; 55; 26; 27). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
1,5 |
2 |
1 |
2 |
1,8 |
|||
10. ai |
(96; 104; 58); |
T |
3,5 |
1 |
4 |
3 |
1 |
|
1 |
|||
|
|
|
|
2 |
1,2 |
5 |
2,5 |
3 |
1,6 |
|||
|
b j |
(51; 39; 76; 22; 34; 36). |
|
|
|
|
|
|
|
|
|
|
44
Глава 5. Транспортные задачи с учетом времени и издержек
Решение транспортных задач по критерию минимума времени оправдано лишь в особых случаях в связи с высокими затратами на их реализацию. Возможность существования нескольких планов, минимизирующих время, позволяет выбрать из них планы с наименьшими издержками.
Наряду с матрицей времени T 
tij используется матрица издержек C 
cij . По методу потенциалов определяется план Хс, минимизирующий издержки Zmin . Определяется продолжительность его реализации Тс. Если
такая продолжительность удовлетворительна в данной ситуации, то распределение следует считать наименьшим. Если же необходимо уложиться в более короткий срок Тк, то используют планы меньшей продолжительности и определяют затраты для их реализации.
Среди всех планов, которые входят во время Тк, найти план с относительно меньшими издержками, сохраняя запреты на клетки, для которых tij Tk . Осуществляют перераспределение грузов, снимая их с
«дорогих» коммуникаций и перебрасывая их на «дешевые» по замкнутым маршрутам. Так при перемещении по маршруту издержки изменяются на величину
Z Ci1 j1 Ci1 j2 |
Ci2 j2 Ci2 j1 |
Ci1 j1 Ci2 j2 Ci1 j2 Ci2 j1 |
||
(i1, j1) |
|
|
(i1, j2 ) |
|
|
|
|
|
|
|
- |
+ |
|
|
(i2 , j1) |
+ |
- |
(i2 , j2 ) |
|
|
|
|
||
Если выражение положительно, то его величина характеризует выигрыш в суммарных затратах, если отрицательно, то – удорожание стоимости перевозок.
Пример. Среди найденных планов наименьшего времени реализации по условию примера предыдущей главы найти план с относительно наименьшими издержками при заданной матрице издержек
|
6 |
3 |
4 |
7,5 |
5 |
5,5 |
С |
8 |
2,2 |
5,5 |
3 |
2 |
7,5 . |
|
7 |
6 |
5,8 |
4,2 |
4,3 |
3,2 |
Оценить выигрыш во времени и потери в издержках относительно Zmin .
Решение. Определяем план Хс, минимизирующий издержки, по методу потенциалов. Записывая tij в верхнем правом углу клеток, а Cij – в
нижнем правом (табл. 7)
45
(При реализации на компьютере внести информацию по ai ,bj и cij без
учета tij ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
План Хс |
|
|
|
|
|
|
|
Таблица 7 |
|
63 |
|
34 |
43 |
50 |
|
65 |
|
|
70 |
||
|
|
1,5 |
3 |
2,5 |
|
|
1 |
|
2 |
|
1,8 |
|
75 |
32 |
|
43 |
|
7,5 |
|
|
|
5,5 |
|||
|
|
6 |
3 |
4 |
|
5 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|||
|
|
1 |
3 |
2 |
|
|
3 |
|
4 |
|
1 |
|
100 |
|
|
34 |
|
1 |
|
|
65 |
|
|
|
|
|
|
8 |
|
2,2 |
5,5 |
|
|
3 |
2 |
|
7,5 |
|
|
|
|
|
|
|
|
||||||
|
|
1,2 |
2 |
2,2 |
|
|
2,5 |
|
2,5 |
|
3 |
|
150 |
33 |
49 |
|
|
70 |
|||||||
|
7 |
6 |
5,8 |
|
4,2 |
|
4,3 |
|
3,2 |
|||
|
|
|
|
|
||||||||
Определяем Тс max tij |
t25 |
4 (час); Zmin |
1218,6 руб. |
|||||||||
Для определения плана наименьшего по времени с относительно наименьшими издержками решим задачу с запретами на клетки, для которых tij 2,5 , заблокировав их запретительными тарифами M 100 .
Данные для решения задачи на компьютере предоставлены в таблице
|
|
63 |
34 |
43 |
50 |
65 |
70 |
|
|
6 |
|
4 |
7,5 |
5 |
5,5 |
75 |
|
62 |
|
|
|
|
13 |
100 |
8 |
|
5,5 |
|
|
7,5 |
|
|
|
43 |
|
|
57 |
||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
150 |
7 |
6 |
5,8 |
4,2 |
4,3 |
|
|
1 |
34 |
|
50 |
65 |
|
||
|
|
|
|
||||
Получаем оптимальное решение задачи |
|
|
|||||
t |
2,5 (час) |
Z 1808 |
|
|
|
|
|
Дополнительные издержки
Z Z Zmin 589,4