Содержание
- 2. Описание транспортной задачи
- 3. Решить транспортную задачу – это найти оптимальный план перевозок (х11, х12,…, х34), который минимизирует его стоимость
- 4. Общая стоимость перевозок F, выраженная в тонно-километрах хіjсіj - количество тонно-километровая характеристика перевозки.
- 6. Нахождение оптимального плана перевозок (х11, х12,….). Сводится к решению системы линейных уравнений, относительно определяемых переменных хіj
- 7. Примечание Если сij означает расстояния между базами и заказчиками, то F (общая стоимость) выражается в в
- 8. Если суммарный объем груза, содержащийся на базах, равен суммарной потребности заказчиков, то транспортная задача называется закрытой
- 11. 1. Формирование опорного решения
- 12. Формирование опорного решения методом северо-западного угла Вначале заполняется левая верхняя клетка (северо-западный угол) исходной таблицы или
- 18. Стоимость перевозок по опорному (первоначальному) плану составит: Fнач = 70·170 + 50·110 + 15·20 + 40·80
- 19. Решение транспортной задачи методом потенциалов
- 20. Пересчитывать опорный план можно с помощью потенциалов. Тариф сij базисных переменных представляется в виде суммы сij
- 22. Значение одного из данных неизвестных можно выбирать произвольно. Например, можно принять, что α1 = 0. Тогда
- 23. Значение одного из данных неизвестных можно выбирать произвольно. Например, можно принять, что α1 = 0. Тогда
- 24. . Посчитаем алгебраические суммы свободных клеток s14 = c14 – c'14= 80 – (0 + 35)
- 25. Тариф свободной клетки обозначают как c′ij и называют косвенным тарифом. Сравнение тарифов свободной клетки определяется разностью
- 26. Новая стоимость перевозок находится по формуле: Т.е стоимость перевозок уменьшится на число:
- 27. 3. Циклы пересчета в таблице перевозок
- 28. Для уменьшения стоимости перевозок используются циклы пересчета. Циклом пересчета в таблице перевозок называется последовательность переменных хіj,
- 29. в каждый цикл может входить только одна свободная переменная (клетка с прочерком). Все остальные переменные должны
- 30. Если для свободной клетки исходной таблицы, заполненной методом северо-западного угла, можно построить цикл пересчета, то такой
- 31. Перераспределение груза происходит по следующим правилам: а) снабдим свободную клетку знаком (+) и с каждым переходом
- 32. Циклы пересчета №1 Выбрали свободную клетку, построил цикл.
- 33. Циклы пересчета №1 Расставили знаки
- 34. Циклы пересчета №1 в клетках, отмеченных знаком (−) выберем наименьшее из чисел
- 35. Циклы пересчета №1 Из клеток, отмеченных знаком (−), зафиксированное количество груза вычтем; в клетках со знаком
- 36. F = 70·170 + 50·110 + 80·20 + 40·100 + 60·50 + 11·50 = 26 550
- 37. Следует сравнить стоимость перевозок в каждом цикле со стоимостью перевозок по опорному (первоначальному) плану Fнач =
- 38. Примечание. Если минимальное значение среди базисных переменных содержится в цикле пересчета в нескольких отрицательных вершинах цикла,
- 39. 4. Критерий оптимальности решения транспортной задачи
- 40. Изменение стоимости перевозок в каждом цикле связано с числом m (фиксированное число цикла) (Если вершина снабжена
- 41. Факт увеличения или уменьшения стоимости перевозок определяется не количеством перевозимого груза, а знаком алгебраической суммы тарифов
- 42. Критерий оптимальности решения Очередное решение определяет оптимальный план перевозок, если алгебраические суммы тарифов для всех возможных
- 44. Циклы пересчета строятся только для тех свободных клеток, для которых алгебраические суммы тарифов отрицательны.
- 45. Принимается наибольшее уменьшение стоимости перевозок. Строим таблицу, соответствующую самому выгодному циклу:
- 47. К новой таблице применяют еще раз метод потенциалов для минимизации стоимости перевозок до тех пор, пока
- 48. Fопт. = 70 ·140 + 50 · 60 + 15 · 100 + 80 · 30
- 50. Скачать презентацию