#0
by Domovoi
На складе имеются остатки по товарам. Склад получает некоторое количество заказов в один момент. Нужно собрать максимальное количество заказов, пользуясь остатками на данный момент. Заказ считается собранным, если он собран по стоимости на 90% от его стоимости. Цены на одинаковые товары из разных заказов одинаковы. (Общая стоимость заказа 100р, если насобирать товара чтобы общая сумма получилась не меньше 90р, то заказ считается собранным). Так же хотелось бы сделать решение, чтобы 90% можно было задавать перед расчетом, т.е. 80% или иную цифру. Подскажите хотя бы к какому классу задач линейного программирования она относится(если я не ошибся с ЛП), ну а вообще хотелось бы узнать метод решения, и если их несколько то несколько. Если есть что почитать толковое скиньте ссылки. Зарание спасибо
#1
by ILM
Прикольно, а вы как заказы принимаете? По остаткам на складе? Похоже на СЛАУ, но я бы руки оторвал постановщику. Клиенту говорим: - Мужик, понимаешь. Мы тут тебе на 90 % подобрали остатков. Ты доволен? А если я дом строю и мне только цемент не дали, то это как нормально?
#6
by Domovoi
Ну условия придумывал не я, так мне сказали. Нет это не мы так принимаем, это сторонний заказчик. Точно? Что-то меня сомнения взяли, но я не слишком силен в этой области. Да в этом загвоздка и возникла, не смог я целевую описать.
#8
by Domovoi
Везет им:) у меня на 10 максимум:) Да дело то не в этом, мне нравятся такие задачи, только я пока еще учусь их решать.
#10
by Domovoi
Обращу внимание еще раз на рюкзак спасибо. Если есть еще какие соображения пишите не откажусь.
#12
by Domovoi
+Но как я говорил дело не в этом, мне интересно решить или скатав решение понять как решается, короче осознать для себя что за задача и с чем ее едят, деньги меня не волнуют.
#13
by aleks-id
нифига там не рюкзак. рюкзак позволяет затолкать по максимуму/минимуму. а тут куча рюкзаков с линейным распределением.
#16
by ILM
Нормальная задача нахождения максимума. Ничего так для генетического алгоритма. Опиши требования к Геному как функцию максимума, каждый ген как часть заказа. И пошел перебирать их ))) Так тоже можно решать. Только зачем.
#18
by Krendel
А терь по вопросам: 1. Продажа идет единицах измерения прихода, или в отличных от них 2. Разукомлектовывается номенклатура 3. Заказы менее 90% собираются или нет. 4. В случае ненахождения товара, мы опять нормируем заказы или нет? Ну и куча всех вопросов вытекающих отсюда ;-)
#19
by mistеr
> Нужно собрать максимальное количество заказов Точно количество или все же общую стоимость максимизируем?
#20
by Domovoi
1)Прихода, чтоб не заморачиватся представьте что все в штуках и приходит и хранится. 2.Непонял 3.Да собираются 4.Что значит опять нормируем? Не можем все собрать так не можем. Число заказов максимизируем. Про стоимость задача не стоит, но наверное добавят условие:) Точнее было бы логичнее собрать из одинково возможного количества более дорогие заказы.
#21
by Jackman
Заказчик сам не понимает множества вариантов решения. Например, можно специально формировать неполные заказы по 90%, чтобы отгрузить макс. кол-во заказов. Но, скорее всего, он это не имел в виду. Формируй ТЗ с остатками, перебирай заказы поочереди, если не менее 90% - заполняй заказ в отдельную ТЗ, где будут все удачные заказы и уменьшай остатки в ТЗ с остатками
#22
by Domovoi
Заказчик то как раз понимает, т.к. делает эту херню вручную как получится:) Изначально конечно специльно формируешь на 90% а потом довешиваешь, если остается свободный остаток. Формируй ТЗ с остатками, перебирай заказы поочереди, если не менее 90% - заполняй заказ в отдельную ТЗ, где будут все удачные заказы и уменьшай остатки в ТЗ с остатками - что-то я думаю я так не выйду на максимальное закрытие заказов.
#23
by Steel_Wheel
>> 2. Разукомлектовывается номенклатура если у тебя коробка товара, то ее могут разобрать на "штуки" из коробки? Как тогда будет выглядеть заказ? Если у тебя есть коробка товара, но по одной штуке из разных коробок, они могут собраться в коробку?
#24
by Jackman
Предлагаю разбить ТЗ на два: простая аналитика и сложная. Простая аналитика - по моему алгортиму, т.е. последовательный перебор заказов, отбраковкой неполных и уменьшения доступного остатка. Объясни заказчику, что эта простая будет работать гарантированно всегда и оцени ее в столько-то. Реализуй, пусть несколько дней поиграются - потом подойди к обсуждению сложной аналитики, как раз они, возможно, предложат направление усовершенствования простой аналитики.
#25
by moshefoo
Не какое не линейное программирование .даже в лом описывать алгоритм подобного задания вам
#26
by Jackman
Придумал как сделать 1. Формируешь ТЗ из доступных остатков 2. Формируешь ТЗ потребностей товаров из всех заказов. Отсортируй по возрастанию цены и кол-ва. 3. Берешь первый самый дорогой и штучный товар и и пытаешься удовлетворить в нем потребность по заказам. Преверяешь, по мепе добавления, не достигла ли сумма заказа 90% от общего. Если достигла - этот заказ переносим в отделную ТЗ. 4. Далее берем второй товар и проделываем тоже самое... 5. Когда пройдены все заказы, проходим еще раз по удачным заказам и пытаемся их дополнить оставшимся товаром от 90 до 100% Алгоритм хороший и с точки зрения маркетинга - в первую очередь распродаем жорогой и штучнй (возможно, неходовой товар)
#27
by Domovoi
Все в штуках:) Скажем так этот этап уже пройден. Интересный ответ:) Не получится оптимальное решение.
#28
by Jackman
Почему? Подумай хорошенько, алгоритм позволит пренебречь дешевым и массовым товаром, который и так продается хорошо. Зря отвергаешь, готов реализовать этот алгоритм в виде продцедуры за 100-150 долларов, если дашь на входе таблицу с остатками и товаром в разрезе заказов, колва и суммами. Не надо усложнять вполне реализуемые задачи. Если твоей квалификации не хватает в данной сфере- обсуди предложенный алгоритм с заказчиком, уверен, что он одобрит.
#29
by Domovoi
Не, платить я не буду. С заказчиком обсудить это будет весело, он ничего не поймет, но у меня будет работу проверять начальник и он сразу отметет такой вариант:) Берешь первый самый дорогой и штучный товар и и пытаешься удовлетворить в нем потребность по заказам - одного заказа удовлетворил потребность, второго, а на третий не хватило, что делать?
#31
by Jackman
Переходишь ко второму товару, более дешевому и с большей потребностью, проходишь по всем заказам его содержавщим. И так, пока заказы не начнут выпадать из обработки, набрав 90% общей стоимости заказа. Кстати, можно усовершенствовать алгоритм, добавив в первоначальную сортировку потребности в товаре не только по возрастанию цены и кол-ва, но и по отношению наличия товара к потребности, умноженному на 100, т.е. по возможности в % удовлетворить потребность наличием товара на складе. Можно еще добавить колонку с кол-вом заказов на каждый товар.
#33
by Jackman
+ т.е. побрав нужные колонки и направление сортировки для сводной таблицы с потребностью товара - получишь правильную последовательсть обработки товара.
#34
by 25-11
Если формализовать чисто математически, то ограничения линейные, а целевая функция максимизации стоимости выполненных заказов будет кусочно-линейная.
#35
by 25-11
каждый заказ - это ограничение. Точнее, несколько ограничений, соответствующих тому, чтоб не отгрузить больше чем заказано. И, естественно, ограничения по остатками. Хотя скорее всего при чисто математическом подходе могут абсолютно "нечеловеческие" решения получаться.
#37
by Domovoi
Вот если с процентами то такой метод я сам думал наваять если ничего не придумаю, только он не оптимален.
#38
by Domovoi
На счет системы неравенст уравнений и ограничений я понял, я целевую функцию не смог составить и не знаю каким методом решать.
#39
by Torquader
Вообще-то задача на перебор вариантов. У нас конечное число заказов и конечное число товара. Мы должны выбрать максимум по критерию заполненности заказов.
#40
by К_Дач
в хороший вариант предложили для избежания "залеживания" дорогих товаров и "перенасыщения" дешевыми можно ввести критерий ликвидности В отдельную ТЗ запросом вывести анализ уже заказанных товаров ранее и для каждого товара посчитать соотношение "цена*количество/общая сумма заказов за период" то есть в долях, какой товар какую долю за период составляет
#41
by Domovoi
Понятно что перебор неизбежен, каким образом его осуществлять? Можно долго беседовать по данному методу, но он не даст нужного результата.
#42
by КонецЦикла
Можно тупо перебором догнать до процента выполнения, затем - второй проход, добить Можно посчитать частоту встречаемости товара в заказе, его общую потребность и сравнить с остатком. Начать с наиболее востребованных и дорогих товаров. Т.е. плясать от списка товаров как будто имеем дело с одним большим заказом. Считать что каждая такая итерация (товар) наполняет некий средний по стоимости заказ. Но это все равно не точно, так что имхо не стоит заморачиваться :)
#43
by Крепкий
классическая задачка оптимизации, перебор тут конечно не того, пятое колесо, попробуй тот же симплекс-метод.. Помогать не буду, чтоб тебе не помешать насладиться процессом решения.. оч. интересно..
#44
by Steel_Wheel
Целевая функция -- самое главное. Все методы лишь оптимизируют ее. Попытайся хотя бы устно со слов клиента ее выяснить. Или составь сам, предложи, пусть клиент думает
#47
by kot_bcc
+ Решение - симплекс-метод. При вычислении дельт - необходимо учитывать дополнительные вариации количества и выполнения заказа. Как это сделать быстро - хз, но главное, что решение существует. Ессно - из матрицы можно выкидывать те позиции, которых точно хватает, с учетом эластичности (только не забываем пропорционально уменьшать требования к суммам заказов, то есть к количеству по остальным позициям).
#50
by 25-11
, +100 Только вот работает ли симплекс-метод, когда нужно искать целочисленные решения? Подозреваю, что вряд ли. Опять же условия выполнения заказа - ступенчатые. А самое главное, подозреваю,что математических ограничени для жизни недостаточно. Обычно еще всегда накладываются условия по приоритетам. Типа, если клиент - торговая сеть, то ей всегда все в первую очередь и на 100%... А остальные - перетопчутся.
#51
by Domovoi
Спасибо. Вопрос правда был в другом:) Мы оттолкнулись что эта задача транспортная, но учитывая она не транспортная(возможно ошибаюсь) плюс возник вопрос как уже сказали при решении симплекс методом получатся дробные решения. Может методом ветвей и границ для целочисленного линейного программирования?
#52
by Steel_Wheel
Это -- рюкзак. Транспортная -- она другого типа. А у тебя рюкзак, где заказы -- "вещи"
#53
by Steel_Wheel
Честно говоря, на ЭВМ симплекс-методом не решал, только эволюционным. На русском, к сожалению, нет у меня того документа
#54
by kot_bcc
Не транспортная. Вектор А неоднороден. Общая задача линейного ЛП, весьма похожая (за исключением вариативности по нормам) на задачу нахождения оптимального производственного плана. Насчет дробных решений - я уже писал в , это решается при вычислении дельта-матриц. Лично я проблему вижу в другом. Если m>>n быстро растёт вычислительная сложность. 1C вполне может и загнуться. Это не рюкзак. Скорее - дольный граф с узловыми сочетаниями высоких порядков. Впрочем, главное - что это задача ЛП, значит симплекс-метод должен работать. Главное - закодировать. Т.е. избавиться от агрегата {О}. Как - пока не придумал. Начать с перебора, а там чего-нить надумаем))))) ЗЫ Подправил последнее условия (исправлены ошибки записи двойной суммы)
Тэги: 1С 8
Ответить:
Комментарии доступны только авторизированным пользователям
Похожие вопросы 1С
В этой группе 1С
- КнигаУчетаДоходовИРасходов
- v8: 1С:Розница 2 "Не смогли определить доступный магазин...
- &НаКлиентеНаСервереБезКонтекста помогите понять и разобраться что это
- Можно ли в управляемой форме выгрузит табличную часть документа в таблицу?
- v8: Запретить вход в конфигуратор в самописной конфигурации
- Шаблон Ворд и 1С
- Как программно добавить лидирующие нули
- Как выбрать список значений заданного реквизита из справочника
- Настройка прав доступа к отдельным объектам информационной базы
- Как быстро получить список всех доменов 3-его уровня ?
- Как получить значение строки табличной части документа
- Обмен УТ 10.3 БП 2.0 После обновления не пашет.
- При подключений по RDP запускается сразу 1С
- v7: Как получить данные из XML файла?
- Как записать форму при закрытии
- Как в СКД в параметрах указать счет дебета или кредита?
- Кто понимает как устроен отчет "Карточка счета" в 1С БП 2.0 ?
- v7: КЛАДР: задвоение городов
- Настройка весов CAS-LP 1.6
- Как получить СКД по счету по субконто?