Рефетека.ру / Промышленность и пр-во

Реферат: Оптимизация доставки инсектицидного средства в Ростове-на-Дону

Курсовая работа по дисциплине: «Исследование операций и принятие решений»

Выполнил студент гр. 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 остаются равными нулю, а кроме того, в нуль превращается и элемент Оптимизация доставки инсектицидного средства в Ростове-на-Дону.

Если все элементы матрицы Сk+1 окажутся неотрицательными, то Xk - оптимальный план, и на этом процесс заканчивается. В противном случае переходят ко второму этапу.

Второй этап. Цель этого этапа - построить более экономичный план Хk+1. Выбирают наибольший по модулю отрицательный элемент матрицы Сk+1. Пусть это элемент Оптимизация доставки инсектицидного средства в Ростове-на-Дону. Строят цепочку из положительных элементов плана, которая замыкается на Оптимизация доставки инсектицидного средства в Ростове-на-Дону. После того, как цепочка построена, в ней находят минимальный нечетный по порядку следования элемент:

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

Прибавляют Оптимизация доставки инсектицидного средства в Ростове-на-Дону ко всем четным элементам (по порядку следования) цепочки и к элементу Оптимизация доставки инсектицидного средства в Ростове-на-Донуи вычитают Оптимизация доставки инсектицидного средства в Ростове-на-Дону из всех нечетных элементов. Остальные элементы Хk оставляют без изменения.

Новый план Хk+1 построен. Он является базисным, так как число его ненулевых элементов не изменилось.

Пусть Lk - транспортные издержки, отвечающие плану Хk. Тогда новое значение целевой функции, отвечающее плану Xk+1, находят по соотношению

Оптимизация доставки инсектицидного средства в Ростове-на-Дону . (3.2.1)

Так как Оптимизация доставки инсектицидного средства в Ростове-на-Дону и Оптимизация доставки инсектицидного средства в Ростове-на-Дону, то Оптимизация доставки инсектицидного средства в Ростове-на-Дону. Поэтому Хk+1 - улучшенный опорный план.

Затем производят аналогично (k+2)-ю итерацию.

Поставим в соответствие каждому пункту Ai некоторое число Оптимизация доставки инсектицидного средства в Ростове-на-Дону и каждому пункту назначения Bj некоторое число Оптимизация доставки инсектицидного средства в Ростове-на-Дону.

Оптимизация доставки инсектицидного средства в Ростове-на-Дону и Оптимизация доставки инсектицидного средства в Ростове-на-Дону называются потенциалами, Оптимизация доставки инсектицидного средства в Ростове-на-Дону, где Оптимизация доставки инсектицидного средства в Ростове-на-Дону - это псевдостоимость.

В базисных клетках cij=Оптимизация доставки инсектицидного средства в Ростове-на-Дону. План перевозок является оптимальным если

cij=Оптимизация доставки инсектицидного средства в Ростове-на-Дону, для всех базисных клеток,

Оптимизация доставки инсектицидного средства в Ростове-на-Дону≤ cij, для всех свободных клеток.

Алгоритм метода потенциалов

Строим исходный оптимальный план, в котором r=m+n-1 базисных клеток.

Одной из неизвестных Оптимизация доставки инсектицидного средства в Ростове-на-Дону, Оптимизация доставки инсектицидного средства в Ростове-на-Дону присваиваем произвольное численное значение (к примеру, 0) и по формуле Оптимизация доставки инсектицидного средства в Ростове-на-Дону для базисных клеток находим потенциалы Оптимизация доставки инсектицидного средства в Ростове-на-Дону и Оптимизация доставки инсектицидного средства в Ростове-на-Дону.

Вычисляем псевдостоимости Оптимизация доставки инсектицидного средства в Ростове-на-Дону для всех свободных клеток, если псевдостоимость ≤ стоимости (Оптимизация доставки инсектицидного средства в Ростове-на-Дону≤ cij), то план перевозок оптимальный.

Если хотя - бы в одной клетке псевдостоимость > стоимости (Оптимизация доставки инсектицидного средства в Ростове-на-Дону>cij), то улучшаем план перевозок путем переноса перевозок по циклу пересчета для свободной клетки с отрицательной ценой (в которой Оптимизация доставки инсектицидного средства в Ростове-на-Дону>cij).

Подсчитываем новые потенциалы.

Постановка задачи

Предметная область и общая постановка задачи

Объектом данной работы будет отдел крупной торговой фирмы ООО «ТОНВИДЕО»( пер.Доломановский 183) в Ростове-на-Дону, который занимается распределением и сбытом в Ростове-на-Дону инсекцицидное средство «КРА ДЕО СУПЕР» для уничтожение летающих насекомых, которое поставляется в Ростов-на-Дону из Казани (ул 3-я Кленовая 9) железнодорожными путями.

Товар принимается в Ростове на трех складах: Можайская 167(в р-не авто рынка «Алмаз»), Врубова 32 и Доватора 44/3, и уже оттуда распределяется на рынки: рынок «Лидер»(р-н александровка), «Нахичеванский», Ц.Рынок, «Привоз», «Военвед», «Темерник», в которых арендуются небольшие складские помещения специально под донный товар.

Необходимо составить план перевозок товара из трех складов на рынки таким образом, чтобы доставка осуществлялась без лишних затрат для фирмы. Для достижения цели используем транспортную задачу и определим, какие рынки будет обсуживать данный склад. Решим задачу по временному критерию, т.к. перевозки по Ростову осуществляются грузовым автотранспортом и стоимость перевозки рассчитывается от расхода топлива, а топливо расходуется даже если транспорт застрял в пробке.

Итак, задача сводится к тому, что нужно выяснить из какого склада на какой рынок доставка будет осуществлена быстрее, с учетом пробок на дорогах и средней скорости машины 25 км/ч.

Для решения транспортной задачи необходимо знать количество заявок с каждого рынка (для нашей задачи используем количество заявок на 1 неделю), количество заявок равно вместимости складского помещения, т.е. количеству упаковок которые можно поместить на складе.

«Лидер» - 30

«Нахичеванский»-40

«Ц.Рынок»-50

«Привоз»-40

«Военвед»-20

«Темерник»-60

Математическая постановка задачи

Имеются 3 пункта отправления товара Можайская 167 (А1), Врубова 32(А2) и Доватора 44/3 (А3), в которых сосредоточено 90, 80 и 80 упаковок соответственно, предназначенных для доставки, и 6 пунктов назначения: «Лидер» (В1), «Нахичеванский», (В2), Ц.Рынок (В3), «Привоз»(В4), «Военвед»(В5), «Темерник» (В6), которые подали заявки на некоторое количество товара, которое описано выше. Известны время перевозки из каждого склада на каждый рынок.

Требуется составить план перевозок, при котором все заявки были бы удовлетворены и суммарное время перевозок была бы минимальна.

Обозначим xij-количество товара, которое надо отправить из склада на рынок. Тогда наша задача выглядит следующим образом L=Оптимизация доставки инсектицидного средства в Ростове-на-Дону min, где Оптимизация доставки инсектицидного средства в Ростове-на-Дону, Оптимизация доставки инсектицидного средства в Ростове-на-Дону, j=(1,6), i=(1,3) (n=6, m=3). План перевозок xij, будет опорным, если в нем не равны нулю не более чем r=m+n-1 перевозок xij.Так как 90+80+80=30+40+50+40+20+60, следует транспортная задача закрытая.

Транспорт перевозит товар из А1 в В1 за 20 минут

Из А1-В1 за 20мин

Из А1-В2 за 25мин

Из А1-В3 за 35мин

из А1-В4 за 50мин

из А1-В5 за 50мин

из А1-В6 за 20мин

из А2-В1 за 25мин

из А2-В2 за 15мин

из А2-В3 за 25мин

из А2-В4 за 35мин

из А2-В5 за 40мин

из А2-В6 за 25мин

из А3-В1 за 50мин

из А3-В2 за 40мин

из А3-В3 за 30мин

из А3-В4 за 10мин

из А3-В5 за 20мин

из А3-В6 за 45мин

Оптимизация доставки инсектицидного средства в Ростове-на-Дону 

Составим матрицу временных затрат (С) и транспортную таблицу.

С=Оптимизация доставки инсектицидного средства в Ростове-на-Дону - матрица временных затрат

Таблица 2.3 - Транспортная таблица

 пн

по

В1 В2 В3 В4 В5 В6

запасы

аi

А1 20 25 35 50 50 20 90
30 40 20
А2 25 15 25 35 40 25 80
30 40 10
А3 50 40 30 10 20 45 80
20 60

запасы

bj

30 40 50 40 30 60 250

РЕШЕНИЕ ЗАДАЧИ

Метод потенциалов

Поставим в соответствие каждому пункту Ai некоторое число Оптимизация доставки инсектицидного средства в Ростове-на-Дону и каждому пункту назначения Bj некоторое число Оптимизация доставки инсектицидного средства в Ростове-на-Дону. Выбрав Оптимизация доставки инсектицидного средства в Ростове-на-Дону=0, находим остальные потенциалы,(потенциалы обладают тем свойством, что для базисных клеток их сумма должно равняться стоимости) а после считаем псевдостоимость перевозок и заполняем таблицу 3.4.

Таблица 3.1 - Транспортная таблица

 пн

по

В1 В2 В3 В4 В5 В6

запасы

аi

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

А1 20 25 35 45 50 50 50 75 20 90 0
30 40 20
А2 10 25 15 15 25 35 40 65 25 80 -10
30 40 10
А3 -10 50 -5 40 5 30 15 10 20 45 80 -30
20 60

запасы

bj

30 40 50 40 30 60

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

20 25 35 45 50 75

L=30*20+40*25+20*35+30*25+40*35+10*40+20*20+60*45=7950

Необходимо выделить те клетки, где косвенные стоимости больше заданных стоимостей. Если таких клеток нет то план оптимален для задачи минимизации. Таких клеток в таблице много, выбираем ту клетку, где разница больше, чтобы привести её в состав базисных- это (1,6).

Построим цикл –замкнутую ломаную с вертикальными и горизонтальными звеньями, вершины которых находятся в клетке (1,6). Вершины цикла – это (1,6)-(3,6)-(3,5)-(2,5)-(2,3)-(1,3)-(1,6)

Для сохранения баланса в вершинах цикла нужно чередовать вычитание и добавление величины, которая выбирается минимальной поставкен в тех клетках, где вычитаем. Таким образом min(60,10,20)=10.

После переноса товара с ячейки (2,8) таблица получится таблица 3.5.

Таблица 3.2 - Транспортная таблица

 пн

по

В1 В2 В3 В4 В5 В6

запасы

аi

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

А1 20 25 35 45 50 -5 50 20 90 0
30 40 10 10
А2 10 25 15 15 25 35 -35 40 10 25 80 -10
40 40
А3 45 50 50 40 60 30 70 10 20 45 80 25
30 50

запасы

bj

30 40 50 40 30 60

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

20 25 35 45 -5 20

L=30*20+40*25+10*35+40*25+40*35+30*20+50*45+10*20=7400

Проделав еще одну итерацию получим таблицу 3.3.

Таблица 3.3 - Транспортная таблица

 пн

по

В1 В2 В3 В4 В5 В6

запасы

аi

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

А1 20 25 25 35 -15 50 -5 50 20 90 0
30 40 20
А2 45 25 75 15 25 35 45 40 70 25 80 50
50 30
А3 45 50 50 40 0 30 10 20 45 80 25
10 30 40

запасы

bj

30 40 50 40 30 60

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

20 25 -25 -15 -5 20

L=30*20+40*25+50*25+30*35+10*10+30*20+40*45+20*20=6800

Проделав еще одну итерацию получим таблицу 3.4.

Таблица 3.4 - Транспортная таблица

 пн

по

В1 В2 В3 В4 В5 В6

запасы

аi

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

А1 20 25 35 35 -15 50 45 50 20 90 0
30 10 50
А2 15 25 15 25 -25 35 35 40 10 25 80 -10
30 50
А3 45 50 50 40 60 30 10 20 45 80 25
40 30 10

запасы

bj

30 40 50 40 30 60

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

20 25 35 -15 45 20

L=30*20+10*25+30*15+50*25+40*10+30*20+45*10+50*20=5000

Проделав еще одну итерацию получим таблицу 3.5.

Таблица 3.5 - Транспортная таблица

 пн

по

В1 В2 В3 В4 В5 В6

запасы

аi

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

А1 20 25 35 35 15 50 25 50 20 90 0
30 0 60
А2 10 25 15 25 5 35 15 40 10 25 80 -10
40 40
А3 15 50 20 40 30 10 20 40 45 80 -5
10 40 30

запасы

bj

30 40 50 40 30 60

Оптимизация доставки инсектицидного средства в Ростове-на-Дону

20 25 35 15 25 20

L=30*20+0*25+40*15+40*25+10*30+40*10+30*20+60*20=4700

В таблице 3.5 не одна псевдостоимость не больше времени перевозок, следует данная таблица оптимальна.

АНАЛИЗ РЕЗУЛЬТАТОВ И РЕКОМЕНДАЦИИ

Используя транспортную задачу линейного программирования, мы получили оптимальный план перевозок, т.е. план по которому время доставки будет минимальна, а значит и минимальными будут затраты на перевозки. Согласно конечной транспортной таблице можем сказать, что из пункта отправления А1 доставку лучше осуществлять в пункты назначения В1 и В6, из А2 в В2 и В3 из А3 в В3, В4, В5.

В результате решения транспортной задачи данной фирме рекомендуется осуществлять доставку товара в следующим образом:

Оптимизация доставки инсектицидного средства в Ростове-на-ДонуОптимизация доставки инсектицидного средства в Ростове-на-ДонуОптимизация доставки инсектицидного средства в Ростове-на-Дону

Можайская 167                     Врубова 32                         Доватора44/3

Оптимизация доставки инсектицидного средства в Ростове-на-Дону
Оптимизация доставки инсектицидного средства в Ростове-на-Дону Оптимизация доставки инсектицидного средства в Ростове-на-Дону

«Лидер»(30уп) «Нахичеванский»(40уп) «Ц.Рынок»(10уп)

«Темерник»(60уп) «Ц.Рынок»(40уп) «Привоз»(40уп)

«Военвед»(30),

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://referat.ru


Рефетека ру refoteka@gmail.com