Как бы вы решили олимпиадную задачу для студентов по программированию на 1с? #649216

Для хранения спецодежды на предприятии используется три склада. Предприятие ведет бухгалтерский учет в программе "1С:Бухгалтерия 8". Учет спецодежды ведется в составе материальных запасов на счете 10 в разрезе субконто "Материалы" и "Склады" в стоимостном и натуральном выражении. Оценка материальных запасов производится по средневзвешенной цене, которая определяется отдельно для каждого материала по предприятию в целом. В информационной базе предприятия зафиксированы остатки спецодежды на 1 апреля 2012 г. по каждому наименованию спецодежды и по каждому складу. Предприятие решает ликвидировать один из складов для хранения спецодежды, а остатки спецодежды с этого склада переместить на два оставшихся склада таким образом, чтобы стоимостная оценка запасов спецодежды на этих двух складах по возможности составляла бы одинаковую величину или, если это невозможно, различалась бы минимально. При этом следует исходить из того, что перемещать исходные запасы спецодежды между неликвидируемыми складами запрещено. Требуется В каркасной конфигурации разработать программу, которая анализирует текущие остатки спецодежды на складах и формирует отчет, содержащий две таблицы. В первой таблице отображается текущее наличие запасов спецодежды на складах и определяется средняя цена для каждого наименования спецодежды.

Кроме симплекс метода ничего не придумал с ходу.

БУГАГА! Дафпесту.

позвал бы прога 1с и дал ему задание.

Да там задача к 1С опосредованное отношение имеет. На любом языке можно эту же задачу решать.

сто пудов, только  симплекс метод!

Так он тоже оптимального решения не даст. Даже какой-нибудь случайный перебор может дать лучшее решение.

симлекс даст лучшее решение. Но можно решать направленным перебором с отсечениями.

+ в порядке уменьшения

да, естественно.

Вот олимпийская задачка:

Я может что то путаю, но исходя из задачи можно подобрать такую комбинацию товара так что сумма на обоих складах будет одинакова. Симплекс метода может не привести к тому же результату.

Это олимпиада телепатов?

серьезно? Чего симлекс метод может не дать?

Все вспомнил. Туплю. Прошу прощения.

симплекс метода недостаточно, задача-то целочисленная, иначе чего ей делать на олимпиаде.

Задача о рюкзаке сводится к чистому симлекс методу. А это она и есть.

Но лучше решать перебором с отсечениями.

это расширение симплекс метода. "чистый" симплекс метод допускает действительные решения

Нет, это способ решения задач целочисленного линейного программирования симлекс методом.

а нафига вообще огород городить? тут переменная одна, остальное константы.

Тут не одна переменная. С каких пор в задаче о рюкзаке одна переменная? Тут нужно найти целочесленный оптимальный вектор согласно условиям.

в Тема нашей Глыбе, задам она .... в шоке )))

тут переменная одна симплекс метод

Для каждой спецодежды нужно найти количество. Тут переменный вектор, чистая задача о рюкзаке. Решить можно например так -

Пусть на первом складе остатков на сумму а, на втором на сумму в, на третьем на сумму с. Если а>=b+c, то весь остаток посылаем на второй склад, если b>=a+c, то весь остаток посылаем на первый склад. Иначе подбираем с отсечениями начиная с самых дорогих сумму(с-abs(a-b))/2 и закидываем на склда с большим остатком.

А точнее - последним пунктом решаем задачу о рюкзаке любым из известных способов.

ты  правильно сказал,сам ты запутался ,+61 и 62

Зачем два одинаковых по сумме склада нужны?

если нужно неоптимальное решение - то это просто: 1.считаем средневзвешенное на 1 складе и на втором (не просто считаем а готовим показатели для пересчёта при очередном изменении (т.е. сумму и кол-во)). 2.сортируем товар неликвида по стоимости в порядке убывания. 3.ну и погнали в цикле: пусть на очередном шаге по товару СПЕЦКУРТКА на складе А себестоимость > себестоимости этого товара на складе Б, то отправляем этот товар с ликвидируемого склада(по 1 шт) в склад с меньшей себестоимостью в том случае если цена единицы будет больше стоимости на складе Б или на склад А если будет меньше... но много шагов.. можно оптимизировать отправляя сразу такое кол-во, что-бы оно выравнивало себестоимость (рассчитывается в несколько арифм. операций), но не более остатка этого товара на ликвидируемом складе... если после округдения получим =0, то отправляем 1 шт т.к. всёравно нужно по этим складам расфасовать. ну это типа как в первом приближении, можно ещё оптимальнее схему нарисовать но нужно уже брать в руки ручку, марать бумагу...

ЗЫ: Это я про прикладное, а не про академическое применение решения.

Оценка материальных запасов производится по средневзвешенной цене, которая определяется отдельно для каждого материала по предприятию в целом. В информационной базе предприятия зафиксированы остатки спецодежды на 1 апреля 2012 г. по каждому наименованию спецодежды и по каждому складу. то есть еще и политика поменялась, раньше склады учитывались - теперь нет

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

В Excel/MathCAD расчеты провел бы - проще паренной репы, а потом в 1С данные об остатках и стоимости одежды на складах задолбил бы.

Нецелые количества спецодежды?

Рукав на один склад, полу - на другой.:-) А про нецелые количества я написал в связи с упоминаем симплекс-метода. Целочисленный вариант тоже описан.

Целочисленный вариант - это задача о рюкзаке.

. Почти согласен (в том, что "рюкзачные" методы могут подойти): давайте постановку и сведение к рюкзаку.

, см.

гыы, задание по 1с уже на олимпиадах по программированию в универе. В топку такие универы.

получить разницу между складами, разбить перемещаемое на достаточно мелкие наборы и перемещать. для простоты эту разницу "перевернуть", представить остатком, дополнить суммы остатка тем, что окажется лишним после уравнивания, и вперед

Это способ решения, а не сведение к ранцу.

@Ns, а в типовых нет реализации?

Непонял. Последний пункт это что?

Я действительно написал все-го лишь метод решения, но последним пунктом в этом методе - рюкзак.

Нет конечно.

"Рюкзаком" можно, конечно, назвать широкий класс похожих задач, но "классически" это переменные 0 или 1 и максимизация суммы при ограниченном весе. Не уверен, что в олимпиадной задаче в условиях ограниченности времени целесообразно реализовывать схему ветвей и границ, но при обсуждении здесь, наверное, не лишне "проявить" математический характер задачи и дать ссылку на известные подходы к ее решению. Правда, не уверен, что автор топика понял, о чем идет речь.

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

Число переменных неоправданно разрастается: будет выбран тот или иной конкретный экземпляр сапог неважно. Я бы так исходную задачу не переформулировал. Кроме того, однозначно лучшего метода для рюкзака нет: часто достаточно жадного алгоритма.

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