рефераты бесплатно
Рефераты бесплатно, курсовые, дипломы, научные работы, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения,рефераты литература, рефераты биология, рефераты медицина, рефераты право, большая бибилиотека рефератов, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент и многое другое.
ENG
РУС
 
рефераты бесплатно
ВХОДрефераты бесплатно             Регистрация

Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения  

Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

А.А. Колоколов, Т.В. Леванова, Институт информационных технологий и прикладной математики СО РАН

1. Введение

В [1] описаны алгоритмы для решения частично целочисленных задач производственно-транспортного типа, основанные на идее декомпозиции Бендерса и метода направленного перебора. В данной работе предлагаются декомпозиционные алгоритмы для простейшей задачи размещения (ПЗР), задачи о p-медиане [2, 8] и некоторых других постановок, в которых наряду с отсечениями Бендерса для решения целочисленной подзадачи используется лексикографический перебор L-классов [?]. Краткое сообщение о них имеется в [7].

Рассмотрим ПЗР в следующей постановке. Дано конечное множество пунктов возможного размещения предприятий и список клиентов. Предприятия производят однородный продукт в неограниченном количестве. Известны стоимости размещения предприятий в указанных пунктах и затраты на удовлетворение спроса каждого клиента. Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы суммарные производственно-транспортные затраты были минимальны. Введем некоторые обозначения:

m - число пунктов возможного размещения предприятий, i - номер предприятия,  Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

n - число клиентов, j - номер клиента,  Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

ci - стоимость размещения предприятия в пункте i;

tij - затраты на удовлетворение спроса клиента j предприятием i (включающие издержки на производство и транспортировку);

xij - часть всей продукции, которую необходимо доставить с предприятия i клиенту j;

 Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

Обозначим  Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения.

Мы используем следующую модель ПЗР:

 Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения



© 2010.