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

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

Вопрос: Как проверить что заказ можно выполнить? (Алгоритм)

Вопрос№2: Какое количество максимально доступных остатков по каждому производителю и заводу и их сочетаниям?

вопрос 2 - имеется ввиду доступные остатки после заказа

Перебрать все варианты, в твоем случае вариантов будет: 2*2*2*1=8
Проверить каждый вариант

Если заманить производителя на организации, а заводы на склады, то можно посмореть у УТ 11  механизм интеркампанй.

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  - единичный вектор

Задача линейного программирования, не?

тьфу, знаки перепутал в конце но суть не меняется.

(0) Алгоритм:
1. Остатки по производителю/заводу закидываем в таблицу значений.

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

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

3. Проверяем для всех остальных и также помечаем количество зарезервированного.

(7) это будет оптимальный вариант?
разве задача в (0) не разновидность задачи о рюкзаке?

(8) Не оптимальный.

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

Да, возможно придется озадачится "рюкзаком".

(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 - любые вообще...

типа так https://www.screencast.com/t/rga7X0gJ

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

(12) Дык просто по фифо заполняешь? Игры только с последней датой паллет.

(13) не обязательно (?). если нужная выборка итоговая стопудово цепляет последнюю дату - то играть можно и количествами в нетиповых паллетах предыдущих дат, чтобы минимизировать невязку

(14) сортировка по дате, внутри даты по коэфф.паллет

Незамкнутая транспортная задача

В общем случае, я бы попробовал решить Жадным алгоритмом наоборот.
Считаем удельный вес для каждом потребности: <сколько надо>/<сколько есть>.
Потом начинаем выбирать с самого малого удельного.

(17) тьфу, блин...
<сколько есть>/<сколько надо>

(18) и таким образом на этапе расчетов можно узнать о невозможности выполнить, если удельный вес будет меньше 1.

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

Это задача целочисленного линейного программирования. Гугли "метод Гомори".

У меня была задача - хитро.опый интеркампани по упр. и бух. учету.
Материалы списывают с какого угодно склада с какой угодно организации. Есть список организаций, участвующих в передаче материалов с установленным приоритетом, и есть список складов с установленным приоритетом, есть допустимые бух. счета учета номенклатуры. Отрицательные остатки по концу месяца нужно скорректировать:
1) имеющимися на любом из допустимых счетов учета в пределах организации списания и склада списания;
2) имеющимися на складе списания в любой из доступных организаций на любом из доступных счетов учета (в первую очередь счет учета из документа списания);
3) имеющимися в данной организации на любом из доступных складов на любом из доступных счетов учета (в первую очередь счет учета из документа списания);
4) имеющимися в любой из доступных организаций на любом из доступных складов на любом из доступных счетов учета (в первую очередь счет учета из документа списания).

Может что забыла или переставила местами.
Если нужно, могу скинуть обработку.

Все же, по моему мнению, прав автор (5), это задача линейного программирования. Тут нет принципиально целочисленных ограничений.

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

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

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

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

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

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

(23) там штуки — это суровое целочисленное ограничение.

А если по-простому:

Строчка Производиель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 штук

На каждом этапе смотрим, чтобы остатки не уходили в минус.

Видимо (16) прав.
Источники: остатки по производителям и заводам;
Получатели: строки заказа.
Дуги (от источника к получателям) - в соответствии с тем, какие условия на производителя и завод.
Например: Производитель1 (все равно какой завод) -  50 штук - будут две дуги от (Производитель 1, Завод1) и (Производитель 1, Завод2).
Транспортная задача довольно быстро решается (северо-западный угол или венгерский метод - найдете в Инете).
Могу выслать реализацию симплекс-метода для общей задачи ЛП.
Если нужно - пишите на мыло (в профиле).

(22) Тань, отправил тебе письмо на почту

(26) Михаил, отправил письмо

Может, так:

http://cyclowiki.org/wiki/Транспортная_задача

(28) Выслал.

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

(31) скажут: "в интернете же уже есть решение!" :-)

(31) +100500

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

(34) с книжкой/инетом справятся...тем более, если знают куда копать...

(35) ну вот чтоб хотя бы "знать, куда копать" - и надо учить.
иначе все эти "науки" остаются в памяти студиоузов далекой и призрачной абстракцией...

(36) Согласен целиком и полностью...
Проблемы многих преподов в том, что не могут привести реальный пример из жизни, где может пригодится их наука.

(24) "суровое целочисленное ограничение" вовсе не суровое.
Дело в том, что в уравнениях ограничений в этой конкретной задаче нет коэффициентов (!), вернее, они равны единицам. Поэтому в процессе решения (при выражении одних переменных через другие) не будут появляться дроби, поэтому применять метод Гомори и подобные просто нет смысла.

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

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

А если пойдете по пути (26) - зря потратите время, хотя знать о том, что эта задача - частный случай задачи ЛП, наверное, в теории нужно.

+(38) Сообщите имена таблиц и их полей, где хранятся исходные данные этой задачи - можно будет запрос написать. Это простой пакетный запрос из трех подзапросов.

(39) Сергей, написал на почту

(36) В ВУЗах это всё теория. Я лично - практик, и мне тяжело понять теорию, не увидев ее применение. Вернее я ее пониманию с научной точки зрения, но в каком конкретном случае что применить - не могу понять, пока не вижу хоть какой-то призрачный пример.

(41) не во всех ВУЗах, и не всё.
по крайней мере, у нас много из преподов было "практиками", поэтому давали реальные примеры.
а по некоторым темам была возможность применить знания в деле "прям щас" (причем иногда даже в оплачиваемом деле).

(38) Если не оптимизационная, тогда так:
http://cyclowiki.org/wiki/Метод_северо-западного_угла

(42) Были и такие, но это молодые, в основном. И их было не много. Остальные очень сильные теоретики (в большинстве своем, сильные).

(44) Мне повезло меньше. 90% - было самообучение. Это, конечно, хорошо, но затратно по времени. Гораздо больше можно освоить, если теорию хотя бы преподнесут и в идеале покажут на примере.

Можно и  чисто практически  подойти.

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


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

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

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

(45) Это и плохо, и хорошо.
Плохо, что в прописных истинах приходится разбираться самостоятельно. Хорошо, что запомнишь их лучше)))

(47) это скорее  плохо.
запомнишь лучше, но не факт, что правильно :-)
(46) я даже боюсь спрашивать тебя про практический метод определения съедобности грибов и ягод...

(43) Да, именно. Вот тут http://catalog.mista.ru/public/74343/ есть картинка, демонстрирующая, что метод северо-западного эквивалентен списанию по ФИФО.

(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 нет допустимых решений.

(50)+ Может надо посмотреть в сторону потока в сети?

https://ru.wikipedia.org/wiki/Алгоритм_Форда_%E2%80%94_Фалкерсона

как разберете задачу автора - можно с моей будет поковыряться..?

Виноват: в (50) вместо ПiЗj нужно читать ПiФj

(51) Форд-Фалкерсон, вроде, подходит.
Для примера в 50 Фордом-Фалкерсоном получим решение:
(П1Ф1,З2) = 30; (П1Ф1,З1) = 10; (П1Ф2,З1) = 30; (П2Ф1,З1) = 20 и (П2Ф2,З1) = 10;

(54) Михаил, как вы считали?

(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).
А дальше - прямо по википедии.

+(38)+(49)(50) По зрелом размышлении понял, что это не транспортная задача - структура ограничений другая. ФИФО и северо-западный угол прямо работать не будут.
Но это ЗЛП и искать нужно допустимое решение. Чуть более сложным методом.
Плюс уточнения задачи, данные "за кадром" тоже задачу усложняют. Но и делают интереснее. В голове решение есть. Теперь попробую запрограммировать. Отпишусь.

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

Вообще задача носит общий для 1С характер: подобрать из остатков (в разрезе измерений) "желаемое".
Частными случаями является подбор серий и партий в типовых решениях (правда, только для одного измерения).
На мой взгляд, неплохая тема для дипломной работы.
Интересно, в Зазеркалье задача ставилась в таком виде?

(59) А как связана задача с Зазеркальем?

(59) Не согласен. Это задача на 20 минут для олимпиадного программирования. А никак не тема для диплома.

1. Вычитаем из остатков все заказанные пары Производитель-Завод.
2. По каждому заводу из заказа берем из списка остатков этого завода так, чтоб суммарный остаток по производителю из текущей пары остатка не стал меньше заказа по этому производителю.
3. Смотрим хватает ли остатков на производителей из заказа.

(60) Например, распределение по сериям или партиям являются частными случаями.
(61) "Это задача на 20 минут для олимпиадного программирования" - ну значит мы м....и - столько времени потратили на обсуждение.
(62) Это не оптимальное решение.

(62) Оптимальное. Оно совершенно точно выдаст есть решение или нет, если решение есть то выдаст его.

(64) Или неоптимальное по сложности алгоритма?

1. Без хешей, с индексами.
Создаем две таблицы
С остатками по завод-производитель, отсортированная по заводу.
С остатками по производителю, отсортированная по производителю.
Ну и сложность несложно посчитать.

Каждый элемент первой таблицы с нужным заводом будет просмотрен не более одного раза. На каждый завод для поиска первой записи логарифм от количества заводов.
На каждый просмотр записи из первой таблицы допустим одно обращение к таблице производителей чтоб посмотреть и скорректировать остаток.
Итого сложность алгоритма О(N*ln(NN)+КК*ln(MM)+M*ln(MM))
Где N - количество заводов в заказе, NN - всего заводов
М - Количество Производителей в заказе, MM - всего производителей.
КК - количество записей в таблице остатков с заводами из заказа.

(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-х).
Мне кажется, что это все-таки задача о потоке в сети (граф, правда, не общий, а двудольный). Впрочем, могу ошибаться.

(66) (67) так и хочется добавить классическое: "это вы с кем сейчас разговаривали?"© :-)))

(68)Не мешай!
Продолжайте, продолжайте...

(68) Я, вроде, указал в (67) номер сообщения (64).

(67) (70)
Да, виноват, склинило.

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

Да, в той же самой складской логистике куча задач и по оптимизации, и по управлению ресурсами

(72) Есть вариант создать ветку на CodeForces. Думаю что быстро дадут ответ. Могу у сына спросить.

(63) Ну распределение по партиям слишком вырожденный случай. Куда интереснее многомерные варианты, сразу выпадаем в осадок дружно.
(74) Неспортивно.

(75) многомерный вариант - ограничения по весу и обьему

Ну пока одно решение есть - сводим к задаче линейного программирования.

(77) -> (75)

(77) Ну да, я же первый и предложил )
Другой вопрос как реализовать, что будет более изящным. С условием того что это должно работать на 1С.

(76) Можно еще: (серия, склад, качество)
(74) Да решение, по сути, есть: поток в сети. Только посмотреть, какой из вариантов предпочтительнее. Плюс еще продуманная структура данных (учитывая, что граф двудольный).
(77) У ТС размерности таковы, что симплекс может захлебнуться. Да и матрица условий может оказаться разреженной (т.е. иметь ее в памяти в виде матрицы нецелесообразно). Да и коэффициенты в матрице = 1.
Заметьте, что в УПП используется не точный, а итерационный алгоритм решения СЛАУ.
(73) Есть, конечно. Тут нечастый случай, когда есть приемлемый (и точный) алгоритм.

(0) Загугли "задача о рюкзаке"