Russian Qt Forum
Март 29, 2024, 09:59 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1] 2 3   Вниз
  Печать  
Автор Тема: большое количество комбинаций и выбор оптимального решения  (Прочитано 24190 раз)
ksv-uk
Гость
« : Сентябрь 06, 2016, 11:47 »

Столкнулся со следующей задачей:
Существует 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)
                        {
 
                        }
 
 
Какой алгоритм или метод можно применить для решения данной задачи?
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #1 : Сентябрь 06, 2016, 11:53 »

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

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
ksv-uk
Гость
« Ответ #2 : Сентябрь 06, 2016, 12:07 »

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


В таблице показано вложение сырья по продуктам.
« Последнее редактирование: Сентябрь 06, 2016, 12:10 от ksv-uk » Записан
ksv-uk
Гость
« Ответ #3 : Сентябрь 06, 2016, 12:14 »

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

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Сентябрь 06, 2016, 12:47 »

Столкнулся со следующей задачей:
Существует 9 продуктов, которые можно производить друг за другом и с определенными объемами.
Например, 1 от 10 до 20 шаг 0,1
               2 от 10 до 20 шаг 0,1
              ...
               9 от 10 до 20 шаг 0,1
Ну наверное 1, 2. 9 - номера продуктов. Но от каких "10"? До каких "20"?
Таким образом получаются различные комбинации 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
А тут я вообще "потерял нить" Улыбающийся

При производсте используется сырье, которое содержится в бочках.
Минимальные затраты будут только тогда, когда будут вырабатываться целые бочки, т.е. не будет остатков сырья.
Ну вот, теперь еще бочки. Ничего не понял
Записан
ksv-uk
Гость
« Ответ #5 : Сентябрь 06, 2016, 12:57 »

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

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #6 : Сентябрь 06, 2016, 13:04 »

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

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
ksv-uk
Гость
« Ответ #7 : Сентябрь 06, 2016, 13:50 »

В таблице выше показал связь сырье-продукт . В ячейках заклади сырья в продукт.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Сентябрь 06, 2016, 14:05 »

Мы ищем отпимальное решение в диапазоне от 10 до 20 с шагом 0,1, т.е. производственная партия может быть 10 , 10.1,..., 10.5, ...,11, ...,15.8, ..., 20
Кто такие эти "10", "20" и "шаг"? Как они связаны с сырьем и бочками?
Записан
ksv-uk
Гость
« Ответ #9 : Сентябрь 06, 2016, 14:13 »

у меня есть производственная программа
продукт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 бочек)

итд.
« Последнее редактирование: Сентябрь 06, 2016, 14:19 от ksv-uk » Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #10 : Сентябрь 06, 2016, 14:58 »

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

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
kambala
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4724



Просмотр профиля WWW
« Ответ #11 : Сентябрь 06, 2016, 15:15 »

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

Изучением C++ вымощена дорога в Qt.

UTF-8 has been around since 1993 and Unicode 2.0 since 1996; if you have created any 8-bit character content since 1996 in anything other than UTF-8, then I hate you. © Matt Gallagher
ksv-uk
Гость
« Ответ #12 : Сентябрь 06, 2016, 15:18 »

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

Сообщений: 1175


Просмотр профиля
« Ответ #13 : Сентябрь 06, 2016, 16:32 »

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

Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #14 : Сентябрь 06, 2016, 16:36 »

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

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


Страница сгенерирована за 0.084 секунд. Запросов: 22.