Здравствуйте.
Я сейчас пытаюсь приспособить алгоритм генерации столбца для решения задачи линейного раскроя.
К примеру есть заготовка L=16 метров.
есть следующие детали/их количества на которые нужно порезать исходную заготовку:
1. 3 метра. Необходимо 25 штук
2. 6 метров. Необходимо 20 штук
3. 7 метров. Необходимо 18 штук
Задача-использовать как можно меньше заготовок для выполнения данного заказа.
Обычно рекомендуют начать с самого простейшего плана раскроя, где количество раскроя равно количеству заготовок:
1. 16/3=5 Количество деталей первого типа, которые максимально можно разместить на заготовке (взята целая часть числа)
2. 16/6=2 Количество деталей второго типа (взята целая часть числа)
3. 16/7=2 Количество деталей третьего типа (взята целая часть числа)
Таким образом получается исходная матрица, и она будет использована на первой итерации симплекс-метода:
5 0 0
0 2 0
0 0 2
Решив задачу линейного программирования, и получив двойственные оценки, решаем задачу о рюкзаке, передав ей двойственные
оценки, длину исходного материала, и длину каждой детали. Получили решение. Решение будет новым столбцом.
Если целевая функция задачи о рюкзаке меньше нуля (кстати где то пишут что должна быть больше единицы, не пойму разницу), то столбец добавляется.
Добавили столбец.
Допустим, получилась следующая матрица, где последний столбец это решение задачи о рюкзаке:
5 0 0 1
0 2 0 2
0 0 2 0
Решается задача линейного программирования уже с этой матрицей. Находим двойственные оценки из решения.
Снова решается задача о рюкзаке. Вот тут вопрос: Полученные столбцы после задачи о рюкзаке нужно постоянно добавлять, или же их
надо ставить вместо других столбцов, вместо тех, которые не будут входить в базис, т.е. задача будет в первом случае расти постоянно
по количеству переменных или же размер задачи уже не будет изменяться? (т.е. он будет равен размеру последней матрицы, будут только меняться значения в столбцах)