Автор работы: Пользователь скрыл имя, 26 Марта 2013 в 03:27, контрольная работа
Цель работы – определение метода расчета плана перевозки продукции со склада по предприятиям-потребителям, при котором обеспечивается минимальные транспортные расходы на перевозку всей продукции.
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом.
Введение
Цель работы – определение метода
расчета плана перевозки
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громоздко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.
Содержание
Задача 7.1. Решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана, произвести перепланировку поставок с помощью метода потенциалов.
Решение: Общий объём запасов:
Общая потребность:
Т.к. , то это транспортная задача закрытого типа.
Построение оптимального плана методом северо-западного угла.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |||
|
1 |
2 |
3 |
4 | |||
95 |
160 |
135 |
110 | |||
1 |
105 |
- 17 95 |
+ 12 10 |
17
2 |
21
1 |
U1 = 0 |
2 |
70 |
6
-10 |
11 70 |
20
6 |
28
9 |
U2 = -1 |
3 |
240 |
+ 10
-14 |
- 19 80 |
22 135 |
27 25 |
U3 = 7 |
4 |
85 |
18
14 |
14
15 |
23
21 |
7 85 |
U4 = -13 |
Vj |
V1 = 17 |
V2 = 12 |
V3 = 15 |
V4 = 20 |
№1 | |
Здесь в верхнем правом углу клеток записана стоимость перевозки.
Заполнять таблицу первоначального опорного плана начинаем с клетки а1b1 – это северо-западный угол.
Закрываем потребности b1 поставкой из а1 и этот столбец исключаем из дальнейшего рассмотрения. Остаток груза из а1 отправляем потребителю b2 и строку а1 исключаем из дальнейшего рассмотрения. Затем весь груз из а2 отправляем в b2, исключая строку а2 и частью груза из а3 закрываем потребность b2, исключая столбец b2. Далее закрываем потребность b3 поставкой из а3, а остаток груза из а3 отправляем потребителю b4. Груз из а4 отправляем потребителю b4. Опорный план составлен.
Стоимость перевозок по этому плану:
Z1 = 95·17 + 10∙12 + 70∙11 + 80∙19 + 135∙22 + 25·27 + 85·7 = 8265 д.е.
Число заполненных клеток должно быть m + n –1 = 4 + 4 – 1 = 7, что так и есть, т.е. план не вырожден.
Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:
Ui = Cij – Vj; Vj = Cij – Ui;
V1 = C11 – U1 = 17 – 0 = 17; V2 = C12 – U1 = 12 – 0 = 12; U2 = C22 – V2 = 11 – 12 = -1;
U3 = C32 – V2 = 19 – 12 = 7; V3 = C33 – U3 = 22 – 7 = 15; V4 = C34 – U3 = 27 – 7 = 20.
U4 = C44 – V4 = 7 – 20 = -13;
Определяем характеристики клеток, оставшихся свободными по формуле:
Eij = Cij – (Vj + Ui) (вписаны в левый нижний угол)
Е13 = С13 – (V3 + U1) = 17 – (15 + 0) = 2; Е14 = С14 – (V4 + U1) = 21 – (20 + 0) = 1;
Е21 = С21 – (V1 + U2) = 6 – (17 - 1) = -10; Е23 = С23 – (V3 + U2) = 20 – (15 - 1) = 6;
Е24 = С24 – (V4 + U2) = 28 – (20 - 1) = 9; Е31 = С31 – (V1 + U3) = 10 – (17 + 7) = -14;
Е41 = С41 – (V1 + U4) = 18 – (17 - 13) = 14; Е42 = С42 – (V2 + U4) = 14 – (12 - 13) = 15;
Е43 = С43 – (V3 + U4) = 23 – (15 - 13) = 21;
Среди характеристик свободных клеток есть две отрицательные (Е21 = -10 и Е31 = -14), значит полученный план не оптимален.
Строим для клетки а3b1 с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (80), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2).
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |||
|
1 |
2 |
3 |
4 | |||
95 |
160 |
135 |
110 | |||
1 |
105 |
- 17 |
12 90 |
17
-12 |
+ 21
-13 |
U1 = 0 |
2 |
70 |
6
-10 |
11 70 |
20
-8 |
28
-5 |
U2 = -1 |
3 |
240 |
+ 10 80 |
19
14 |
22 135 |
- 27 25 |
U3 = -7 |
4 |
85 |
18
8 |
14
29 |
23
21 |
7 85 |
U4 = -27 |
Vj |
V1 = 17 |
V2 = 12 |
V3 = 29 |
V4 = 34 |
№2 | |
Цена этого плана:
Z2 = 15·17 + 90∙12 + 70∙11 + 80∙10 + 135∙22 + 25·27 + 85·7 = 7145 д.е.
что меньше первого плана на 1120 ден. ед.
Проверка методом потенциалов показывает, что этот план не оптимален, т.к. среди характеристик свободных клеток есть отрицательные.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
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 | |
Далее без комментариев повторяем итерацию с перемещением перевозки по циклу в клетку a1b4 с отрицательной характеристикой (-13). Получаем третий план (табл. №3).
Его цена:
Z3 = 90∙12 + 15·21 + 70∙11 + 95∙10 + 135∙22 + 10·27 + 85·7 = 6950 д.е.
что меньше второго плана на 195 ден. ед.
Этот план оптимальный, т.к. все характеристики свободных клеток положительны.
Zопт = Zmin = Z3 = 6950 ден. ед.
Построение оптимального плана методом минимального элемента.
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |||
|
1 |
2 |
3 |
4 | |||
95 |
160 |
135 |
110 | |||
1 |
105 |
17
14 |
12 105 |
17
2 |
21
1 |
U1 = 0 |
2 |
70 |
- 6 70 |
+ 11
-4 |
20
2 |
28
5 |
U2 = 3 |
3 |
240 |
+ 10 25 |
- 19 55 |
22 135 |
27 25 |
U3 = 7 |
4 |
85 |
18
29 |
14
16 |
23
22 |
7 85 |
U4 = -14 |
Vj |
V1 = 3 |
V2 = 12 |
V3 = 15 |
V4 = 20 |
№1 | |
Минимальная стоимость перевозок (6) в клетке а2b1 – отправляем весь груз из а2 потребителю b1 и строку а2 исключаем из дальнейшего рассмотрения.
Следующий минимум (7) в клетке а4b4 – отправляем весь груз из а4 потребителю b4 и строку а4 исключаем из дальнейшего рассмотрения.
Следующий минимум (10) в клетке а3b1 – закрываем потребность b1 поставкой из а3 и столбец b1 исключаем из дальнейшего рассмотрения.
Следующий минимум (12) в клетке а1b2 – весь груз из а1 отправляем в b2 и строку а1 исключаем из дальнейшего рассмотрения.
Следующий минимум (19) в клетке а3b2 – закрываем потребность b2 поставкой из а3 и столбец b2 исключаем из дальнейшего рассмотрения.
Поставкой остатка груза из а3 закрываем потребности b3 и b4.
Опорный план составлен.
Стоимость перевозок по этому плану:
Z1 = 105·12 + 70∙6 + 25∙10 + 55∙19 + 135∙22 + 25·27 + 85·7 = 7215 д.е.
Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:
Ui = Cij – Vj; Vj = Cij – Ui;
Определяем характеристики клеток, оставшихся свободными по формуле:
Eij = Cij – (Vj + Ui) (вписаны в левый нижний угол).
Среди характеристик свободных клеток есть одна отрицательная (Е22 = -4), значит полученный план не оптимален.
Строим для клетки а2b , цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2).
Номер поставщика |
Мощность поставщика |
Потребители и их спрос |
Ui | |||
|
1 |
2 |
3 |
4 | |||
95 |
160 |
135 |
110 | |||
1 |
105 |
17
10 |
- 12 105 |
17
-2 |
+ 21
-3 |
U1 = 0 |
2 |
70 |
- 6 15 |
+ 11 55 |
20
2 |
28
5 |
U2 = -1 |
3 |
240 |
+ 10 80 |
19
4 |
22 135 |
- 27 25 |
U3 = 3 |
4 |
85 |
18
28 |
14
19 |
23
21 |
7 85 |
U4 = -17 |
Vj |
V1 = 7 |
V2 = 12 |
V3 = 19 |
V4 = 24 |
№2 | |