Interview question

[helg]

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

Рассмотрим идеальный случай, когда требуемая суммарная мощность больше суммарной минимальной мощности всех генераторов - то есть для решения задачи не надо никого выключать. Определим понятие "нагрузка сети" - от 0 до 100%. Когда требуемая мощность равна минимальной суммарной, нагрузка - 0%, когда она равна максимальной сумарной - 100%, посередине всё линейно. Точно таким же образом опеределим понятие нагрузки для каждого генератора. Очевидно, что если каждый из генераторов нагружен на X%, вся сеть нагружена на X%.

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

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

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

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

Т.е. если я правильно понял, определим процент загрузки для генератора i как
P_I = (G_i - min_i) / (max_i - min_i).
Предположим, что процент загрузки одинаков, i.e. P_i = P. Отсюда G_i = P *(max_i - min_i) + min_i.
X = SUM G_i = P * SUM(max_i - min_i) + SUM min_i. Отсюда P = (X - SUM min_i) / SUM(max_i - min_i).
Т.к 0 <= P <= 1 получаем, что решений нет, если X < SUM min_i или X > SUM max_i.

Правильно ли я Вас понял в рамках Вашего определения равномерности?

Одим коммент. В моем алгоритме надо возвращаться из пункта 4 в пункт 1, т.е. снова проверять условия минимум и максимума.

[Tatarin]

В интервью вопрос звучал как "even distribution". Я понял это как разброс с минимальным среднеквадратичным отклонением. Подумав пару дней я пришел к выводу что можно было на интервью написать просто тупой перебор с N вложенными циклами вот так например. Обидно что я не догадался. Мне эта вакансия очень нравилась.

Code: Select all

max_std_dev=10^10;

for (i1=Gmin[1];i<=Gmax[1]; i1=i1+gstep)
  for (i2=Gmin[2];i<=Gmax[2]; i2=i2+gstep)
    for (i3=Gmin[3];i<=Gmax[3]; i3=i3+gstep)
     .... etc
         { 
            sum=i1+i2+....+iN;
            mean =sum/N;
            if (sum >X-delta)and(sum<X)                 //проверка если сумма нагрузок=Х
               {
                   std_dev=(i1-mean)^2+(i2-mean)^2+....+(iN-mean)^2   //standard deviation
                   if (std_dev<max_std_dev)               // сравниваем если разброс лучше
                      {
                        max_std_dev=std_dev;              // если да то обновляем рекорд 
                        // сохранить текущую нагрузку генераторов как лучшую

                }

[лопарь]

> Подумав пару дней я пришел к выводу что надо было на интервью написать просто тупой перебор с N вложенными циклами

N фиксировано и невелико? Что-то мне кажется, что вам бы такое решение не зачли. Хоть бы простейший градиентный спуск сделали, что ли. Заодно решили бы вопрос с произвольностью gstep.

У вас если есть, допустим, всего лишь 10 генераторов, а шаг вы выбрали довольно грубый - в десятую долю диапазона, то всего придётся сделать 10^10 итераций.

[Tatarin]

В нашей шараге где-то 12 генераторных станций разного вида поэтому наверное тупой перебор долго бы искал оптимальный разброс нагрузок генераторов.

Я только сейчас понял что я пытался решить эту задачу с точки зрения нагрузок наиболее близких к среднему числу Х/N. Но ведь even distribution можно понять как например разброс нагрузок когда каждый генератор нагружен так чтобы ближе к своему среднему пределу! Это наверное будет полезно для равномерного старения генераторов ведь тот который работает на пределе сломается раньше того который работает на минимуме, скорее всего.

Короче у меня соблазн появился написать двум интервьюрирам то что вопрос их был не совсем корректен. Это нормально будет описать если написать им до оглашения их выбора? Или просто подождать чтобы огласили выбор.

[лопарь]

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

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

Нет, решение с циклами как-то не очень. Как правильно заметили, оно потребует много времени. Вы как бы делаете маленькие шажки для каждой переменной. Даже при умеренных N вычислительно неэффективно. Здесь еще могут быть проблемы, т.к у Вас есть "точность" делта и шаг цикла. Возможны неоднозначные решения (вопрос, конечно, решается).

Если равномерность определяется процентом загрузки, то решение уже выписано в "аналитической" форме.

[helg]

Короче у меня соблазн появился написать двум интервьюрирам то что вопрос их был не совсем корректен. Это нормально будет описать если написать им до оглашения их выбора? Или просто подождать чтобы огласили выбор.

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

Для того, чтобы показать заинтересованность, после интервью принято слать "thank you letter". Вот в этом письме про другое решение и сказать.

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

По-моему, даже в случае минимизации среднеквадратического отклонения (т.е. вариации) есть аналитическое решение.
Обозначим через x_i - генераторы, e = X/N, диапазон работы генераторов: m_i = min_i, M_i = max_i.

f(x_1, ..., x_N) = SUM (x_i - e)^2 -> min,
условия:
SUM(x_i) =X, m_i <= x_i <= M_i.
Запишем функцию Лагранжа:
L = f(x_1, ..., x_N) - a * SUM(x_i - e)^2 - SUM b_i (x_i - m_i) - SUM g_i (M_i - x_i).
Первое необходимое условие миниума (условия Каруша-Куна-Такера):
dL/dx_k =0, т.е. x_k = 0.5 *(a + b_k - g_k + 2e);
SUM(x_k) = X
b_k *(x_k - m_k) =0
g_k * (x_k-M_k) = 0
b_k >= 0
g_k >= 0.
Собственно далее идет переборка, которую как раз мoжно делать в цикле.
Например, если x_k != m_k, x_k != M_k, тогда получим x_k = 0.5 * a + e. Далее X = SUM x_k = 0.5*a*N + e*N +> a = 0. Т.е. x_k = e = X/N, что очевидно сразу.
Допустим x_1 = m_1. Тогда x_1 = m_1 = 0.5*(a+b_1+2e); x_k = 0.5*a + e, k>1. X = m_1 + SUM' x_k. Из последних двух условий находим b_1 и a. При этом необходимо проверить, что b_1 >= 0. a_1 = 2(e-m_1)/(N-1). Про этом b_1 = 2(m_1-e)(1+1/(N-1)).
Т.к. b_1 должен быть >=0 имеем m_1 >= e. T.e сажаем x_1 на минимум, x_k = (X-m_1)/(N-1).

У нас есть цикл по b_i и g_i. По формулам находим все коэффициенты и решение. Проверям, что необходимые условия выполнены.

[goldenstate]

Я понимаю загрузку генератора как процент от 0 до 100% соответствующий его мин и мах. Так что 50% это к примеру (мах-мин)/2.

Если так, то уравнение получится: min1+delta1*P + min2+delta2*P + ... + minN+deltaN*P = X. Откуда находится неизвестное P (процент загрузки).

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

А как на практике устанавливают этот процент зарузки? Там все генераторы заранее откалиброваны (типа рычажок на нужное деление ставится) или применяется какой-либо автоматический метод "проб и ошибок" (типа PID loop control), если надо в процессе работы менять мощность (или суммарную мощность)?