На складе имеются остатки по товарам. Склад получает некоторое количество заказов в один момент. Нужно собрать максимальное количество заказов, пользуясь остатками на данный момент. Заказ считается собранным, если он собран по стоимости на 90% от его стоимости.  Цены на одинаковые товары из разных заказов одинаковы. (Общая стоимость заказа 100р, если насобирать товара чтобы общая сумма получилась не меньше 90р, то заказ считается собранным). Так же хотелось бы сделать решение, чтобы 90% можно было задавать перед расчетом, т.е. 80% или иную цифру.
Подскажите хотя бы к какому классу задач линейного программирования она относится(если я не ошибся с ЛП), ну а вообще хотелось бы узнать метод решения, и если их несколько то несколько. Если есть что почитать толковое скиньте ссылки. Зарание спасибо

Прикольно, а вы как заказы принимаете? По остаткам на складе?

Похоже на СЛАУ, но я бы руки оторвал постановщику.

Клиенту говорим: - Мужик, понимаешь. Мы тут тебе на 90 % подобрали остатков. Ты доволен? А если я дом строю и мне только цемент не дали, то это как нормально?

рюкзак

(2) То рюкзак, а то заказы...

(2)+ но ты упаришься целевую функцию описывать

(3) он про класс задач спрашивал. это — «рюкзак»

(1)Ну условия придумывал не я, так мне сказали. Нет это не мы так принимаем, это сторонний заказчик.
(2)Точно? Что-то меня сомнения взяли, но я не слишком силен в этой области.
(4)Да в этом загвоздка и возникла, не смог я целевую описать.

такая задачка у франчей тянет тыщь на 300 не меньше...

(7)Везет им:) у меня на 10 максимум:) Да дело то не в этом, мне нравятся такие задачи, только я пока еще учусь их решать.

(8) если ты думаешь что я шучу, то ты ошибаешься...

Обращу внимание еще раз на рюкзак спасибо. Если есть еще какие соображения пишите не откажусь.

(9)Я не думаю что ты шутишь.

+(11)Но как я говорил дело не в этом, мне интересно решить или скатав решение понять как решается, короче осознать для себя что за задача и с чем ее едят, деньги меня не волнуют.

нифига там не рюкзак. рюкзак позволяет затолкать по максимуму/минимуму. а тут куча рюкзаков с линейным распределением.

Вот я тоже подумал что какой-то комбинированный рюкзак или я что-то не догоняю

+(14)Собственно поэтому и отошел изначально от идеи что эта задача из класса Рюкзак

Нормальная задача нахождения максимума. Ничего так для генетического алгоритма. Опиши требования к Геному как функцию максимума, каждый ген как часть заказа.  И пошел перебирать их ))) Так тоже можно решать. Только зачем.

(7) Это минимум, ибо результат не понятен, по которому сдавать эту задачу

А терь по вопросам:
1. Продажа идет единицах измерения прихода, или  в отличных от них
2. Разукомлектовывается номенклатура
3. Заказы менее 90% собираются или нет.
4. В случае ненахождения товара, мы опять нормируем заказы или нет?

Ну и куча всех вопросов вытекающих отсюда ;-)

(0) > Нужно собрать максимальное количество заказов

Точно количество или все же общую стоимость максимизируем?

(18)1)Прихода, чтоб не заморачиватся представьте что все в штуках и приходит и хранится.
2.Непонял
3.Да собираются
4.Что значит опять нормируем? Не можем все собрать так не можем.
(19)Число заказов максимизируем. Про стоимость задача не стоит, но наверное добавят условие:) Точнее было бы логичнее собрать из одинково возможного количества более дорогие заказы.

Заказчик сам не понимает множества вариантов решения. Например, можно специально формировать неполные заказы по 90%, чтобы отгрузить макс. кол-во заказов. Но, скорее всего, он это не имел в виду. Формируй ТЗ с остатками, перебирай заказы поочереди, если не менее 90% - заполняй заказ в отдельную ТЗ, где будут все удачные заказы и уменьшай остатки в ТЗ с остатками

(21)Заказчик то как раз понимает, т.к. делает эту херню вручную как получится:)
Изначально конечно специльно формируешь на 90% а потом довешиваешь, если остается свободный остаток.

Формируй ТЗ с остатками, перебирай заказы поочереди, если не менее 90% - заполняй заказ в отдельную ТЗ, где будут все удачные заказы и уменьшай остатки в ТЗ с остатками - что-то я думаю я так не выйду на максимальное закрытие заказов.

(20) >> 2. Разукомлектовывается номенклатура
если у тебя коробка товара, то ее могут разобрать на "штуки" из коробки? Как тогда будет выглядеть заказ? Если у тебя есть коробка товара, но по одной штуке из разных коробок, они могут собраться в коробку?

(22) Предлагаю разбить ТЗ на два: простая аналитика и сложная. Простая аналитика - по моему алгортиму, т.е. последовательный перебор заказов, отбраковкой неполных и уменьшения доступного остатка. Объясни заказчику, что эта простая будет работать гарантированно всегда и оцени ее в столько-то. Реализуй, пусть несколько дней поиграются - потом подойди к обсуждению сложной аналитики, как раз они, возможно, предложат направление усовершенствования простой аналитики.

Не какое не линейное программирование .даже в лом описывать алгоритм подобного задания вам

(0) Придумал как сделать

1. Формируешь ТЗ из доступных остатков
2. Формируешь ТЗ потребностей товаров из всех заказов. Отсортируй по возрастанию цены и кол-ва.
3. Берешь первый самый дорогой и штучный товар и и пытаешься удовлетворить в нем потребность по заказам. Преверяешь, по мепе добавления, не достигла ли сумма заказа 90% от общего. Если достигла - этот заказ переносим в отделную ТЗ.
4. Далее берем второй товар и проделываем тоже самое...
5. Когда пройдены все заказы, проходим еще раз по удачным заказам и пытаемся их дополнить оставшимся товаром от 90 до 100%

Алгоритм хороший и с точки зрения маркетинга - в первую очередь распродаем жорогой и штучнй (возможно, неходовой товар)

(23)Все в штуках:)
(24)Скажем так этот этап уже пройден.
(25)Интересный ответ:)
(26)Не получится оптимальное решение.

(27) Почему? Подумай хорошенько, алгоритм позволит пренебречь дешевым и массовым товаром, который и так продается хорошо. Зря отвергаешь, готов реализовать этот алгоритм в виде продцедуры за 100-150 долларов, если дашь на входе таблицу с остатками и товаром в разрезе заказов, колва и суммами.

Не надо усложнять вполне реализуемые задачи. Если твоей квалификации не хватает в данной сфере- обсуди предложенный алгоритм с заказчиком, уверен, что он одобрит.

(28)Не, платить я не буду. С заказчиком обсудить это будет весело, он ничего не поймет, но у меня будет работу проверять начальник и он сразу отметет такой вариант:)

Берешь первый самый дорогой и штучный товар и и пытаешься удовлетворить в нем потребность по заказам - одного заказа удовлетворил потребность, второго, а на третий не хватило, что делать?

(29) С транспортной разобрался?

(29) Переходишь ко второму товару, более дешевому и с большей потребностью, проходишь по всем заказам его содержавщим. И так, пока заказы не начнут выпадать из обработки, набрав 90% общей стоимости заказа.

Кстати, можно усовершенствовать алгоритм, добавив в первоначальную сортировку потребности в товаре не только по возрастанию цены и кол-ва, но и по отношению наличия товара к потребности, умноженному на 100, т.е. по возможности в % удовлетворить потребность наличием товара на складе.

Можно еще добавить колонку с кол-вом заказов на каждый товар.

(0) Причем тут ЛП. все решается банальными проверками и условиями

+ т.е. побрав нужные колонки и направление сортировки для сводной таблицы с потребностью товара - получишь правильную последовательсть обработки товара.

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

(13) каждый заказ - это ограничение. Точнее, несколько ограничений, соответствующих тому, чтоб не отгрузить больше чем заказано.
И, естественно, ограничения по остатками.
Хотя скорее всего при чисто математическом подходе могут абсолютно "нечеловеческие" решения получаться.

(30)У меня вопрос возник а ту втек, залазь в тс я тебя еще помучаю:)

(31)Вот если с процентами то такой метод я сам думал наваять если ничего не придумаю, только он не оптимален.

(34)(35)На счет системы неравенст уравнений и ограничений я понял, я целевую функцию не смог составить и не знаю каким методом решать.

Вообще-то задача на перебор вариантов.
У нас конечное число заказов и конечное число товара.
Мы должны выбрать максимум по критерию заполненности заказов.

в (26) хороший вариант предложили

для избежания "залеживания" дорогих товаров и "перенасыщения" дешевыми можно ввести критерий ликвидности

В отдельную ТЗ запросом вывести анализ уже заказанных товаров ранее и для каждого товара посчитать соотношение "цена*количество/общая сумма заказов за период"

то есть в долях, какой товар какую долю за период составляет

(39)Понятно что перебор неизбежен, каким образом его осуществлять?
(40)Можно долго беседовать по данному методу, но он не даст нужного результата.

Можно тупо перебором догнать до процента выполнения, затем - второй проход, добить
Можно посчитать частоту встречаемости товара в заказе, его общую потребность и сравнить с остатком. Начать с наиболее востребованных и дорогих товаров. Т.е. плясать от списка товаров как будто имеем дело с одним большим заказом. Считать что каждая такая итерация (товар) наполняет некий средний по стоимости заказ. Но это все равно не точно, так что имхо не стоит заморачиваться :)

(41) классическая задачка оптимизации, перебор тут конечно не того, пятое колесо, попробуй тот же  симплекс-метод.. Помогать не буду, чтоб тебе не помешать насладиться процессом решения.. оч. интересно..

(38) Целевая функция -- самое главное. Все методы лишь оптимизируют ее. Попытайся хотя бы устно со слов клиента ее выяснить. Или составь сам, предложи, пусть клиент думает

Постановка задачи здесь - http://zalil.ru/33162161

(0) 50000

+(45) Решение - симплекс-метод. При вычислении дельт - необходимо учитывать дополнительные вариации количества и выполнения заказа. Как это сделать быстро - хз, но главное, что решение существует. Ессно - из матрицы можно выкидывать те позиции, которых точно хватает, с учетом эластичности (только не забываем пропорционально уменьшать требования к суммам заказов, то есть к количеству по остальным позициям).

+(45) Подправил второе неравенство в условиях (не хватало сумм по верхним границам)
http://zalil.ru/33162175

+(48) Добавил условие принадлежности неизвестных v множеству Z
http://zalil.ru/33162183

(48),(49) +100
Только вот работает ли симплекс-метод, когда нужно искать целочисленные решения? Подозреваю, что вряд ли.
Опять же условия выполнения заказа - ступенчатые.
А самое главное, подозреваю,что математических ограничени для жизни недостаточно.
Обычно еще всегда накладываются условия по приоритетам.
Типа, если клиент - торговая сеть, то ей всегда все в первую очередь и на 100%... А остальные - перетопчутся.

(49)Спасибо. Вопрос правда был в другом:) Мы оттолкнулись что эта задача транспортная, но учитывая (49) она не транспортная(возможно ошибаюсь) плюс возник вопрос как уже сказали при решении симплекс методом получатся дробные решения. Может методом ветвей и границ для целочисленного линейного программирования?

(51) Это -- рюкзак. Транспортная -- она другого типа. А у тебя рюкзак, где заказы -- "вещи"

Честно говоря, на ЭВМ симплекс-методом не решал, только эволюционным. На русском, к сожалению, нет у меня того документа

(51) Не транспортная. Вектор А неоднороден. Общая задача линейного ЛП, весьма похожая (за исключением вариативности по нормам) на задачу нахождения оптимального производственного плана. Насчет дробных решений - я уже писал в (49), это решается при вычислении дельта-матриц. Лично я проблему вижу в другом. Если m>>n быстро растёт вычислительная сложность. 1C вполне может и загнуться.

(51) Это не рюкзак. Скорее - дольный граф с узловыми сочетаниями высоких порядков. Впрочем, главное - что это задача ЛП, значит симплекс-метод должен работать. Главное - закодировать. Т.е. избавиться от агрегата {О}. Как - пока не придумал. Начать с перебора, а там чего-нить надумаем)))))

ЗЫ Подправил последнее условия (исправлены ошибки записи двойной суммы)
http://zalil.ru/33163412