Страницы: 1
RSS
настройка "Поиска решения" для оптимизации использования ресурсов
 
Уважаемые форумчане, доброго времени суток  
 
Нужна помощь.  
Требуется решить задачу наилучшего использования остатков деталей-комплектующих для выпуска максимального количества готовой продукции в пределах плана производства.  
Каждая деталь идёт на изделие в количестве 1шт.  
В файле - упрощенная модель для двух видов комплектующих и небольшого перечня готовой продукции.  
 
Исходные данные выделены зеленым цветом:  
В левой таблице - перечень изделий, два столбца наименований соответствующих деталей, в столбце "план" - план готовых изделий;  
В двух правых табличках - перечень наименований каждого из двух типов деталей и имеющиеся остатки.  
 
"Подготовительные" расчеты (всё - формулами) выделены жёлтым цветом:  
В правых табличках - это потребность каждого наименования деталей на план;  
В левой таблице - максимально комплектуемое остатками кол-во в отдельности по каждому изделию (без связи с другими изделиями).  
 
Ячейки, используемые для поиска решения, в обеих таблицах выделены голубым цветом.  
Текущая модель хорошо видна в окне "поиска решения", кратко опишу идею:  
Ищем такие числа для каждого изделия (целые, положительные, не больше "максимального" плана), которые в сумме дали бы максимальное кол-во готовых изделий и при этом кол-во используемых комплектующих не превысило остатки.  
 
 
Проблема:  
Наибольшее кол-во изделий для данных примера составляет 865 шт. - соответствующий столбец (для справки) выделен сиреневым цветом. Однако, сколько бы времени и итераций я не давал решателю на поиск оптимума, я не могу прийти к этой цифре с первого раза.    
Например, при установках 600 секунд на решение, 500 итераций, отн.погрешность =0,00001 и допустимое отклонение =2% я, взяв в кач-ве нулевого приближения максимальный план (копирую значения из столбца F в G), получаю 862шт.  
Всё то же, но установив "от балды" нулевое приближение по 100шт. на изделие - 864шт.  
Всё то же, но исходно - нули => вообще 848 шт.  
И т.д.  
При этом заданный предел времени не достигается никогда, итераций - кажется, тоже. Короче говоря, решать бы ему, да решать, но нет ведь - останавливается.  
Самое интересное, на мой взгляд, в следующем: сохранив полученное решение, я снова запускаю решатель, НИЧЕГО не меняя (просто тупо "поиск решения" - "выполнить"). Требуется от одного до пяти таких "дополнительных" запусков - и решатель выходит на искомые 865шт. ВСЕГДА. При этом суммарное время (включая нажимание кнопок) тоже не превышает 600 секунд. Вообще, весь процесс занимает не более трёх-четырёх минут.  
 
 
Вопрос(ы), собственно говоря, в следующем:  
1. может ли кто-нибудь подсказать - является ли такое построение модели для такой задачи хорошим? (я понимаю, что, собственно говоря, это вопрос "не по Excel'ю", но прошу сильно не бить - если у кого-нибудь есть опыт или просто логические умопостроения - прошу подсказать; нет - значит, нет)?  
2. что нужно поменять в настройках решателя для такого типа модели, чтобы выйти на результат если уж не с первого раза (вообще говоря - желательно, конечно), то хотя бы при минимальном кол-ве "дополнительных" запусков?  
3. какие могут быть принципы для определения того, какое кол-во брать в качестве "нулевого" приближения?  
4. если нет уверенности, что решение оптимально, то как это определить?  
5. насколько может быть приемлема такая модель при большем объеме исходных данных (перечень наименований изделий - до 500, типов комплектующих - до 10, наименований каждого типа комплектующих - до 100)? т.е. - стоит ли с этим возиться вообще или послать начальство нафиг и пусть оно, в конце-то концов, ищет деньги на внедрение нормального MRPII-продукта???    
6. есть ли смысл переходить на Excel 2010 (интересуют как скорость, так и точность решения)?  
 
Если кто-нибудь сможет подсказать что-нибудь конкретное, или просто дать совет - в каком направлении копать, или поделится опытом - буду благодарен безмерно. Но денежек обещать не могу, хоть и не из простых задачка-то :(  
 
пс. Ex'2002.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
Немного изменил настройки, находит оптимальное решение от нулей с первого раза, но не факт, что при других условиях будет также находить
 
большое спасибо.  
 
да, с первого раза.  
ну пара параметров (кол-во итераций до 5000 и сходимость до 0,0000001) - явно экстенсивный путь? а вот почему метод поиска выбран именно такой? в этом есть глубинный смысл или просто "так получилось"?  
хотелось бы (по возможности) понять именно принципы выбора тех или иных параметров.  
 
пс. вопрос 4 из первого пвоста. наверное, снят - использовал формулу из столбца F, но не для исходных остатков деталей, а для остатков, "оставшихся" после оптимизации. если все значения равны 0, значит, предел оптимизации достигнут.  
 
остальные вопросы, увы, актуальны.  
 
пс. установил ТАКИЕ ЖЕ параметры в своём файле - 863шт., хоть тресни :(((
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
Поменял 'СУММ(перерасход)>=0' на 'перерасход=0' (?)
 
Александр, Solver от Excel 2010 имеет быстрый алгоритм поиска почти целочисленных (с указанной точностью) значений. Вашу задачу из post_232065.xls он решил за несколько секунд, решение: G30=677.93454 H30=668  
Модель - та же, но установил алгоритм GRP и точность целочисленный 1%. При этом Solver использовал не полный перебор целочисленных вариантов, а поиск целых с заданной точностью, т.е. вместо 39 найдено 39,3333203845659, вместо 19 - 18.9809418749261 и т.п. - см. приложение
 
Александр, замечательно!  
честно говоря, играюсь с этой задачкой третий день, вариантов была куча, и упрощал, и усложнял, и перестраивал модельку.  
сразу такое условие и было, но потом в одном из вариантов были причины поменять его на СУММ(), а вот назад вернуть, когда надобность отпала - не показалось очевидным. честно говоря, не очевидно и до сих пор - неужелю Решателю проще проверить каждый элемент диапазона, чем сумму этих элементов???  
по факту, однако (а факты - штука упрямая) выходит именно так!  
решение ищется намного быстрее, на данных примера - сразу наилучшее (хотя, опть же, не факт, что для другого набора данных это останется так, но экспериментировать по-любому надо, экспериментов я не боюсь. просто не хочется экспериментировать методом слепого тыка).  
 
один минус - работает идеально от нулей.  
если же в кач-ве "нулевого" приближения задать значения из столбца F, то, во-первых, считает подольше, во-вторых, с первого раза даёт 861шт. и, самое главное - запущенный на "второй круг", думает долго-предолго, при этом видно, что результат на миллиметры колеблется от идеального, но остановка вручную ни к чему хорошему не ведёт - значения настолько далеки от целых, что и 861шт. не дают.  
 
продолжаю играться дальше.  
 
за идею - оргомное спасибо. свежий взгляд - самое оно!
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
Если в Solver-е Excel 2010 стартовать с полученого в предыдущем варианте значения, то результат: G30=694  
Если запустить расчет с нулевых начальных значений, то результат G30=802
 
{quote}{login=ZVI}{date=29.05.2011 05:17}{thema=}{post}Александр, Solver от Excel 2010 имеет быстрый алгоритм поиска почти целочисленных (с указанной точностью) значений. Вашу задачу из post_232065.xls он решил за несколько секунд, решение: G30=677.93454 H30=668  
Модель - та же, но установил алгоритм GRP и точность целочисленный 1%. При этом Solver использовал не полный перебор целочисленных вариантов, а поиск целых с заданной точностью, т.е. вместо 39 найдено 39,3333203845659, вместо 19 - 18.9809418749261 и т.п. - см. приложение{/post}{/quote}  
 
гм... Владимир, спасибо большое.  
сейчас посмотрю повнимательней...  
но... с первого взгляда... решение, мягко скажем, не "ахти" :(  
найденные 668 при реальном максимуме 865 - за это и побить могут, не то что уволить :)  
 
пс. "несколько секунд" - хорошо, но результат, более близкий к оптимальному - всё же гораздо лучше.  минут 20-30 поисков на реальном объеме номенклатуры мы переживём, а вот плохое использование ресурсов - нет.  
 
поэтому наберусь наглости ещё раз спросить:  
а что Вы скажете насчёт вопроса за №5 из первого поста?
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
{quote}{login=ZVI}{date=29.05.2011 05:27}{thema=}{post}Если в Solver-е Excel 2010 стартовать с полученого в предыдущем варианте значения, то результат: G30=694  
Если запустить расчет с нулевых начальных значений, то результат G30=802{/post}{/quote}  
 
(смотрит недоверчиво): Solver в 2010-м совсем испортился? :(
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
Саша, у меня сразу считает при начальном F-приближении и раскладе (см. рисунок), но при сумме=865 результаты в столбце отличаются от 0-начального :(
 
Он другой и требует изучения :-)  
На Сашиной модели Solver 2010 отработал точно, как с не совсем целыми, так и с целыми. Но вообще-то ограничение равенства, которое использовал Саша, считается жестким для решателя, и в данном случае повезло, что такое решение существует.  
 
По поводу п.5 - Solver Excel, независимо от версии, не работает с моделями, содержащими более чем 200 переменных. Можно попробовать самому написать макрос, который изначально помещал бы в подбираемые ячейки плановые цифры и в задаваемых пределах, например, от 100 до 50% перебирал бы все возможные варианты. Но это может быть очень долго. Если так очень долго, но требуется решение, то лучше перенести (создать) модель полностью в VBA, тогда расчет значительно ускорится. От начальства в таком случае можно потребовать новый комп :-)
 
{quote}{login=С.М.}{date=29.05.2011 05:54}{thema=}{post}Саша, у меня сразу считает при начальном F-приближении и раскладе (см. рисунок), но при сумме=865 результаты в столбце отличаются от 0-начального :({/post}{/quote}  
это плохо.  
вернее - плохо то, что у меня, стартовав со значений из F, работает именно так, как я и описал - не с первого раза.  
погоняю завтра ещё на рабочем.  
а то, что набрались какие-то другие штуки, а не те, которые у меня в качестве примера в столбце I - это неважно. главное - общее кол-во максимально, а по позициям распределение (пока?) устраивает любое.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
{quote}{login=ZVI}{date=29.05.2011 05:55}{thema=}{post}Он другой и требует изучения :-)  
На Сашиной модели Solver 2010 отработал точно, как с не совсем целыми, так и с целыми. Но вообще-то ограничение равенства, которое использовал Саша, считается жестким для решателя, и в данном случае повезло, что такое решение существует.  
 
По поводу п.5 - Solver Excel, независимо от версии, не работает с моделями, содержащими более чем 200 переменных. Можно попробовать самому написать макрос, который изначально помещал бы в подбираемые ячейки плановые цифры и в задаваемых пределах, например, от 100 до 50% перебирал бы все возможные варианты. Но это может быть очень долго. Если так очень долго, но требуется решение, то лучше перенести (создать) модель полностью в VBA, тогда расчет значительно ускорится. От начальства в таком случае можно потребовать новый комп :-){/post}{/quote}  
 
понятно.  
в общем-то, эта моделька - часть задачи. здесь оптимизируем только остатки в сборочном цехе и план этого цеха. с таким решением, будь оно хоть за две миллисекунды, можно вообще никуда не соваться.    
реально же "хотелка" начальства шире - оптимизировать ВСЕ ресурсы, в т.ч. сырья и материалов на изготовление недостающих деталей в заготовительных цехах, учитывая наличие людей по профессиям, возможности оборудования и много чего ещё, даже перечислять неохота.  
мои попытки объяснить, что для таких задач нужны и соответствующие программы (ERP или хотя бы MRP), успеха не возымели. ответом было: "у вас же есть КОМПЬЮТЕР - на нём и считайте!". т.к. MS Word для такой задачи явно не подходит, остался один трудяга Excel...  
 
как убедить - ума не приложу. хочется "дёшево и сердито", причём - вчера.  
:(  
 
пс. ладно, попробую разбивать исходные объемы на какие-то слабосвязанные подмножества, возможно, что-то и получится.  
 
в любом случае, Владимир, большое спасибо за подробную консультацию.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
{quote}{login=ZVI}{date=29.05.2011 05:55}{thema=}{post}  
Но вообще-то ограничение равенства, которое использовал Саша, считается жестким для решателя, и в данном случае повезло, что такое решение существует.  
{/post}{/quote}  
ikki, заменил '=МИН(K2-M2;0)' в N:N на '=K2-M2' и в Решателе выставил ограничение 'перерасход >= 0'  
Летает !
 
Остапа = С.М.
 
Для увеличения количества перебираемых переменных решения можно попытаться обмануть Solver, подставив ему в качестве подборную общую ячейку, значения различных разрядов которой будут использоваться несколькими другими ячейками, реально участвующими в модели.  
 
P.S. Руководство воспринимает Вас как свой ресурс, и с точки зрения бизнеса  это правильно. Попробуйте предложить ему в виде бизнес плана предложение, от которого оно в силу законов притяжения денег не сможет отказаться: оцените стоимость его проблем и предложите решение но не за зарплату, а за 30... 50%  от стоимости этих проблем, с созданием отдельной команды под Вашим руководством, закупкой необходимого софта и оборудования. Для этого рассчитайте и покажите на красивых диаграммах  постоянные и переменные затраты, срок окупаемости (лучше не более года) и прибыль, которую начнет загребать контора после этого срока. Все должно быть не на словах, а на бумаге и в электронном виде, чтобы Вас воспринимали на понятном им уровне. Возможно, потребуется несколько итераций, чтобы руководство стало воспринимать Вашу новую позицию. Здесь еще важно, чтобы в Вас сразу не увидели потенциального конкурента на свою должность, иначе уволят или засунут куда подальше. Если такая опасность есть, то можно вступить в «сговор» и со своим непосредственным начальником, выдать все от него, чтобы не подставляться самому. Риски и перспективы оцените уже сами по месту, а вдруг сработает? :-)
 
{quote}{login=C.М.}{date=29.05.2011 07:11}{thema=}{post}Остапа = С.М.{/post}{/quote}Без этой поправки даже не заметил, что это могло быть обо мне :-)  
Теперь не придерешься, это я уже о новом ограничении >=0 ;-)
 
{quote}{login=С.М.}{date=29.05.2011 07:04}{thema=Остапа понесло ...}{post}{quote}{login=ZVI}{date=29.05.2011 05:55}{thema=}{post}  
Но вообще-то ограничение равенства, которое использовал Саша, считается жестким для решателя, и в данном случае повезло, что такое решение существует.  
{/post}{/quote}  
ikki, заменил '=МИН(K2-M2;0)' в N:N на '=K2-M2' и в Решателе выставил ограничение 'перерасход >= 0'  
Летает !{/post}{/quote}  
 
стоило чуть отвлечься "на покушать", а тут столько интересного... ))  
 
to С.М.  
да, Саша, летает вообще супер!!! огромное спасибо.  
можно резко обрезать время поиска и некоторые другие ограничения, результат с первого раза и наилучший.  
попробовал поменять план-остатки (в разумных пределах) - всё равно всё ОК!  
 
однако, с учётом тех ограничений, о которых говорил Владимир и того, о чём говорил я в п.5 в первом посте, наверное, придётся остановиться на таком варианте:    
1) в столбце N оставить формулы без МИН(), просто разность;  
2) в отдельных ячейках считать сумму отрицательных по диапазонам в N с помощью СУММЕСЛИ();  
3) подсунуть Решателю в качестве ограничения условие равенства этих ячеек нулю, точнее (с учетом допустимых погрешностей - условие >-0.001)  
 
такой вариант испробовал, летает чуть-чуть медленнее, но очень даже прилично. с первой версией и сравнивать стыдно. попадание в цель - на высшем уровне.  
 
to ZVI  
да, это я понял. 200 - это именно насчет ограничений? диапазон изменяемых может быть больше?    
тупой перебор, даже в VBA, на массивах - вряд ли имеет смысл, имхо. хотя о таком варианте я думал. другая альтернатива - реализация алгоритмов оптимизации в VBA. но для этого: алгоритмы надо найти; среди них надо выбрать наиболее оптимальные по скорости, точности и т.п.; алгоритмы надо запрограммировать.  
если Вы, Владимир, с разбегу сможете порекомендовать неск-ко интернет-ресурсов (именно интернет, с бумажными книгами - как последний вариант) с такими алгоритмами - буду благодарен. наличие кодов на языках программирования или готовых DLL-ек совсем необязательно, даже вредно :)    
 
пс. да, я наглый, и, разогнавшись, иногда прошу слишком много. :((  
если что - не обижусь, т.к. кроме наглости ещё и понятливый :)  
 
всё остальное, то что в Вашем последнем P.S...  
оценка потенциальных убытков от нерационального использования ресурсов - это отдельная песня на нашем предприятии. честно говоря, с нашим начальством (не путать с хозяином! тот вообще недоступен) связываться не хочется совершенно. это... ммммм... нехорошие люди. я сегодня дочитал книжку А.Г.Орлова "Записки автоматизатора. Профессиональная исповедь" - так вот, всё, что там написано о небожителях, гениях и прочем негативе - на 100% имеется у нас.    
впрочем, безвыходных ситуаций (говорят:) не бывает, спасибо за совет. собственная лень и безынициативность - это тоже имеется. 100% :)
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
э, нет... :(  
прочитал внимательней: всё как раз наоборот - Владимир пишет именно про 200 изменяемых переменных :(  
но - решение он предложил, пойду думать.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
Александр, 200 - это всего, включая ячейки ограничения и целевую ячейку.  
 
Вот некоторые сохраненные ссылки по схожей тематике:  
 
1. Проект ALGLIB с открытыми исходными текстами: http://alglib.sources.ru/  
Одномерная и многомерная оптимизация http://alglib.sources.ru/optimization/  
Статья «Перебор и его сокращение» http://alglib.sources.ru/articles/perebor.php  
 
2. Оптимизация перебора вариантов, раскроя и т.п.:  
http://www.sql.ru/forum/actualthread.aspx?tid=354995  
http://www.sql.ru/forum/actualthread.aspx?tid=539855  
http://www.sql.ru/forum/actualthread.aspx?tid=594996  
http://www.sql.ru/forum/actualthread.aspx?tid=634152  
http://www.sql.ru/forum/actualthread.aspx?tid=662918  
http://www.sql.ru/forum/actualthread.aspx?tid=826744  
http://www.mrexcel.com/pc09.shtml  
http://www.tushar-mehta.com/excel/templates/match_values/index.html  
 
Можно посмотреть в сторону других уже готовых Solver-ов.  
Существуют множество библиотек различных алгоритмов оптимизации, в том числе,  с открытыми текстами (не халява, а с соответствующей лицензией), в основном на  C++.  
Но конкурировать самому с дорогими продаваемыми вряд ли правильно. Для универсальных задач разумнее покупать что-то готовое.  
А вот для своих конкретных задач можно правильно продумать модель, придумать частный алгоритм и написать свою обработку.  
 
При большом количестве переменных решения рассчитывать на поиск глобального максимума не разумно, так как  это по срокам вычисления может быть не совместимо со сроком  человеческой жизни.  Лучше ограничить количество вариантов перебора в расчете на поиск приемлемого локального решения,  приносящего достаточную прибыль.
 
попробовал.  
ровно 200 ячеек в поле "Изменяя ячейки:"    
плюс целевая ячейка,  
плюс два массива ограничений изменяемых ячеек,  
плюс ограничения ещё на две ячейки.  
 
работает.  
правда, тормоза жуткие.  
 
 
итоги по вопросам из первого поста (так, как я понял):  
1. модель в целом правильна, каких-либо глобальных улучшений нет, но улучшения "по мелочам", особенно в части условий ограничений, эффект приносят порой ошеломительный - отдельное спасибо С.М.;  
2. с настройками более-менее тоже разобрались - МСН, С.М., ZVI подковали и теоретически, и практически;  
3. по этому вопросу ясности нет, после дополнительных экспериментов пока решил устанавливать всегда нули;  
4. решил;  
5. увы. самый большой облом. буду думать над разбиением задачи на части;  
6. стоит, конечно. вопрос был немного глуповат, просто неявно подразумевалось, что сроки достаточно жёсткие, надо будет осваивать и интерфейс, и сам решатель, и, возможно, что-то ещё... пока решил - не буду. должен остаться резерв повышения производительности труда :)))  
 
плюс куча бонусов от ZVI.  
 
итого - тему можно считать закрытой, при том, что она практически неисчерпаема :)  
всем большое спасибо.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
Страницы: 1
Читают тему
Наверх