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

Вот один из примеров
Длина раскраиваемой заготовки L=8000
Даны следующие заготовки и их количества:
2392-6 000 шт.
946-14 000 шт.
2256-6 000 шт.
78-12 000 шт.
178-12 000 шт.
Теперь определяю сколько каждого размера укладывается целое число раз в длину 8000:
2392 - 3 [8000/2392]
946 - 8 [8000/946]
2256 - 3
78 - 102
178 - 44
Таким образом получилось 5 вариантов раскроя (по кол-ву заготовок) и составляются ограничения задачи линейного программирования:
3 0 0 0 0 >= 6 000
0 8 0 0 0 >= 14 000
0 0 3 0 0 >= 6 000
0 0 0 102 0 >= 12 000
0 0 0 0 0 >= 12 000
Целевая функция все время минимизируется и коэффициенты при неизвестных равны единицам.
Решив данную задачу симплекс-методом получаю значения: 2000, 1750, 2000, 2000/17, 3000/11
и следующие оценки: 1/3, 1/8, 1/3, 1/102, 1/44
Теперь решаю задачу о неограниченном рюкзаке (т.е каждый предмет можно брать несколько раз):
Z=1/3*x1+1/8*x2+1/3*x3+1/102*x4+1/44*x5
2392*x1+964*x2+2256*x3+78*x4+178*x5<=8000
Решение задачи о рюкзаке: x1=0, x2=1, x3=3, x4=1, x5=1
Так как Z>1, то продолжаем решение
Подставляю найденные значения в качестве свободных членов в предыдущую задачу лин. прогр.
3 0 0 0 0 >= 0
0 8 0 0 0 >= 1
0 0 3 0 0 >= 3
0 0 0 102 0 >= 1
0 0 0 0 0 >= 1
Решив данную задачу симплекс-методом получаю значения: 0, 1/8, 1, 1/102, 1/44
Теперь нахожу наименьшее значение между предыдущим значением симплекс решения и найденным только что:
[2000/0] [1750/(1/8)] [2000/1] [(2000/17)/(1/102)] [(3000/11)/(1/44)]
Наименьшее отношение выделено жирным шрифтом (2000/1).Соответствено третий столбец заменяется значениями задачи о рюкзаке и получаем новую задачу лин. прогр.
3 0 0 0 0 >=6 000
0 8 1 0 0 >=14 000
0 0 3 0 0 >=6 000
0 0 1 102 0 >=12 000
0 0 1 0 44 >=12 000
Далее все делается также и я не буду расписывать так подробно, а буду приводить матрицу, где жирным шрифтом будет выделен столбец, замененный значениями задачи о рюкзаке
3 0 0 3 0
0 8 1 0 0
0 0 3 0 0
0 0 1 6 0
0 0 1 2 44
Далее
3 0 0 2 0
0 8 1 3 0
0 0 3 0 0
0 0 1 0 0
0 0 1 2 44
И наконец, последняя задача лин прогр. где получилась нулевая строка
3 0 0 2 0
0 8 0 3 0
0 [b]0 0 0 0[/b]
0 0 102 0 0
0 0 0 2 44
Вот здесь то я и не пойму что делать дальше. Симплекс-метод дальше не решает т.к система ограничений несовместна. Вообще в методе генераци столбцов возникают ли такие ситуации (или только у меня так получилось) и что делать при этом