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

Здравствуйте.
У меня такой вопрос. Я сделал применил метод генерации столбца для задачи одномерного раскроя. Но в одной из задач у меня на определенной итерации получилась нулевая строка! Что делать в этом случае?
Вот здесь все подробно описано!
ссылка удалена
Задавал вопрос на другом форуме, но там что то на него не могут ответить, да и в интернете все перерыл

0

	Комментарий модератора
	Правила форума 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и какие результаты получены. 5.8. Запрещено публиковать ссылки на другие форумы, а также их пропаганда. Публикация ссылок на форумы допустима только в разделе "Готовые движки, cms и форумы" для решения технических проблем и с предварительного одобрения администрации.

0

Вчера не смог привести пример и сам принцип алгоритма, по которому сделал программу.
Сначала принцип.
Сам принцип такой: составляю исходные варианты раскроя, где кол-во вариантов равно количеству заготовок. В каждый вариант входит только одна очередная заготовка.
Далее запускаю симплекс (назовем этот шаг симплекс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 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 0 0 0 0
0 0 102 0 0
0 0 0 2 44
Вот здесь то я и не пойму что делать дальше. Симплекс-метод дальше не решает т.к система ограничений несовместна. Вообще в методе генераци столбцов возникают ли такие ситуации (или только у меня так получилось) и что делать при этом.

Добавлено через 5 минут
там небольшая помарка
в примере, где только составляется матрица исходных вариантов раскроя, значение в пятом столбце пятой строки значение не ноль , а 44 , по кол-ву заготовок пятой заготовки.

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

Есть какие нибудь мысли по этому вопросу?
Может где то дополнительная проверка должна быть или что то добавить в сам алгоритм?

Вложения

cuttingstock.pdf (571.8 Кб, 31 просмотров)

0