Здравствуйте.
Решаю задачу одномерного раскроя. Решаться будет симплекс-методом, но чтобы изначально не перебирать все варианты раскроя, а потом уже решать задачу, буду использовать метод генерации столбца, столбцы будут замещать другие в процессе их генерации.

Может кто сталкивался с такой проблемой:
Длина исходной заготовки L=24.
Необходимо выполнить следующий заказ на раскрой (длина/количество):
1. 4/100
2. 5/800
3. 8/100
Простейший план раскроя, для начального решения задачи симплекс-методом:
1.24/4=6. Максимальное кол-во заготовок первого типа, которые можно разместить в заданной длине
2. 24/5=4 Максимальное кол-во заготовок второго типа, которые можно разместить в заданной длине. (Целая часть числа)
3. 24/6=3 Максимальное кол-во заготовок третьего типа, которые можно разместить в заданной длине

Таким образом, получаются исходные коэффициенты при переменных в ограничениях в задаче линейного программирования:
6 0 0
0 4 0
0 0 3

Решается задача лин. программирования, получаются следующие двойственные оценки из решения :
0,167; 0,25; 0,333
Двойственные оценки, длину каждой детали и размер исходной заготовки передаем в задачу о рюкзаке.

Решение задачи о рюкзаке:
Значения переменных:
1; 4; 0
Значение "рюкзачной" функции, ну или максимальная стоимость всего рюкзака:
z=1,167
Теперь, заменяем сгенерированным столбцом (это значения переменных в задаче о рюкзаке) первый столбец исходных ограничений.
Получаются следующие коэффициенты при переменных в ограничениях задачи линейного программирования:
1 0 0
4 4 0
0 0 3
А чтобы вычислить , какой столбец заменить, выполняются все те же операции при замене столбца как в обычном модифицированном симплекс-методе. Двойственные оценки решенной задачи : 0,25; 0,333; 0

Решение задачи о рюкзаке дает следующее решение:
Значения переменных:
1; 4; 0
Значение "рюкзачной" функции, ну или максимальная стоимость всего рюкзака:
z=1,583

Но такое значение уже было получено на предыдущем шаге, а функция еще не равна 1 (условие окончания поиска оптимального решения задачи раскроя) Если на этом остановить решение, то решение всей задачи о раскрое не будет оптимальным, а именно нужно использовать 234 заготовки. Сравнивая решение с перебором всех вариантов раскроя и решение целочисленной задачи лин. программирования дает 225 заготовок.

т.е проблема в повторе предыдущего решения задачи о рюкзаке