Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 22.05.2010, 11:13
Новичок

Отправить личное сообщение для Srpj Посмотреть профиль Найти все сообщения от Srpj
 
Регистрация: 22.05.2010
Сообщений: 4

Вариант задачи о рюкзаке с двумя критериями
Здравствуйте!
Мне нужно решить вариант задачи о рюкзаке.
Вот неформальная постановка задачи.
Имеется склад с пронумерованными ячейками, в которых лежат различные товары. Один товар может лежать в нескольких ячейках.

Пример содержимого склада:
Ячейка №1 - Товар №1 - 6 коробок по 500 шт.
Ячейка №1 - Товар №2 - 5 коробок по 300 шт.
Ячейка №1 - Товар №3 - 3 коробки по 200 шт.
Ячейка №2 - Товар №2 - 1 коробка по 300 шт.
Ячейка №2 - Товар №2 - 2 коробки по 200 шт.
Ячейка №2 - Товар №3 - 1 коробка по 300 шт.
Ячейка №3 - Товар №1 - 4 коробки по 300 шт.
Ячейка №3 - Товар №3 - 2 коробки по 200 шт.
Ячейка №3 - Товар №3 - 3 коробки по 300 шт.
...

Есть список товара, который нужно выгрузить. Список состоит из нескольких позиций (позиция = вид товара + количество штук).

Пример списка:
Товар №1 - 2840 шт.
Товар №2 - 3130 шт.
Товар №3 - 700 шт.
...

Задача: оптимальным образом выгрузить всю продукцию по списку.
Критерии оптимальности следующие:
1. Число использованных ячеек (для списка в целом) должно быть минимальным.
2. Точность подбора по количеству штук должна быть максимальной.
Критерии применяются по порядку: сначала критерий №1, затем критерий №2.

Если бы не было критерия №1, это была бы классическая задача о рюкзаке с возможностью единичного выбора предмета. Решение этой задачи динамическим программированием приведено здесь: http://ru.wikipedia.org/wiki/Задача_о_ранце.
Проблема в том, как минимизировать число использованных ячеек для всего списка. Можно, конечно, сначала найти все минимальные наборы ячеек, содержащие всю продукцию по списку (например, {Ячейка №1, Ячейка №7} или {Ячейка №2, Ячейка №5}), и затем для каждого набора решить задачу о рюкзаке с подбором по количеству. Но, боюсь, что такое решение будет работать долго.

Может быть, можно рекуррентные соотношения, приведенные в этой статье (http://ru.wikipedia.org/wiki/Задача_о_ранце), модифицировать так, чтобы находилось решение, оптимальное в первую очередь по количеству ячеек (для списка в целом), а затем по количеству штук?
Я затрудняюсь найти такое рекуррентное соотношение. Может быть, вы поможете найти его, или подскажете другой эффективный алгоритм решения задачи?
  #2  
Старый 22.05.2010, 15:58
гость

 
Сообщений: n/a

Цитата:
1. Число использованных ячеек (для списка в целом) должно быть минимальным.
2. Точность подбора по количеству штук должна быть максимальной.
Критерии применяются по порядку: сначала критерий №1, затем критерий №2.
ну очевидно, что лучше ващще не заходить на склад, не открывать ни одной ячейки. 0 ячеек => наилучшее решение с точки зрения критерия №1.
  #3  
Старый 22.05.2010, 16:13
Новичок

Отправить личное сообщение для Srpj Посмотреть профиль Найти все сообщения от Srpj
 
Регистрация: 22.05.2010
Сообщений: 4

Задача: оптимальным образом выгрузить ВСЮ продукцию по списку (см. условие).
Ваше сообщение навело на мысль: задача сформулирована несколько противоречиво. Сейчас подумаю над переформулировкой.

Последний раз редактировалось Srpj, 22.05.2010 в 16:41.
  #4  
Старый 22.05.2010, 17:06
гость

 
Сообщений: n/a

Сообщение от Srpj Посмотреть сообщение
Задача: оптимальным образом выгрузить ВСЮ продукцию по списку (см. условие).
А тогда в чем смысл критерия 2? Вы говорите надо всю продукцию, критерий 2 говорит что можно не всю...
  #5  
Старый 22.05.2010, 17:14
Новичок

Отправить личное сообщение для Srpj Посмотреть профиль Найти все сообщения от Srpj
 
Регистрация: 22.05.2010
Сообщений: 4

Согласен, задача сформулирована противоречиво.
Переформулируем ее.

Задача: оптимальным образом выгрузить продукцию по списку.

Критерии оптимальности:
1. Минимальное число использованных ячеек (для списка в целом).
2. Максимальная точность по количеству штук (для каждого элемента списка).
Считаем, что между критериями нет четкого порядка.

Необходимо найти все Парето-оптимальные решения, т. е. такие решения, которые нельзя улучшить по любому критерию без ухудшения по остальным критериям.

Примечание: товар можно извлекать только целыми коробками (нельзя открывать коробки).

Подскажите алгоритм.

Последний раз редактировалось Srpj, 22.05.2010 в 17:40.
  #6  
Старый 22.05.2010, 20:10
гость

 
Сообщений: n/a

Цитата:
2. Максимальная точность по количеству штук (для каждого элемента списка).
А точность тут что такое? Сумма модулей разностей? Квадратов? Число товаров где нет точного равенства?

В любом случае, сильно сомнаввюсь что есть алгоритм лучше перебора с отсечениями.

Даже забыв про второй критерий, оптимизация под первый критерий - есть задача multiple knapsack, для которой даже динамическое программирования практически непригодно.
  #7  
Старый 22.05.2010, 20:15
гость

 
Сообщений: n/a

Цитата:
Примечание: товар можно извлекать только целыми коробками (нельзя открывать коробки).
из каждого склада извлекаются все коробки или на выбор?

если все, то, думаю можно свести к задаче линейного целочисленного программирования (с переменными - брать/не брать каждый склад). там есть более менее работающие алгоритмы, экспоненциальные, но сильно пошустрее перебора.
  #8  
Старый 22.05.2010, 21:29
Новичок

Отправить личное сообщение для Srpj Посмотреть профиль Найти все сообщения от Srpj
 
Регистрация: 22.05.2010
Сообщений: 4

Сообщение от гость
А точность тут что такое? Сумма модулей разностей? Квадратов? Число товаров где нет точного равенства?
Честно говоря, еще не решил. Можно, например, в качестве точности (со знаком минус) взять максимальную из относительных погрешностей по списку. Думаю, что способ определения точности здесь не принципиален.

Сообщение от гость
Даже забыв про второй критерий, оптимизация под первый критерий - есть задача multiple knapsack, для которой даже динамическое программирования практически непригодно.
Если оптимизацию по первому критерию можно свести к задаче multiple knapsack, покажите, как это сделать.

Сообщение от гость
из каждого склада извлекаются все коробки или на выбор?
Из каждой ячейки может извлекаться любое количество коробок.
Для приведенного примера решение (выборка) может быть таким:
Ячейка №1 - Товар №1 - 5 коробок по 500 шт.
Ячейка №1 - Товар №2 - 5 коробок по 300 шт.
Ячейка №1 - Товар №3 - 3 коробки по 200 шт.
Ячейка №2 - Товар №2 - 1 коробка по 300 шт.
Ячейка №2 - Товар №2 - 2 коробки по 200 шт.

Использовано ячеек: 2
Макс. относ. погрешность: (3130-2200)/3130=29,71% (товар №2)
  #9  
Старый 30.07.2010, 21:18
Новичок

Отправить личное сообщение для deosis Посмотреть профиль Найти все сообщения от deosis
 
Регистрация: 30.07.2010
Сообщений: 8

http://www.mslevin.iitp.ru/Lev-Saf-AIDM_53_64.pdf
здесь описание и решение задачи, почти идентичной Вашей
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача о рюкзаке buddyroo Задачи 2 30.12.2010 22:11
Вариация задачи о рюкзаке гость Математические алгоритмы (другое) 1 05.10.2009 19:44
Рекуррентные двумя строками vosminog Математические алгоритмы (другое) 6 17.03.2009 17:47
LLL-алгоритм решения задачи о рюкзаке Emerald Реализация, исходники, языки 3 15.01.2009 01:32
Минимальное расстояние между двумя конусами Vektor64 Вычислительная геометрия 1 26.08.2008 14:07