Russian Qt Forum

Столкнулся со следующей задачей:
Существует 9 продуктов, которые можно производить друг за другом и с определенными объемами.
Например, 1 от 10 до 20 шаг 0,1
               2 от 10 до 20 шаг 0,1
              ...
               9 от 10 до 20 шаг 0,1
Таким образом получаются различные комбинации 10,10,10,10,10,10,10,10,10 ; 10,10,10,10,10,10,10,10,10.1;...; 20,20,20,20,20,20,20,20,20

И только одна комбинация имеет минимальные затраты. Поиск комбинаций очень трудозатратен, получается 1E+18 комбинаций , что может занять длительное время.
Если решать так:

C++ (Qt)
 for(i=0;i<=10;i=i+0.1)
     for(j=0;j<=10;j=j+0.1)
        for(k=0;k<=10;k=k+0.1)
               for(l=0;l<=10;l=l+0.1)
                   for(m=0;m<=10;m=m+0.1)
                        for(n=0;n<=10;n=n+0.1)
                         {
 
                         }
 
 

Какой алгоритм или метод можно применить для решения данной задачи?

А что входит в понятие минимальных затрат комбинаций?

При производсте используется сырье, которое содержится в бочках.
Минимальные затраты будут только тогда, когда будут вырабатываться целые бочки, т.е. не будет остатков сырья.


В таблице показано вложение сырья по продуктам.

Решение поиска комбинаций для 6 продуктов (вложенные циклы) занимает 52.291383333333 min.
И это без учета расчета потребности сырья, определения целых бочек и поиска отптимального решения.
Для 9 продуктов наверное можно вообще не дождаться.

Ну наверное 1, 2. 9 - номера продуктов. Но от каких "10"? До каких "20"?
А тут я вообще "потерял нить" :)

Ну вот, теперь еще бочки. Ничего не понял

Существует 9 продуктов и есть 9 видов сырья. Есть рецептуры согласно которым продукты использую сырье.
Мы ищем отпимальное решение в диапазоне от 10 до 20 с шагом 0,1, т.е. производственная партия может быть 10 , 10.1,..., 10.5, ...,11, ...,15.8, ..., 20
И так для 9 продуктов. Сырье хранится в бочках, которые имеют свой вес. Задача оптимально использовать бочки (расход целыми бочками).
Также необходимо не отклоняться от производственной программы, если цель произвести 10, значит можно отклоняться только с допуском.

одно сырье на продукт?
или они могут миксоваться?
если да, то как?
задача непонятна, честно говоря... :(

В таблице выше показал связь сырье-продукт . В ячейках заклади сырья в продукт.

Кто такие эти "10", "20" и "шаг"? Как они связаны с сырьем и бочками?

у меня есть производственная программа
продукт1 10
продукт2 10
продукт3 10
продукт4 10
продукт5 10
продукт6 10
продукт7 10
продукт8 10
продукт9 10
но если я так произведу продукты, останется невыработанное сырье в бочках.
Поэтому я ищу в диапазоне, т.е. составляю все комбинации с учетом диапазона с определенным шагом.
Среди всех найденных комбинаций будет такая комбинация , в которой все бочки будут выработаны или макисмально выработаны.


пример для одного продукта.  Продукт1 партия пр-ва 10 тыс.л.  Расход сырья (выше в таблице закладки. Для данного продукта используется только сырье 4. Закладка 179,5) : уйдет сырья 4 - 1795 кг. (вес бочки 250 кг). т.е видно что мы не вырабатываем бочку. (7.18 бочек)
След итерация +0,1  Продукт1 партия пр-ва 10.1 тыс.л.  Расход сырья (выше в таблице закладки) : уйдет сырья 4 - 1812,95 кг. (вес бочки 250 кг). т.е видно что мы не вырабатываем бочку. (7,2518 бочек)

итд.

То есть получется, что вам надо подгонять объем партии под объемы сырья в бочках...
На каждом шаге инкремент (коэффициент) должен быть одинаковый длях все бочек в пределах продукта.
А вам надо каждый раз все 9 продуктов производить за цикл? или на это нет ограничений?

звучит как задача о ранце

Да, нужно найти оптимальную выработку бочек, но чтобы не было большого отклонения от производственной программы.
Производственная программа может включать 9 продуктов, а может 5 или 6. Проблема возникает, когда много продуктов.
Думаю , это не совсем задача о ранце, та как там нет такого количества комбинаций.

а может подойти с точки зрения максимизации прибыли, а не минимизации затрат ?
ведь может быть что "неоптимальный" продукт по затратам берут лучше
хотя конечно это не исходная задача, так мысли вслух

Немного яснее, а что с "производственной программой"? Пока (из того что Вы рассказали) можно просто найти такое число бочек при котором кол-во продукта от 10 до 20 и остаток в бочке минимален. Причем отдельно по каждому продукту, никаких переборов пока нет

Вот, с этого места можно подробнее. Я понимаю, что можно решать обратным методом, но там тоже будут циклы.

Например потребность продукта на неделю  15 , я могу отклониться +-5, поэтому ищу в дипазоне нужную партию

У вас есть продукты, которые не используют все 9 бочек.
Делайте цикл только по бочкам в пределах продуктов, которые будут включены в данную серию.
Например, Продукт 1 зависит только от Бочки 4 - значит, нет смысла для него перебирать остальные :)

Так с первым продуктом понятно. Как поступать с остальными? Например есть продукт который использует несколько видов сырья. а также продукты , которые также используют данное сырье. Т.е. я выравняю одно сырье, как сбалансировать все виды сырья?

Ну смотрите. Делаете цикл по продуктам от 1 до 10. С 1 понятно. Затем для 2 продукта подбираем пропорции так, что бочки использованы по максимуму. Запоминаем остатки в бочках, переходим к продукту 3. Снова подбираем максимальный расход бочек, с учётом остатков с предыдущего шага, если такие имеются для текущих бочек. Опять запоминаем остатки и переходим к продукту 4 и т.д. Таким образом получается только один внешний цикл по продуктам, а в каждом продукте циклы по коэффициентам только для используемых в нем бочек. В конце получим несколько бочек с "издержками производтства", но это будет ваш допустимый минимум :)

не забыть qtconcurent для использования всех ядер при обработке в цикле

Продукты 2 и 3 могут использовать одну и ту же бочку. Идеальным может оказаться напр у каждого остаток по пол-бочки

Могут, поэтому мы должны запомнить остатки и использовать их в последующих продуктах.

Ну а если пол-бочки осталось и ничего с этим не сделать, придется, наверно, разбодяжить :)
Кстати, алгоритм мог бы еще подсчитывать оптимальное разбодяживание сырья, с допустимым ухудшением продукта...

А как Вы выровняете хотя бы одно сырье? Напр сырье 8 используется всеми продуктами кроме 1. Тогда может так.

1) Перебираем все варианты продукта 2 (с шагом как у Вас) и сохраняем все остатки в контейнере. Если такой остаток уже есть - пропускаем
 
2) То же самое для продукта 3

3) Теперь из 2 контейнеров собираем общий. В него заносим остатки-суммы всех комбинаций 1-го и 2-го. Большинство остатков будет повторяться, их отбрасываем

4) Вычисляем остатки для продукта 4 и делаем сумму общий + остатки 4

И так по всем продуктам. В итоге получаем контейнер остатков из которого выбираем минимальный элемент. Смысл в том что с увеличением числа продуктов вычислительные расходы растут линейно
 

Что вы понимаете под "сохраняем все остатки в контейнере"?

Тот пример что Вы привели
Остатки будут 8-7.18 и 8-7,2518. Вот их и храним

Update: только храним как целые числа, напр домножаем float на 1000 и отнимаем 1 если не ноль. Чтобы контейнер не сильно разрастался

Мое имхо, что нужно вводить весовые коэффициенты продуктов. Например, по количеству используемых материалов. Начинать расчет нужно с продукта, использующего максимальное количество сырья. Ввести ограничение сколько нужно его произвести или определить сколько его вообще можно выработать. А потом или начинать считать по убыванию количества используемого сырья. За примером смотреть тут (тут правда один материално разные продукты. несложно переложить на лад топикстартера)  http://industrial-wood.ru/lesopilenie/6250-proektirovanie-optimalnyh-sistem-postavov-s-ispolzovaniem-evm.html (http://industrial-wood.ru/lesopilenie/6250-proektirovanie-optimalnyh-sistem-postavov-s-ispolzovaniem-evm.html) . Да  похоже на рюкзак, но другого ничего не выдумаешь. В конце концов Задача о назначении какую мы тут видим это тоже вариант рюкзака.

В самой постановке задачи "выбор оптимального решения" есть ответ, каким образом целесообразно ее решить без полного перебора комбинаций. Сейчас имеется 9 продуктов, а как быть, если продуктов станет больше? Требуется сформулировать целевую функцию - сейчас это количество остатков, потом может другой критерий оптимизации. Затем использовать любой алгоритм оптимизации, подставляя объемы продуктов из области допустимых значений. Имхо, такая задача сходится достаточно быстро.

Ну как-то складывается впечатление что, мол, да тут легко, общих фраз вполне достаточно :) Я так не считаю, задачка трудная (хотя возможно и стандартная).

Ну и типа дальше все ясно - гуглим, находим решение и реализуем. Вряд ли. Во-первых не вижу где тут (зас)ранец ??? Мы ничего не наполняем, наоборот, общее кол-во может быть очень разным. Во-вторых, даже если бы и "попали" - толку немного. "Ранец", "Коммивояжер" и др. - эти задачи известны сотни лет, а вот каких-то четких решений нет. Ну вот рекомендуют напр "метод ветвей и границ" - и что? Как его здесь применить, где же "ветви"? :) Не говоря уже о том что есть масса вариаций задачи

Да, согласен. Я тоже не увидел здесь стандартных алгоритмов. Может кто-то сталкивался с подобными задачами на практике?
Если решать обратным методом, т.е. идти циклом не по продуктам, а по бочкам. То тоже кол-во комбинаций будет большое, так как если я вырабатываю не целые бочки, а например
98% 1 бочки (1 сырье), 99,5% бочек (2 сырье); 96% бочек (3 сырье) ... Это тоже может быть решением. 

То что я предложил стандартно, называется "динамика" (динамическое программирование), вроде здесь подходит

Как я уже писал, по продуктам можно идти линейно, т.е. для каждого продукта проверять комбинации только с задействованными для него бочками плюс остатки с предыдущего шага. Это будет намного быстрее "тупого" перебора.

Грубо получается: P * (K * Bp), P - это продукты, Bp - кол-во бочек для продукта P, К - кол-во комбинаций проверки.
Например, если Р=10, Bp (грубо в половину) =5, K = 10..20 step 0.1 = 100, то имеем: 10 * 5 * 100, всего 5000 вычислений.
Секунда? Полсекунды?
:)

Основная сложность в четком определении
- перечня варьируемых параметров и области их определения - в данном случае 9 переменных из области [10...20].
- целевой функции, которая рассчитывается по варьируемым параметрам - это может быть остатки сырья, стоимость оставшегося сырья и т.д.
- ограничивающих параметров - например, ограниченный объем сырья (не более N бочек) и т.п.

Как только есть метод расчета целевой функции с проверкой на выполняемые ограничения, можно использовать любой понравившийся метод оптимизации, например, отсюда http://www1.icsi.berkeley.edu/~storn/code.html (http://www1.icsi.berkeley.edu/~storn/code.html) или взять готовый продукт http://www.iosotech.com/ru/products.htm (http://www.iosotech.com/ru/products.htm) или Mathcad.

вот с ограничениями в условии задачи и трудности - нет ограничения на количества сырья. А в этом случае ничего кроме как тупого перебора не остается.

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

Ну что ж так быстро-то программист опускает руки?  Вроде еще не "пользователь Qt" :)

Кажется понял как решать, вот набросок

C++ (Qt)
// структура элемента
struct CReminder {
 std::vector<int> mRem;   // остатки по каждому сырью (0..999)
 int mSum;                       // сумма остатков
 int mTblIndex;                 // индекс в предыдущей таблице
 std::vector<int> mAdd;   // число произведенных продуктов по каждому сырью
};
 
// подсчет новых остатков
int TryAdd( const CReminder & rem, std::vector<int> & data )
{
  int result = 0;
  assert(rem.,Rem.size() == data.size());
  for (size_t i = 0; i < data.size(); ++i) {
    int a = rem.mRem[i];
    if (data[i]) 
      a = (a + data[i]) % 1000;
    result += a; 
  }  
  return result;
}
 
// шаг (вычисление остатков при производстве 1 продукта)
void Step( int productNo, const std::vector<float> & num, std::vector<int> & data )
{
 assert(data.size() == NUM_RAW);
 std::fill(data.begin(), data.end(), 0);
 
 for (size_t i = 0; i < NUM_RAW; ++i)  // по всем видам сырья
  data[i] = std::remainder(GlobalTable[productNo][i] * num[i], BARREL_SIZE) / BARREL_SIZE * 1000;
}
 
void Process1Product( int productNo )
{
   int numRaw = 0;
   for (size_t i = 0; i < NUM_RAW; ++i)  // кол-во сырья для этого продукта
     if (GlobalTable[productNo][i]) ++numRaw;
 
  float limit[2] = { DEF_LOW_LIMIT,  // 10
                          DEF_HI_LIMIT } // 20
  if (numRaw > 1) limit[0] = 0.0f;
 
  int rawIndex = 0;
  Process1ProductRecursive(productNo, 0, rawIndex, numRaw, limit);        
}
 

Ну все расписать не смогу - там довольно много. Смысл в том что вложенные переборы (Recursive) только по столбцу когда продукт использует 2 или больше сырья. Остальное как говорилось раньше - тот же контейнер остатков, только по всем видам сырья

Ого, да тут целый матан. Шо-то я забыл уже все, программирование отупляет.  ;)

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

Пытаюсь вникнуть в вашу идею.Пишу пока без глубокого осмысления (первая прикидка). Если все верно понял, вы предлагаете(описываю словесно):

1) В цикле идем от 1 до 100 ((20-10/0.1=100). Если диапазон решений будет другой, соотв. границы будут другие
2) Берем 1 продукт, ищем остатки сырья 4, без учета целых бочек (заносим остатки в массив№1 (массив 9(кол-во сырья) на 100 (вариантов))
3) Берем 2 продукт , ищем остатки сырья 1, 3, 8 без учета целых бочек (заносим остатки в массив №2)
и.т.д для всех продуктов.
В итоге получаем 9 массивов (9Х100) в которых будут сохранены остатки сырья, если бы производили продукты отдельно друг от друга.
Теперь нужно получить суммы остатков.
1) цикл по видам сырья (1 до 9)
2) цикл по массивам (1 до 9)
3) цикл по вариантам (1 до 100)

Получается 9*9*100 = 8100

Ищем комбинацию с наименьшим остатком по всем видам сырья.

По моему что-то напутал, ушел в размышления... ???

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

Ага, "сборки", "ключики", std::срань и.т.п. - где уж тут чего-то помнить  :)

Она не моя. Есть классическая "задача о монетках"
Казалось бы - ну без перебора никак. Но лучшее решение есть. Захотите - нагуглите, вещь известная.

Здесь я пытался сделать то же самое. Для каждого продукта есть "таблица остатков" (контейнер). Элемент хранит остатки по каждому сырью и суммарный. Индекс элемента совпадает с суммарным остатком. Напр 5-й элемент имеет mSum = 5. Остатки меряем от 0 до 999 для одного продукта, для 10 продуктов от 0 до 9999. Пустые эл-ты (такого остатка еще не было) помечаем напр mSum = -1

Process1Product перебирает все комбинации "по столбцу". Напр продукт 7 использует 3 вида сырья. На какой-то итерации 3 циклов у нас напр 5.0, 4.2, 8.1 по каждому сырью - переводим их в остатки (как если бы все бочки еще целые). Пытаемся добавить эти остатки к каждому в предыдущей таблице остатков. При этом всякий раз по mSum мы попадаем на какой-то индекс в новой таблице. Если он пустой - записываем туда новый эл-т, иначе просто ничего не делаем - такой остаток уже есть, неважно как он получен.

Update: деталь реализации. После вычисления mSum провериться был ли уже такой при производстве данного продукта. Чтобы избегать дороговатой операции "добавить к каждому"

только плюс "каждый с каждым" :) Кстати задача "разпоточивается", пусть и с некоторыми накладными расходами

Да, и вообще-то интересно как написать "общий for" для перебора в столбце. Ну вот, сейчас опять пойдет "вода"  :)

не надо "каждый с каждым" - остатки то суммируются...
выиграем мизер, потеряем время..

Пусть есть 2 продукта юзающих 2 вида сырья (одни и те же). После вычисления первого продукта имеем остатки, (по первому и второму сырью) напр
А для второго продукта
Новые комбинации остатков могут образоваться при сложении каждого эл-та первого контейнера с каждым эл-том второго. Поэтому "каждый с каждым" - квадратичный перебор

После того, как для первого продукта остатки посчитались, их надо добавлять к последующим рассчетам и с их учетом подбирать следующие расходы для продуктов 2, 3 и пр.

На это ответ уже был