Это набор (1, 1, 1, 0, 0). Значит найденный набор является решением задачи.

Решение в EXCEL.

Сервис, поиск решения

У становить целевую функцию равную

Максимальное значение

Изменяя ячейки

Ограничения х_i – двоичное

	i	1	2	3	4	5
	Сi	5	4	6	5	3
	рi	2	2	1	2	1	pixi
	xi	0	0	0	0	0	cixi

2. Задача о назначениях.

Предположим, что вычислительная сеть выделяет n специализированных ЭВМ. На вход сети поступают задачи. Известно, что наибольшая производительность конкретной сети ЭВМ достигается на определенном классе задач. Это выражается коэффициентом a_ij использования i –ой ЭВМ при решении j – ого класса задач. Найти оптимальное распределение задач по сети таким образом, что бы эффективность ее использования была наибольшей.

Линейные рекуррентные соотношения.

Рассмотрим последовательность u_n, n=1,2,…Будем говорить, что задано однородное линейное рекуррентное соотношение с постоянными коэффициентами порядка r, если для членов последовательности выполняется равенство

u_n+r=c₁u_n+r-1+ c₂u_n+r-2+ c₁u_n+r-1+ …+c_ru_n, (1)

где с₁, с₂, …, с_n-постоянные величины. Выражение позволяет вычислить очередной пласт последовательности по предыдущим r членам.

Задав точные значения последовательности u₁,u₂,…,u_r-1 можно последовательно определить все члены последовательности. Существует метод решения рекуррентного отношения, т.е. нахождения u_n как функцию от n.

Для решения задачи достаточно найти производящую функцию последовательности u_n.Нам понадобится полинома

K(x)=1-c₁x-c₂x²-…-c_rx^r и произведение u(x)K(x)=c(x).

Характеристикой полином является соотношение (1), которое можно разложить на множества

F(x)=x^r-c₁x^r-1-c₂x^r-2-…-c_r-1x-c_r.

K(x)=x_rF .

Задача. Найти члены последовательности u_n, удовлетворяющие рекуррентному соотношению:

U_n+2=5u_n+1-6u_n, u₀=u₁=1.

Решение. K(x)=1-5x+6x²,

K(x)U(x)=C(x)

Выполним данное умножение:

( 1-5x+6x²)(u₀+u₁x+u₂x²+…)=u₀+(u₁-5u₀)x+ (u₂-5u₁+6u₂)x²+…= u₀+(u₁-5u₀)x = 1-4x.

Т.о.C(x)=1-4x.

Представим U(x) в виде суммы простых дробей.

Значения величин А и В находим методом неопределённых коэффициентов:

A(1-3x)+B(1-2x)=1-4x

A +B=1

-3A-2B=-4

A =1-B

(1-B)3+2B=4

A =1-B

3-3B+2B=4

A=2; B=-1.

Далее,

С другой стороны Поэтому, сравнивая коэффициенты при одинаковых степенях xⁿ заключаем, что U_n=2ⁿ⁺¹-3ⁿ.

Числа Фибоначчи.

Числа называются числами Фибоначчи, если

f₀=f₁=1, f_n=f_n-1+f_n-2, n≥2.

Их производящая функция имеет вид:

F(t)=1+t+2t²+3t³+5t⁴+8t⁵+13t⁶+…

Общая запись F(t):

F(t)=1+t+(f₁+f₀)t²+…+(f_n-1+f_n-2)tⁿ+…

F(t)=(1-t-t²)^-1.

Ещё F(t)=(1-at)(1-bt), где

a и b определяем из соотношения

a+b=1, ab=-1,

откуда .

Число Фибоначчи f_k есть число способов расположения n знаков, n≥1, из которых каждый есть либо 0, либо 1, в последовательность не содержащую двух нулей подряд.