Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
3-11. Модель классической транспортной задачи и её ЭОС.
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными.
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).
Постановка транспортной задачи:
1) Задается план перевозки, после осуществления которого груз будет полностью вывезен из всех пунктов отправления А (27,20,43) и потребности всех пунктов назначения Б (33,13,27,17) буду удовлетворены. Строим исходный план методом северо-западного угла. Число занятых клеток рассчитывается как (m + n) – 1, где m – пункты назначения, n – пункты отправления. Тарифы – 14,28,21,28. 10,17,15,24. 14,30,25,21.
2) Далее используем метод потенциалов, добавляя новую строку и столбец ai и bj.
3) a1 = 0, все остальные значения потенциалов для занятых клеток находятся из Cij = ai + bj. Для не занятых клеток Δij = ai + bj - Cij.
Если все Δij ≤ 0 – план оптимален, в нашем случае ячейка 1:3 = 6, следовательно, план не оптимален.
4) Выбираем клетку с максимальным Δij (1:3), из которой будем строить цикл. (цикл – сплошная линия, все отрезки которой горизонтальны или вертикальны, все вершины располагаются только в занятых клетках. Расставляем знаки +\- поочередно во всех вершинах цикла, начиная в той клетке, где строился цикл. Определяем минимальный объем перевозки в клетках с – (6), обозначаем его как t = 6.
5) Строим новую таблицу с переносом в нее тарифов, а так же занятые клетки не вошедшие в цикл. Во всех клетках со знаком + объем перевозки увеличивается на t = 6. Во всех клетках со знаком – объем перевозки уменьшается на t. Повторяем построение находя потенциалы. Стоимость перевозки по данному плану 1645.
T = 20.
Все Δij ≤ 0, план оптимален, стоимость перевозок составит – 1565.