Метод генерации столбца

[damir_777]

Здравствуйте.
Сделал небольшую программу для одномерного раскроя симплекс-методом с генерацией столбца.
Сам принцип такой: составляю исходные варианты раскроя, где кол-во вариантов равно количеству заготовок. В каждый вариант входит только одна очередная заготовка.
Далее запускаю симплекс (назовем этот шаг симплекс1), полученные оценки передаю в модуль решения задачи о неограниченном рюкзаке, получаю данные. Проверка что сумма произведения всех оценок на соответствующие результаты задачи о рюкзаке была больше единицы, в противном случае останов, т.к найдено оптимальное решение. Далее подставляю результат задачи о рюкзаке в качестве свободных членов текущей задачи лин. программирования . Получаю результат (назовем это симплекс2). А дальше нахожу минимальное отношение симплекс1/симплекс2 чтобы определить какой столбец заменяется данными задачи о рюкзаке.
Однако на некоторых тестовых данных программа не могла дальше продолжить решение, потому что система ограничений становилась несовместимой. Начал делать трассировку. Оказалось что появляется нулевая строка! Т.е коэффициенты все по нулям, все ограничения стандартно имеют знак в правой части ">=" а свободный член в правой части больше нуля. Тут то и возникает конфликт с другими ограничениями. Требуем чтобы оно было больше определенного значения, а все коэффициенты по нулям.
Вот и хотел спросить что нужно делать дальше? Причем я заметил чем больше заготовок берется, то вероятность появления строки возрастает.
Второй вопрос связан со скоростью. Я сравнил на одних и тех же данных обычный симплекс и симплекс с генерацией столбца. Первый работает быстрее, скорость ощущается именно когда данных становиться больше. Незнаю может это связано с тем что задача о рюкзаке реализована методом динамического программирования , а он не так быстр при больших данных? Хотя преимущество метода генерации столбцов очевидно на больших данных, когда перебор всех вариантов неразумен.

[mserg]

Все нули - это вариант, который не используется?
А ненулевая правая часть - результат погрешности?

[damir_777]

http://www.sql.ru/forum/1207674/generac ... o-raskroya
вот здесь есть пример, на котором я застрял
Правая часть это кол-во заготовок которые нужно нарезать, а нулевая строка получилась в результате замены столбцов

[mserg]

А эта строчка как была получена?
0 0 0 0 0 >= 12 000

[damir_777]

Решив предпоследнюю задачу лин. программирования, я получил такое решение и оценки:
Решение задачи1: $x_1=\frac {14 000} {3}, x_2=0, x_3=12 000, x_4=\frac {2000} {3}, x_5=0$
Оценки: $\frac {1} {3}, \frac {1} {9}, 0, \frac {8} {9}, 0$
и подставив полученные оценки в целевую функцию задачи о рюкзаке, я получил следующее решение задачи о рюкзаке: 0, 0, 0, 102, 0
Теперь эти оценки я подставляю в качестве свободных членов в правую часть ограничений предпоследней задачи и решаю симплекс-методом
Найденное решение:
Решение задачи2:$x_1=0, x_2=102, x_3=102, x_4=0, x_5=0$
Теперь ищу наименьшее отношение между Решением задачи1 и Решением задачи2 чтобы узнать, какой столбец должен быть заменен решением задачи о рюкзаке. Получилось что 3-ий столбец. Теперь если заменить третий столбец данными задачи о рюкзаке (0 0 0 102 0) то получается нулевая строка.
Честно говоря уже в интернете столько искал, что то ни разу такая ситуация не попадалась, дается только объяснение принципа метода генерации столбца. Я думал может где то неправильно считает, но остальные примеры проверял, все совпадает