This is my question Строительный подрядчик оценивает потребность в количестве рабочей силы на каждуюиз последующих пяти недель как 5, 7,8, 4 и 6 рабочих. Подрядчик может наниматьи увольнять рабочих в начале каждой недели, исходяиз того, что содержание избыточной рабочей силы обходится в 300 руб, на одного рабочего В неделю, выплата выходного пособия для увольнения равна 200 руб, а наем рабочей силы обходится в 400 руб. плюс 200 руб. на каждого рабочего. Чему равны наименьшие затраты на наем and this is my friend's explanation"Начнем с того, что мы знаем, что нам нужно будет иметь 5, 7, 8, 4, 6 рабочих на следующие 5 недель.Еще мы знаем, что
1. Если у нас рабочих больше, чем нужно на неделю, то за каждого рабочего нужно заплатить 300
2. Если мы хотим уволить рабочего, то должны заплатить ему 200
3. Если мы хотим нанять рабочих, то должны заплатить 400, и еще по 200 за каждого рабочего, которого нанимаем.И последнее, что нужно из условия задачи - нужно найти НАИМЕНЬШИЕ затраты, и все рабочие будут уволены в конце недели 5.Сперва нам нужно определить все ОПТИМАЛЬНЫЕ состояние, которые могут быть. Pi - состояние в начале недели i.Теперь давай определим ОПТИМАЛЬНОЕ состояние на каждую неделю:1. P1 = {0}, потому что в начале недели 1 у нас нет рабочих (все только началось, и мы еще не успели никого нанять).По условию задачи мы знаем, что на неделю 1 нам требуются 5 рабочих. Тогда за неделю 1 мы наймем КАК МИНИМУМ 5 рабочих (меньше мы не можем, потому что нам нужно хотя бы 5). Но мы можем нанять больше, если для нас это будет выгодно (то есть если это будет дешевле). Но сколько МАКСИМАЛЬНО мы можем нанять рабочих за неделю 1. Ответ: МАКСИМАЛЬНО мы можем нанять 8 рабочих, потому что больше нам НИКОГДА НЕ ПОТРЕБУЕТСЯ (нам нужно 5, 7, 8, 4, 6). Так мы получаем состояния на неделю 2:2. P2 = {5, 6, 7, 8}, потому что за неделю 1 наняли минимально 5 и максимально 8 рабочих.3. P3 = {7, 8}, потому что на неделе 2 нам нужно было МИНИМАЛЬНО 7 рабочих. Если на неделе 1 у нас было 5 рабочих, то мы нанимаем 2 или 3. Если было 6, то 1 или 2. Если 7, то 1 или не нанимаем. Если 8, то точно не нанимаем.4. P4 = {8}, потому что на неделе 3 нам нужно было 8 рабочих. Нанимать больше рабочих, чем 8, НЕ ОПТИМАЛЬНО, потому что нам никогда не потребуется больше рабочих, чем 8.5. P5 = {4, 5, 6}, потому что на неделе 4 нам нужно хотя бы 4 рабочих. Но мы можем иметь больше рабочих, потому что на неделе 5 нам понадобятся 6 рабочих. То есть на начало недели 5 у нас МИНИМАЛЬНО 4 (если мы решили, что нам выгоднее будет иметь только требуемое число рабочих) и МАКСИМАЛЬНО 6 (если мы решили, что нам выгоднее будет оставить столько рабочих, чтобы хватило на следующую неделю).6. P6 = {6}, потому что на начало недели 5 нам требуется 6 рабочих. Больше рабочих нанимать нет смысла, потому что в конце недели 5 все будут уволены, потому что больше не нужны.Посмотри на функцию Ti(p, q). Здесь и дальше используются p и q. p - количество рабочих, которое есть на начало недели i, q - количество рабочих, которое мы решили нанять за неделю i.Ti(p, q) - функция перехода к следующему состоянию. Ti(p, q) = p + q, потому что мы суммируем текущее количество рабочих и количество, которое мы решили нанять. В начале следующей недели (i + 1) будет p + q рабочих.gi(p, q) - затраты на наем и увольнение сотрудников на неделе i.gi записывается из этих условий.Только вместо 200 мы писали 2, чтобы было проще считать.Просто делим все затраты на 100.Это никак не связано с решением, просто так удобнее считать.Если ты хочешь, можешь не делить затраты на 100.Дальше самое сложное - определение fn(p).fn(p) - это затраты СУММАРНЫЕ МИНИМАЛЬНЫЕ затраты на неделе n в состоянии p. Из условия мы знаем, что нужно найти НАИМЕНЬШИЕ затраты.При решении этих задач мы используем метод, который называется "N-шаговый процесс принятия решений".Как я понимаю, его суть состоит в том, что мы начинаем "с конца" и идем к началу, суммируя fn(p) для различных состояний. Для нашей задачи N=5 (потому что 5 недель), а p - состояние на шаге n.Теперь можем записать функцию fn(p).Начинаем с n=N=5.f5(p) = min g5(p, q). То есть на неделе 5 мы МИНИМИЗИРУЕМ только затраты на неделю 5. Мы знаем, что на неделе 5 нам нужно 6 рабочих, поэтому можем записать q = 6 - p, то есть f5(p) = min g5(p, 6 - p).А дальше на каждом шаге n мы суммируем затраты за шаг n (gn) и суммарные минимальные затраты за все следующие шаги до N (f_n+1).При этом также нужно учесть, что для f_n+1 состояние измениться, потому что мы уволим или наймем новых рабочих на текущем шаге n.То есть нужно считать f_n+1(Tn(p, q)) = f_n+1(p + q).Если все объединить, то получаем, что
fn = min g_n(p, q) + f_n+1(p + q).Дальше рисуем вот эту таблицу. Для тех состояний, которые никогда не будут, можно зачеркнуть. Я ставил крестики (x).Например, для n=3 P3 = {7, 8}.Все остальное можно зачеркнуть и не считать.И теперь осталось самое простое.Начинаем все считать.Начинаем с n=5, состояние можно выбрать любое из 4, 5, 6.Пусть n=5, p=4.f5(4) = g5(p, q) = g5(4, q) = 4 + 2q = 4 + 2 * 2 = 8.Здесь q = 2, потому что P6 = {6}.То есть мы знаем, что в начале недели 6 может быть только 6 рабочих, а у нас их 4 (p = 4). Тогда нанимаем 2 рабочих (q = 2).f5(5) считается так же, только p = 5 и q будет равно 1 (6 - p).f5(6) = 0, потому что q = 0, и нам не нужно никого нанимать или увольнять.Записываем результаты для n=5 в таблицу.Нужно обязательно записывать fn и qn, чтобы в конце можно было восстановить оптимальное решение.Дальше начинаем расчет для n=4.И здесь будет самая важная часть, постараюсь хорошо объяснить.Так же можем начать с любого состояния для n=4. Но у нас может быть только одно состояние (p=8), поэтому считаем его, то есть f4(8).Мы знаем, что на n=5 может быть 3 состояния: 4, 5, 6.Чтобы из состояния p = 8 на следующем шаге перейти в состояния 4, 5 или 6, нужно уволить 4, 3 или 2 рабочих.То есть:
1. p = 8 -> p = 4    q = -4
2. p = 8 -> p = 5    q = -3
3. p = 8 -> p = 6    q = -2.Нужно посчитать для каждого q и взять то, которое дает МИНИМАЛЬНОЕ значение для f4(8).Считаем q = -4:
 g_n(p, q) + f_n+1(p + q) = g4(8, -4) + f5(8 - 4) = (-2 * (-4) + 3 * 0) + 8 = 8 + 8 = 16.Считаем q = -3:
 g_n(p, q) + f_n+1(p + q) = g4(8, -3) + f5(8 - 3) = (-2 * (-3) + 3 * (8 - 3 - 4)) + 6 = 6 + 3 * 1 + 6 = 15.Минимальное - 10, поэтому f4(8) = 10, q = -2.Записываем в таблицу.Дальше считаем для n=3.Для n = 3 есть 2 состояния: 7 и 8.Начнем, например, с p = 7.То есть считаем f3(7).Мы знаем, что на следующем шаге (n=4) есть только состояние 8. Поэтому считаем только:
p = 7 -> p = 8    q  = 1.Минимум искать не нужно, потому что только один вариант.Расчеты можешь посмотреть в моей тетради, подробно писать не буду.Если будут вопросы, то пиши, и я помогу.Дальше считаем для p = 8.f3(8):
p = 8 -> p = 8    q = 0.Опять минимум не нужен, потому что один q.Записываем результаты в таблицу.Дальше так же для n = 2. Начнем с p = 5. f2(5):
p = 5 -> p = 7    q = 2
p = 5 -> p = 8    q = 3
Нужно взять минимум, потому что возможно 2 варианта (для n = 3 есть 2 состояния: 7 и 8).Дальше для n=2, p = 6:
p = 6 -> p = 7    q = 1
p = 6 -> p = 8    q = 2.Так же считаем для (n=2, p=7) и (n=2, p = 8).После этого переходим к n = 1 (завершающий шаг). Здесь есть только состояние 0. Но на шаге n=2 есть 4 состояния. Поэтому нужно найти минимум из:
p = 0 -> p = 5    q = 5
p = 0 -> p = 6    q = 6
p = 0 -> p = 7    q = 7
p = 0 -> p = 8    q = 8.Получаем, что f1(0)=37. Это и есть ответ задачи.Минимальные затраты равны 37.После этого нужно также восстановить порядок того, как мы нанимали работников. То есть найти все qi, которые приводят к оптимальному решению 37.Начинаем с p1 = 0 (n=1) - исходное состояние.Из таблицы знаем, что для f1(0) q = 5. То есть q1* = 5.Если q1* = 5, то тогда происходит переход: p = 0 -> p = 5, то есть p2* = 5.Из таблицы знаем, что для f2(p2*) = f2(5) q = 3, то есть q2* = 3.Если q2* = 3, то тогда происходит переход: p = 5 -> p = 8, то есть p3* = 8.И так далее.Так получаем q1*, q2*, q3*, q4*, q5* - оптимальные решения для недель 1, 2, 3, 4, 5.И если мы будем использовать эти оптимальные решения, то получим МИНИМАЛЬНЫЕ затраты, которые равны 37.I don't understand.Explain me in English language