Методы оптимальных решений транспортной задачи

«Методы оптимальных решений»

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

Необходимо:

1) свести исходные данные в таблицу 1.1.

Таблица 1.1

2) составить математическую модель задачи;

3) привести её к стандартной транспортной задаче с балансом запасов и потребностей;

4) построить начальный опорный план задачи методом минимального элемента;

5) решить задачу методом потенциалов;

6) проанализировать полученные результаты.

Таблица 2

2) составляем математическую модель задачи:

Ограничения по запасам:

математический задача транспортный Ограничения по потребностям:

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

3) Проверим необходимое и достаточное условие разрешимости задачи:

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на складах. Следовательно, модель исходной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную, фиктивную, потребность, равной 5 (90−85=5). Тарифы перевозки груза из склада во все объекты полагаем равной нулю. Занесем данные в таблицу:

Таблица 3

4) Используя метод наименьшей стоимости, построим первый опорный план задачи.

Наименьшая стоимость = 3. Для этого элемента запасы равны 30, а потребности 18. Поскольку минимальным является 18, то вычитаем его:

Таблица 4

Наименьшая стоимость = 3. Для этого элемента запасы равны 20, а потребности 10. Поскольку минимальным является 10, то вычитаем его:

Таблица 5

Наименьшая стоимость = 4. Для этого элемента запасы равны 25, а потребности 20. Поскольку минимальным является 20, то вычитаем его:

Таблица 6

Таблица 7

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

Выбираем максимальную оценку свободной клетки с₁₅=7

В эту клетку ставим знак +, а в остальных вершинах многоугольника чередующие знаки.

Таблица 9

Из грузов с_ij стоящих в минусовых клетках, выбираем наименьшее, т. е. у=min (2,5)=2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из с_ij, стоящих в минусовых клетках. В результате получим новый опорный план:

Таблица 10

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

Потенциалы занесем в таблицу.

Проведем оценки свободных клеток:

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j? c_ij.

Минимальные затраты составят:

6)

Из 1-го склада необходимо груз направить в 1-й объект (10), в 3-й объект (18), в 5-й объект (2)

Из 2-го склада необходимо груз направить в 2-й объект (20), в 4-й объект (5)

Из 3-го склада необходимо весь груз направить в 5-й объект Из 4-го склада необходимо груз направить в 4-й объект (7), в 5-й объект (3)

На 4-ом складе остался невостребованным груз в количестве 5 ед.