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