Вход | Регистрация


1С:Предприятие :: Математика и алгоритмы

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

Как бы вы решили олимпиадную задачу для студентов по программированию на 1с?
Я
   Doomer
 
25.01.13 - 22:58
сходная ситуация

Для хранения спецодежды на предприятии используется три склада.

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

В информационной базе предприятия зафиксированы остатки спецодежды на 1 апреля 2012 г. по каждому наименованию спецодежды и по каждому складу.

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

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

В первой таблице отображается текущее наличие запасов спецодежды на складах и определяется средняя цена для каждого наименования спецодежды.
http://fa-kit.ru/main_dsp.php?top_id=22317
 
 
   Doomer
 
1 - 25.01.13 - 22:58
Кроме симплекс метода ничего не придумал с ходу.
   Бешеная Нога
 
2 - 25.01.13 - 23:01
БУГАГА! Дафпесту.
   saasa
 
3 - 25.01.13 - 23:02
позвал бы прога 1с и дал ему задание.
   Doomer
 
4 - 25.01.13 - 23:03
(3) Да там задача к 1С опосредованное отношение имеет. На любом языке можно эту же задачу решать.
   Neg
 
5 - 25.01.13 - 23:06
сто пудов, только  симплекс метод!
   Doomer
 
6 - 25.01.13 - 23:07
(5) Так он тоже оптимального решения не даст. Даже какой-нибудь случайный перебор может дать лучшее решение.
   NS
 
7 - 25.01.13 - 23:10
(6) симлекс даст лучшее решение. Но можно решать направленным перебором с отсечениями.
   Alsh
 
8 - 25.01.13 - 23:10
(7) + в порядке уменьшения
   NS
 
9 - 25.01.13 - 23:11
(8) да, естественно.
   GROOVY
 
10 - 25.01.13 - 23:14
Вот олимпийская задачка: v8: Алгоритм: перебор месяцев в периоде
 
 Рекламное место пустует
   Doomer
 
11 - 25.01.13 - 23:14
(9) Я может что то путаю, но исходя из задачи можно подобрать такую комбинацию товара так что сумма на обоих складах будет одинакова. Симплекс метода может не привести к тому же результату.
   Doomer
 
12 - 25.01.13 - 23:15
(10) Это олимпиада телепатов?
   NS
 
13 - 25.01.13 - 23:16
(11) серьезно? Чего симлекс метод может не дать?
   Doomer
 
14 - 25.01.13 - 23:17
(13) Все вспомнил. Туплю. Прошу прощения.
   Asmody
 
15 - 26.01.13 - 00:52
симплекс метода недостаточно, задача-то целочисленная, иначе чего ей делать на олимпиаде.
   NS
 
16 - 26.01.13 - 00:52
(15) Задача о рюкзаке сводится к чистому симлекс методу.
А это она и есть.
   NS
 
17 - 26.01.13 - 00:56
   NS
 
18 - 26.01.13 - 00:58
Но лучше решать перебором с отсечениями.
   Asmody
 
19 - 26.01.13 - 00:59
(17) это расширение симплекс метода. "чистый" симплекс метод допускает действительные решения
   NS
 
20 - 26.01.13 - 01:00
(19) Нет, это способ решения задач целочисленного линейного программирования симлекс методом.
   Asmody
 
21 - 26.01.13 - 01:03
а нафига вообще огород городить? тут переменная одна, остальное константы.
   NS
 
22 - 26.01.13 - 01:08
(21) Тут не одна переменная. С каких пор в задаче о рюкзаке одна переменная? Тут нужно найти целочесленный оптимальный вектор согласно условиям.
   Lionee
 
23 - 26.01.13 - 01:15
в (0) Тема нашей Глыбе, задам она .... в шоке )))
   Lionee
 
24 - 26.01.13 - 01:18
тут переменная одна 
 симплекс метод
   NS
 
25 - 26.01.13 - 01:21
(24) Для каждой спецодежды нужно найти количество.
Тут переменный вектор, чистая задача о рюкзаке.
Решить можно например так -
Нужен алгоритм набора нужной суммы
   NS
 
26 - 26.01.13 - 01:30
Полное решение -
Пусть на первом складе остатков на сумму а, на втором на сумму в, на третьем на сумму с.
Если а>=b+c, то весь остаток посылаем на второй склад,
если b>=a+c, то весь остаток посылаем на первый склад.
Иначе подбираем с отсечениями начиная с самых дорогих сумму(с-abs(a-b))/2 и закидываем на склда с большим остатком.
   NS
 
27 - 26.01.13 - 01:30
А точнее - последним пунктом решаем задачу о рюкзаке любым из известных способов.
   Lionee
 
28 - 26.01.13 - 01:38
Нужен алгоритм набора нужной суммы
ты  правильно сказал,сам ты запутался ,+61 и 62
   ILM
 
29 - 26.01.13 - 04:55
Зачем два одинаковых по сумме склада нужны?
   rphosts
 
30 - 26.01.13 - 06:50
(0)если нужно неоптимальное решение - то это просто:
1.считаем средневзвешенное на 1 складе и на втором (не просто считаем а готовим показатели для пересчёта при очередном изменении (т.е. сумму и кол-во)).
2.сортируем товар неликвида по стоимости в порядке убывания.
3.ну и погнали в цикле:
пусть на очередном шаге по товару СПЕЦКУРТКА на складе А себестоимость > себестоимости этого товара на складе Б, то отправляем этот товар с ликвидируемого склада(по 1 шт) в склад с меньшей себестоимостью в том случае если цена единицы будет больше стоимости на складе Б или на склад А если будет меньше...

но много шагов.. можно оптимизировать отправляя сразу такое кол-во, что-бы оно выравнивало себестоимость (рассчитывается в несколько арифм. операций), но не более остатка этого товара на ликвидируемом складе... если после округдения получим =0, то отправляем 1 шт т.к. всёравно нужно по этим складам расфасовать.

ну это типа как в первом приближении, можно ещё оптимальнее схему нарисовать но нужно уже брать в руки ручку, марать бумагу...
   SilverMan
 
31 - 26.01.13 - 08:03
"Нарисовать 7 перпендикулярных линий..."(с)

ЗЫ: Это я про прикладное, а не про академическое применение решения.
   НафНаф
 
32 - 26.01.13 - 09:26
Оценка материальных запасов производится по средневзвешенной цене, которая определяется отдельно для каждого материала по предприятию в целом.

В информационной базе предприятия зафиксированы остатки спецодежды на 1 апреля 2012 г. по каждому наименованию спецодежды и по каждому складу.

то есть еще и политика поменялась, раньше склады учитывались - теперь нет
   Михаил Козлов
 
33 - 28.01.13 - 11:45
1. Если перемещаемые количества могут быть нецелыми, то задача сводится к решению 1 линейного уравнения в положительных переменных. Можно и симплекс-методом, но в данном случае решение (одно из решений, т.к. их много) ищется проще.
2. В случае целочисленности переменных, если требуется точное равенство сумм, задача состоит в решении 1 линейного уравнения в неотрицательных целых. Решения может и не быть, но, в общем случае, чтобы в этом удостовериться, может понадобиться полный перебор.
Если требуется по возможности приблизиться к равенству сумм ("минимизировать" отклонение сумм), можно попробовать какую-нибудь разумную эвристику. Например, начав с самых дорогих товаров пытаться за счет распределения очередного товара добиваться равенства сумм. Тогда отклонение сумм не будет превышать цены самого дешевого товара.
 
 
   GANR
 
34 - 28.01.13 - 11:50
(0)В Excel/MathCAD расчеты провел бы - проще паренной репы, а потом в 1С данные об остатках и стоимости одежды на складах задолбил бы.
   NS
 
35 - 28.01.13 - 11:53
(33) Нецелые количества спецодежды?
   Михаил Козлов
 
36 - 28.01.13 - 11:56
Рукав на один склад, полу - на другой.:-)
А (33) про нецелые количества я написал в связи с упоминаем симплекс-метода. Целочисленный вариант тоже описан.
   NS
 
37 - 28.01.13 - 11:56
(36) Целочисленный вариант - это задача о рюкзаке.
   Михаил Козлов
 
38 - 28.01.13 - 12:00
(37). Почти согласен (в том, что "рюкзачные" методы могут подойти): давайте постановку и сведение к рюкзаку.
   NS
 
39 - 28.01.13 - 12:01
(38), см. (26)
   Shurjk
 
40 - 28.01.13 - 12:01
гыы, задание по 1с уже на олимпиадах по программированию в универе. В топку такие универы.
   samozvanec
 
41 - 28.01.13 - 12:04
получить разницу между складами, разбить перемещаемое на достаточно мелкие наборы и перемещать. для простоты эту разницу "перевернуть", представить остатком, дополнить суммы остатка тем, что окажется лишним после уравнивания, и вперед
   Михаил Козлов
 
42 - 28.01.13 - 12:14
(39) Это способ решения, а не сведение к ранцу.
   Новенький_2009
 
43 - 28.01.13 - 12:16
@Ns, а Нужен алгоритм набора нужной суммы в типовых нет реализации?
   NS
 
44 - 28.01.13 - 12:20
(42) Непонял. Последний пункт это что?
   NS
 
45 - 28.01.13 - 12:23
Я действительно написал все-го лишь метод решения, но последним пунктом в этом методе - рюкзак.
   NS
 
46 - 28.01.13 - 12:23
(43) Нет конечно.
   Михаил Козлов
 
47 - 28.01.13 - 12:38
(45) "Рюкзаком" можно, конечно, назвать широкий класс похожих задач, но "классически" это переменные 0 или 1 и максимизация суммы при ограниченном весе.
Не уверен, что в олимпиадной задаче в условиях ограниченности времени целесообразно реализовывать схему ветвей и границ, но при обсуждении здесь, наверное, не лишне "проявить" математический характер задачи и дать ссылку на известные подходы к ее решению. Правда, не уверен, что автор топика понял, о чем идет речь.
   NS
 
48 - 28.01.13 - 12:43
(47) считай каждый штуку предмета отдельным предметом. И ставь ноль либо один. Но на самом деле формулировка задачи о рюкзаке. Нет там нуля и единицы, а есть набор предметов.

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

Данная задача (последний пункт описанного мной метода в (26)) - это чистый рюкзак.
   Михаил Козлов
 
49 - 28.01.13 - 12:55
(48) Число переменных неоправданно разрастается: будет выбран тот или иной конкретный экземпляр сапог неважно.
Я бы так исходную задачу не переформулировал. Кроме того, однозначно лучшего метода для рюкзака нет: часто достаточно жадного алгоритма.
 
 Рекламное место пустует
   NS
 
50 - 28.01.13 - 13:00
(49) Я и пишу - не надо переформулировать.
В общей задаче о рюкзаке нет условия что каждого предмета по одной штуке. Есть формулировка что количество каждого целочисленно, и либо ограничено, либо неограничено (это тоже задача о рюкзаке).
Способов решения есно куча, начиная с динамического программирования, и заканчивая подбором точной суммы решением системы линейных уравнений.


Список тем форума
Рекламное место пустует  Рекламное место пустует
Миста — веселый ресурс со своими эксклюзивными тараканами Ymryn
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует