Автор: Евгений Степанов, 22 Ноября 2010 в 19:37, контрольная работа
Линейные транспортные задачи составляют особый класс задач линейного
программирования. Задача заключается в отыскании такого плана перевозок
продукции с “m “ складов в пункт назначения “n” который, потребовал бы
минимальных затрат.
Введение 3
1. Реальная постановка задачи 4
2. Математическая модель задачи 5
3. Определение опорных планов 6
4.Определение оптимальных планов 13
5.Охрана труда 30
Список литературы 32
Приложение 33
Найдём первую итерацию:
Найдём потенциалы для занятых клеток:
Найдём потенциалы для свободных клеток:
Так
как среди потенциалов
| Таблица 5 | ||||||
| Пункты отправления | Пункты
назначения |
Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | -6 | -7 | -8 | -1 | 0 | 15 |
| 15 | ||||||
| А2 | -12 | -13 | -14 | -8 | 0 | 47 |
| 3 | 10 | 34 | ||||
| А3 | -8 | -9 | -4 | -3 | 0 | 71 |
| 19 | 51 | 1 | ||||
| А4 | -4 | -6 | -8 | -9 | 0 | 28 |
| 28 | ||||||
| А5 | -2 | -1 | -3 | -1 | 0 | 33 |
| 33 | ||||||
| Потребности | 18 | 29 | 34 | 51 | 62 | |
Найдём потенциалы для свободных клеток:
Так
как среди потенциалов
| Таблица 6 | ||||||
| Пункты отправления | Пункты
назначения |
Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | -6 | -7 | -8 | -1 | 0 | 15 |
| 15 | ||||||
| А2 | -12 | -13 | -14 | -8 | 0 | 47 |
| 3 | 10 | 34 | ||||
| А3 | -8 | -9 | -4 | -3 | 0 | 71 |
| 19 | 23 | 29 | ||||
| А4 | -4 | -6 | -8 | -9 | 0 | 28 |
| 28 | ||||||
| А5 | -2 | -1 | -3 | -1 | 0 | 33 |
| 33 | ||||||
| Потребности | 18 | 29 | 34 | 51 | 62 | |
Найдём потенциалы для свободных клеток:
Так
как среди потенциалов
| Таблица 7 | ||||||
| Пункты отправления | Пункты
назначения |
Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | -6 | -7 | -8 | -1 | 0 | 15 |
| 5 | 10 | |||||
| А2 | -12 | -13 | -14 | -8 | 0 | 47 |
| 13 | 34 | |||||
| А3 | -8 | -9 | -4 | -3 | 0 | 71 |
| 29 | 19 | 23 | 19 | |||
| А4 | -4 | -6 | -8 | -9 | 0 | 28 |
| 28 | ||||||
| А5 | -2 | -1 | -3 | -1 | 0 | 33 |
| 33 | ||||||
| Потребности | 18 | 29 | 34 | 51 | 62 | |
Найдём потенциалы для свободных клеток:
Так
как среди потенциалов
| Таблица 8 | ||||||
| Пункты отправления | Пункты
назначения |
Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | -6 | -7 | -8 | -1 | 0 | 15 |
| 5 | 10 | |||||
| А2 | -12 | -13 | -14 | -8 | 0 | 47 |
| 13 | 29 | 34 | ||||
| А3 | -8 | -9 | -4 | -3 | 0 | 71 |
| 42 | ||||||
| А4 | -4 | -6 | -8 | -9 | 0 | 28 |
| 9 | 19 | |||||
| А5 | -2 | -1 | -3 | -1 | 0 | 33 |
| 33 | ||||||
| Потребности | 18 | 29 | 34 | 51 | 62 | |
Найдём потенциалы для свободных клеток:
Так как среди потенциалов свободных клеток есть положительные числа, план не оптимален, улучшим данный план. Цикл пересчёта нарисован в таблице 8.Среди отрицательных вершин найдём минимальное значение перевозок. Прибавим это значение к вершине, где стоит знак “плюс” и вычтем из вершин, где стоит знак минус. Новый опорный план представлен в таблице 9. Проверим план на оптимальность.
| Таблица 9 | ||||||
| Пункты отправления | Пункты
назначения |
Запасы | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 | -6 | -7 | -8 | -1 | 0 | 15 |
| 15 | ||||||
| А2 | -12 | -13 | -14 | -8 | 0 | 47 |
| 13 | 34 | |||||
| А3 | -8 | -9 | -4 | -3 | 0 | 71 |
| 5 | 29 | 37 | ||||
| А4 | -4 | -6 | -8 | -9 | 0 | 28 |
| 14 | 14 | |||||
| А5 | -2 | -1 | -3 | -1 | 0 | 33 |
| 33 | ||||||
| Потребности | 18 | 29 | 34 | 51 | 62 | |