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

@1helen · Регистрация: 20.02.2019

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста решить задачу
На складе деревообрабатывающего завода имеются доски двух видов: 1000 штук длиной 6 м и 1500 штук длиной 5 м. Из этих досок нужно сделать максимальное число комплектов, состоящих из 2 досок по 2,4 м и 3 досок по 1,6 м. Сколько таких комплектов можно сделать из имеющихся на складе досок?

Комментарий модератора

Правило 4.3: "Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос ответят."
Правило 4.2: "Если собираетесь создать новую тему, определитесь с разделом или существующей темой, в которой ведется обсуждение этого вопроса." При чём здесь теория вероятностей? Где в вашей задаче поиск вероятности?

Fairuza · 10.01.2020, 09:06

Посмотрите вариант

iifat · 10.01.2020, 19:54

Как понимаю, надо расписать комплекты исходных досок, из которых можно сделать ровно один комплект, начиная с 1+1 и заканчивая... Ну, не знаю. Тремя, наверное, из четырёх уж точно можно сделать два. Таких исходных комплектов 12 (4 из двух досок, 8 из трёх). Количество их и будет переменными.
Впрочем, всё это не о том. Из любой пары досок можно сделать ровно один комплект и несколько не годных к данной задаче обрезков. Так что делим по парам и всё.

@jogano · 13.01.2020, 17:57

доски по 6 м можно распилить на нужные куски тремя способами, доски по 5 метров тоже.
Для досок по 6 м:

Количество досок по 6 м с таким распилом	досок по 2,4 м	досок по 1,6 м
x1	2	0
x2	1	2
1000-x1-x2	0	3

Для досок по 5 м:

Количество досок по 5 м с таким распилом	досок по 2,4 м	досок по 1,6 м
x3	2	0
x4	1	1
1500-x1-x2	0	3

Итоговое количество досок по 2,4 м будет 2x1+x2+2x3+x4, количество досок по 1,6 м тогда 2x2+3000-3x1-3x2+x4+4500-3x3-3x4=7500-(3x1+x2+3x3+2x4).
Нужно найти такое решение (x1,x2,x3,x4) в целых числах >=0, чтобы
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}x_1+x_2\leq 1000 \\ x_3+x_4\leq 1500 \\ min \left(\frac{2x_1+x_2+2x_3+x_4}{2}; \: 2500-\frac{3x_1+x_2+3x_3+2x_4}{3} \right) \to max \: \: (*)\end{cases}$
Это сводится к двум задачам линейного программирования, решаемых симплекс-методом каждая.
Если минимум в целевом выражении равен I дроби, то получаем задачу на максимум
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}x_1+x_2\leq 1000 \\ x_3+x_4\leq 1500 \\12x_1+5x_2+12x_3+7x_4\leq 15000 \\2x_1+x_2+2x_3+x_4 \to max\end{cases}$
С решением (не целым, обо этом потом) (x1,x2,x3,x4)=(0;1000;833,333;0), со значением целевой функции 2666,666, а количество комплектов тогда в 2 раза меньше, то есть 1333,333, и нас ограничивает количество досок по 2,4 метра.
Если минимум выражения (*) равен II выражению, то есть количество комплектов ограничивается досками по 1,6 метра, то получаем другую задачу:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}x_1+x_2\leq 1000 \\ x_3+x_4\leq 1500 \\12x_1+5x_2+12x_3+7x_4 \geq 15000 \\3x_1+x_2+3x_3+2x_4 \to min\end{cases}$
с тем же самым решением (x1,x2,x3,x4)=(0;1000;833,333;0) и значением целевого функционала 3500, что даёт 2500-3500/3=1333,333 комплектов.
Нужно решение в целых числах и по неизвестным, и по количеству комплектов. Можно перебрать 4 соседних решения по вариантам распила 5-метровых досок (833;0;667), (833;1;666), (834;0;666) и (834;1;665), чтобы обнаружить, что максимальное количество комплектов (вместе с распилом 6-метровых досок) будет в первых двух случаях по 1333, а в последних двух по 1332.
Значит, 6-метровые доски нужно пилить так: все 1000 досок распилить на куски 1*2,4 м+ 2*1,6 м, а 5-метровые или так:
- 833 доски на 2*2,4 м, 667 досок на 3*1,6 м, или
- 833 доски на 2*2,4 м, 1 доска на 1*2,4 м+ 1*1,6 м, 666 досок на 3*1,6 м.
Количество комплектов 1333.

iifat · 14.01.2020, 00:01

Ну, что касается целых решений, для этого существует специальная метода — целочисленное программирование.

@jogano · 14.01.2020, 00:10

iifat, да, у меня до метода Гомори руки пока не дошли

Новые блоги и статьи Все статьи Все блоги /
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .

iifat 2892 / 1927 / 208 Регистрация: 05.06.2011 Сообщений: 5,643
	10.01.2020, 19:54
	Как понимаю, надо расписать комплекты исходных досок, из которых можно сделать ровно один комплект, начиная с 1+1 и заканчивая... Ну, не знаю. Тремя, наверное, из четырёх уж точно можно сделать два. Таких исходных комплектов 12 (4 из двух досок, 8 из трёх). Количество их и будет переменными. Впрочем, всё это не о том. Из любой пары досок можно сделать ровно один комплект и несколько не годных к данной задаче обрезков. Так что делим по парам и всё. 0

iifat 2892 / 1927 / 208 Регистрация: 05.06.2011 Сообщений: 5,643
	14.01.2020, 00:01
	Ну, что касается целых решений, для этого существует специальная метода — целочисленное программирование. 0

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	14.01.2020, 00:10
	iifat, да, у меня до метода Гомори руки пока не дошли 0