Часть полного текста документа:Оптимизация доставки инсектицидного средства в Ростове-на-Дону Курсовая работа по дисциплине: "Исследование операций и принятие решений" Выполнил студент гр. 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 единицы товара. Для уменьшения стоимости перевозок необходимо делать переносы по циклам с отрицательной ценой. Распределительный метод или метод последовательного улучшения плана перевозок В транспортной таблице отыскиваются циклы с отрицательной ценой, по ним переносятся до тех пор, пока не будет получен оптимальный план. ............ |