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

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

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

Выполнил студент гр. 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.

Данную задачку можно решить 3-мя способами:

способ северо-западного угла (этот способ является основой для других 2-ух),

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

способ потенциалов.

Способ северо-западного угла

Проверяется баланс .

Составляется таблица транспортной задачки.

Считается количество ненулевых перевозок r=m+n-1.

Считается L= .

Если при построении начального опорного плана перевозка сразу закрывает строчку и столбец, то в последующую по строке либо столбцу клеточку необходимо записать 0.

Цикл Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат в транспортной таблице – это ломаная с верхушками в клеточках и звеньями, лежащих повдоль строк либо столбцов удовлетворяющая последующим требованиям:

ломаная должна быть связанной,

в хоть какой верхушке цикла встречаются 2 звена 1-ое по строке, другое по столбцу.

Означенный цикл – цикл верхушкам которого приписаны «+» и «-» попеременно. При переносе Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат по означенному циклу 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)-я итерация. Любая итерация, не считая первой, где Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат отсутствует 1-ый шаг, состоит из 2-ух шагов. Представим, что уже проведено k итераций (k=1,2,.),в итоге которых получен план Хk и вспомогательная матрицу Сk. Цель (k+1)-й итерации - построение матрицы Сk+1, также или установление оптимальности плана Хk, или нахождение более экономного плана Xk+1.

1-ый шаг. Вычисляют матрицу Сk+1. Преобразвание Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат матрицы Сk в матрицу Сk+1 состоит в последующем. Выбирают больший по модулю отрицательный элемент Сk. Пусть это элемент . Тогда вычеркивают (либо выделяют) строчку , в какой он содержится. Просматривают эту строчку и ищут огромное количество существенных его частей. Хk -существенными элементами именуют те элементы =0, которые отвечают базовым элементам Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат плана Хk т.е. для которых . Вычеркивают столбцы, которые содержат эти элементы. Дальше просматривают вычеркнутые столбцы и отыскивают в их новые значительные элементы, которые лежат в строчках хороших от уже вычеркнутых ранее. Если такие элементы имеются, то вычеркивают строчки, в каких они содержатся. Процесс выделения продолжают до того времени, пока еще Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат одно огромное количество новых существенных частей не окажется пустым. Так как каждые строчка и столбец не могут быть выделены два раза, то весь процесс завершается менее чем за l =m+ n - 1 шагов. Дальше строят матрицу Сk+1. Для этого величину добавляют ко всем элементам выделенных строк и Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат вычитают из частей всех выделенных столбцов матрицы Сk. При всем этом все значительные элементы матрицы Сk остаются равными нулю, а не считая того, в нуль преобразуется и элемент .

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

2-ой Оптимизация доставки инсектицидного средства в Ростове-на-Дону - реферат шаг. Цель этого шага - выстроить более экономный план Х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) жд способами.

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

Нужно составить план перевозок продукта из 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),



oprosnik-stilej-yumora-martina.html
oprosnik-travmaticheskogo-stressa-ots-koteneva.html
oprosnik-virazhennosti-psihopatologicheskoj-simptomatiki-symptom-check-list-90-revised-scl-90-r.html