Стандартная транспортная задача

Задача №4.01

Заводы некоторой автомобильной фирмы расположены в городах А, В и С. Основные центры распределения продукции сосредоточены в городах D и E. Объемы производства указанных трех заводов равняются 1000, 1300 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимости перевозки автомобилей по железной дороге по каждому из возможных маршрутов приведены в табл.4.2.

Таблица 4.2

Стоимость перевозки автомобилей, руб./шт.

Постройте математическую модель, позволяющую определить количество автомобилей, перевозимых из каждого завода в каждый центр распределения, таким образом, чтобы общие транспортные расходы были минимальны.

Решение

Определение переменных

Обозначим количество автомобилей, перевозимых из i-го завода в j-й пункт потребления через .

Проверка сбалансированности задачи

Проверим равенство суммарного производства автомобилей и суммарного спроса

откуда следует вывод – задача несбалансирована, поскольку спрос на автомобили превышает объем их производства. Для установления баланса введем дополнительный фиктивный завод с ежеквартальным объемом производства 200 шт. ( ). Фиктивные тарифы приравняем к нулю (т.к. перевозки в действительности производиться не будут).

Построение транспортной матрицы

Согласно результатам проверки сбалансированности задачи №4.01 в транспортной матрице должно быть четыре строки, соответствующих заводам и два столбца, соответствующих центрам распределения (см. табл.4.3). Тариф перевозки обычно вписывают в правом нижнем углу клетки матрицы для удобства дальнейшего нахождения опорных планов задачи.

Таблица 4.3

Транспортная матрица задачи №4.01

Задание ЦФ

Суммарные затраты в рублях на ежеквартальную перевозку автомобилей определяются по формуле

Задание ограничений

[шт./квартал]

Модификации стандартной транспортной задачи

Недопустимые перевозки

Иногда в определенных направлениях перевозки продукции невозможны, например, по причине ремонта транспортных магистралей. Такие ситуации моделируются с помощью введения так называемых запрещающих тарифов . Запрещающие тарифы должны сделать невыгодными перевозки в соответствующих направлениях. Для этого величина запрещающих тарифов должна быть больше реальных тарифов в транспортной матрице

.

Максимизация ЦФ

Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой ЦФ вводится ЦФ , в которой тарифы умножаются на (-1). Таким образом, максимизация будет соответствовать минимизации .

Многопродуктовые модели

Если в задаче идет речь о том, что из каждого пункта отправления можно перевозить продукцию нескольких видов, то при построении модели можно использовать один из следующих вариантов:

· каждому виду продукции должна соответствовать одна транспортная матрица;

· все виды продукции представлены в одной общей матрице с использованием запрещающих тарифов в клетках, связывающих разные виды продукции.

МЕТОДЫ НАХОЖДЕНИЯ ОПОРНЫХ ПЛАНОВ

Теоретическое введение

Опорный планявляется допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

Все существующие методы нахождения опорных планов отличаются только способом выбора клеткидля заполнения. Само заполнение происходит одинаково независимо от используемого метода. Следует помнить, что перед нахождением опорного плана транспортная задача должна быть сбалансирована.

Метод северо-западного угла

На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов.

Для того, чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце .

Если существующий запас позволяет перевезти всю потребность, то

· в клетку (i,j) в качестве перевозки вписывается значение потребности ;

· j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

· от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. .

Если существующий запас не позволяет перевезти всю потребность, то

· в клетку (i,j) в качестве перевозки вписывается значение запаса ;

· i-я строка вычеркивается, поскольку ее запас уже исчерпан;

· от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е. .

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

Метод минимального элемента

На каждом шаге метода минимального элемента из всехне вычеркнутых клеток транспортной матрицы выбирается клетка с минимальной стоимостью перевозки . Заполнение выбранной клетки производится по правилам, описанным выше.

Метод Фогеля

На каждом шаге методаФогеля для каждой i-й строки вычисляются штрафы как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом .

Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом .

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

Не нашли, что искали? Воспользуйтесь поиском по сайту: