|
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 342
|
|
| 1 | |
Задача на минимизацию остатков03.11.2018, 12:18. Показов 2669. Ответов 10
Метки нет (Все метки)
Есть задача и я не знаю как верно составить алгоритм для ее решения. Подскажите какие-нибудь идеи, пожалуйста  В компании по производству стальных труб есть набор базовых элементов с длиной 11800см, которые можно разрезать и использовать для сварки. Поступил заказ на Nое количество труб с разными длинами. Каждая такая труба может состоять из нескольких блоков, но блок должен быть не менее 1100см. Задача определить оптимальное деление базовых элементов, чтобы составить все трубы с минимальным количеством обрезков. Пример: Требуется сделать трубы с длинами: 1) 11000 2) 15000 3) 9000 Общая необходимая длина = 11т + 15т +9т =35т 35000 / 11800 = 2.966. Значит, что мне достаточно взять 3 базовых элемента. В идеальном случае минимальный остаток будет: (3-2.966)*11800 = 400 Вопрос: Какие деления базовых элементов делать и как их разделять по трубам, чтобы максимально приблизится к идеальному остатку? Если на трубу1 я беру 11000, то остается 800. 800 < 1100, поэтому я не могу брать его в дальнейшее использование и 800 сразу идет в обрезки. Значит такое деление уже не оптимально! Делаем так: нб - взяли новый блок ос - взяли из остатков 1) 9900 (нб) + 1100 (нб) = 11000 (в остатках 1900 и 10700) 2) 10700 (ос) + 4300 (нт) = 15000 (в остатках 1900 и 7500) 3) 7500 (ос) + 1500 (1900 порезали на 1500 и 400) = 9000 (в остатках 400) То есть мы получили лучшее решение. Нужен алгоритм на любом языке программирования или в экселе, чтобы найти вот такие деления и остаток. Подскажите, как это можно сделать?
0
|
|
( Лучшие ответы (1)
| 03.11.2018, 12:18 | |
|
Ответы с готовыми решениями:
10
Задача на минимизацию негладкой функции Задача на арифметику остатков
Нахождение суммы остатков (задача с Codeforces) |
|
|
| 03.11.2018, 15:24 | 2 |
|
offtopic: 11800 -- это все-таки миллиметры... Ну сами представьте себе трубу длиной 118 метров...
Судя по всему, это задача на многокритериальную оптимизацию. И для начала нужно эти критерии четко определить. Потому что к примеру минимум обрезков - это одно, а минимальная суммарная длина обрезков - уже другое. Вы же как-то очень постепенно излагаете условия задачи... Сперва у вас есть только базовые трубы, потом вдруг обнаруживается склад с остатками... Есть подозрение, что дальше еще возникнет условие минимизировать сварные операции, потому что они стоят дороже обрезков. ps: где-то мне на глаза попадалась кандидатская на близкую тему, суть ее была в применении генетических алгоритмов для поиска решений. pps: а задача очень интересная и кстати весьма дорогостоящая...
1
|
|
|
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
|
|
| 03.11.2018, 17:18 | 3 |
|
Из примера непонятно - зачем 1900 резать на 1500 и 400, если можно для 1500 взять новый блок, а 1900 складировать до следующего заказа, избежав при этом потери 400?
0
|
|
|
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 342
|
|
| 03.11.2018, 19:37 [ТС] | 4 |
Сообщение от renat_dmitriev
Добавлено через 9 минут
Сообщение от vantfiles
Сообщение от vantfiles
0
|
|
|
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
|
|
| 03.11.2018, 19:37 | 5 |
|
Kertis138, Тогда задача предельно простая: ищете можно ли использовать ровно 11800, если нет, то отрезаете вплоть до 11800 - 1100, то есть до 10700, а остаток идет на следующую трубу и т.д. до бесконечности. Если какая-то труба последняя, ну значит выхода нет и если обрезка составляет меньше 1100, значит никуда не денешься.
1
|
|
|
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
|
|
| 03.11.2018, 20:14 | 7 |
|
Kertis138, Немного засомневался в написанном выше...Уточняющий вопрос: у вас заказаны трубы на 6200 и 6200, вы бы предпочли их отрезать из одной заготовки и потерять 400, но зато ничего не надо сваривать, либо отрезать 6200 и 4500 от одной трубы, и 1700 от следующей, ничего не теряя(остатки годны для других заказов), но зато будет лишняя сварка.
И скажите пожалуйста, каким количеством труб может оперировать алгоритм, потому что возможно можно делать полным перебором по частям. Полный перебор на 14 труб будет делаться примерно час на одном процессе... Добавлено через 3 минуты
Сообщение от Kertis138
Вообще трубы больше 11800 можно оставлять на потом. Поскольку их все равно нужно разрезать, то их можно скомбинировать с любой трубой которая меньше 10700, дополнив до 11800, а если будут две такие трубы, то вообще прекрасно.
1
|
|
|
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 342
|
|
| 03.11.2018, 20:18 [ТС] | 8 |
|
на первом месте минимизация остатков. Чем меньше, тем лучше. 14 труб за час - очень много. Их может быть больше 150
Добавлено через 1 минуту Есть один из вариантов от проектировщиков. Но я не смог понять, какие остатки получились, и какая логика была при делении. То есть они на каждую трубу брали 2 куска Нужная длина - Сегмент 1 - Сегмент 2 18600 9700 8900 18600 9700 8900 18600 11700 6900 18600 11700 6900 18600 11700 6900 18600 11700 6900 18600 9700 8900 18600 9700 8900 18600 11700 6900 18600 11700 6900 18600 11700 6900 18600 11700 6900 18600 9700 8900 18600 9700 8900 18600 9700 8900 18600 11700 6900 18600 11700 6900
0
|
|
|
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
|
|
| 03.11.2018, 22:58 | 9 |
|
Kertis138, Если на первом месте оптимизация остатков, то как я написал, безостаточный алгоритм вполне прост - если нельзя использовать все 11800, то отрезаем не больше 10700, а 1100 используем для следующих деталей. Здесь нет разницы больше или меньше 11800 длина трубы. Так что вопрос только в оптимизации числа разрезов и здесь нужно подумать и поанализировать.
1
|
|
|
|
|
| 04.11.2018, 06:19 | 10 |
|
renat_dmitriev, "...то отрезаете вплоть до 11800 - 1100, то есть до 10700, а остаток идет на следующую трубу..."
Не все так просто... Допустим у нас нет остатков, только исходные трубы 11800 -- и поступает заказ на одну трубу длиной 11100 Из условий видно, что нам придется отрезать по куску от двух исходных труб, но: (10700 + 400) -- не получается, довесок не может быть короче 1100 А вот дальше встает вопрос критерия - как резать эти два куска, потому что длина первого куска L1 должна быть в диапазоне: 1100 < L1 < 10000 и соответственно длина второго куска L2 = 11100 - L1 Что выгоднее -- (10000 + 1100) или (5550 + 5550 ) ?.. или проще отрезать так -- (6000 + 5100) ? Добавлено через 1 час 0 минут В общем, тут получается три варианта - 1) заказы до 10700, 2) заказы от 10700 до 12900, 3) свыше 12900 Чисто интуитивно - нельзя отрезать кусок больше 9600 -- то есть больше, чем 11800 - 2*1100 -- но объяснить не могу...
1
|
|
|
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
|
|
| 04.11.2018, 11:02 | 11 |
 Сообщение было отмечено Kertis138 как решение
Решение
vantfiles, Мне кажется вы абсолютно правы, и куски в интервале от длина_заготовки - 2200 и возможно длина_заготовки + 2200 лучше не отрезать, а взять другой кусок. Соответственно куски от 9600 до 14000 нельзя использовать в начале и нельзя оставлять на конец, на них нужно расходовать уже отрезанные трубы, чтобы не попадать в этот интервал. Но по хорошему надо запустить тесты с перебором для 12 рандомных позиций и все станет ясно.
Добавлено через 36 минут Да, все верно, кажется все встало на свои место. Сформулировать можно так: ДЗ - длина заготовки МБ - минимальный блок СПО - сумма длин предыдущих обрезков ДК - длина очередного куска При последовательном обрезании кусков нужно избегать ситуаций, когда следующий кусок(за исключением первого) оставляет после себя больше обрезанных труб, чем было до него. И эта ситуация происходит только тогда, когда ABS(ДЗ + СПО - ДК) не равен 0, но меньше МБ, потому что в этом случае придется делать лишний разрез. В этой ситуации нужно брать другой кусок, а потенциально опасные куски от ДЗ - МБ до ДЗ + МБ (не включительно) не оставлять на конец, а дополнять ими уже отрезанные Пример: Пусть у нас 3 куска 8200 15000 и 17000 1. Отрезаем 8200, обрезка 3600 (первый кусок закончен) 2. 3600 используем для второго куска, еще для второго куска нужно 11400 3. 11400 отрезать не можем, поэтому отрезаем 10300, обрезка 1500 4. Отрезаем 1100 от новой заготовки, обрезки 1500 и 10700 5. Используем обрезки для третьего куска, еще для третьего куска нужно 4800 6. Отрезаем 4800, обрезка 7000. Дело сделано. Итого получаем 4 отрезания и 4 сварки(по 2 на второй и третий кусок) Соответственно на втором куске у нас не выполняется условие, получив одну обрезку, он вернул 2. Пробуем поменять местами 2й и 3й кусок 1. Отрезаем 8200, обрезка 3600 (первый кусок закончен) 2. 3600 используем для второго куска, еще для второго куска нужно 13400 3. Используем целую заготовку(11800), еще для второго куска нужно 1600 4. Отрезаем 1600 от новой заготовки, обрезка 10200, второй кусок закончен 5. Используем 10200 для третьего куска, еще нужно 4800 6. Отрезаем 4800, обрезка 7000. Дело сделано. Итого: 3 отрезания и 3 сварки (2 на второй кусок, 1 на третий) Что и требовалось доказать... =) Естественно, если есть кусок, чья длина равна длине обрезки, то использовать нужно его по принципу чем меньше обрезок после куска тем лучше.
1
|
|
| 04.11.2018, 11:02 | |
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
| 04.11.2018, 11:02 | |
|
Помогаю со студенческими работами здесь
11
Верно ли, что сумма остатков от деления нечётных x на k будет больше, чем сумма остатков от деления чётных x на k Минимизацию функции..Очень сложная Выполнить минимизацию функций методом Квайна Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||||
|
Элементы алгоритмизации
hw_wired 28.01.2025
Основы алгоритмизации
В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .
|
Человек и информация
hw_wired 28.01.2025
Введение: роль информации в познании мира
В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .
|
Компьютер и информация
hw_wired 28.01.2025
Эволюция вычислительных машин
История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .
|
Информационные технологии
hw_wired 28.01.2025
Введение в современные технологии работы с информацией
В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .
|
Информация вокруг нас
hw_wired 28.01.2025
Основные понятия информации
В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .
|
Компьютер для начинающих
hw_wired 28.01.2025
Введение в мир компьютерных технологий
В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
|
|
[golang] 189. Rotate Array
alhaos 28.01.2025
Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO
/ / https:/ / leetcode. com/ studyplan/ top-interview-150/
package topInterview
. . .
|
КуМир: решение задач на матрицы
bytestream 28.01.2025
КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .
|
КуМир: решение задач на строки
bytestream 28.01.2025
В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .
|
КуМир: решение геометрических задач
bytestream 28.01.2025
Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .
|
КуМир, исполнитель Водолей: Задачи и решения
bytestream 28.01.2025
КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .
|
КуМир, исполнитель Чертежник: Решение задач
bytestream 28.01.2025
КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации.
Исполнитель Чертежник работает на координатной плоскости, где может. . .
|
Наверх