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

Очевидно, позиции матрицы С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, для всех свободных клеток.

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

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

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

3. Вычисляем псевдостоимости для всех свободных клеток, если псевдостоимость ≤ стоимости (≤ cij), то план перевозок оптимальный.

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

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

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

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

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

 Скачать реферат