1.Общие сведения

1. Скалярное произведение

Скалярным произведением называется сумма попарных произведений соответственных координат векторов или произведение их длин на косинус угла между ними

(ab)= a₁b₁ + a₂b₂ + … + a_nb_n = |a| |b| cos 

2. Частная производная

Пусть F(x )=F(x₁,x₂,… x_n,) определена в некоторой окрестности точки x₀(x₁₀,x₂₀,… x_n0). Производная F(x ) по переменной x₁, вычисленная в предположении, что все остальные переменные не меняются (т.е. производная вдоль прямой, параллельной оси x₁) называется частной производной первого порядка по x₁ в точке x₀(x₁₀,x₂₀,… x_n0). Эта частная производная обозначается F/x₁(x₁₀,x₂₀,… x_n0) или F_x1(x₁₀,x₂₀,… x_n0)

2.Градиент

Пусть n-мерный вектор, здесь символом «′» обозначена операция транспозиции, которая превращает строки в столбцы и столбцы в строки, а F(x) – дважды непрерывно дифференцируемая функция переменной x , т.е. F(x) функция n переменных x_i. Градиентом F(x) в точке x₀ называется n-мерный вектор-столбец = , координатами которого являются частные производные F(x) по координатам x_i, вычисленные в некоторой точке x₀. Основные свойства:

1. Используя вектор-градиент можно записать первый дифференциал в виде скалярного произведения:

dF= ( dx) = │ │ │dx│ cos φ

Здесь cos φ это косинус угла между вектором смещения dx и градиентом. Из такой формы записи следует несколько выводов:

2. Производная по любому направлению равна проекции градиента на это направление.

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

4. В направлении перпендикулярном градиенту производная равна нулю. Т.к. вдоль линии уровня производная очевидно равна нулю (функция вдоль линии уровня не меняется) то понятно, что линия уровня в каждой своей точке перпендикулярна градиенту (проекция градиента равна производной по направлению, а производная в направлении линии уровня нуль).

5. Для линейной функции F(х) = c₁ x₁ + c₂ x₂ +.... c_n x_n = (cx) градиентом является постоянный вектор коэффициентов (c₁, c₂,.... c_n)′= c т.е. линейная функция быстрее всего растет в направлении c , и вообще растет только в тех направлениях, на которые c имеет положительную проекцию.

3. Первый дифференциал

Пусть F(x) в окрестности точки x₀ имеет непрерывные производные по всем переменным, тогда называется дифференцируемой в точке x₀ и ее приращение имеет вид:

F=F(x₀+dx) – F(x₀) =

При этом скалярное произведение градиента на вектор смещения называется первым дифференциалом:

2.Линейное программирование

1. Основная и симметричная задача

Основной задачей ЛП (ОЗЛП) называется такая задача: найти переменные x₁, x₂,... x_n которые доставляют максимум целевой функции

F(х) = c₁ x₁ + c₂ x₂ +.... c_n x_n = (cx) max (4)

при ограничениях-равенствах:

 Ax = b (5)

и ограничениях-неравенствах: x  0 (6)

Допустимым вектором (планом) ОЗЛП называется всякий вектор x, удовлетворяющий уравнениям (5) и неравенствам (6). Допустимый вектор, доставляющий максимум целевой функции F(х), называется решением задачи линейного программирования.

Стандартной (симметричной) задачей линейного программирования называется следующая задача:

Найти вектор x, доставляющий максимум(минимум) целевой функции

F(х) = c₁ x₁ + c₂ x₂ +.... c_n x_n = (cx)max

при ограничениях-неравенствах:

(в матричной форме – Ax  b )

и требованиях неотрицательности¹:

x₁  0, x₂  0,... x_n  0  x  0

Всякую симметричную задачу можно превратить в основную, вводя новые неотрицательные переменные – невязки неравенств y_i= b_i – a_ij x_j Например:

3x₁ + 5x₂ ≤ 4 3x₁ + 5x₂ + 1y₁ + 0y₂ = 4

2x₁ – 5x₂ ≤ 6 2x₁ – 5x₂ + 0y₁ + 1y₂ = 6

x₁ ≥0 x₂ ≥0 x₁ ≥0 x₂ ≥0 y₁ ≥0 y₂ ≥0

В общем случае: симметричная задача

Ax  b превращается в основную задачу

Ax +Еу = b

x  0 x  0 у  0

2. Геометрические соображения