Оптимизация доставки инсектицидного средства в Ростове-на-Дону (стр. 1 из 3)
Оптимизация доставки инсектицидного средства в Ростове-на-Дону
Курсовая работа по дисциплине: «Исследование операций и принятие решений»
Выполнил студент гр. 3-1 Амирджанян В.Г.
Южный федеральный университет
Ростов-на-Дону 2007
Введение
Сегодня многие предприятия, организации, фирмы и компании предлагают пользователям услуги доставки своей продукции. Для каждого предприятия важна оперативная и быстрая доставка, при этом все обязательно стремятся к минимальным затратам. Решением подобных задач занимается дисциплина исследование операций. В частности для оптимизации доставок и перевозок используются транспортная задача и задача коммивояжера линейного программирования. Для организации доставки продукции предприятия, которое далее будем рассматривать, будет целесообразным использовать транспортную задачу. Здесь можно поставить задачу так, чтоб минимизировать затраты при доставке данной продукции или минимизировать время доставки в зависимости от требований и нужд предприятия.
Теоретическая постановка задачи
Имеются m пунктов отправления A1…Am в которых сосредоточено а1…аm единиц однородного товара и n пунктов назначения B1…Bn, которые подали заявки на b1…bn единицы этого товара. Известны стоимость (время перевозки) единицы перевозки cij единицы товара из Ai в Bj.
Требуется составить план перевозок, при котором все заявки были бы удовлетворены и суммарная стоимость (время) перевозок была бы минимальна.
Обозначим xij-количество товара, которое надо отправить из Ai в Bj.Тогда наша задача выглядит следующим образом L=
min, где 
, 
, j=(1,n), i=(1,m). Если 
, то транспортная задача называется закрытой. План перевозок xij, будет опорным, если в нем неравны нулю не более чем r=m+n-1 перевозок xij.Данную задачу можно решить тремя методами:
метод северо-западного угла (этот метод является основой для остальных двух),
распределительный метод или метод последовательного улучшения плана перевозок,
метод потенциалов.
Проверяется баланс
.Составляется таблица транспортной задачи.
Считается количество ненулевых перевозок r=m+n-1.
Считается L=
.Если при построении исходного опорного плана перевозка одновременно закрывает строку и столбец, то в следующую по строке или столбцу клетку нужно записать 0.
Цикл в транспортной таблице – это ломаная с вершинами в клетках и звеньями, лежащих вдоль строк или столбцов удовлетворяющая следующим требованиям:
ломаная должна быть связанной,
в любой вершине цикла встречаются 2 звена первое по строке, другое по столбцу.
Означенный цикл – цикл вершинам которого приписаны «+» и «-» поочередно. При переносе по означенному циклу k единиц перевозки в положительных вершинах добавляем k единиц, а в отрицательных вершинах отнимаем k единиц. При таком переносе равновесие между запасами и заявками не нарушаются, следует план остается допустимым.
Ценой однозначного цикла называется увеличение суммарной стоимости перевозок, при переносе по этому циклу 1 единицы товара. Для уменьшения стоимости перевозок необходимо делать переносы по циклам с отрицательной ценой.
Распределительный метод или метод последовательного улучшения плана перевозок
В транспортной таблице отыскиваются циклы с отрицательной ценой, по ним переносятся до тех пор, пока не будет получен оптимальный план. При этом одна из свободных перевозок переходит на базисную клетку и наоборот, заполняется одна из свободных клеток и освобождается одна из базисных.
Циклом пересчета данной свободной клетки называется цикл одна вершинка которого находится в этой свободной клетке, а остальные в базисных клетках. Для любой свободной клетки транспортной таблицы существует единственный цикл пересчета. Свободной клетке цикла пересчета присваивается знак «+». Если цена цикла пересчета некоторой свободной клетки отрицательна, то по этому циклу следует перенести количество груза равного минимальному из перевозок в отрицательных вершинах.
Метод потенциалов позволяет, исходя из некоторого опорного плана, построить за конечное число итераций решение Т-задачи.
Метод потенциалов впервые предложили Л. В. Канторович и М. К. Гавурин в 1949 г. [18; 59]. Позже аналогичный метод разработал Г. Данциг, исходя из общих идей ЛП.
Общая схема метода такова. В данном начальном опорном плане перевозок каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов Ai i Bj, связанных основной коммуникацией, была равна cij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит cij, то данный план перевозок - оптимальное решение задачи. В противном случае указывают способ улучшения текущего плана Т-задачи.
Описание алгоритма метода потенциалов. Алгоритм складывается из предварительного этапа и конечного числа однотипных итераций.
На предварительном этапе строят начальный опорный план и составляют матрицу
где
- предварительные потенциалы пунктов 
.Предварительный этап. С помощью известного метода (например северо-западного угла или минимального элемента) определяют начальный опорный план Х0 и вычисляют предварительные потенциалы
.Вычисление предварительных потенциалов производят так. По найденному опорному плану Х0 строят схему перевозок Т-задачи из основных коммуникаций плана. Напомним, что основные коммуникации
плана Х0 = 
- это те, которым отвечают базисные компоненты плана, т.е. коммуникации для которых 
. Далее образуют следующие множества: J1 - множество индексов всех пунктов Bj, которые связаны с пунктом А1 основными коммуникациями; І1 - множество индексов тех пунктов Аі, которые связаны основными коммуникациями с множеством J1; J2 - множество пунктов Bj, которые связаны основными коммуникациями с множеством І1 и т.д. Образование таких множеств Ік продолжаем до тех пор, пока не получим пустое множество.Поскольку на выполнение условий оптимальности оказывают влияние лишь разности
(см. теорему 3.2), то за начало отсчета (нуль) можно принять потенциал любого из пунктов.Полагаем для определенности
и вычислим систему потенциалов относительно А1. Тогда 
где j 
J1. Затем по значениям 
определяем потенциалы пунктов 
. Аналогично вычисляем потенциалы 
(для и 
.) и т.д. После того как потенциалы всех пунктов найдены, строим матрицу 
Очевидно, позиции матрицы С1, отвечающие базисным элементам плана Х0, будут заняты нулями. Если матрица С1 не содержит отрицательных элементов, то Х0 - оптимальный план. В противном случае Х0 - неоптимальный план, который может быть улучшен. Тогда переходим к выполнению однотипных итераций.
(k+1)-я итерация. Каждая итерация, кроме первой, где отсутствует первый этап, состоит из двух этапов. Предположим, что уже проведено k итераций (k=1,2,.),в результате которых получен план Хk и вспомогательная матрицу Сk. Цель (k+1)-й итерации - построение матрицы Сk+1, а также либо установление оптимальности плана Хk, либо нахождение более экономичного плана Xk+1.
Первый этап. Вычисляют матрицу Сk+1. Преобразвание матрицы Сk в матрицу Сk+1 состоит в следующем. Выбирают наибольший по модулю отрицательный элемент Сk. Пусть это элемент
. Тогда вычеркивают (или выделяют) строку 
, в которой он содержится. Просматривают эту строку и отыскивают множество существенных его элементов. Хk -существенными элементами называют те элементы 
=0, которые отвечают базисным элементам плана Хk т.е. для которых 
. Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают вычеркнутые столбцы и ищут в них новые существенные элементы, которые лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы имеются, то вычеркивают строки, в которых они содержатся. Процесс выделения продолжают до тех пор, пока очередное множество новых существенных элементов не окажется пустым. Поскольку каждые строка и столбец не могут быть выделены дважды, то весь процесс заканчивается не более чем за l =m+ n - 1 шагов. Далее строят матрицу Сk+1. Для этого величину 
прибавляют ко всем элементам выделенных строк и вычитают из элементов всех выделенных столбцов матрицы Сk. При этом все существенные элементы матрицы Сk остаются равными нулю, а кроме того, в нуль превращается и элемент 
.