При низкой оригинальности работы "Решение транспортной задачи методом линейного программирования", Вы можете повысить уникальность этой работы до 80-100%
Решение транспортной задачи методом линейного программированияМодель транспортной сети представляет собой чертеж-схему на плане местности с указанием вершин (пунктов) транспортной сети. Ее построение производится по заданной схеме расположения пунктов, по наличию звеньев сети, соединяющих два соседних пункта, и длине этих звеньев. Начальному пункту, от которого требуется определить кратчайшие расстояния, присваивается потенциал Vi = 0. Просматриваются все звенья, начальные пункты i которых имеют потенциал Vi, а для конечных j потенциалы не присвоены. Из всех полученных потенциалов выбирается потенциал c наименьшим значением, т.е. определяется: ; , (2) где {Vj(i)} - множество значений потенциалов конечных пунктов j звеньев i-j, i-м начальным пунктом которых ранее присвоены потенциалы; {Vj’(i’)} - потенциал конечного пункта j’ звена i’-j’, являвшийся наименьшим по значению элементом множества {Vj(i)}.
Далее полученный план перевозок проверяется на оптимальность. В таблицу транспортной задачи вводятся вспомогательные строка и столбец, в которые заносятся специальные показатели, называемые потенциалами.
Основан метод потенциалов на том, что если к расстояниям любой строки (столбца) таблицы прибавить или отнять произвольное одно и тоже число, то оценка оптимальности относительно не изменится. Если, например, от расстояний каждой i-ой строки отнимать число ui и от расстояний каждого j-ого столбца - uj, то тогда относительной оценкой любой клетки ij может служить параметр uij вместо lij, рассчитываемый по формуле:
(9)
Потенциал для наиболее загруженной строки таблицы принимается равным нулю и по расстояниям загруженных клеток подбираются потенциалы для других строк и столбцов таблицы таким образом, чтобы соблюдалось условие (1.9), т.е. расстояние в каждой загруженной клетке должно быть равно сумме потенциалов строки и столбца данной клетки. Затем по вычисленным потенциалам строки столбцов определяются значение оценочного параметра uij для каждой незагруженной клетки (не вошедшей в базисный план). Пример расчета приведен в таблице 1.15.
Величина параметра uij характеризует общее увеличение пробега с грузом, достигаемое при включении в план единицы груза по корреспонденции ij по сравнению с рассматриваемым планом.
Если значение оценочного параметра свободной клетки будет меньше нуля uij <0, то это значит, что перераспределение корреспонденций по клеткам таблицы с занесением объема перевозок в такую свободную клетку, называемую потенциальной, уменьшит значение целевой функции.
Отсутствие клеток со значением параметра uij <0, означает, что проверяемый план закрепления потребителей за постановщиками является оптимальным.
Lx1=100*1 50*3 125*25 25*23 100*19 125*11 25*20 125*14 25*13=10300 км
Суммарный холостой пробег автомобилей для данного плана перевозок составляет 10300 км, однако он не является оптимальным, так как есть отрицательные оценки. Для улучшения плана перевозок строится замкнутый контур для клетки (Б2,А3). Он содержит клетки (Б2,А3), (Б2,А1), (Б5,А1), (Б5,А3). Клетки (Б2,А3), (Б5,А1) помечаются знаком “ ”, а клетки (Б2,А1) и (Б5,А3) - знаком “-”. Так как для клеток, помеченных “-”, минимальный объем перевозок равен 125 ездок, то отнимать и прибавлять необходимо 125 единиц. Получается матрица с новым планом перевозок.
Lx2=100*1 50*3 0*25 25*23 125*16 100*19 125*11 150*20 25*13=9425 км
Суммарный холостой пробег автомобилей для данного плана перевозок составляет 9425 км, однако и он не является оптимальным. Для улучшения плана перевозок строится цикл для клетки (Б5,А4).
Lx3=75*1 75*3 0*25 25*23 125*16 100*19 125*11 150*20 25*9=9375 км
Суммарный холостой пробег автомобилей составляет 9375 км. Полученное решение является оптимальным, так как все оценки пустых (небазисных) клеток имеют неотрицательное значение.
Размещено на .ru
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
