Автор работы: Пользователь скрыл имя, 26 Марта 2013 в 03:27, контрольная работа
Цель работы – определение метода расчета плана перевозки продукции со склада по предприятиям-потребителям, при котором обеспечивается минимальные транспортные расходы на перевозку всей продукции.
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом.
Очевидно, что полученный план не является оптимальным, т.к. среди характеристик свободных клеток есть отрицательные.
Далее без комментариев повторяем итерацию с перемещением перевозки (15) по циклу в клетку a1b4 с отрицательной характеристикой (-3). Получаем третий план (табл. №3).
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |||
|
1 |
2 |
3 |
4 | |||
95 |
160 |
135 |
110 | |||
1 |
105 |
17
13 |
12 90 |
17
1 |
21 15 |
U1 = 0 |
2 |
70 |
6
3 |
11 70 |
20
5 |
28
8 |
U2 = -1 |
3 |
240 |
10 95 |
19
1 |
22 135 |
27 10 |
U3 = 6 |
4 |
85 |
18
8 |
14
16 |
23
21 |
7 85 |
U4 = -14 |
Vj |
V1 = 4 |
V2 = 12 |
V3 = 16 |
V4 = 21 |
№3 | |
Этот план оптимальный, т.к. все характеристики свободных клеток положительны. План повторяет план, ране полученный методом северо-западного угла.
Zопт = Zmin = 6950 ден. ед.
Построение оптимального плана методом Фогеля.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
||||||||
1 |
2 |
3 |
4 |
|||||||
95 |
160 |
135 |
110 |
|||||||
1 |
105 |
17
|
12 90 |
17
|
21 15 |
5 |
5 |
5 |
5 |
5 |
2 |
70 |
6
|
11 70 |
20
|
28
|
5 |
5 |
9 |
||
3 |
240 |
10 95 |
19
|
22 135 |
27 10 |
9 |
9 |
3 |
3 |
3 |
4 |
85 |
18 |
14 |
23 |
7 85 |
7 |
||||
4 |
1 |
3 |
14 |
|||||||
4 |
1 |
3 |
6 |
|||||||
1 |
3 |
6 |
||||||||
2 |
5 |
6 |
||||||||
2 |
5 |
|||||||||
При определении опорного плана методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находим разность между двумя записанными в них минимальными затратами. Эти разности записаны в специально отведенных для этого строках и столбцах для каждого шага. Среди указанных разностей выбрана максимальная. В строке (или в столбце), которой данная разность соответствует, определён минимальный тариф и клетка, в которой он записан, заполнена на данной итерации (выделено жирным шрифтом).
Например, на первом шаге в первой строке минимальные затраты 17 и 12, разность – 5, во 2-ой строке 11 и 6, разность 5, в 3-ей 19 и 10, разность 9, в 4-ой 14 и 7, разность 7.
В 1-ом столбце минимальные затраты 10 и 6, разность 4, во 2-ом 12 и 11, разность 1, в 3-ем 20 и 17, разность 3, в 4-ом 21 и 7, разность 14.
Наибольшая из этих разностей – 14 соответствует 4-му столбцу. В этом столбце минимум затрат – 7 в строке 4. Заполняем клетку а4b4 объёмом поставок 85 единиц, который может быть поставлен от четвёртого поставщика и строку 4 из дальнейшего рассмотрения исключаем. По аналогии заполнены остальные клетки таблицы и получен опорный план.
Цена этого плана:
Z1 = 90∙12 + 15·21 + 70∙11 + 95∙10 + 135∙22 + 10·27 + 85·7 = 6950 д.е.
Этот полученный план является оптимальным, т.к. такой же план получен при использовании методов северо-западного угла и минимального элемента.
Задача 7.2. Решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана, произвести перепланировку поставок с помощью метода потенциалов.
Решение: Общий объём запасов:
Общая потребность:
Т.к. , то это транспортная задача открытого типа.
Для приведения её к закрытому типу вводим фиктивного потребителя с нулевой стоимостью перевозок, имеющего потребность:
Построение оптимального плана методом северо-западного угла.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | ||||
|
1 |
2 |
3 |
4 |
5 | |||
95 |
135 |
135 |
110 |
25 | |||
1 |
105 |
- 17 |
+ 12 10 |
17
2 |
21
1 |
0
-13 |
U1 = 0 |
2 |
70 |
6
-10 |
11 70 |
20
6 |
28
9 |
0
-12 |
U2 = -1 |
3 |
240 |
+ 10
-14 |
- 19 55 |
22 135 |
27 50 |
0
-20 |
U3 = 7 |
4 |
85 |
18
14 |
14
15 |
23
21 |
7 60 |
0 25 |
U4 = -13 |
Vj |
V1 = 17 |
V2 = 12 |
V3 = 15 |
V4 = 20 |
V5 = 13 |
№1 | |
Порядок составления опорного плана этим методом описан в задаче 7.1.
Стоимость перевозок по этому плану:
Z1 = 95·17 + 10∙12 + 70∙11 + 55∙19 + 135∙22 + 50·27 + 60·7 = 8290 д.е.
Число заполненных клеток должно быть m + n –1 = 4 + 5 – 1 = 8, что имеет место в действительности, т.е. план не вырожден.
Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:
Ui = Cij – Vj; Vj = Cij – Ui;
Определяем характеристики клеток, оставшихся свободными по формуле:
Eij = Cij – (Vj + Ui) (вписаны в правый нижний угол).
Среди характеристик свободных клеток есть отрицательные, значит полученный план не оптимален.
Строим для клетки а3b1 с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2) с ценой z2 = 7520.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | ||||
|
1 |
2 |
3 |
4 |
5 | |||
95 |
135 |
135 |
110 |
25 | |||
1 |
105 |
- 17 |
12 65 |
17
-12 |
+ 21
-13 |
0
-27 |
U1 = 0 |
2 |
70 |
6
-10 |
11 70 |
20
-8 |
28
-5 |
0
-26 |
U2 = -1 |
3 |
240 |
+ 10 55 |
19
14 |
22 135 |
- 27 50 |
0
-20 |
U3 = -7 |
4 |
85 |
18
28 |
14
29 |
23
21 |
7 60 |
0 25 |
U4 = -27 |
Vj |
V1 = 17 |
V2 = 12 |
V3 = 29 |
V4 = 34 |
V5 = 27 |
№2 | |
Среди характеристик свободных клеток есть отрицательные значит полученный план не оптимален.
Строим для клетки а1b4 с отрицательной характеристикой (-13), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (40), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №3) с ценой z3 = 7000.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | ||||
|
1 |
2 |
3 |
4 |
5 | |||
95 |
135 |
135 |
110 |
25 | |||
1 |
105 |
17
13 |
12 65 |
17
1 |
21 40 |
0
-14 |
U1 = 0 |
2 |
70 |
6
3 |
11 70 |
20
5 |
28
8 |
0
-13 |
U2 = -1 |
3 |
240 |
10 95 |
19
1 |
22 135 |
- 27 10 |
+ 0
-20 |
U3 = 6 |
4 |
85 |
18
28 |
14
16 |
23
21 |
- 7 60 |
+ 0 25 |
U4 = -14 |
Vj |
V1 = 4 |
V2 = 12 |
V3 = 16 |
V4 = 21 |
V5 = 14 |
№3 | |
Проверка методом потенциалов показывает, что этот план тоже не оптимален, т.к. среди характеристик свободных клеток есть отрицательные. Cтроим цикл для клетки а3b5 с характеристикой (-20). Получаем четвёртый план (табл. №4) c ценой z4 = 6800.
Проверка методом потенциалов показывает, что этот план тоже не оптимален, т.к. среди характеристик свободных клеток есть отрицательные. Cтроим цикл для клетки а2b1 с характеристикой (-17). Перемещаем по этому циклу наименьшую перевозку (15), отмеченную знаком "минус".
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | ||||
|
1 |
2 |
3 |
4 |
5 | |||
95 |
135 |
135 |
110 |
25 | |||
1 |
105 |
17
-7 |
+ 12 65 |
17
-19 |
- 21 40 |
0
-14 |
U1 = 0 |
2 |
70 |
+ 6
-17 |
- 11 70 |
20
-15 |
28
-8 |
0
-13 |
U2 = -1 |
3 |
240 |
- 10 95 |
19
21 |
22 135 |
27
20 |
+ 0 10 |
U3 = -14 |
4 |
85 |
18
28 |
14
16 |
23
3 |
+ 7 70 |
- 0 15 |
U4 = -14 |
Vj |
V1 = 24 |
V2 = 12 |
V3 = 36 |
V4 = 21 |
V5 = 14 |
№4 | |
Получаем пятый план (табл. №5) с ценой z5 = 6545.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | ||||
|
1 |
2 |
3 |
4 |
5 | |||
95 |
135 |
135 |
110 |
25 | |||
1 |
105 |
17
10 |
- 12 80 |
+ 17
–2 |
21 25 |
0
3 |
U1 = 0 |
2 |
70 |
- 6 15 |
+ 11 55 |
20
2 |
28
8 |
0
4 |
U2 = -1 |
3 |
240 |
+ 10 80 |
19
4 |
- 22 135 |
27
3 |
0 25 |
U3 = 3 |
4 |
85 |
18
25 |
14
16 |
23
18 |
7 85 |
0 |
U4 = -14 |
Vj |
V1 = 7 |
V2 = 12 |
V3 = 19 |
V4 = 21 |
V5 = -3 |
№5 | |