Interview question

[Tatarin]

На работе мне задали вопрос чтобы я написал псевдо код для решения данной задачи.
Дано N генераторов которых могут вырабатывать мегаватты от мин и максимума. У каждого генератор свои мин и макс и не обязательно одинаковые. Дано Х это нужное количество мегаватт которое должно генерироваться всеми генераторами вместе суммарно. Надо найти нагруженность каждого генератора так чтобы нагрузка была распределена между N генераторами наиболее равномерно. Генератор может вырабатывать только в пределах данных мин и макс.

Как решить данную задачу?

Я за 45мин написал алгоритм но думаю неправильно.
Он заключается сначала в распределении нагрузки для генераторов для которых Х/N находится вне их пределов. Таким генераторам я присваивал их граничные значения (мин или макс)
После этого я пересчитывал новый Хremainder/Nnew где Nnew это количство неприсвоенных генераторов а Хremainder это не распределенная нагрузка. Короче я написал бред.
Не пинайте я. Я ЕЕ поэтому не силен в алгоритмах.
Спасибо.

[Komissar]

так это дали на текущей работе или на интервью?

[Tatarin]

да на текущей работе. it was a promotional interview.

[Komissar]

гоните в задницу такой промоушен. Все равно Вас скоро заменят сладкоречивым индусом.

[Tatarin]

ну это само собой:)

А по существу есть советы по алгоритму?

[Komissar]

скорее всего, там self-leveling regression. Типа, закидываете некие начальные параметры, а потом оно само должно устаканиться.

[Deynekin]

Я [...] написал алгоритм но думаю неправильно.

Какой-то очень странный стиль представления материала.
Речь сейчас не о безграмотном написании "думаю неправильно", возводящем вводное слово "думаю" в ранг полноценного сказуемого со смыслом, на который явно не рассчитывали: "[я] неправильно думаю", а о попытке заранее сделать себя кругом правым. Смысл этой "хитрости" — и свою мысль изложить, и тут же назвать её неправильной — очевиден: если алгоритм всё-таки будет признан верным, тогда получится вполне заслуженное: "Ага, я таки прав!" А если окажется неправильным — тогда: "Ага, я же сразу сказал, что это неправильно!" — и этим "я же сразу сказал" ...снова прав.
(Такой фортель только блондинкам прощается; у них ещё один похожий приём есть: "Я именно так с самого начала и думала, но почему-то сказала наоборот...")

А ведь всего-то и нужно было сказать: "я написал алгоритм, но не уверен, правильно ли это: ..." — и всё выглядело бы совершенно этично.

[helg]

Необходимо уточнить условие: как понимается "равномерно"? Можно словами функцию, которую оптимизируем, описать. А можно на примере. Есть два генератора. 1-10 и 1-100 МВт. Как в понимании заказчика правильно генерить 3, 10, 30 и 100 MBт?

[Физик-Лирик]

Необходимо уточнить условие: как понимается "равномерно"? Можно словами функцию, которую оптимизируем, описать. А можно на примере. Есть два генератора. 1-10 и 1-100 МВт. Как в понимании заказчика правильно генерить 3, 10, 30 и 100 MBт?

Тоже самое хотел спросить.
Воможно имеется в виду, что вариация распределения мощностей минимальна? Т.е есть N случайный чисел. Найти такую реализацию, при которой сумма равна Х, а вариация распределения минимальна?

[лопарь]

На работе мне задали вопрос чтобы я написал псевдо код для решения данной задачи.
Дано N генераторов которых могут вырабатывать мегаватты от мин и максимума. У каждого генератор свои мин и макс и не обязательно одинаковые. Дано Х это нужное количество мегаватт которое должно генерироваться всеми генераторами вместе суммарно. Надо найти нагруженность каждого генератора так чтобы нагрузка была распределена между N генераторами наиболее равномерно. Генератор может вырабатывать только в пределах данных мин и макс.

Как решить данную задачу?

Я за 45мин написал алгоритм но думаю неправильно.
Он заключается сначала в распределении нагрузки для генераторов для которых Х/N находится вне их пределов. Таким генераторам я присваивал их граничные значения (мин или макс)
После этого я пересчитывал новый Хremainder/Nnew где Nnew это количство неприсвоенных генераторов а Хremainder это не распределенная нагрузка. Короче я написал бред.
Не пинайте я. Я ЕЕ поэтому не силен в алгоритмах.
Спасибо.

Это задача выпуклой оптимизации.

[Физик-Лирик]

Может так.
Предположим вначале, что минимум нуль.
1) Если сумма максимумов меньше Х, тогда решения нет.
2) M = X/N.
3) Найдем все генераторы, для которых максимум меньше М. Запустим эти генераторы на максимум.
4) Перейти к пункту 2, где тепeрь N - число оставшихся генераторов (после пункта 3), а Х - оставшаяся мощность.

Если минимум не ноль:
1) Найти генераторы, для которых минимум больше М. Запустить их по минимуму.
2) Для оставшихся генераторов применить вышеизложенный алгоритм.

Хотя тут воможны ньюансы. Надо еще подумать.

[Физик-Лирик]

Это задача выпуклой оптимизации.

Для какой функции?

[лопарь]

Это задача выпуклой оптимизации.

Для какой функции?

Для функции "чтобы нагрузка была распределена между N генераторами наиболее равномерно" при условиях "У каждого генератор свои мин и макс и не обязательно одинаковые. Дано Х это нужное количество мегаватт которое должно генерироваться всеми генераторами вместе суммарно".

Какая конкретно функция минимизируется - зависит от того, что понимать под "распределена наиболее равномерно" (если неравномерно, то какова мера этой неравномерности?)

[Физик-Лирик]

Ну так давайте примем за данную функцию вариацию. Drugimi slovami:

L(G_1, ..., G_N) = SUM[G_i - X/N]^2 ;
Найти argmin L при условии:
SUM G_i = X; min_i <= G_i <= max_i.

Очевидно, что L = SUM G_i^2 - X^2/N. (последний член можно убрать).
Если убрать одну степень свободы, т.е. G_N = X - SUM' G_i, где теперь SUM' означает суммирование до N-1.
L' = SUM'(G_i^2) + (SUM' G_i)^2 - 2 X SUM' G_i. Теперь остались ограничения между min и max.

Похoже тепрь можно функцию Лагранжа выписывать и добавлять KKT условия.

[Физик-Лирик]

Похоже алгоритм, что я описал, должен сработать, если в качестве фукнции оптиизации взять вариацию.
У нас есть N величин. Их срeднее задано и равно Х/N.
1) Если все максимумы меньше среднего или если все минимумы больше среднего - решения нет.
2) Если все максимумы выше серднего, а все минимумы ниже среднего - ставим каждый генератор на среднее. Вариация нулевая. Задача решена.
3) Если часть минимумов выше среднего, ставим на минимум. Если часть максимум ниже серднего - ставим на максимум. Для оставшихся генераторов берем новое среднее значение с учетом того, что мы уже поставили часть генераторов на максимум и/или минимум (т.е. среднее для всех генераторов должно оставаться Х/N).
4) Повторяем пункт 3 для оставшихся генераторов.

Похоже получится типа рекурсивной функции.