2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Метод генерации столбца
Сообщение03.04.2016, 11:47 


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

 Профиль  
                  
 
 Re: Метод генерации столбца
Сообщение06.04.2016, 18:57 


17/10/08

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

 Профиль  
                  
 
 Re: Метод генерации столбца
Сообщение06.04.2016, 19:45 


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

 Профиль  
                  
 
 Re: Метод генерации столбца
Сообщение06.04.2016, 21:56 


17/10/08

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

 Профиль  
                  
 
 Re: Метод генерации столбца
Сообщение07.04.2016, 09:15 


03/08/15
114
Решив предпоследнюю задачу лин. программирования, я получил такое решение и оценки:
Решение задачи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) то получается нулевая строка.
Честно говоря уже в интернете столько искал, что то ни разу такая ситуация не попадалась, дается только объяснение принципа метода генерации столбца. Я думал может где то неправильно считает, но остальные примеры проверял, все совпадает

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group