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

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

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

0

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

Вложения

доски.xlsx (9.7 Кб, 21 просмотров)

1

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

0

доски по 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, чтобы

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

С решением (не целым, обо этом потом) (x1,x2,x3,x4)=(0;1000;833,333;0), со значением целевой функции 2666,666, а количество комплектов тогда в 2 раза меньше, то есть 1333,333, и нас ограничивает количество досок по 2,4 метра.
Если минимум выражения (*) равен II выражению, то есть количество комплектов ограничивается досками по 1,6 метра, то получаем другую задачу:

с тем же самым решением (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.

0

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

0

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

0