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

Новый план Х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 - Транспортная таблица

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

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

Поставим в соответствие каждому пункту Ai некоторое число и каждому пункту назначения Bj некоторое число

. Выбрав

=0, находим остальные потенциалы,(потенциалы обладают тем свойством, что для базисных клеток их сумма должно равняться стоимости) а после считаем псевдостоимость перевозок и заполняем таблицу 3.4.

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

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 - Транспортная таблица

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

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