На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Нужен алгоритм распределения
    опробую задачу в придуманной реализации представить.

    Есть сущности.
    Множества, виды, как угодно.

    Например, несколько видов растений.
    Известны их количественные отношения друг к другу.
    Например, горох - 5 горстей, пшеница 10 горстей, кукуруза - 3 горсти и т.п.

    Нужно засеять поле в 20 ячеек.
    В каждую ячейку по одной горсти.
    И поле должно быть заполнено полностью.
    Но полей может быть больше одного.
    Почему?
    Потому что суммарное количество горстей всех видов обычно превышает 20.

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

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

    Как-то так...

    Нужно оптимально разложить тираж этикетки на листе (листах).
    На картинке.

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

    Количество каких-то этикеток может увеличиваться, но в пределах заданного пользователем (мной) % превышения.
    Если условия не выполняются - если этикеток много или их количества неудачные (одной намного больше другой или общее количество пропорций больше общего количества на листе), нужно добавлять еще лист, еще лист. Так сказать, разбивать на поднаборы.


    На входе, например:

    Вводим количество ячеек на листе.
    Вводим набор.
    этикетка1 - 2 шт, этикетка2 - 5 шт, этикетка3 - 12 шт, этикетка4 - 40 шт и т.д.
    Вводим % превышения (на сколько можно увеличить (при необходимости) некоторое количество этикеток на листах)

    Только штуки - это части. Сколько частей занимает каждый вид в общем наборе.

    На выходе:
    Лист 1: этикетка1 - 2 шт. этикетка2 - 5 шт, этикетка3 - 13 шт (значит, превышение, но в заданных пределах), этикетка4 - 6 шт..
    Лист 2 - этикетка4 - 30 шт, этикетка5 - ... и т.п.
    То есть, этикетки 4 намного больше других, поэтому часть пошла на Лист 1, другая часть на Лист 2.
    Увеличение листов крайне нежелательно.


    Что-то может упрощаться.
    Скажем, тиражи:
    13 т.
    27 т.
    27 т.
    72 т.
    На листе 20 шт.

    Размещаем:
    13 - 2 шт.
    27 - 4 шт.
    27 - 4 шт
    72 - 10 шт.
    Печатаем 7000 листов.
    И получаем нужное с небольшими превышениями.
    Сообщение отредактировано: egorus -

    Прикреплённая картинка
    Прикреплённая картинка
      Зело похоже на обычную задачу линейного раскроя. Ну или рюкзак без весовых коэффициентов. То, что лист абы двумерный, в данном случае не используется.

      Или речь о том, что ВСЕ листы должны иметь один и тот же макет? Или количество макетов может быть более 1, но ограничено? или ограничено минимальное количество листов одного макета? как вариант, следует максимизировать минимальное количество листов одного макета...

      Про поля с горстями - вообще не по делу.

      Добавлено
      Цитата egorus @
      Печатаем 7000 листов.
      И получаем нужное с небольшими превышениями.

      Хрен. Не допечатали 2000 этикеток нумер 4. Надо 7200 листов указанного раскроя.

      Excel - Поиск решения. Нашёл этот раскрой за доли секунды.

      Добавлено
      При допустимых 2 раскроях Excel за 3 минуты нашёл такое решение:

      Раскрой 1 - 1+4+4+11, количество 6548
      Раскрой 2 - 16+2+2+0, количество 404
      Всего: листов 6952, наклеек 13012+27000+27000+72028, лишних 40 штук.
        И что ето за Ексель? ;)

        Можете подробнее?
        Я в Экселе не ориентируюсь

        2. Я вам попозже реальную историю в картинках нарисую.
        Я понимаю, что тяжело вникнуть сразу в прикладную сторону.
        А теоретически - мне трудно правильно сформулировать.
        Я же не вы )
        Сообщение отредактировано: egorus -
          Вот, например.
          Слева направо.
          Виды этикеток
          Их требуемое количество.
          Эти количества, сокращены. Кратны 3800 (это сейчас неважно)
          Следующие два столбика - это как я разложил этикетки на печатных листах (формах, клише, штампах, полях ;) )
          То есть, три вида этикеток легли на печатный лист 1.
          И одна из них (В) перешла и на второй лист.
          А потом. Вверху - это сколько именно этих печатных листов нужно (6756 и 3800), чтобы порезав на отдельные этикетки, получить требуемые тиражи.
          Самый простой способ - печатать каждую этикетку на отдельном листе.
          В данном случае - это 7 комплектов.
          Но это нереально дорого.
          В реальности проще выкинуть (или попробовать продать 5000 лишних этикеток), но обойтись всего двумя комплектами печатных форм (листов, штампов, полей ;) )
          Прикреплённая картинка
          Прикреплённая картинка
          Сообщение отредактировано: egorus -
            egorus, давай я попробую задачу перефразировать чуль локаничнее?

            * есть набор этикеток разной геометрии и количества
            * есть листы, на которых этикетки нужно разместить

            Задача разместить этикетки так, чтобы использовать минимальное количество листов. В случае, если последний лист заполняется не полностью - смотреть баланс "использование листа" или "получение остатка неиспользованных этикеток"

            А правильно задачу понял?
              Формализуем задачу. Дано:

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

              На основании этих данных формируем целевую функцию. Например, это может быть сумма разностей между количеством этикеток, печатаемых в варианте, и потребным.

              В такой форме видно, что целевая функция линейна относительно любой отдельно взятой переменной. Следовательно, она элементарно оптимизируется на поиск минимума любым доступным методом. С учётом того, что область существования по одной переменной (ограничения на значения переменных и компонентов вычисления целевой функции) зависит от значений остальных переменных, считаю оптимальным (главным образом - наиболее простым в изучении и реализации) для поиска минимума метод покоординатного спуска (за исключением количества раскладок, для которого используется перебор от 1 в сторону увеличения до получения удовлетворяющего результата).

              Цитата egorus @
              Можете подробнее?
              Я в Экселе не ориентируюсь

              Встроенная справка Excel и Интернет содержат достаточно информации для изучения надстройки "Поиск решения". Я за Вас изучать её не намерен.
              Сообщение отредактировано: Akina -
                Akina, сдается мне что ТС решает обычную задачу раскроя, лишь с конечным постусловием "кроить ли последний лист" или "оставить наклейки". Ну или я что-то не так понял.
                  В "раскрое" каждый лист заполняется сам по себе. Есть у портного 100 кусков материала, и он их будет заполнять.
                  Может, у него каждый кусок выглядит по разному.
                  И ему все равно, потому что цена от этого не изменится.

                  А здесь (я поэтому и начал сочинять разные сказки про поля) изготавливается штамп (на котором собран набор этикеток).
                  Мы этим штампом отпечатаем мульен листов. И на каждом будет одинаковый набор.
                  НО все этикетки (НАБОР этикеток) никогда не влезают на один штамп.
                  Придется комбинировать и создавать два (три, четыре...).
                  А штампы стоят намного дороже. Ну что я повторяюсь.

                  Есть специализированные программы.
                  Но они работают только с одним листом.
                  Раскладывать на несколько они не умеют.

                  Вроде бы есть и такое, но стоит бешеных денег.
                  А я не владелец фирмы, а простой наемный рабочий, который сидит, и голову ломает постоянно.
                  Поэтому и спрашиваю - эти бешеные деньги оправданы?
                  Трудно написать программку раскладки, решаюшую такую задачу?
                  Только цифры.
                  Никакого GUI и пр.
                  Сообщение отредактировано: egorus -
                    Это так примерно выглядит описанная табличкой выше работа.
                    Сделано два штампа и ими печатаем тысячи листов, чтобы в итоге вышло требоемое количество.
                    (Правда, да втором наборе еще одна этикетка превышена (это для пытливых)).
                    Но это неважно. Я просто упрощаю, чтобы не рисовать по 100 этикеток на листе
                    Прикреплённая картинка
                    Прикреплённая картинка


                    Добавлено
                    Вот еще.
                    Первый.
                    Соотношение такое, что лучше все же разбить на два штампа.
                    Так как превышение тиража приличное. Если пытаться их делать на одном штампе.

                    Второе.
                    А здесь добавилась этикетка, а штамп только один.


                    Третье.
                    Количества вроде бы больше, чем помещается.
                    А штамп все равно один.
                    Прикреплённая картинка
                    Прикреплённая картинка
                    Сообщение отредактировано: egorus -
                      Цитата JoeUser @
                      сдается мне что ТС решает обычную задачу раскроя

                      Да, это самый обычный линейный раскрой. ОБ этом я ещё в самом начале говорил:
                      Цитата Akina @
                      Зело похоже на обычную задачу линейного раскроя. Ну или рюкзак без весовых коэффициентов. То, что лист абы двумерный, в данном случае не используется.

                      Или речь о том, что ВСЕ листы должны иметь один и тот же макет? Или количество макетов может быть более 1, но ограничено? или ограничено минимальное количество листов одного макета? как вариант, следует максимизировать минимальное количество листов одного макета...

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

                      Цитата egorus @
                      Следующие два столбика - это как я разложил этикетки на печатных листах

                      Всего 2 минуты ручного труда - и у меня есть вариант оптимальнее:

                      Раскрой 1: 3,0,5,2,6,3,1, количество 3800
                      Раскрой 2: 0,5,0,7,0,8,0, количество 6515
                      Избыток суммарный - 4900 этикеток (245 листов), что лучше показанного решения на 241 лист...
                        1 Я же сказал, что это только пример и я не совсем правильно указал реальные числа.
                        Поэтому точно-неточно - это не в данном случае.
                        2. Вы мне лучше скажите, как именно Вы трудились?
                        Цитата Akina @
                        Всего 2 минуты ручного труда
                        Сообщение отредактировано: egorus -
                          Цитата egorus @
                          как именно Вы трудились?

                          На лист бросаем исходные, ограничения, расчёты, критерий, потом просто подбираем значения. С помощью "поиска решения" или вручную.
                            То есть, никакого алгоритма (в узком смысле) нет?
                            Вручную - это как и я, лист бумаги, карандаш и калькулятор.
                            И перебор, что ли?
                              И еще раз - как же линейный раскрой& Я же привел самый последний пример. Когда можно вычленить кратные друг другу этикетки и составить из них набор. В линейном раскрое написано "20 штук" - он и будет делать 20 шт. Или нет?

                              Добавлено
                              Или намекните хотя бы - вы пользовались моим столбиком "Соотношения", или он не нужен для вычислений?

                              Я понимаю, что вы за меня и мороженое с пирожными будете есть, но если бы я понимал в этих раскроях, я бы сюда не писал.

                              И почему вообще эти соотношения нарисовались.
                              Это заказчик печатался в другом месте. Там на лист укладывалось 54 этикетки. Поэтому суммарный тираж / 54 = 3800. Наименьшая единица, вес или как ее еще назвать...
                              НО заказчику проще - он корректирует сам, как хочет, себя же, чтобы получить нужное количество.
                              А мне нельзя уже ничего менять.

                              А если будет 150 видов этикеток с весами от 1 до 150?
                              (Было у меня примерно и такое)
                              За какое время вы это разложите руками?
                              Сообщение отредактировано: egorus -
                                Открываем Excel. Убеждаемся, что надстройка "Поиск решения" подключена (если нет - F1, читаем и подключаем).

                                Составляем таблицу расчётов.

                                Руками вводим:
                                • Шапку
                                • Столбцы A и B
                                • Значения в ячейки C3:D9
                                Формулами вводим:
                                • C2=20-СУММ(C3:C8)
                                • аналогично D2
                                • E2=C2*$C$9+D2*$D$9-B2
                                • Аналогично E3:E8
                                • E9=СУММ(E2:E8)
                                При необходимости корректируем введённое руками так, чтобы ВСЕ числа были неотрицательны.

                                Формируем задание на поиск решения:
                                Цель: минимизация E9
                                Ограничения:
                                • C2:D9>=0
                                • E2:E8>=0
                                • C3:D9 целые
                                Прикреплённая картинка
                                Прикреплённая картинка

                                Запускаем поиск и идём пить чай...

                                На таком количестве параметров он будет пыхтеть достаточно долго. Можно пить чай и ждать окончания... а можно смотреть на текущее значение оптимизируемого параметра (параметр "Действующее" в строке статуса), и когда оно станет приемлемым и перестанет меняться - прервать поиск по Ctrl-Break и сохранить полученный результат.

                                Я прервал через 15 минут и получил решение:
                                Прикреплённая картинка
                                Прикреплённая картинка

                                Файл с финальным состоянием прилагается.

                                Цитата egorus @
                                А если будет 150 видов этикеток с весами от 1 до 150?

                                Оптимизация набора из более чем 20 этикеток не имеет смысла. Делите его на части и оптимизируйте из независимо.
                                Прикреплённый файлПрикреплённый файл____________.zip (6,45 Кбайт, скачиваний: 172)
                                Сообщение отредактировано: Akina -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,1498 ]   [ 23 queries used ]   [ Generated: 19.03.24, 02:04 GMT ]