Методы оптимизации в технико-экономических задачах
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
е процесс продолжается аналогично до полного определения начального базиса.
Метод, который дает наиболее близкий к оптимальному план - метод Фогеля. Согласно этому методу для каждой строки и столбца находим "штраф", равный модулю разности между двумя наименьшими стоимостями. Затем начинаем заполнять клетки с той строки или столбца, где имеется наибольший штраф. Заполняем клетку с наименьшей стоимостью перевозки наибольшим объемом груза. Затем столбец вычеркивается и "штрафы" пересчитываются. Процесс продолжается дальше до полного определения начального базиса.
После выработки начального базиса начинается решение. Наиболее простым для нахождения решения является метод потенциалов.
Потенциалы находятся при рассмотрении занятых клеток. Поскольку количество таких клеток (m+n-1), а общее количество клеток (m*n), то количество потенциалов на единицу больше, чем базисных клеток, поэтому один из потенциалов можно задать произвольно (обычно задают нулевой потенциал).
Обозначим потенциалы строк через ui, а потенциалы столбцов через vj. Потенциал столбца находится так, чтобы для базисных клеток сумма потенциалов была равна стоимости перевозок, то есть
+vj = cij
После того, как все потенциалы найдены, вычисляются косвенные стоимости (косвенные стоимости находятся для клеток, не вошедших в базис):
= ui+vj
Затем, для каждой свободной клетки определяется разность:
=ckl - ckl ,
где к и l - индексы свободных клеток.
Оптимальное решение найдено, если все разности fkl=ckl - ckl для свободных клеток неотрицательные. Выражение для целевой функции через свободные неизвестные имеет все неотрицательные коэффициенты, значит уменьшить функцию дальше нельзя, найдено оптимальное решение.
В случае, если среди разностей fkl оказываются отрицательные, нужно найти наименьшую из них и организовать цикл пересчёта. Далее производят сдвиг по циклу пересчета.
При решении транспортной задачи необходимо помнить, что загруженные базисные клетки не должны образовывать цикла.
При правильном построении начального базиса для любой свободной клетки можно построить лишь один цикл пересчёта. После того как для выбранной свободной клетки он построен, следует перейти к новому базисному решению. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой. Это перемещение производят по следующим правилам:
1)каждой из клеток, связанных циклом с данной свободной клеткой, приписывают знак (+ или -), причём свободной клетке - знак плюс, а всем остальным клеткам - поочерёдно знаки минус и плюс;
2)в данную свободную клетку переносят меньшее из чисел xij, стоящих в клетках со знаком -, одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком +, и вычитают из чисел, стоящих в клетках со знаком -.
Клетка, которая ранее была свободной, будет занятой, а клетка с наименьшей загрузкой и со знаком -станет свободной.
Таким образом, осуществляется переход к другому распределению загрузок и новому базису. Полученный новый базис транспортной задачи проверяют на оптимальность.
3.2 Задание
Имеется четыре завода А1, А2, А3, А4, из которых нужно вывести некоторое количество грузов. И пять пунктов назначения В1, В2, В3, В4, В5, в которые должны быть привезены товары с заводов. Количество товаров в каждом пункте отправления, потребности каждого пункта назначения и тарифы на доставку приведены в таблице.
Пункты отправленияПункты назначенияЗапасыВ1В2В3В4В5А15324102524А23022216715А3302427291016А41517212324Потребности121314319
Требуется составить план перевозок так, чтобы стоимость была наименьшей.
3.3 Построение математической модели задачи
Транспортная задача сводится к определению такого плана перевозок некоторого продукта с заводов в пункты потребления (реализации) - , который минимизирует целевую функцию
(2.1)
на множестве допустимых планов:
(2.2)
При соблюдении баланса
.(2.3)
Объемы запасов и заказов равны. Значит, задача сбалансированна и фиктивных пунктов доставки и отправления вводить не нужно.
Пункты отправленияПункты назначенияЗапасыВ1В2В3В4В5А15324102524А23022216715А3302427291016А41517212324Потребности1213143197979
Обозначим через xij количество продукции, перевозимой из i-го склада в j-ый магазин. Тогда условия перевозки грузов обеспечиваются за счет выполнения следующих равенств:
(2.4)
При данном плане перевозок общая стоимость перевозок составит:
=5*x11+3*x12+24*x13+10* x14+25* x15+30*x21+2*x22+22*x23+16*x24+7* *x25+30*x31+24*x32+27*x33+29*x34+10*x35+15*x41+17*x42+21*x43+2*x44+3*x45 (2.5)
Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений 2.4, при котором целевая функция 2.5 принимает минимальное значение.
Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения.
3.4 Решение транспортной задачи
. Метод северо-западного угла.
Заполняется клетка С11 максимальным грузом, затем вычеркивается соответствующая строка или столбец. Затем заполняется клетка С12 или С21 максимальным грузом равным А1-В1, затем вычеркивается соответствующая строк