2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Оптимизация перевозки грузов в лодке с одного берега на друг
Сообщение17.08.2007, 21:58 


17/08/07
3
Грузы различного вида (обозначим, как множество $X = \{x_1, x_2, ..., x_n\}$) необходимо перевезти с одного берега на другой, для чего используется лодка. Объем груза каждого вида (обозначим, как $V(x_i), i = 1:n$) строго меньше вместимости лодки $V$.
При перевозке грузы различного вида можно комбинировать только в заданных сочетаниях, т.е. в лодку могут быть помещены только заданные подмножества грузов множества $X$ (одноэлементные подмножества множества $X$ считаются априори заданными, остальные подмножества определяются в зависимости от вида грузов и текущих обстоятельств).
Каждому подмножеству множества $X$ поставлено в соответствие число, определяющее время перевозки с исходного берега на другой (на семействе множеств $X$ задана функция $F$). Время возврата лодки с противоположного берега на исходный является константой. Перевоз каждого груза по отдельности требует наименьшего количества времени, т.е. значение функции $F(х_1)$ всегда меньше или равно значению функции $F(\{x_1,x_2,x_3\}$). Но при этом $F(x_1)$ не обязательно может быть меньше, чем $F(\{x_2,x_3\}$).
Необходимо перевезти весь имеющийся груз на другой берег за минимальное время.
Груз каждого вида может делиться на части, т.е., если например, в лодку помещается груз $x_1$, а затем $x_2$, но для груза вида $x_2$ не хватает места, часть груза $x_2$ (или $x_1$) можно оставить до следующего раза (вопрос, также требующий разрешения, --- какой вид груза оставлять на берегу при перегрузе лодки.).

Не хотелось бы изобретать велосипед, а попытаться классифицировать приведенную выше задачу (а там сразу и метод (методы) решения обнаружится). Не удалось классифицировать приведенную задачу, как дискретную задачу о рюкзаке (о нескольких рюкзаках) или задачу о раскрое (хотя, аналогии ощущаются). Полной уверенности (доказательства) пока нет, но задача, кажется, NP-полная.
Имеющийся на данный момент метод решения задачи, позволяющий с уверенностью получить оптимальное решение, --- метод ветвей и границ (хотя, как кажется, применение метода ветвей и границ особенной эффективности по сравнению с полным перебором не даст, отсечение ветвей будет проводиться лишь на предпоследнем и последнем шаге). От метода в данном случае остается одно лишь красивое название, без ощутимой эффективности его применения.
Как здесь применить динамическое программирование (принцип Белмана) --- тоже пока не ясно.
Спасибо.

 Профиль  
                  
 
 Re: Классификация одной задачи (перевозка грузов).
Сообщение29.08.2007, 18:59 


17/08/07
3
Рассмотрим известную задачу покрытия с минимальным весом. Задано множество X = \{x_1, x_2, ..., x_n\} и семейство его подмножеств S = \{s_1, s_2, ..., s_m\}. Определим на семействе S вещественную функцию c:S \rightarrow R^+. Необходимо найти такое покрытие C \subseteq S, \cup_{s \in C} \{s\} = X, что вес покрытия \sum\limits_{s \in C} c(s) минимален.
В данном случае:
X --- множество грузов,
S --- семейство его подмножеств (возможные комбинации одновременного перевоза нескольких грузов),
значение функции c(s'), s' \in S --- есть время перевозки для s'.

Если бы не ограничение на вместимость лодки, то на этом можно было бы завершить классификацию задачи, сказав, что она NP-трудная. Ограничение на вместимость требует (а вернее, может потребовать) разбиения элементов покрывающего подсемейства --- "комбинации" на "подкомбинации". К задаче нахождения покрытия с минимальным весом добавляется ограничение на вес элемента покрывающего подсемейства C. Спрашивается, остается ли после добавления упомянутого ограничения задача перевозки груза NP-трудной или нет? Скорее всего --- да, остается, но как это доказать, пока не знаю. Не нашел также подобного случая и в литературе.

Разбиение каждого из элементов подсемейства C также является NP-трудной задачей (известная задача разбиения множества чисел). Но я не уверен, что после "разбиения" элементов оптимального покрытия C, полученное в итоге решение будет оптимальным для задачи перевозки грузов.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group