Автор работы: Пользователь скрыл имя, 19 Сентября 2012 в 10:24, контрольная работа
Цель работы – определение метода расчета плана перевозки продукции со склада по предприятиям-потребителям, при котором обеспечивается минимальные транспортные рас-ходы на перевозку всей продукции.
Под названием транспортная задача объединяется широкий круг задач с единой матема-тической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом.
Задача 7.1. 3
Задача 7.2. 10
Список литературы 19
Проверка методом потенциалов показывает, что этот план тоже не оптимален, т.к. среди характеристик свободных клеток есть отрицательные. 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 | |
Ещё одна итерация по клетке а1b3 с перемещением 15 единиц груза и получаем оптимальный план с положительными характеристиками всех свободных клеток (табл.№6):
Номер поставщика | Мощность поставщика | Потребители и их спрос | Ui | ||||
1 | 2 | 3 | 4 | 5 | |||
95 | 135 | 135 | 110 | 25 | |||
1 | 105 | 17 12 | 12 65 | 17 15 | 21 25 | 0
5 | U1 = 0 |
2 | 70 | 6
2 | 11 70 | 20
4 | 28
8 | 0
6 | U2 = -1 |
3 | 240 | 10 95 | 19
2 | 22 120 | 27
1 | 0 25 | U3 = 5 |
4 | 85 | 18
27 | 14
16 | 23
20 | 7 85 | 0
19 | U4 = -14 |
Vj | V1 = 5 | V2 = 12 | V3 = 17 | V4 = 21 | V5 = -5 | №6 | |
Цена этого плана:
Z6 = 65·12 + 15∙17 + 25·21 + 70∙11 + 95·10 + 120·22 + 85·7 = 6515 ден.ед.
Zопт = Zmin = Z6 = 6515 ден. ед.
Т.о. у поставщика а3 не будет запрошено 25 единиц груза, т.к. этой частью своего груза он прикрепился к фиктивному потребителю.
Построение оптимального плана методом минимального элемента.
Номер поставщика | Мощность поставщика | Потребители и их спрос | Ui | ||||
1 | 2 | 3 | 4 | 5 | |||
95 | 135 | 135 | 110 | 25 | |||
1 | 105 | 17
14 | 12 105 | 17
2 | 21
1 | 0
7 | U1 = 0 |
2 | 70 | - 6 70
| + 11
-4 | 20
2 | 28
5 | 0
4 | U2 = 3 |
3 | 240 | + 10 25
| - 19 30 | 22 135 | 27 25 | 0 25
| U3 = 7 |
4 | 85 | 18
28 | 14
15 | 23
21 | 7 85 | 0
20 | U4 = -13 |
Vj | V1 = 3 | V2 = 12 | V3 = 15 | V4 = 20 | V5 = -7 | №1 | |
Построение опорного плана эти методом описано в задаче 7.1.
Стоимость перевозок по этому плану Z1 = 6740 д.е.
Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:
Ui = Cij – Vj; Vj = Cij – Ui;
Определяем характеристики клеток, оставшихся свободными по формуле:
Eij = Cij – (Vj + Ui) (вписаны в правый нижний угол).
Среди характеристик свободных клеток есть отрицательные, значит полученный план не оптимален. По аналогии производим итерации по перемещению груза в клетки с отрицательными характеристиками.
Второй план (табл. №2) с ценой Z2 = 6620 д.е.
Номер поставщика | Мощность поставщика | Потребители и их спрос | Ui | ||||
1 | 2 | 3 | 4 | 5 | |||
95 | 135 | 135 | 110 | 25 | |||
1 | 105 | 17
10 | - 12 105 | + 17
-2 | 21
-3 | 0
3 | U1 = 0 |
2 | 70 | - 6 40
| + 11 30 | 20
2 | 28
5 | 0
4 | U2 = -1 |
3 | 240 | + 10 55
| 19
4 | - 22 135 | 27 25 | 0 25
| U3 = 3 |
4 | 85 | 18
28 | 14
19 | 23
21 | 7 85 | 0
20 | U4 = -17 |
Vj | V1 = 7 | V2 = 12 | V3 = 19 | V4 = 24 | V5 = -3 | №2 | |