Алгоритм симплекс-метода для решения задачи раскроя

19.10.23

Разработка - Математика и алгоритмы

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

Совместная работа с: Владимиром Батуриным

Алгоритм раскроя построенный на симплекс-методе
На работе столкнулся с интересной задачей, нужно написать алгоритм, который из заготовочной пленки раскроит заказы клиентов с минимальным остатком. Если говорить более понятным языком, то имеем большой кусок плёнки определенной ширины и длинный, который нужно порезать на какое-то количество маленьких кусков определенной шириной и длинной, в своей статье хочу продемонстрировать свой алгоритм и услышать стороннее мнение(замечание) по нему, так как вошел в профессию недавно. Рассматривать будем на простом примере, когда у нас есть один тип пленки и из параметров только длинна и ширина(в реальных условиях могут добавляться разные параметры).

Постановка задачи:

На производстве по изготовлению пленки разработать функционал по оптимальному раскрою.
На входе имеем остатки изготовленной пленки с разными параметрами: ширина и количество(в км). И потребности клиентов с параметрами: количество(в км) и ширина.
Подробно с задачей оптимального раскроя можно ознакомиться по ссылке: https://ru.wikipedia.org/wiki/Задача_раскроя.

Решение задачи:

При разработке алгоритма раскроя принято решение воспользоваться алгоритмом решения оптимизационной задачи линейного программирования "Симплекс-метод". Подробный разбор симплекс метода можно изучить по ссылке: https://habr.com/ru/articles/474286/.
Для начала нам нужно подвести нашу задачу к каноничной форме задачи линейного программирования, для этого нам нужно создать матрицу с картами раскроя(переменная "Канон") и массив с остатками плёнки(Переменная "МассивФункции") для каждой карты раскроя. Здесь вместо кода объясню общий принцип алгоритма. К примеру имеем 2 остатка пленки и 3 потребности. 


Составляем таблицу с вариантами карт раскроя(Так как при создании карт раскроя на каждом производстве свои отличия, вместо кода объясню принцип алгоритма). Для каждой пленки, из таблицы "Остатки пленки", нужно подобрать все вариации потребностей, при которых остаток для отхода не будет превышать ширину минимальной потребности.


На примере первых строчек таблицы объясню заполнение. Сначала берем первый остаток(в нашем случае 1200), и начиная с большей потребности заполняем карту раскроя. В ширину 1200 вмещается две потребности по 500, тем самым остается остаток 200(1200-500*2=200). Проверяем, можем ли мы вместить еще какую-нибудь потребность, 350 не подходит, так как эта потребность больше остатка, а вот 200 нам подходит, добавляем её в нашу карту и получаем остаток 0. Переходим к следующей карте, теперь берем только одну 500, записываем её во вторую строку, в остаток у нас выходит 700. Берем следующую потребность 350, такой потребности вмещается 2 шт. Записываем в таблицу и в остаток записываем 0. Для третьей карты оставляем потребность 500, а 350 берем на 1 меньше и получаем в остатке 350(1200-500-350=350). В данный остаток вмещается только одна 200. В итоге в 3 строчке у нас имеется каждая потребность по одной штуке и остаток в 150(1200-500-350-200=150). И так пока последняя карта раскроя не будет состоять только из последней потребности(В нашем случае 200). Повторяем такой алгоритм для каждого остатка пленки.

Первые пять колонок таблицы с вариантами карт раскроя являются в моём решении переменной "Канон" и представляет собой матрицу, а шестая колонка с остатками является переменной "МассивФункции" и представляет собой массив.

Далее формируем каноничную матрицу, для этого транспонируем матрицу с картами раскроя с некоторыми изменениями:

//Переменная "Базис" вводится для заполнения последней колонки Матрицы, она показывает базисный элемент в строке(Базисный элемент всегда равен 1).
Базис = Канон.Количество() + 1;
//В алгоритме будем пользоваться методом искусственного базиса, который подразумевает добавление дополнительных ограничений, и чтобы они не вошли в наше оптимальное решение, для каждого нового ограничения добавляем в Массив Функции дополнительные элементы с большим значением(В моём примере 1000), чтобы оптимальное решение включало в себя все потребности(Ограничение типа "=");
Для индекс = 1 По Объект.ПотребностьРаскроя.Количество() Цикл
    МассивФункции.Добавить(1000);
КонецЦикла;
//Так как Остатки не должны израсходоваться все, добавляем в Массив Функции дополнительные элементами со значением 0(Таким образом получаем ограничение для остатков типа "<=")  
Для Каждого Остатка Из ТЗОстатки Цикл
    МассивФункции.Добавить(0);
КонецЦикла;
//Формируем каноничную матрицу, в которой последняя колонка представляет собой базисные переменные(Номер строки карты раскроя из матрицы "Канон"), первая колонка представляет собой нужное количество определенной карты раскроя(на которую ссылается базис), для начального заполнения используем нужное количество потребностей(Для первой строки - количество первой потребности, для второй строки - количество второй потребности и так далее, как закончатся потребности заполняем количество Остатков)
//В последней строке матрицы Считаются дельты, начальным заполнением этой строки является Массив Функции, которую мы заполняли излишками от карт раскроя. Первое значение этой строки заполняется нулем(в дальнейшем при расчете это значение будет являться показателем целевой функции)
Для i = 0 По КолСтроки - 1 Цикл
    Если i = КолСтроки - 1 Тогда
        Матрица[i][0] = 0;
        Матрица[i][КолКолонки - 1] = 0;
        Для j = 1 По Канон.Количество() Цикл
            Матрица[i][j] = МассивФункции[j];
        КонецЦикла;
    Иначе
        Если i < Объект.ПотребностьРаскроя.Количество() Тогда
            Если Объект.ПотребностьРаскроя[i].ДлинаНамотки.ДлинаНамотки = 1000 Тогда
                Матрица[i][0] = Объект.ПотребностьРаскроя[i].Количество; //Было целое
            Иначе
                КоэфНамотки = Объект.ПотребностьРаскроя[i].ДлинаНамотки.ДлинаНамотки / 1000;
                Матрица[i][0] = Объект.ПотребностьРаскроя[i].Количество / КоэфНамотки; //Было целое
            КонецЕсли;
            Матрица[i][КолКолонки - 1] = Базис;
            Для j = 1 По Канон.Количество() Цикл
                Матрица[i][j] = Канон[j - 1][i];
            КонецЦикла;
        Иначе
            Матрица[i][0] = ТЗОстатки[i - КоличествоПотребностей].Количество; //Было целое
            Матрица[i][КолКолонки - 1] = Базис;
            Для j = 1 По Канон.Количество() Цикл
                Матрица[i][j] = Канон[j - 1][i];
            КонецЦикла;
        КонецЕсли;
    КонецЕсли;
    
    Для j = Канон.Количество() + 1 По КолКолонки - 2 Цикл
        Если j = Базис И i <> КолСтроки - 1 Тогда
            Матрица[i][j] = 1;
        Иначе
            Матрица[i][j] = 0;
        КонецЕсли;
    КонецЦикла;
    Базис = Базис + 1;
КонецЦикла;


Теперь у нас имеется готовая каноничная Матрица, каждая строка, кроме последней, является ограничением к каждой потребности и остатку. 1 строка является ограничением 1 потребности, 2 строка является ограничением 2 потребности, 3 строка является ограничением 3 потребности, 4 строка является ограничением 1 остатка и 5 строка является ограничением 2 остатка.Последняя строка заполнилась значениями из массива "МассивФункций", каждый элемент этой строки, начиная со второго, в симплекс-методе называется дельтой, а первый элемент показывает нам значение функции, с каждой итерацией симплекс-метода она должна уменьшаться, пока мы не найдем минимум функции.


Теперь можем приступать к алгоритму Симплекс-метода. Так как мы ищем оптимальные раскроя, нам нужен минимум функции, а значит у нас должны быть положительные ограничения и отрицательные дельты. Так как при формировании Матрицы у нас все ограничения получаются положительные, переходим к алгоритму, который проверяет дельты:

//Алгоритм будет работать пока все дельты не будут отрицательные, как только это случится, мы наёдем нужное решение
ЕстьПоложительныеЭлементы = Истина;
Пока ЕстьПоложительныеЭлементы Цикл
    //Создаем новую матрицу в которой будем производить расчеты
    Матрица2 = Новый Массив(КолСтроки, КолКолонки);
    СтолбецБазиса = Неопределено;
    СтрокаБазиса = 0;
    СтрокаНайдена = Ложь;
    //Среди элементов нижней строки матрицы выбираем максимальный положительный элемент . Столбец, в котором будет этот элемент объявляем ведущим (разрешающим).
    Для j = 1 По КолКолонки - 2 Цикл
        Если Окр(Матрица[КолСтроки - 1][j], 5) > 0 Тогда
            МаксимальныйБазис = Матрица[КолСтроки - 1][j];
            СтолбецБазиса = j;
            Прервать;
        КонецЕсли;
    КонецЦикла;
    Если НЕ СтолбецБазиса = Неопределено Тогда
        Для j = СтолбецБазиса + 1 По КолКолонки - 2 Цикл
            Если Окр(Матрица[КолСтроки - 1][j], 5) > Окр(МаксимальныйБазис) Тогда
                МаксимальныйБазис = Матрица[КолСтроки - 1][j];
                СтолбецБазиса = j;
            КонецЕсли;
        КонецЦикла;
    КонецЕсли;
    //Если Положительных элементов не оказалось, завершаем алгоритм
    Если СтолбецБазиса = Неопределено Тогда
        Прервать;
    КонецЕсли;
    //После того, как нашли максимальный положительный элемент, в этом столбце выбираем элемент, который будем превращать в базис
    //Левый столбец почленно делится на ведущий столбец(который мы выбрали в прошлом шаге)
    //Среди полученных значений выбирают минимальное положительное (отрицательные и нулевые ответы не рассматривают)
    МинимальныйБазис = 0.001;
    Для i = 0 По КолСтроки - 2 Цикл
        Если Матрица[i][СтолбецБазиса] > 0 Тогда
            Если СтрокаНайдена Тогда
                Если Матрица[СтрокаБазиса][0] / МинимальныйБазис > Матрица[i][0] / Матрица[i][СтолбецБазиса]
                    И Матрица[i][0] / Матрица[i][СтолбецБазиса] > 0 Тогда
                    МинимальныйБазис = Матрица[i][СтолбецБазиса];
                    СтрокаБазиса = i;
                КонецЕсли;
            Иначе
                Если 1 / МинимальныйБазис > Матрица[i][0] / Матрица[i][СтолбецБазиса]
                    И Матрица[i][0] / Матрица[i][СтолбецБазиса] > 0 Тогда
                    МинимальныйБазис = Матрица[i][СтолбецБазиса];
                    СтрокаБазиса = i;
                    СтрокаНайдена = Истина;
                КонецЕсли;
            КонецЕсли;
        КонецЕсли;
    КонецЦикла;
    //Если при расчетах мы не нашли удовлетворяющий нам вариант, прекращаем алгоритм, так как решения нет
    Если СтрокаНайдена = Ложь Тогда
        Сообщить("С текущими входными данными оптимального решения нет!");
        РешениеЕсть = Ложь;
        Прервать;
    КонецЕсли;
    //Если мы нашли подходящую строку, объявляем ведущий элемент, который будем превращать в базис.
    ВедущийЭлемент = Матрица[СтрокаБазиса][СтолбецБазиса];
    //Всю строку делим на ведущий элемент, чтобы получить единицу
    Для j = 0 По КолКолонки - 2 Цикл
        Матрица2[СтрокаБазиса][j] = Окр(Матрица[СтрокаБазиса][j] / ВедущийЭлемент, 10);
    КонецЦикла;
    //Далее каждую строку нужно перерассчитать по формуле: ЭлементСтроки[n] - ЭлементСтроки[СтолбецБазиса] * ЭлементБазиснойСтроки[n] 
    Переменная2 = Матрица2[СтрокаБазиса];
    Для i = 0 По КолСтроки - 2 Цикл
        Переменная = Матрица[i][СтолбецБазиса];
        Переменная3 = Матрица[i];
        Если i = СтрокаБазиса Тогда
            Продолжить;
        Иначе
            Для j = 0 По КолКолонки - 2 Цикл
                Матрица2[i][j] = Окр(Переменная3[j] - Переменная * Переменная2[j], 10);
            КонецЦикла;
            Матрица2[i][КолКолонки - 1] = Матрица[i][КолКолонки - 1];
        КонецЕсли;
    КонецЦикла;
    //Приравниваем последнему элементу в базисной строке индекс базисной переменной 
    Матрица2[СтрокаБазиса][КолКолонки - 1] = СтолбецБазиса;
    Выгружаем наши расчеты в основную матрицу
    сз = Новый СписокЗначений;
    сз.ЗагрузитьЗначения(Матрица2);
    Матрица = сз.ВыгрузитьЗначения();
    //перерасчет дельт 
    Для j = 0 По МассивФункции.Количество() - 1 Цикл
        Элемент = Матрица[0][КолКолонки - 1];
        Переменная = МассивФункции[Элемент] * Матрица[0][j];
        Для i = 1 По КолСтроки - 2 Цикл
            Элемент = Матрица[i][КолКолонки - 1];
            Переменная = Переменная + МассивФункции[Элемент] * Матрица[i][j];
        КонецЦикла;
        Матрица[КолСтроки - 1][j] = Окр(Переменная - МассивФункции[j], 1);;
    КонецЦикла;
    //после каждой итерации проверяем план на оптимальность, то-есть смотрим, чтобы не было отрицательных ограничений
    ПроверкаНаПоложительныеОграничения(Матрица, КолСтроки, КолКолонки, МассивФункции, Канон);
КонецЦикла;


В процедуре ПроверкаНаПоложительныеОграничения() проверяем, чтобы в первой колонке матрицы не было отрицательных элементов, если такие элементы присутствуют перерассчитываем матрицу

    

//Переменная ПроверкаДельт нужна для проверки условия, если мы не нашли отрицательные элементы в колонке, то и пересчет дельт не нужен
ПроверкаДельт = Ложь;
Пока ЕстьОтрицательныеЭлементы Цикл
    Матрица2 = Новый Массив(КолСтроки, КолКолонки);
    МинимальныйБазис1 = Матрица[0][0];
    СтрокаБазиса = 0;
    СтолбецБазиса = 1;
    //Циклом находим минимальный элемент в первой колонке
    Для i = 1 По КолСтроки - 2 Цикл
        Если МинимальныйБазис1 > Матрица[i][0] Тогда
            МинимальныйБазис1 = Матрица[i][0];
            СтрокаБазиса = i;
        КонецЕсли
    КонецЦикла;
    //Если минимальный элемент положительны, прекращаем вычисления и возвращаемся к поиску положительных дельт
    Если МинимальныйБазис1 >= 0 Тогда
        Прервать;
    КонецЕсли;
    ПроверкаДельт = Истина;
    //Если находим отрицательный элемент, проводим расчёты, для этого ищем подходящий минимальный элемент в найденной строке
    МинимальныйБазис2 = Матрица[СтрокаБазиса][1];
    Для j = 2 По КолКолонки - 2 Цикл
        Если МинимальныйБазис2 > Матрица[СтрокаБазиса][j] Тогда
            МинимальныйБазис2 = Матрица[СтрокаБазиса][j];
            СтолбецБазиса = j;
        КонецЕсли;
    КонецЦикла;
    //Как только находим нужный элемент, фиксируем его в переменной, и объявляем ведущим(Делаем из него базисный элемент)
    ВедущийЭлемент = Матрица[СтрокаБазиса][СтолбецБазиса];
    //Проводим такие-же вычисления как и в алгоритме по поиску положительных дельт
    Для j = 0 По КолКолонки - 2 Цикл
        Матрица2[СтрокаБазиса][j] = Окр(Матрица[СтрокаБазиса][j] / ВедущийЭлемент, 10);
    КонецЦикла;
    Для i = 0 По КолСтроки - 2 Цикл
        Переменная = Матрица[i][СтолбецБазиса];
        Если i = СтрокаБазиса Тогда
            Продолжить;
        Иначе
            Для j = 0 По КолКолонки - 2 Цикл
                Матрица2[i][j] = Окр(Матрица[i][j] - Переменная * Матрица2[СтрокаБазиса][j], 10);
            КонецЦикла;
            Матрица2[i][КолКолонки - 1] = Матрица[i][КолКолонки - 1];
        КонецЕсли;
    КонецЦикла;
    
    Матрица2[СтрокаБазиса][КолКолонки - 1] = СтолбецБазиса;
    сз = Новый СписокЗначений;
    сз.ЗагрузитьЗначения(Матрица2);
    Матрица = сз.ВыгрузитьЗначения();
КонецЦикла;
Если ПроверкаДельт = Истина Тогда
    //перерасчет дельт 
    Для j = 0 По МассивФункции.Количество() - 1 Цикл
        Элемент = Матрица[0][КолКолонки - 1];
        Переменная = МассивФункции[Элемент] * Матрица[0][j];
        Для i = 1 По КолСтроки - 2 Цикл
            Элемент = Матрица[i][КолКолонки - 1];
            Переменная = Переменная + МассивФункции[Элемент] * Матрица[i][j];
        КонецЦикла;
        Матрица[КолСтроки - 1][j] = Окр(Переменная - МассивФункции[j], 1);
    КонецЦикла;
КонецЕсли;

Как только в матрице все дельты станут отрицательные, а ограничения положительные, значит алгоритм нашёл решение, но оно является нецелочисленным.

В последней колонке представлены номера карт раскроя, например в первой строке видим значение 1, значит это первая карта раскроя(0 индекс в массиве Канон), а в первой колонке представлено количество этих карт. На примере первой строки, получается, что нам нужно 1,25 первой карты раскроя. Также можем видеть, что в последней колонке есть значения 18 и 19, которые не входят в границы массива "Канон". Такие строки не учитываются в конечном решении. 

Для преобразования решения в целочисленное, используем упрощённый вариант алгоритма округления:

    

Для Каждого СтрокаМатрицы Из Матрица Цикл
    СтрокаМатрицы[0] = Окр(СтрокаМатрицы[0]);
КонецЦикла;

В итоге получаем 1 шт. первой карты раскроя, 8 шт. второй и 5 шт. восьмой

Симплекс-метод линейное программирование задача раскроя оптимальный раскрой.

См. также

Математика и алгоритмы Программист Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    3687    stopa85    12    

38

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    3620    maksa2005    8    

26

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    11373    8    SpaceOfMyHead    19    

61

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    4866    RustIG    9    

25

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022    4015    gzharkoj    14    

25

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    9140    7    kalyaka    11    

44
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. RustIG 1752 19.10.23 16:23 Сейчас в теме
(0) допустим одномоментно на утро есть остатки и есть потребности, к обеду подвезли еще рулоны, +упали менеджерам новые заказы - и на момент обеда остатки и потребности изменились.
Оптимальное решение на утро вовсе не равно оптимальному решению, рассчитанному в обед.
При этом будем считать что между утром и обедом никаких решений по резке рулонов не принималось, скажем так резать начнем ночью.
А вот еще: допустим утром все-таки порезали, в обед снова рассчитали оптимальное решение - но оно может быть хуже (сложим Оптимальное решение утром и в обед), чем если бы мы утром не резали и отложили расчет на обед...
pisarevEV; +1 Ответить
2. user1959478 36 19.10.23 17:10 Сейчас в теме
(1) Немного не понимаю, что Вы хотите сказать этим сообщением? Если Вы о том, как именно использовать данный алгоритм в работе какой-либо компании, то это уже совсем другой вопрос. Целью данной статьи является показать функционал раскроя пленки.
3. RustIG 1752 19.10.23 17:15 Сейчас в теме
(2) почему на глаз не режите рулоны? зачем все эти матрицы и симплекс-метод?
что такое симплекс-метод вы понимаете? или просто взяли с хабра алгоритм и перевели в 1с-синтаксис?
pisarevEV; +1 Ответить
4. user1959478 36 19.10.23 17:35 Сейчас в теме
(3) Понимание, что такое симплекс-метод есть. Условно у нас есть какое-то количество изготовленной пленки с определенными параметрами и есть какое-то количество заказов пленки, конечно можно попытаться попробовать раскроить "На глаз", но когда количество остатков и потребностей повышается, нужен какой-то функционал, который покажет как можно раскроить, чтобы отходов было на минимум. Первой мыслью конечно же приходит полный перебор, но это слишком долго и не всегда хватит памяти. Вот на помощь и приходит симплекс-метод. А задачу раскроя как раз можно решать линейным программированием, главное правильно привести к канонической форме. А в вопросе о том, как её использовать, уже виднее пользователю, который знает что ему нужно раскроить и в какой срок.
8. RustIG 1752 19.10.23 19:13 Сейчас в теме
(4)вотпишите, что пользователь сам знает. А вы только алгоритм выложили. Как пользователь с этим будет работать?
12. user1959478 36 19.10.23 21:27 Сейчас в теме
(8) По объективным причинам не могу выкладывать скрины из рабочей базы, но на славах могу объяснить, что есть обработка, в которую запросом поступают остатки пленки и потребности с разными параметрами, после пользователь выбирает какая пленка попадет в алгоритм. После запуска алгоритм начинают генерироваться возможные варианты раскроя(так называемые "карты раскроя"), и вот когда все подходящие карты раскроя готовы, по ним создаются ограничения и после этого начинается сам алгоритм симплекс метода. Так как в программировании я новичек, хотелось услышать критики именно в части кода, ну и конечно самой реализация симплекс-метода. Также стоит понимать что реализован не весь функционал этого метода, так как в данной ситуации алгоритм ищет именно минимальный экстремум.
13. RustIG 1752 19.10.23 22:33 Сейчас в теме
5. ogre2007 302 19.10.23 17:42 Сейчас в теме
(3)Коллега, вы умеете эффективно решать NP-полные задачи "на глаз" ? Здесь пишется о реальном опыте применения симплекс метода в 1С для практической задачи. Опубликовали для получения конструктивной критики, надеюсь она будет.
SedovSU@mail.ru; +1 Ответить
7. RustIG 1752 19.10.23 19:05 Сейчас в теме
(5)про нарезку на глаз - это был наводящий вопрос, для понимания насколько осведомлен автор. Раз вы поделились реальным опытом, дополните, пожалуйста, сколько месяцев уже используете данный подход? Какие интерфейсные формы реализовали? Как это выглядит в 1с? Какие подводные камни обнаружили? Сколько у вас видов рулонов, и как следствие остатков? Сколько в день заказов? Как часто делаете пересчет обрезки? Кто делает расчет? При каких входных данных модель перестанет быстро считать? Пока не могу дать конструктивную критику: не было подобного опыта, а обсуждать представленный алгоритм в теории очень сложно - тестить надо на разных данных.
52. smazovets 22.11.24 16:00 Сейчас в теме
Хотел примнить это к своей задаче, но тут не полный код выложен, не понятно что за переменные: КолСтроки, КолКолонки, КоличествоПотребностей
(2)
6. RustIG 1752 19.10.23 18:55 Сейчас в теме
(4)если вы не поняли мой первый вопрос, значит как-то поверхностно понимаете , почему именно симплекс метод используется, у него свои ограничения. Поэтому задал второй уточняющий вопрос, чтобы понимать насколько глубоко и широко это обсуждать с вами.
28. ВикторП 350 23.10.23 10:03 Сейчас в теме
(6) Какие ограничения у симплекс- метода?
29. RustIG 1752 23.10.23 11:51 Сейчас в теме
(28)
Жадный алгоритм весьма быстр, позволяет найти некоторое приемлемое решение за котороткое время, но при этом часто не дает идеального результата

взято отсюда https://infostart.ru/marketplace/1421562/
31. ВикторП 350 23.10.23 23:19 Сейчас в теме
(29) Это не симплекс - метод, там же написано- метод Монте-Карло
38. RustIG 1752 24.10.23 11:01 Сейчас в теме
(31) может вы и правы, возможно я не корректно связал задачу раскроя - приводимую к задаче о рюкзаке, последнюю решают или с помощью жадного алгоритма, или с помощью динам. программирования. Почему -то я решил что жадный алгоритм - это как раз через симплекс-метод. Наверное, не прав.

Из описания википедии по задаче раскроя вообще много чего вытекает, в том числе ограничения, допущениясамой постановки задачи. Сам по себе симплекс-метод имеет ряд ограничений чисто технического характера - не всегда приводит к решению или к единственному решению. Применительно к задаче раскроя модель надо строить с допущениями. В статье из википедии вообще сказано, что дробное решение нельзя округлять
"Исходный метод Гилмора и Гомори не был целочисленным, так что решение могло содержать дробные составляющие, например, некоторая карта должна была использоваться 3,67 раз. Округление до ближайшего целого часто не работает, в том смысле, что это приводит к подоптимальному решению и недопроизводству или перепроизводству для некоторых заказов (и возможное нарушение ограничений, если они двусторонние). Этот недостаток преодолён в новых алгоритмах, которые позволяют находить оптимальные решения (в смысле нахождения решения с минимальными отходами) очень больших задач (в общем случае больших, чем нужно на практике[4][5])".
9. pisarevEV 8 19.10.23 19:50 Сейчас в теме
15 лет работаю с производственниками средней руки... пришел к твердой уверенности что подобные алгоритмы в реальной жизни не только не нужны но и вредны. Более менее опытный мастер на производстве сделает быстрее и лучше, а если ему еще и платить достойно...
10. Brawler 458 19.10.23 20:36 Сейчас в теме
(9) Оправдать можно все что угодно и полное отсутствие квалификации у пользователей 1С тоже, и вы этим и занимаетесь. Практика показывает, что люди не то что 1С пользоваться не хотят так и учиться по профилю не хотят, все по наитию делать пытаются и далеко не самым эффективным способом.
Global__IT; Sashares; +2 Ответить
11. RustIG 1752 19.10.23 20:52 Сейчас в теме
Я не придираюсь, просто интересна тема, а там где интересно, всегда много вопросов...

Тут вот публикация есть Раскрой двумерного материала
Для информации указал.

Всем добра!
15. starik-2005 3092 20.10.23 11:10 Сейчас в теме
(9)
Пришел к твердой уверенности что подобные алгоритмы в реальной жизни не только не нужны но и вредны. Более менее опытный мастер на производстве сделает быстрее и лучше, а если ему еще и платить достойно.
Я как-то писал про то, как мастер "на глаз" делал так, что постоянно приходилось добирать. Почему он так делал? Так ему мотивацию на количество деталей сделали, а не на количество остатков (отходов). Вот он и решал все методом минимального количества телодвижений: сначала пилил то, что было наиболее массовым, чтобы как можно меньше перенастраивать станок.
И если у вас на производстве мастеру платят за количество, а не за отходы, и бизнесу важнее скорость, то все ок. Если же для бизнеса скорость менее важна, чем отходы, то ой... Все зависит от стоимости работы в стоимости готовой продукции. Если материал строит 90%, а работа 10%, то я за такой бизнес с таким крутым мастером и гроша ломаного не дам )))
moralex2k; alexey-simf; Cерый; Sashares; Созинов; +5 Ответить
14. van_za 269 20.10.23 10:37 Сейчас в теме
16. pisarevEV 8 20.10.23 12:31 Сейчас в теме
(15) как оценить эффективность мастера это ответственность руководителя, сказанное мною относится к грамотным руководителям и мастерам, в противном случае никакие "алгоритмы" не помогут.... не надо забивать гвозди микроскопом если это малый и средний бизнес
17. pisarevEV 8 20.10.23 12:32 Сейчас в теме
сам по себе алгоритм не сомневаюсь красив, но это просто игрушку на радость его создателя
18. roman72 390 20.10.23 13:00 Сейчас в теме
Люблю симплекс-метод и СЛУ.
Они могут дать большой экономический эффект на имеющихся производственных ресурсах без необходимости крупных инвестиций в эти ресурсы.
Но, в вашем примере мне кажется применение симплекс-метода неоправданно сложно для простой задачи.
Тем более, задача целочисленная (должна иметь целочисленное решение), а вы реализовали приближённое решение.
Я так понимаю, в итоге вы из матрицы нецелочисленных решений пытаетесь сделать целочисленные решения путём банального отсечения дробных частей.
Это неправильное применение симплекс-метода.
Здесь возможна выдача неоптимальных решений под видом оптимальных.
По той причине, что проверить ваше решение некому.
Производственник не будет заморачиваться, а пилить контрольный алгоритм симплекс-метода с целочисленными решениями дабы проверить часто ли ошибатся ваш метод никто не будет.
Поэтому, как описали в комментариях выше, часто производственники отвергают такие алгоритмы и говорят что "на глазок" они лучше сделают раскрой или расчёт производственной программы.
Orlando Skibraves; AP_ROSTOV; +2 Ответить
19. user1959478 36 20.10.23 13:17 Сейчас в теме
(18)Не могу с Вами не согласиться, данный алгоритм является "простым" и только основой для доработок. Доделать функционал до целочисленного решения присутствует в целях. Создавая данный алгоритм изначально шло понимание, что нужно целочисленное решение, в попытках его реализовать наткнулся на метод Гомори, но по итогу осознал,что это не лучшая идея, так как такой алгоритм при достаточно больших входных данных может искать решение очень долго. В итоге было принято решение доработать упращенный вариант, который показывает хороший результат и не занимает много времени. На данный момент изучаю метод границ и ветвей, который в свою очередь с каждой итерацией приближает к лучшему решению
20. RustIG 1752 20.10.23 14:05 Сейчас в теме
(18)
Я так понимаю, в итоге вы из матрицы нецелочисленных решений пытаетесь сделать целочисленные решения путём банального отсечения дробных частей.
Это неправильное применение симплекс-метода.

вот это очень верное замечание - куда будет двигаться градиент при округлении результата не известно - может уйти в крайне не оптимальное положение.
Есть еще мысль, что для больших размеров потребностей сразу можно отсекать рулоны неподходящих меньших размеров : и может статься так, что для очередного заказа не надо делать расчет - и так понятно, что для заказа большого размера подойдет только один рулон - который самый большой. А если так далее по такому рассуждению по цепочке следующих заказов пойти?
22. user1959478 36 20.10.23 15:33 Сейчас в теме
(20) Вообще, я считаю, что лучше пренебрегать вариантами, когда человек сам решает что он сам раскроит, а что раскроит механизм. Конечно у меня еще в этом вопросе маловато опыта, но когда у меня появилась задача сделать механизм раскроя в 1С, конечно же сначала я начал с простых алгоритмов приближенных к полному перебору(Ну а кто не ошибался), и вот тут как-раз и возникла проблема, алгоритм находил лучший вариант карты раскроя, высчитывал нужное количество из остатков и потребностей, потом из того, что осталось опять искал лучшую карту раскроя и так по кругу, и понятное дело, что в конечном исходе оставались потребности, которые плохо друг другу подходят. И вот исходя из этого примера, можно сделать вывод, что даже если ты нашёл подходящий вариант раскроя для отдельных потребностей и остатков, это не значит, что в общем итоге будут хорошие варианты. Уж лучше довериться алгоритму, в котором все карты раскроя зависят друг от друга.
25. roman72 390 20.10.23 23:37 Сейчас в теме
(20) У меня тут сразу вопросы возникли:
а) имеет ли значение толщина кроя
б) где ограничения на общий размер раскраиваемого листа, если крой в аппарате, а не человеком
в) какая разница в остатках негодного по размерам материала при ручной работе и после работы по СЛУ
И как это в уравнениях учли.
И общее ощущение что можно было сделать проще, без СЛУ.
34. AP_ROSTOV 24.10.23 09:23 Сейчас в теме
(25)
а) Да, имеет, грубо говоря на рез закладывается Х мм. Константа, особенность оборудования, на котором происходит раскрой.
б) Ограничений ещё 100500, просто они весьма специфичны. Хотелось опубликовать универсальную часть алгоритма. Например, есть нюанс, что может резаться плоская пленка, а может рукав. В статье задача решается по ширине пленки, в реальности она ещё решается по длине. Там тоже много нюансов, например ручьи нарезки не должны делать ступенек в карте раскроя.
в) По иронии судьбы мы меряемся эффективностью не с человеком а с Excel где реализована работа с библиотекой lpsolve55. И пока что мы только приблизились к нему по эффективности, но не превзошли. При ручной работе это недостижимый результат. Даже при малых входных таблицах 10 на 10 там вариантов раскроя более 1млн.

По поводу, что можно проще. У меня возникает аналогия с теоремой Ферма, тоже простовато выглядит.
37. RustIG 1752 24.10.23 10:51 Сейчас в теме
(25)
имеет ли значение толщина кроя
имеет конечно, но не в этой задаче - в статье есть две ссылки + в самой статье - если все прочитать, то станет многое ясно...
21. PowerBoy 3419 20.10.23 14:29 Сейчас в теме
Не пробовали рассчитать платформенным механизмом (РасчетСистемЛинейныхУравнений)?
user1959478; +1 Ответить
23. user1959478 36 20.10.23 15:37 Сейчас в теме
(21) Не слышал о таком, но спасибо за информацию.
24. roman72 390 20.10.23 23:32 Сейчас в теме
(21) Там разве не просто СЛУ решается? Это не для симплекс метода же.
36. RustIG 1752 24.10.23 10:49 Сейчас в теме
(24) верно замечено.
Видимо нужно совместно использовать решение СЛУ + анализ целевой функции на экстремум
42. roman72 390 24.10.23 14:20 Сейчас в теме
(37)
(36) Правда, в голый СЛУ-механизм без целевой функции (те без симплекс-метода) можно таки погрузить саму целевую функцию...
26. van_za 269 21.10.23 06:25 Сейчас в теме
Программист user1959478 проделал исследовательскую работу, сделал некий экспериментальный код, в наших 1с системах вообще не затрагивается тема оптимизации, а на производстве это очень важная тема... давайте приветствовать всяческие начинания в этом направлении, и всячески респектовать... тогда 1с будет не только бухгалтерия, а инструмент оптимизации и экономии не только в громких заголовках проектов.
mikmaster; Orlando Skibraves; AP_ROSTOV; fancy; user1959478; EzeskyAndrew; +6 Ответить
27. stopa85 42 21.10.23 17:44 Сейчас в теме
Эх, я когда-то решал задачу VPR...(Дано центральный склад товаров, автопарк, множество заявок на доставку товара. Нужно найти оптимальный план доставки товаров учитывая временные ограничения на продолжительность марштрута, окно ожидания клиента, грузоподъемность автомобиля)

Отличный диплом написал. Уровня диссертации провинциального ВУЗа. Ох, много там было математики... А еще я был красноглазым. Linux, Vim, C++, QT, doxygen, emegre live и т.п.

Начал с генетических алгоритмов, а закончил методом генерации столбца (один из способов решения задачи линейного программирования) и методом ветвей и границ... Эх, мог человеком стать, математиком. А стал 1С-негом.

P.S. У меня ничего с тех пор не сохранилось, но интернет помнит "все", где мы тогда это обсуждали
Прикрепленные файлы:
30. RustIG 1752 23.10.23 17:22 Сейчас в теме
Программное обеспечение для решения задач раскроя для бумажной промышленности поставляют ABB Group, Greycon, Honeywell и Tieto.

Взято из википедии.
И ни слова про 1с и разработки наших спецов.
32. fancy 35 24.10.23 07:45 Сейчас в теме
В итоге получается что из 1+8+5 полос шириной 1200 выйдет 10х500, 16х350 и 31х200. Лишние два куска остается?
33. user1959478 36 24.10.23 09:22 Сейчас в теме
(32) Да, в данном случае из-за простого округления
35. RustIG 1752 24.10.23 10:48 Сейчас в теме
(32) целевая функция, видели, какая?
не минимизировать остатки, а чтобы остатки были не более минимальной потребности
39. user1959478 36 24.10.23 11:19 Сейчас в теме
(35) Остатки не более минимальной потребности, это для карт раскроя, чтобы в решении не было карт с большим излишком. Сам симплекс метод считает вровень(Так как ограничения преимущественней к типу "="). Из-за того, что пока он округляется простым способом, получаются лишние, или недорезанные потребности. Но как получится реализовать более сложный вариант целочисленного решения, после нецелочисленного симплекс-метода алгоритм по определенным правила будет добавлять некие ограничения, которые будут постепенно избавляться от дробных частей. И после этого в решении потребности будут уходить в 0.
40. RustIG 1752 24.10.23 14:00 Сейчас в теме
(39) по хорошему вам бы написать здесь какую систему неравенств вы решаете в примере и целевую функцию.
иначе ваш алгоритм тестировать не получится - в идеале те, кто будет проверять ваш алгоритм, должны прийти к такому же решению, что и у вас. Тестирование начинается собственно с бумаги. Я вот например не вижу изначальную задачу, и не могу проверить ваш результат даже на бумаге.
После совпадения, можно уже проверять техническую часть алгоритма.
41. user1959478 36 24.10.23 14:05 Сейчас в теме
(40)Думаю это верное замечание. В статье приведены только входные данные и сама реализация. Хорошо бы добавить промежуточный итог в виде системы неравенств после образования карт раскроя. Просмотрю этот момент.
44. roman72 390 24.10.23 14:25 Сейчас в теме
(40) Что дст показ системы неравенств и целевой функции - если для проверки качества решения придётся сделать целочисленное решение поставленной задачи?
Те проверка решает саму задачу...
45. RustIG 1752 24.10.23 14:58 Сейчас в теме
(44) у меня нет целочисленного алгоритма. я хотел бы для начала проверить то, что представлено в публикации.
одно дело я буду вариться в собственном соку - изучая симплекс-метод, другое дело здесь с автором обсудить одну задачу.
43. roman72 390 24.10.23 14:23 Сейчас в теме
(39) Симплекс-метод (а точнее метод Гаусса в СЛУ) как раз решает неравенства.
А ограничения по типу "=" в реальной жизни так вообще меньшую часть составляют при решении экономических задач, при описании предметной области.
46. user1959478 36 24.10.23 15:05 Сейчас в теме
(43) На предприятии преимущество отдается количеству производимого материала, в плане того, что если мы поставим ограничения ">=" Или "<=", да, мы можем получить лучший лучший вариант с точки зрения экстремума функции, но по заказам будет существенное отличие от того, что нам нужно. Конечно мой алгоритм не строго для "=", но преимущественней.
47. roman72 390 24.10.23 19:30 Сейчас в теме
(45)
(46) Что-то здесь не так.
Алгоритм СЛУ никак не зависит от вида условия = или <
Просто у вас условие "заказ" не включено в систему уравнений.
48. RustIG 1752 24.10.23 21:15 Сейчас в теме
(47) Собственно я не увидел "условия" задачи - а именно какие уравнения составлены и какая связь между остатками и потребностями. Скажем так, того, что описано в публикации, мне лично не достаточно, чтобы понять это.

Дополнительно прочитав описание "задачи раскроя" в википедии , я понял что эта тема обширна. И на каждом производстве ставится "ровно своя" задача, а не "общая со всеми вытекающими" - составляется система неравенств - и способы решения тоже разные применяются - при этом каждый способ обосновывается. Здесь же нет обоснования - просто приняли на веру, что давайте решать "симплекс-методом". Да, а почему бы и нет - ведь это же способ решения СЛАУ.

только нам не показали эти СЛАУ.
49. RustIG 1752 27.11.23 13:31 Сейчас в теме
50. user1013372 25.02.24 09:41 Сейчас в теме
Добрый день, тоже захотел попробовать решить такую задачу, на сколько верно две заготовки (1200 и 1000) в одну матрицу решения вставлять? В ответе получилось, нужно использовать только заготовку 1200, но в идеале нужно сначала израсходовать все остатки от прошлых производств, те 1000 заготовку, а потом уже переходить к 1200.
51. Pavel_08 19.11.24 13:52 Сейчас в теме
Добрый день! Спасибо за алгоритм! Очень полезная статья! Не понял только, что за 1000 мы добавили в массив функций в качестве дополнительных ограничений. Почему 1000?
Спасибо!
Оставьте свое сообщение