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

Исходные данные по транспортной задаче.

Решение.

Задача относится к типу «транспортных». Следует найти такую совокупность перевозок, которая полностью обеспечивает потребности пунктов назначения при вывозе всего продукта из пунктов отправления.

Для определения исходных данных следует заполнить матрицу. Обозначение а_i соответствует запасам продукта на пункте отправления i, а обозначение b_i потребности в продукте на пункте получения J.

Перенумерованными клетками матрицы моделируются пути между пунктами отправления i и пунктами получения J.

Для решения задачи необходимо выполнения условия:

Данное условие выполняется.

Разделим каждую рабочую клетку матрицы по диагонали на две половины. В верней половине каждой клетки даются значения стоимости перевоза единицы груза по данному маршруту, а нижняя предназначена для записи объёмов перевозки по маршруту.

На матрице отмечены клетки, найденные методом двойного предпочтения.

После назначения матрицы его следует проверить на оптимальность.

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

Перед таким преобразованием матрицы стоимости следует добиться выполнения определённых условий, которым отвечает оптимальный план:

- оптимальный план состоит из m+n-1 перевозок, где m – кол-во пунктов отправления продукта, а n - кол-во пунктов получения продукта;

- в оптимальном плане не может быть циклов.

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

Транспортная задача по предварительному плану дает количество перевозок, не отвечающее первому условию (m=5, n=8 m+n=13), поэтому следует ввести фиктивную перевозку х=0. Такая перевозка должна располагаться так, чтобы удовлетворялось условие 2.

В свободную ячейку 3-2 запишем ноль, как в ячейку не образующую цикл с базисными ячейками и имеющую наименьший тариф.

Количество базисных ячеек (задействованных маршрутов) равно12, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S0 = 6 * 13 + 4 * 37 + 3 * 45 + 8 * 35 + 7 * 40+ 1 * 60 + 7 * 20 + 13 * 45 + 4* 55 + 4 * 45 + 1 * 65 = 2171 ден. ед.

Общие затраты на доставку всей продукции, для начального решения, составляют 2171 ден. ед.

Для улучшения первоначального базисного плана применяется метод потенциалов. Потенциалами называются такие численные характеристики строк U_i и столбцов V_j, при которых соблюдается условие оптимальности плана. Математически это условие записывается так:

(условие для занятых клеток);

(условие для свободных клеток);

,

Подбор потенциалов начинаем с первой строки. Принимаем U₁=0.

Далее производим проверку условия для свободных клеток по формуле:

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

Оптимизируем план.

Для этого от клетки ∆4,8 строим контур перераспределения.

Получаем: до перераспределения условные затраты на перевозку

13*45+6*13+3*45=798;

После перераспределения условные затраты на перевозку составили

6*58+5*45=573.

Оптимизированный базисный план.

Проверяем количество заполненных клеток для оптимизированного плана, которое должно быть равно m+n-1, т.е. суммарному количеству строк и столбцов без единицы.

5+8-1=12, количество заполненных клеток N=10, условие не выполняется, поэтому вводим фиктивную перевозку ∆1,8 равную 0 и ∆4,5 равную 0

Целевая функция плана:

S0 = 6 * 58 + 4 * 37 + 8 * 35 + 7 *40 + 1 * 60 + 7 * 20 + 4* 55+ 5 * 45 + 4 * 45 + 1 * 65 = 1946 ден. ед.

Проверяем условия оптимальности плана.

Подбор потенциалов начинаем с первой строки. Принимаем U₁=0.

Далее производим проверку условия для свободных клеток по формуле:

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

Целевая функция оптимизированного плана:

S0 = 6 * 58 + 4 * 37 + 8 * 35 + 7 *40 + 1 * 60 + 7 * 20 + 4* 55+ 5 * 45 + 4 * 45 + 1 * 65 = 1946 ден. ед.

Оптимизация первоначального базисного плана позволила сократить затраты на перевозку на 2171-1946=225 у.е.

Литература

1. Дикман Л.Г. Организация и планирование строительного производства: Управление строительными предприятиями с основами АСУ: Учеб. Для строит. Вузов и фак. - 3-е изд., перераб. И доп. – М.: Высш. шк., 1988 – 559 с.: ил.

2. Сырцова Е.Д. Математические методы в планировании и управлении строительнвм производством. –М.: Высш. Школа. 1972.-355с.

3. Терехов Л.Л. Экономико-математические методы. М-: Статистика, 1972.- 359с.

4. Организация, планирование и управление строительным производством: Учебник / под ред. И.Г. Галкина – М.: Высш. Школа, 1985. - 463с.

5. Организация, экономика и управление строительством: Учеб. Пособие /под ред. Т. Н. Цая – М.: Стройиздат, 1984.-367с.

Размещено на Allbest.ru