5316.Учебная работа .Тема:Методы оптимальных решений транспортной задачи

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (5 оценок, среднее: 4,80 из 5)
Загрузка...

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

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

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

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

Необходимо:

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

Таблица 1.1

Строительный объект СкладЗапасы стройматериалов на складах, тыс.ед.Потребности строительных объектов, тыс.ед.

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

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

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

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

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

Таблица 2

Строительный объект СкладЗапасы стройматериалов на складах, тыс.ед.48367308465925358542058106815Потребности строительных объектов, тыс.ед.102018122590 85

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

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

математический задача транспортный

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

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

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

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

Таблица 3

Запасы стройматериалов на складах, тыс.ед.483670308465902535854020581068015Потребности строительных объектов, тыс.ед.1020181225590 90

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

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

Таблица 4

Строительный объект СкладЗапасы стройматериалов на складах,

тыс.ед.4836703018=128465902535854020581068015Потребности строительных объектов, тыс.ед.10201818=01225590 90

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

Таблица 5

Строительный объект СкладЗапасы стройматериалов на складах, тыс.ед.48367012846590253585402010=10581068015Потребности строительных объектов, тыс.ед.1010=02001225590 90

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

Таблица 6

Строительный объект СкладЗапасы стройматериалов на складах, тыс.ед.483670128465902520=535854010581068015Потребности строительных объектов, тыс.ед.02020=001225590 90

Таблица 7

Строительный объект СкладЗапасы стройматериалов на складах, тыс.ед.483670127=584659003585400581068015Потребности строительных объектов, тыс.ед.00077=015590 90

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

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

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

Таблица 9

Строительный объект Склад 4 5 3 6 8 0Запасы стройматериалов на складах, тыс.ед. 04(10)83(18)6(2)7+030 184(20)65(5)9025 435854(20)020 058106(5)+8(5)0(5)15Потребности строительных объектов, тыс.ед.1020181225590 90

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

Таблица 10

Строительный объект Склад 4 5 3 6 8 0Запасы стройматериалов на складах, тыс.ед. 04(10)83(18)67(2)030 184(20)65(5)9025 435854(20)020 058106(7)8(3)0(5)15Потребности строительных объектов, тыс.ед.1020181225590 90

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

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

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

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

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

6)

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

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

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

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

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