Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Новый план Х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

Рекомендуем скачать другие рефераты по теме: бесплатно решебник, конспекты статей.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата