Дробно-линейное программирование.

Математическая модель задачи.

Дробно-линейное программирование (ДЛП) относится к нелинейному программированию, т.к. имеет целевую функцию, заданную в нелинейном виде. Задача ДЛП в общем виде записывается следующим образом: найти экстремум функции L = при ограничениях = b_i, i = 1,m, xj => 0, где c_j, d_j, a_ij, b_i – постоянные коэффициенты и при этом 0.

Рассмотрим задачу ДЛП в виде: L = (c₁x₁ + c₂x₂)/(d₁x₁ + d₂x₂) -> max (min), при ограничениях a_i1x₁ + a_i2x₂ = b_i (<=) и x₁, x₂ >= 0. Будем считать, что d₁x₁ + d₂x₂ 0. Для решения этой задачи найдем многоугольник решений, определяемой записанными ограничениями. Пусть этот многоугольник не представляет пустое множество. Найдем из значения целевой функции из выражения целевой функции переменную х₂.

L = (c₁x₁ + c₂x₂)/(d₁x₁ + d₂x₂) | * (d₁x₁ + d₂x₂)

L = (d₁x₁ + d₂x₂) = (c₁x₁ + c₂x₂)

Ld₁x₁ + Ld₂x₂ = c₁x₁ + c₂x₂

x₂ (Ld₂ – c₂) = x₁ (c₁ – Ld₁)

x₂ = (c₁ – Ld₁)/(Ld₂ – c₂ * x₁)

где k = (c₁ – Ld₁)/(Ld₂ – c₂), тогда x₂ = kx₁ – прямая, проходящая через начало координат.

При некотором фиксированном значении L, угловой коэффициент k тоже фиксирован, и прямая займет определенное положение. При изменении значения L, прямая x₂ = kx₁ будет поворачиваться вокруг начала координат.

x₂

L₂

x₁

L₁

Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Для этого найдем производную коэффициента k по переменной L.

dk/dL = k’_L = ((c₁ – Ld₁)/(Ld₂ – c₂))’ = ((c₁ – Ld₁)’ * (Ld₂ – c₂) – (c₁ – Ld₁) * (Ld₂ – c₂)’)/(Ld₂ – c₂)² = (-d₁*(Ld₂ – c₂) – (c₁ – Ld₁) * d₂)/(Ld₂ – c₂)² = (-Ld₁d₂ + d₁c₂ – c₁d₂ + Ld₁d₂)/(Ld₂ – c₂)² = (d₁c₂ – c₁d₂)/(Ld₂ – c₂)².