Распределение объёмов земляных масс и решение транспортной задачи

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

Найти оптимальное решение данной задачи можно методом линейного программирования, в частности, методом транспортной задачи.

Математически транспортная задача формулируется так: мощность поставщика номер i и емкость потребителя номер j соответственно равны Ai и Bj. При этом общая мощность поставщиков должна равняться суммарной емкости потребителей, т. е:

УA i = У B j.

Критерием целесообразности перевозки от i-того поставщика к j-тому потребителю могут быть затраты на перевозку единицы продукции, расстояние перевозок и т. д. этот критерий называется оценкой, коэффициентом цены и обозначается Cij.

Цель решения задачи — получение min значений целевой функции L:

L=.

где xij — объем перевозимого груз, м3.

В курсовом проекте для решения транспортной задачи было использовано 2 метода: метод двойного предпочтения и метод аппроксимации Фогеля.

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

а) Метод двойного предпочтения.

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

После составления первоначального базисного плана проверяется условие m + n — 1 = k — by заполненных клеток. Если количество заполненных клеток меньше m + n-1, то такой план называется вырожденным, и он не подлежит оптимизации, для устранения врожденности в 1-й из свободных клеток (с min оценкой) вводится нулевая постановка и клетка считается заполненной.

После заполнения подсчитываем значение целевой функции L.

Таблица 2 Метод двойного предпочтения.

m + n — 1 = 21 — 1 = 20. 20 = 20.

L = 2 809 512 м4.

б) Метод аппроксимации Фогеля.

Составляем исходную матрицу. В каждой строке находим min оценку и ближней к ней по величине. Разность между этими двумя значениями записывается справа в данной строчке. Аналогичные действия делаем и на столбце.

Полученные числа рассматриваются в совокупности, выделим из них max, в строке (столбце) отмеченные max числом, начинаем загружать клетку с min оценкой. При наличии двух или более одинаковых чисел max можно принять любое число. Если в двух клетках столбца или строках оценка одинакова, то разность между ними равна 0. проверяем условие m + n — 1 и если план подлежит оптимизации, подсчитываем целевую функцию.

Таблица 3. Метод аппроксимации Фогеля.

m + n — 1 = 21 — 1 = 20. 20 = 20.

L =2 811 354 м4.

проанализировав два плана для дальнейшей оптимизации принимаем 1-ый, т.к. он имеет меньшую целевую стоимость.