Как сгенерировать все возможные двоичные матрицы nxm, где сумма каждой строки равна 1 - PullRequest
1 голос
/ 29 мая 2019

Я работаю над заданием, в котором мне нужно назначить от 1 до 10 распределительных центров во всех штатах США. Я сделал в Excel модель для расчета всех затрат, и, очевидно, цель задания - найти самый дешевый способ. У меня есть 50 строк (для каждого штата) и 10 столбцов (для всех возможных местоположений DC). Моя модель основана на этой матрице, и если я изменю матрицу, затраты будут отображаться мгновенно. Единственным ограничением является то, что каждое состояние снабжается ровно 1 DC.

Ясно, что я не могу составить все возможные комбинации вручную, я пытался перевести свою модель в программу оптимизации (AIMMS), но потребуется много времени, которое я уже вложил в модель Excel. Я думал, что если бы у меня были все возможные матрицы (сгенерированные в R, Matlab или Python, не заботятся о них), я мог бы просмотреть их в своей электронной таблице и позволить программе прочитать стоимость, чтобы определить лучший выбор. Теоретически возможно снабдить все состояния одним постоянным током и не более 10, поэтому для определения наилучшего из них необходима любая возможная матрица 1x50, 2x50, 3x50 ... 10x50.

Итак, еще раз, вкратце, возможно ли сгенерировать каждую двоичную матрицу nxm с общей суммой 1 в каждой строке предпочтительно в R, или иначе в Matlab или Python?

1 Ответ

2 голосов
/ 29 мая 2019

TLDR:


Давайте рассмотрим самый простой пример: 2 DC.Возможные строки:

  • (1,0)
  • (0,1)

Теперь вы хотите построить все возможные матрицы 2x50.Их количество составляет 2 ^ 50 (2 возможных ряда по 50 строк).Он равен:

1125899906842624

Предполагается, что каждая матрица хранит 100 байтов.Все матрицы 2x50 будут хранить:

(2**50) * 100 / 1024 / 1024 / 1024 / 1024 = 102400 терабайт данных.

И на обработку всех из них (в самых оптимистичных результатах для обычных компьютеров) будет затрачено время, равное:

(2**50) / 10**9 / 60 / 60 = 312 часов.

А 10х50 будет еще больше ...

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...