Имя: Пароль:
1C
 
Алгоритм "Впихнуть невпихуемое"
0 1nvertex
 
30.03.17
00:18
На складе остатки товара:
Производитель1, Завод1 - 100 штук
Производитель1, Завод2 - 150 штук
Производитель2, Завод1 - 80 штук
Производитель2, Завод2 - 60 штук

Есть заказ:
Производитель1 (все равно какой завод) -  50 штук
Завод1 (все равно какой производитель) - 90 штук
Производиель2 (все равно какой завод) - 100 штук
Производиель1, Завод2 - 75 штук

Вопрос: Как проверить что заказ можно выполнить? (Алгоритм)
1 1nvertex
 
30.03.17
00:23
Вопрос№2: Какое количество максимально доступных остатков по каждому производителю и заводу и их сочетаниям?
2 1nvertex
 
30.03.17
00:25
вопрос 2 - имеется ввиду доступные остатки после заказа
3 trad
 
30.03.17
00:56
Перебрать все варианты, в твоем случае вариантов будет: 2*2*2*1=8
Проверить каждый вариант
4 SweetaAngel
 
30.03.17
01:33
Если заманить производителя на организации, а заводы на склады, то можно посмореть у УТ 11  механизм интеркампанй.
5 Лодырь
 
30.03.17
05:52
o1 = 100
o2 = 150
o3 = 80
o4 = 60
..
oM = ХЗ

z11+z12 = 50
z21+z23 = 90
z33+z34 = 100
z42 = 75

o1 >= z11+z21+z31+z41 или z11+z21+..zN1-o1>=0
..
oM >= z1M+z2M+z3M+z4M или z1M+z2M+..zNM-oM>=0

записываем в матричном виде и получим [Z -o]*e >= 0
где e  - единичный вектор

Задача линейного программирования, не?
6 Лодырь
 
30.03.17
05:53
тьфу, знаки перепутал в конце но суть не меняется.
7 VladZ
 
30.03.17
06:04
(0) Алгоритм:
1. Остатки по производителю/заводу закидываем в таблицу значений.

2. Заказы сортируем по убыванию количества.

3. Проверяем условия для тех, у кого конкретно задан производитель и завод. Помечаем в ТЗ количество "зарезервированного" товара.

3. Проверяем для всех остальных и также помечаем количество зарезервированного.
8 Злопчинский
 
30.03.17
06:16
(7) это будет оптимальный вариант?
разве задача в (0) не разновидность задачи о рюкзаке?
9 VladZ
 
30.03.17
06:24
(8) Не оптимальный.

Будут проблемы с распределением заявок вида "Производитель1 (все равно какой завод)" и "Завод1 (все равно какой производитель)".

Да, возможно придется озадачится "рюкзаком".
10 Злопчинский
 
30.03.17
06:31
(9) у меня сейчас стоит аналогичная задача
Товар1-Серия1-паллетN-количествоX
Товар1-Серия1-паллетN-количествоY
Товар1-Серия1-паллетN-количествоZ
Товар1-Серия2-паллетN-количествоQ
Товар1-Серия2-паллетN-количествоК
.
задача - набрать не менее требуемого количества.
соблюдая FEFO.
минимизировать показатель (НабранноеКоличество-ЗаказанноеКоличество)
в основном емкость паллет фиксированная, но могут быть разные "хвосты", например основной массив паллет по 78 и 72 шт, но могут быть огрызки по 12, 15, 30 - любые вообще...
11 Злопчинский
 
30.03.17
06:39
12 Злопчинский
 
30.03.17
06:43
при нескольких вариантах, дающий одинаковый результат - предпочтителен тот, где меньше паллет
13 Лодырь
 
30.03.17
07:20
(12) Дык просто по фифо заполняешь? Игры только с последней датой паллет.
14 Злопчинский
 
30.03.17
07:26
(13) не обязательно (?). если нужная выборка итоговая стопудово цепляет последнюю дату - то играть можно и количествами в нетиповых паллетах предыдущих дат, чтобы минимизировать невязку
15 FIXXXL
 
30.03.17
08:28
(14) сортировка по дате, внутри даты по коэфф.паллет
16 Naf2017
 
30.03.17
09:15
Незамкнутая транспортная задача
17 dezss
 
30.03.17
09:23
В общем случае, я бы попробовал решить Жадным алгоритмом наоборот.
Считаем удельный вес для каждом потребности: <сколько надо>/<сколько есть>.
Потом начинаем выбирать с самого малого удельного.
18 dezss
 
30.03.17
09:24
(17) тьфу, блин...
<сколько есть>/<сколько надо>
19 dezss
 
30.03.17
09:26
(18) и таким образом на этапе расчетов можно узнать о невозможности выполнить, если удельный вес будет меньше 1.
20 Лефмихалыч
 
30.03.17
09:33
(0) это задача на "спеца" по оперучету - реализовать партионное списание с учетом, что в табличной части реализации может быть указана партия. Если партия указана в документе, то сначала списывать именно с нее, а потом - всё остальное.
21 Asmody
 
30.03.17
09:42
Это задача целочисленного линейного программирования. Гугли "метод Гомори".
22 PCcomCat
 
30.03.17
09:52
У меня была задача - хитро.опый интеркампани по упр. и бух. учету.
Материалы списывают с какого угодно склада с какой угодно организации. Есть список организаций, участвующих в передаче материалов с установленным приоритетом, и есть список складов с установленным приоритетом, есть допустимые бух. счета учета номенклатуры. Отрицательные остатки по концу месяца нужно скорректировать:
1) имеющимися на любом из допустимых счетов учета в пределах организации списания и склада списания;
2) имеющимися на складе списания в любой из доступных организаций на любом из доступных счетов учета (в первую очередь счет учета из документа списания);
3) имеющимися в данной организации на любом из доступных складов на любом из доступных счетов учета (в первую очередь счет учета из документа списания);
4) имеющимися в любой из доступных организаций на любом из доступных складов на любом из доступных счетов учета (в первую очередь счет учета из документа списания).

Может что забыла или переставила местами.
Если нужно, могу скинуть обработку.
23 Ildarovich
 
30.03.17
10:00
Все же, по моему мнению, прав автор (5), это задача линейного программирования. Тут нет принципиально целочисленных ограничений.

Но ее решение состоит из двух этапов:
1) поиск допустимого решения;
2) поиск оптимального решения.

И автору требуется только выполнить поиск допустимого решения. Там много методов. Например метод "северо-западного угла". То же, что и ФИФО.

Если данные в таблице значений, то нужно сначала вычесть строки, где задан и производитель и завод. Оставшиеся строки записать в два столбика: потребности по заводам, потребности по производителям, а затем связать их по ФИФО.

Метод в коде можно посмотреть в http://catalog.mista.ru/public/306536/ (Задача 7).

Метод в запросе обсуждался много раз. Последний раз в http://forum.infostart.ru/forum9/topic164079/ . Более точное решение в комментарии http://forum.infostart.ru/forum9/topic164079/message1719985/#message1719985 .

Кстати, если стоит задача не найти решение, а только проверить возможность выполнения заказа, то вообще алгоритм не нужен. После вычитания строк "без прочерков" нужно проверить, что вектор суммы по производителям не больше имеющегося вектора суммы остатков. Также по заводам. Вот эти две проверки и определят ответ.
24 Asmody
 
30.03.17
10:17
(23) там штуки — это суровое целочисленное ограничение.
25 SweetaAngel
 
30.03.17
10:24
А если по-простому:

Строчка Производиель1, Завод2 - 75 штук - однозначно указывает на строку списание. Отнимаем её.

Итого остаток:
Производитель1, Завод1 - 100 штук
Производитель1, Завод2 - 75 штук
Производитель2, Завод1 - 80 штук
Производитель2, Завод2 - 60 штук

Производитель1 (все равно какой завод) -  50 штук
Завод1 (все равно какой производитель) - 90 штук
Производиель2 (все равно какой завод) - 100 штук

Далее сворачиваем по подразделению и по заводу, высчитываемым свободный остаткок и расставляем приоритете в каком порядке брать, т.е. обратная сортировка по свободному остатку:

Производитель1 - 170 штук  (- 50) =  свободный остаток 120 приоритет 1
Производитель2 - 140 штук  (- 100) = свободный остаток 40 приоритет 2


Завод1 - 180 штук   (-90) = свободный остаток 90 приоритет 2
Завод2 - 135 штук   (-0)  = свободный остаток 135 приоритет 1

Дальше выбираем что будем прежде всего удовлетворять  Заводы или Производителей. Допустим Производители.

Производитель1 (все равно какой завод) -  50 штук приоритет у Завода2 берем с него
Итого остаток:
Производитель1, Завод1 - 100 штук
Производитель1, Завод2 - 75 - 50 = 25 штук
Производитель2, Завод1 - 80 штук
Производитель2, Завод2 - 60 штук


Производиель2 (все равно какой завод) - 100 штук (!! Тут можно подумать над тем, чтобы пересчитать приоритеты после каждой итерации!!!!)приоритет у Завода2 берем сначала с него

Производитель1, Завод1 - 100 штук
Производитель1, Завод2 - 25 штук
Производитель2, Завод1 - 80 - 40 = 40 штук
Производитель2, Завод2 - 60 - 60 = 0 штук

Завод1 (все равно какой производитель) - 90 штук Приоритет у Производителя 1


Производитель1, Завод1 - 100 - 90 = 10 штук
Производитель1, Завод2 - 25 штук
Производитель2, Завод1 - 40 штук
Производитель2, Завод2 - 0 штук

На каждом этапе смотрим, чтобы остатки не уходили в минус.
26 Михаил Козлов
 
30.03.17
11:17
Видимо (16) прав.
Источники: остатки по производителям и заводам;
Получатели: строки заказа.
Дуги (от источника к получателям) - в соответствии с тем, какие условия на производителя и завод.
Например: Производитель1 (все равно какой завод) -  50 штук - будут две дуги от (Производитель 1, Завод1) и (Производитель 1, Завод2).
Транспортная задача довольно быстро решается (северо-западный угол или венгерский метод - найдете в Инете).
Могу выслать реализацию симплекс-метода для общей задачи ЛП.
Если нужно - пишите на мыло (в профиле).
27 1nvertex
 
30.03.17
11:17
(22) Тань, отправил тебе письмо на почту
28 1nvertex
 
30.03.17
11:22
(26) Михаил, отправил письмо
29 romix
 
30.03.17
11:37
30 Михаил Козлов
 
30.03.17
11:51
(28) Выслал.
31 Лодырь
 
30.03.17
11:55
Подобные темы надо студням показывать, чтоб понимали прикладной смысл того что они учат и балбесы выучить не могут.
32 АгентБезопасной Нацио
 
30.03.17
11:57
(31) скажут: "в интернете же уже есть решение!" :-)
33 dezss
 
30.03.17
12:13
(31) +100500
34 Лодырь
 
30.03.17
12:17
(32) Сначала надо идентифицировать задачу, выбрать вариант решения, сделать адаптацию алгоритма под конкретный случай. Масса проблем, с которыми неподготовленный человек не справится. Думаю у всех в этой теме было линейное программирование, но многие ли сейчас справятся с несовсем типовыми задачами?
35 dezss
 
30.03.17
12:29
(34) с книжкой/инетом справятся...тем более, если знают куда копать...
36 АгентБезопасной Нацио
 
30.03.17
12:35
(35) ну вот чтоб хотя бы "знать, куда копать" - и надо учить.
иначе все эти "науки" остаются в памяти студиоузов далекой и призрачной абстракцией...
37 dezss
 
30.03.17
12:39
(36) Согласен целиком и полностью...
Проблемы многих преподов в том, что не могут привести реальный пример из жизни, где может пригодится их наука.
38 Ildarovich
 
30.03.17
13:06
(24) "суровое целочисленное ограничение" вовсе не суровое.
Дело в том, что в уравнениях ограничений в этой конкретной задаче нет коэффициентов (!), вернее, они равны единицам. Поэтому в процессе решения (при выражении одних переменных через другие) не будут появляться дроби, поэтому применять метод Гомори и подобные просто нет смысла.

(29) Это действительно транспортная задача. И вроде бы здесь, на Мисте, было ее решение именно с вашим авторством.

Но ... хочу еще раз повторить, это задача не оптимизационная, для ее решения достаточно применить первую часть алгоритма: поиск допустимого решения. А это часть - один в один метод ФИФО. Сотни раз уже обсужденный.
Не нужно городить огород, там где он не нужен. Все гораздо проще. Типа (7), (25). В (23) приведены ссылки на конкретные функции и запросы, решающие именно эту задачу.

А если пойдете по пути (26) - зря потратите время, хотя знать о том, что эта задача - частный случай задачи ЛП, наверное, в теории нужно.
39 Ildarovich
 
30.03.17
13:11
+(38) Сообщите имена таблиц и их полей, где хранятся исходные данные этой задачи - можно будет запрос написать. Это простой пакетный запрос из трех подзапросов.
40 1nvertex
 
30.03.17
13:37
(39) Сергей, написал на почту
41 PCcomCat
 
30.03.17
14:01
(36) В ВУЗах это всё теория. Я лично - практик, и мне тяжело понять теорию, не увидев ее применение. Вернее я ее пониманию с научной точки зрения, но в каком конкретном случае что применить - не могу понять, пока не вижу хоть какой-то призрачный пример.
42 АгентБезопасной Нацио
 
30.03.17
15:34
(41) не во всех ВУЗах, и не всё.
по крайней мере, у нас много из преподов было "практиками", поэтому давали реальные примеры.
а по некоторым темам была возможность применить знания в деле "прям щас" (причем иногда даже в оплачиваемом деле).
43 romix
 
30.03.17
15:41
(38) Если не оптимизационная, тогда так:
http://cyclowiki.org/wiki/Метод_северо-западного_угла
44 dezss
 
30.03.17
15:43
(42) Были и такие, но это молодые, в основном. И их было не много. Остальные очень сильные теоретики (в большинстве своем, сильные).
45 PCcomCat
 
30.03.17
15:47
(44) Мне повезло меньше. 90% - было самообучение. Это, конечно, хорошо, но затратно по времени. Гораздо больше можно освоить, если теорию хотя бы преподнесут и в идеале покажут на примере.
46 Dmitry77
 
30.03.17
15:48
Можно и  чисто практически  подойти.

Насоздавать заказов и заставить 1с  их провести, то что непроведется  -  этого нет. Если заказов не много, то  просто перебором последовтельности поведения.


порядок проведения

Заказ1, Заказ2, Заказ3,
Заказ1, Заказ3, Заказ1.
Заказ2, Заказ1, Заказ3,
...

До заказ3, заказ2, Заказ1.
47 dezss
 
30.03.17
15:51
(45) Это и плохо, и хорошо.
Плохо, что в прописных истинах приходится разбираться самостоятельно. Хорошо, что запомнишь их лучше)))
48 АгентБезопасной Нацио
 
30.03.17
16:03
(47) это скорее  плохо.
запомнишь лучше, но не факт, что правильно :-)
(46) я даже боюсь спрашивать тебя про практический метод определения съедобности грибов и ягод...
49 Ildarovich
 
30.03.17
16:45
(43) Да, именно. Вот тут http://catalog.mista.ru/public/74343/ есть картинка, демонстрирующая, что метод северо-западного эквивалентен списанию по ФИФО.
50 Михаил Козлов
 
30.03.17
17:41
(43), (49) Боюсь северо-западный угол не сработает: в нем предполагается, что можно везти от любого поставщика любому потребителю, а в задаче ТС это не так.
Формально, если нельзя везти от поставщика к потребителю, стоимость доставки = очень большому числу, а это уже оптимизация.
Пусть данные в задаче такие (П1,П2-поставщики, Ф1,Ф2-заводы, З1,З2-строки заказа):
Стоки: П1З1 = 40; П1З2 = 30; П2З1 = 20; П2З2 = 10;
Потребности: З1 (любой П, любой З) = 70; З2 (П1, любой З) = 30;
И пусть строки матрицы = (П1З1,П1З2,П2З1,П2З2).
Тогда северо-западный угол даст (П1З1,З1)=40; (П1З2,З1)=30;
и для З2 нет допустимых решений.
51 Михаил Козлов
 
30.03.17
17:47
(50)+ Может надо посмотреть в сторону потока в сети?

https://ru.wikipedia.org/wiki/Алгоритм_Форда_%E2%80%94_Фалкерсона
52 Злопчинский
 
30.03.17
17:49
как разберете задачу автора - можно с моей будет поковыряться..?
53 Михаил Козлов
 
30.03.17
17:50
Виноват: в (50) вместо ПiЗj нужно читать ПiФj
54 Михаил Козлов
 
30.03.17
18:03
(51) Форд-Фалкерсон, вроде, подходит.
Для примера в 50 Фордом-Фалкерсоном получим решение:
(П1Ф1,З2) = 30; (П1Ф1,З1) = 10; (П1Ф2,З1) = 30; (П2Ф1,З1) = 20 и (П2Ф2,З1) = 10;
55 1nvertex
 
30.03.17
18:35
(54) Михаил, как вы считали?
56 Михаил Козлов
 
30.03.17
18:49
(55) Прямо как написано в Википедии.
Сначала сам граф. Он выглядит так:
- это двудольный граф. Одна доля - 4 вершины (ПiФj), вторая - 2 вершины Зi;
- дуги: четыре дуги вида (ПiФj) - > З1 (т.к.все равно какой поставщик и завод в строке 1 заказа) + две дуги вида (П1Фj) - > З2 (только поставщик1).
У всех дуг пропускная способность = бесконечности.
Добавляем две вершины: "0" (начальная), от которой идут дуги к (ПiФj) с соответствующей пропускной способностью (40,30,20и 10).
И "1" (конечная), к которой идут дуги Зi - > "1" с пропускной способностью = объему строки заказа (70 и 30).
А дальше - прямо по википедии.
57 Ildarovich
 
30.03.17
22:31
+(38)+(49)(50) По зрелом размышлении понял, что это не транспортная задача - структура ограничений другая. ФИФО и северо-западный угол прямо работать не будут.
Но это ЗЛП и искать нужно допустимое решение. Чуть более сложным методом.
Плюс уточнения задачи, данные "за кадром" тоже задачу усложняют. Но и делают интереснее. В голове решение есть. Теперь попробую запрограммировать. Отпишусь.
58 Лодырь
 
31.03.17
10:45
(35) Вот, если даже многоуважаемые опытные практики промахиваются с классификацией ) что говорить о нубасах
59 Михаил Козлов
 
03.04.17
11:48
Вообще задача носит общий для 1С характер: подобрать из остатков (в разрезе измерений) "желаемое".
Частными случаями является подбор серий и партий в типовых решениях (правда, только для одного измерения).
На мой взгляд, неплохая тема для дипломной работы.
Интересно, в Зазеркалье задача ставилась в таком виде?
60 Лодырь
 
03.04.17
13:30
(59) А как связана задача с Зазеркальем?
61 NSSerg
 
03.04.17
13:55
(59) Не согласен. Это задача на 20 минут для олимпиадного программирования. А никак не тема для диплома.
62 NSSerg
 
03.04.17
13:57
1. Вычитаем из остатков все заказанные пары Производитель-Завод.
2. По каждому заводу из заказа берем из списка остатков этого завода так, чтоб суммарный остаток по производителю из текущей пары остатка не стал меньше заказа по этому производителю.
3. Смотрим хватает ли остатков на производителей из заказа.
63 Михаил Козлов
 
03.04.17
13:59
(60) Например, распределение по сериям или партиям являются частными случаями.
(61) "Это задача на 20 минут для олимпиадного программирования" - ну значит мы м....и - столько времени потратили на обсуждение.
(62) Это не оптимальное решение.
64 NSSerg
 
03.04.17
14:00
(62) Оптимальное. Оно совершенно точно выдаст есть решение или нет, если решение есть то выдаст его.
65 NSSerg
 
03.04.17
14:02
(64) Или неоптимальное по сложности алгоритма?

1. Без хешей, с индексами.
Создаем две таблицы
С остатками по завод-производитель, отсортированная по заводу.
С остатками по производителю, отсортированная по производителю.
Ну и сложность несложно посчитать.
66 NSSerg
 
03.04.17
14:08
Каждый элемент первой таблицы с нужным заводом будет просмотрен не более одного раза. На каждый завод для поиска первой записи логарифм от количества заводов.
На каждый просмотр записи из первой таблицы допустим одно обращение к таблице производителей чтоб посмотреть и скорректировать остаток.
Итого сложность алгоритма О(N*ln(NN)+КК*ln(MM)+M*ln(MM))
Где N - количество заводов в заказе, NN - всего заводов
М - Количество Производителей в заказе, MM - всего производителей.
КК - количество записей в таблице остатков с заводами из заказа.
67 Михаил Козлов
 
03.04.17
14:31
(64) П-производитель, Ф-завод, З-заказ
Остатки: П1Ф1=1, П1Ф2=2, П2Ф2=1.
Заказ: З1(П1,неважно какой завод) = 2; З2(неважно какой производитель, Ф2) = 2.
Видно, что есть решение:  П1Ф1->З1 = 1; П1Ф2->З1 = 1; П1Ф2->З2 = 1; П2Ф2->З2 = 1;
Если следовать (62) то можем натолкнуться на 1 шаге на П1Ф2->З2 = 2 и останется только П1Ф1->З1 = 1. (т.е. 3 вместо 4-х).
Мне кажется, что это все-таки задача о потоке в сети (граф, правда, не общий, а двудольный). Впрочем, могу ошибаться.
68 АгентБезопасной Нацио
 
03.04.17
14:38
(66) (67) так и хочется добавить классическое: "это вы с кем сейчас разговаривали?"© :-)))
69 PCcomCat
 
03.04.17
14:40
(68)Не мешай!
Продолжайте, продолжайте...
70 Михаил Козлов
 
03.04.17
14:44
(68) Я, вроде, указал в (67) номер сообщения (64).
71 NSSerg
 
03.04.17
14:44
(67) (70)
Да, виноват, склинило.
72 Михаил Козлов
 
03.04.17
14:49
(71) Вот я и подумал, что неплохая тема для диплома: есть содержательная задача, предлагается мат. модель (пусть известная), можно проанализировать методы с учетом специфики (двудольный граф), предложить программную реализацию.
73 Злопчинский
 
03.04.17
14:57
Да, в той же самой складской логистике куча задач и по оптимизации, и по управлению ресурсами
74 NSSerg
 
03.04.17
15:00
(72) Есть вариант создать ветку на CodeForces. Думаю что быстро дадут ответ. Могу у сына спросить.
75 Лодырь
 
03.04.17
15:05
(63) Ну распределение по партиям слишком вырожденный случай. Куда интереснее многомерные варианты, сразу выпадаем в осадок дружно.
(74) Неспортивно.
76 Злопчинский
 
03.04.17
15:07
(75) многомерный вариант - ограничения по весу и обьему
77 NSSerg
 
03.04.17
15:09
Ну пока одно решение есть - сводим к задаче линейного программирования.
78 NSSerg
 
03.04.17
15:09
(77) -> (75)
79 Лодырь
 
03.04.17
15:20
(77) Ну да, я же первый и предложил )
Другой вопрос как реализовать, что будет более изящным. С условием того что это должно работать на 1С.
80 Михаил Козлов
 
03.04.17
15:34
(76) Можно еще: (серия, склад, качество)
(74) Да решение, по сути, есть: поток в сети. Только посмотреть, какой из вариантов предпочтительнее. Плюс еще продуманная структура данных (учитывая, что граф двудольный).
(77) У ТС размерности таковы, что симплекс может захлебнуться. Да и матрица условий может оказаться разреженной (т.е. иметь ее в памяти в виде матрицы нецелесообразно). Да и коэффициенты в матрице = 1.
Заметьте, что в УПП используется не точный, а итерационный алгоритм решения СЛАУ.
(73) Есть, конечно. Тут нечастый случай, когда есть приемлемый (и точный) алгоритм.
81 Oftan_Idy
 
03.04.17
17:32
(0) Загугли "задача о рюкзаке"