Автор работы: Пользователь скрыл имя, 15 Июня 2014 в 12:03, курсовая работа
Целью данной курсовой работы является рассмотрение теоретической части, в которую входят различные методы решения задачи нахождения потока наименьшей стоимости и практической части, в которой реализованы данные методы для конкретно поставленной задачи.
ВВЕДЕНИЕ 3
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 4
Сетевая модель 4
Сетевая модель как задача линейного программирования 4
Алгоритм симплекс-метода для сетей с ограниченной пропускной способностью 6
Транспортная задача 8
Метод северо-западного угла 9
Метод наименьшей стоимости 9
Метод потенциалов 10
ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ 12
Постановка задачи 12
Нахождение первоначального плана методом северо-западного угла 13
Нахождение первоначального плана методом наименьшей стоимости 14
Метод потенциалов 15
ЗАКЛЮЧЕНИЕ 19
ЛИТЕРАТУРА 20
Наиболее простым методом ТЗ является метод потенциалов. Потенциалами называются условные числа Ui ,Vj , приписанные определённым образом каждому поставщику и потребителю.
Теорема(условия оптимального плана): Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток
Опорный план должен быть не вырожденным (r=m+n-1 – невырожденный план)
Алгоритм решения:
Если оно выполнено, то план оптимален, если нет то улучшаем план.
Метод аппроксимации Фогеля
Данный метод состоит в следующем:
Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям. Данный метод в ряде задач приводит к оптимальному плану.
Имеются три пункта поставки мониторов: Склад №1, Склад №2, Склад №3. И пять магазинов: Магазин "Терабайт", Магазин "Лидер", Магазин "Эксперт", Магазин "Ока-сервис", "Владимирский рынок", потребления этого товара. Найти оптимальный план распределения товаров с минимальными затратами.
Дано:
Склад №1=200 шт.
Склад №2=250шт.
Склад №3=200шт.
Требуется доставить штук:
Магазин "Терабайт"= 190шт.
Магазин "Лидер"= 100 шт.
Магазин "Эксперт" = 120 шт.
Магазин "Ока-сервис" =110 шт.
"Владимирский рынок" =130 шт.
Сетка тарифов:
28 |
27 |
18 |
27 |
24 |
18 |
26 |
27 |
32 |
21 |
27 |
33 |
23 |
31 |
34 |
Построим для данной задачи матрицу тарифов, по которой будет происходить поиск оптимального плана распределения товаров между магазинами. Для более удобного решения задачи обозначим магазины и товары переменными:
Магазины:
Магазин "Терабайт"= B1
Магазин "Лидер"= B2
Магазин "Эксперт" = B3
Магазин "Ока-сервис" = B4
"Владимирский рынок" = B5
Товары:
Склад №1= A1
Склад №2 = A2
Склад №3= A3
Тогда матрица будет выглядеть так:
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы | |
A1 |
28 |
27 |
18 |
27 |
24 |
200 |
A2 |
18 |
26 |
27 |
32 |
21 |
250 |
A3 |
27 |
33 |
23 |
31 |
34 |
200 |
Потребности |
190 |
100 |
120 |
110 |
130 |
Следуя данной модели можно найти опорный план и решение поставленной задачи.
Используя построенную матрицу тарифов найдём оптимальный опорный план методом северо-западного угла.
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы | |
A1 |
28 |
27 |
18 |
27 |
24 |
200 |
A2 |
18 |
26 |
27 |
32 |
21 |
250 |
A3 |
27 |
33 |
23 |
31 |
34 |
200 |
Потреб. |
190 |
100 |
120 |
110 |
130 |
Проверим необходимое и достаточное условие разрешимости задачи.
Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы | |
A1 |
28 [190] |
27 [10] |
18 |
27 |
24 |
200 |
A2 |
18 |
26 [90] |
27 [120] |
32 [40] |
21 |
250 |
A3 |
27 |
33 |
23 |
31 [70] |
34 [130] |
200 |
Потреб. |
190 |
100 |
120 |
110 |
130 |
|
Решение задачи методом северо-западного угла всегда начинается с левого, верхнего тарифа([A1;B1]). Полностью удовлетворяем потребность данного тарифа. Исключаем первый столбец. Дальше смотрим если запасы ещё остались, рассматриваем рядом стоящий тариф ([A2;B1]), если нет, то исключаем и первую верхнею строк. И рассматриваем следующий тариф по аналогичной схеме. В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Подсчитаем затраты на распределение товаров:
F=28*190+27*10+26*90+27*120+
Результат: Затраты на распределение товаров между магазинами найденные методом северо-западного угла составят 19040 рублей.
Используя построенную матрицу тарифов, найдём оптимальный опорный план методом наименьшей стоимости.
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы | |
A1 |
28 |
27 |
18 |
27 |
24 |
200 |
A2 |
18 |
26 |
27 |
32 |
21 |
250 |
A3 |
27 |
33 |
23 |
31 |
34 |
200 |
Потреб. |
190 |
100 |
120 |
110 |
130 |
Проверим необходимое и достаточное условие разрешимости задачи.
Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы | |
A1 |
28 |
27[10] |
18[120] |
27 |
24[70] |
200 |
A2 |
18 [190] |
26 |
27 |
32 |
21[60] |
250 |
A3 |
27 |
33 [90] |
23 |
31 [110] |
34 |
200 |
Потреб. |
190 |
100 |
120 |
110 |
130 |
Для решения задачи методом наименьшей стоимости сначала из все матрицы тарифов выбираем наименьший тариф ([A2;B1]). Полностью удовлетворяем его потребность. Исключаем из решения столбец в котором он находился. Ищем следующий минимальный тариф ([A1;B3]). Удовлетворяем его потребности. Исключаем из решения столбец в котором он находился. Дальше продолжаем до тех пор, пока все запасы не будут розданы.
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Подсчитаем затраты на распределение товаров:
F=27*10+18*120+24*70+18*190+
Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15170 рублей.
Для решения транспортной задачи сначала надо найти опорный план методом северо-западного угла и методом наименьшей стоимости, и из них выбрать метод при котором затраты на распределения товаров минимальны.
Для данной задачи минимальным является метод наименьшей стоимости.
Опорный метод этого плана и будем использовать для решения задачи методом потенциалов:
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы | |
A1 |
28 |
27[10] |
18[120] |
27 |
24[70] |
200 |
A2 |
18[190] |
26 |
27 |
32 |
21[60] |
250 |
A3 |
27 |
33[90] |
23 |
31[110] |
34 |
200 |
Потреб. |
190 |
100 |
120 |
110 |
130 |
Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij
Для этого построим систему уравнений:
Из этой системы уравнений находим потенциалы , полагая, что u1 = 0:
v1=21, v2=27, v3=18, v4=25, v5=24, u1=0, u1=-3, u3=6
v1=21 |
v2=27 |
v3=18 |
v4=25 |
v5=24 | |
u1=0 |
28 |
27[10] |
18[120] |
27 |
24[70] |
u2=-3 |
18[190] |
26 |
27 |
32 |
21[60] |
u3=6 |
27 |
33[90] |
23 |
31[110] |
34 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij, (3;3): 6 + 18 > 23
Выбираем максимальную оценку свободной клетки (3;3): 23
Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы | |
A1 |
28 |
27[100] |
18[30] |
27 |
24[70] |
200 |
A2 |
18[190] |
26 |
27 |
32 |
21[60] |
250 |
A3 |
27 |
33 |
23[90] |
31[110] |
34 |
200 |
Потреб. |
190 |
100 |
120 |
110 |
130 |
Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij (Алгоритм нахождения потенциалов описан выше).
v1=21 |
v2=27 |
v3=18 |
v4=26 |
v5=24 | |
u1=0 |
28 |
27[100] |
18[30] |
27 |
24[70] |
u2=-3 |
18[190] |
26 |
27 |
32 |
21[60] |
u3=5 |
27 |
33 |
23[90] |
31[110] |
34 |
Информация о работе Сетевые модели: нахождение потока наименьшей стоимости