задача про распил симплекс-методом(линейное прогр)

[novak_pd]

Произвести распил тысячи 5-метровых брёвен на брусья размерами 1,5м; 2,4м и 3,2м в отношении 2:3:5 так, чтобы минимизировать общую величину отходов. К отходам отнести и брусья, не вошедшие в комплекты.

в общем вот кое до чего я додумался

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

[Dimka]

novak_pd, первый встречный вопрос, почему в таблице 4 варианта, а не 9, которые даёт уравнение?

1.5x + 2.4y + 3.2z + a = 5

где x, y, z - целые числа >= 0, образующие расклад, a - вещественное число >= 0, описывающее отходы с бревна?

[novak_pd]

ну не 9 потому что остальные варианты бессмысленно рассматривать, либо повторяются либо уже получается больше 5 метров

дальше вы задали вопрос или это утверждение, я не понял

[Dimka]

novak_pd, ну как повторяют, как превышают 5 метров...

У меня лично получаются такие расклады, где 3 цифры - количество соответствующих брусков, а за стрелкой - остаток метров бревна в отходы

1: 0 0 0 -> 5
2: 0 0 1 -> 1.8
3: 0 1 0 -> 2.6
4: 0 2 0 -> 0.2
5: 1 0 0 -> 3.5
6: 1 0 1 -> 0.3
7: 1 1 0 -> 1.1
8: 2 0 0 -> 2.0
9: 3 0 0 -> 0.5

По-моему, тут ничего не повторяется и не превышает...

[novak_pd]

таким способом задача тоже не решаема
прикрепил файл, там посчитано

[Dimka]

novak_pd, видна попытка применить метод, но не видно рассуждений о том, что есть что в задаче.

Вот уравнение 1.5x + 2.4y + 3.2z = 5 - a описывает распределение длины 1 бревна по количеству брусков и имеет параметр отходы. Тут важно сочетание разных единиц измерения - "штук брусков" и метров. Есть коэффициентов приведения одного к другому - размеры брусков.

Решение уравнения даёт 9 вариантов обработки 1 бревна. Есть 1000 бревен, для каждого из которых нужно выбрать один из вариантов. Следовательно, напрашивается уравнение v1 + v2 + v3 + v4 + v5 + v6 + v7 + v8 + v9 = 1000 как распределение брёвен по вариантам обработки. Но эти переменные уже имеют третью единицу измерения "штук брёвен".

Главная интрига всей задачи в том, как соотнести "штуки брёвен", "штуки брусков" и метры.

С точки зрения функции, по которой определяется оптимум, штуки брёвен, действительно, соотносятся с метрами отходов

5*v1 + 1.8*v2 + 2.6*v3 + 0.2*v4 + 3.5*v5 + 0.3*v6 + 1.1*v7 + 2*v8 + 0.5*v9 -> min

А вот как соотносятся "штуки брёвен" со "штуками брусков"?

[Dimka]

По поводу решения: можно неформально прикинуть оптимум для минимального числа комплектов.


Итак, надо получит 5 брусков по 3.2 м, 3 бруска по 2.4 м и 2 бруска по 1.5 м. Всего 10 брусков.

Посмотрим на варианты обработки брёвен. Из варианта 0 можно получить в одно действие варианты 2, 3 и 5. В свою очередь из этих вариантов за счёт использования остатков можно перейти: из 2 в 6; из 3 в 4 или 7; из 5 в 6 или 7, или 8; из 8 в 9.

Дальше жадным алгоритмом, начиная с самой большой потребности. Берём 5 брёвен и пилим по варианту 2, чтобы получить 5 брусков по 3.2 м и, соответственно, 5 остатков по 1.8 м. Из этих остатков не получить 3 бруска по 2.4, следовательно, берём ещё 3 бревна и по варианту 3 получаем искомые бруски и 3 остатка по 2.6 м. Также мы можем из остатков изготовить 2 бруска по 1.5 м по варианту 6, получив 2 остатка по 0.3 м.

Итого нам понадобилось 8 брёвен, и мы получили остатки: 2 штуки по 0.3 м - бесполезные, 3 штуки по 1.8 м - годные для изготовления брусков по 1.5 м, 3 штуки по 2.6 м - годные для изготовления брусков по 2.4 и по 1.5 м.

Откуда видно, что при изготовлении второго комплекта можно отказаться от 3-х новых бревен для изоготовления 3-х брусков по 2.4 м, использовав 3 остатка по 2.6 м от предыдущего комплекта и получив по варианту 4 бесполезные 3 остатка по 0.2 м.

Итого для 2-х комплектов понадобилось 13 брёвен, и мы получили остатки: 4 штуки по 0.3 м - бесполезные, 3 штуки по 0.2 м - бесполезные, 6 штук по 1.8 м - годные для изготовлени брусков по 1.5 м. Но нам столько брусков по 1.5 м не надо.

3-й комплект по расходу брёвен будет изготавливаться как 1-й - нет возможности использовать остатки предыдущих. Т.е. оптимум достигается на 2-х комплектах, а дальше просто масштабируется.

Тогда 1000 брёвен делим на 13 и получаем 76 целых пар комплектов, на которые уйдёт 988 брёвен, а из оставшихся 12 брёвен можно изготовить ещё один комплект как 1-й. Остатки составят по 12.6 м с каждой пары, 13.8 м с последнего комплекта и 4 целых бревна (не обрабатываемых - по варианту 1), т.е. ещё 20 м.

Итого выходит, что мы получим из 5000 м сырья 153 комплекта и 991.4 м отходов.

Распределение по вариантам выходит такое:

v1=4
v2=459
v3=3
v4=228
v5=0
v6=306
v7=0
v8=0
v9=0


Т.е. решение у задачи есть (как здравый смысл и подсказывал с самого начала), и вот такое решение выглядит оптимальным.

Остаётся лишь понять, что тут есть что применительно к симплекс-методу с его гиперпространствами, гиперплоскостями ограничений, вершинами и самим принципом перебора вершин.