Страницы: 1
RSS
Нахождение минимального количества итераций в двоичной матрице
 
Здравствуйте!
Есть условие - на базах(база1,база2,база3..) есть объем условного товара, необходимо за минимальное количество итераций переместить его по пунктам(пункт1,пункт2,пункт3), неважно какой куда, главное освободить базы.

К какому типу задач это можно отнести? Просьба направить на решение с помощью excel.

В прикрепленном файле я попробовал решить это с помощью надстройки *поиск решения*, но почему-то не могу указать целевую функцию в виде "=СЧЁТЕСЛИ(L1:N5;">0")" , так же у поиска решения существует ограничение в 100(или 200 ячеек?), а мне хочется сделать этот инструмент универсальным.

Спасибо.
 
Цитата
raitnax написал:
неважно какой куда
Как говорил один сказочный персонаж: "Если тебе не важно куда попасть, то тогда не важно куда идти".
Для решения задачи надо либо всем выслать миелафоны, либо пояснить что значит:
Цитата
raitnax написал:
переместить его по пунктам
 
Цитата
Мартын написал: Для решения задачи надо либо всем выслать миелафоны, либо пояснить что значит:
Либо стоит открыть файлик, а не *умничать* на форуме? Если хочется пофлудить, можно найти другой форум или чат.

Но я всеравно поясню, лично вам. в пункте А есть 5 единиц пшеницы, когда мы переместили ее в пункт Б, то в пункте Б стало 5 единиц пшеницы. в ячейке пересечения пункта А и пункта Б будет отражено количество единиц пшеницы перемещенной из пункта А в пункт Б.
Изменено: raitnax - 04.09.2017 15:16:34
 
Открыл, посмотрел, но нигде в файле понятия "переместить" не нашёл, к сожалению.
Понятнее не стало. Что есть итерация и какую её характеристику надо минимизировать?
Что мешает сразу записать все значения из баз в первый столбик (типа переместили в пункт1) и на этом закончить?
Изменено: Мартын - 04.09.2017 15:14:32
 
Цитата
Мартын написал:
Открыл, посмотрел, но нигде в файле понятия "переместить" не нашёл, к сожалению.
Я вроде объяснение выше написал. Так тоже непонятно?
Условно, можно интерпретировать как транспортную задачу .

У пунктов есть лимит по вместимости (в файле 170, 160, 38), а количество условного товара, больше чем лимит первого пункта. Соответственно нужно делить.

Минимизировать необходимо количество итераций. Итерация  - это перенос товара из базы в пункт(одна ячейка).  
Изменено: raitnax - 04.09.2017 15:24:20
 
Цитата
raitnax написал:
У пунктов есть лимит
Ну наконец-то!!!! Вот что требуется для понимания! Ограничения! (Интересно, как можно было догадаться, то 170 это лимит, а не рост охранника, например?)
По сути, ИМХО, надо копать в сторону жадного алгоритма, но как это сделать чисто формулами не знаю. Тут макросы нужны.
 
Цитата
Мартын написал:
По сути, ИМХО, надо копать в сторону жадного алгоритма, но как это сделать чисто формулами не знаю. Тут макросы нужны
Есть такая функция, теоретически поиск решения должен отрабатывать на ней.
=СЧЁТЕСЛИ(L1:N5;">0")

и ее минимизация, должна выдать решение, но почему-то он ее вообще не воспринимает.  
 
Цитата
raitnax написал:
но почему-то он ее вообще не воспринимает.
А как он (Ёксель) должен её "воспринимать"? Она просто суммирует значения. Кстати, а зачем такая формула, там и обычная СЧЁТ(L1:N5) прекрасно справится, если нули не рисовать.
Вот если бы в клетках были формулы, изменение которых приводило бы к изменению данных, то тогда да, "поиск решения" мог бы помочь. Да и то, только если менялось бы значение одной единственной ячейки.
Короче говоря, вероятность решения данной задачи без макросов стремится спрятаться в тени нуля.
Изменено: Мартын - 04.09.2017 16:05:40
 
В примере нет самого главного - распределения. Хотя-бы вот такого.
 
Цитата
Мартын написал:
В примере нет самого главного - распределения. Хотя-бы вот такого.
Отличное распределение!) В принципе проверил на матрице где-то 90х12, распределил в 96 ячеек, мат.инструмент дал такой же результат.
Правда его надо видоизменить. Но всеравно спасибо за направление

Если кому-то интересно, у задачи есть дальнейшее усложнение.  
Изменено: raitnax - 04.09.2017 20:03:50
 
Вот мне интересно, как он идет по минимальному пути сопротивления.  
 
Ну в моём случае применяется наивный жадный алгоритм без оптимизации.
 
еще вариант жадного алгоритма
Изменено: MCH - 05.09.2017 09:05:13
 
Цитата
raitnax написал:
В принципе проверил на матрице где-то 90х12
Можете привести пример данных 90х12?
 
Цитата
MCH написал:
еще вариант жадного алгоритма
Тоже, кстати не идеальный, потому как без оптимизации :)
ИМХО, идеальный жадный даст такую картину за 6 итераций:
Нужно17016038
Есть
18 18
19817028
50 50
25 25
48 48
Изменено: Мартын - 05.09.2017 09:33:09
 
Цитата
raitnax написал:
как он идет по минимальному пути сопротивления
В идеале выбирается мах склад и туда "пихается" максимальное количество из базы, потом ситуация повторяется с учётом заполнения складов и опустошения баз. Тут без макросов никак.
 
Да, конечно. Вот пример 87х12. Следующий вопрос, если добавить периоды для тех же самых баз и пунктов, т.е. в месяц1 - одни цифры, в месяц2 - другие цифры, но нужно получить минимальное количество итераций между определенным пунктом и базой в течение всего периода. Я опять мог некорректно выразиться, если что готов расписать подробнее:-)
Изменено: raitnax - 05.09.2017 09:53:40
 
Цитата
Мартын написал:
В идеале выбирается мах склад и туда "пихается" максимальное количество из базы, потом ситуация повторяется с учётом заполнения складов и опустошения баз. Тут без макросов никак.
Скорее всего я к этому и приду, однако сейчас я не могу понять алгоритм, который будет решать эту задачу. Поэтому и спрашиваю совета.

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

спасибо.

upd. файлик поправил и добавил еще один месяц для наглядности.
upd2. Может можно как-то расставлять в ячейки веса в зависимости от того, есть ли на предыдущем листе в этой ячейке данные или нет?  
Изменено: raitnax - 05.09.2017 22:54:16
 
Upd. Оптимально решает:-) Для того, чтобы получить оптимальное решение, нужно отсортировать в порядке убывания базы(сверху вниз) и в порядке убывания пункты (справа налево). Проверил на 12 месячной выборке, таблицы 87х12, получилось с учетом объединения итераций во временном срезе, общее количество итераций 119(+- зависит от чисел) .

Огромное спасибо!
Персонально - спасибо Мартын :-)
Страницы: 1
Наверх