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

 

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

 

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

Задача дробно-линейного программирования в общем виде записывается следующим образом:

 

при ограничениях:

 

где c_j, d_j, b_i, a_ij — постоянные коэффициенты и d_jx_j ≠0.

Рассмотрим задачу дробно-линейного программирования в виде

 

(1.1)

 

при ограничениях:

(1.2)

 

Будем считать, что d ₁ x ₁ + d ₂ x ₂≠ 0.

Для решения этой задачи найдем область допустимых ре­шений, определяемую ограничениями (1.2). Пусть эта область не является пустым множеством.

Из выражения (1.1) найдем х ₂:

 

 

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

 

Рис. 1.6

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

 

 

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоян­ный знак и при увеличении L угловой коэффициент будет толь­ко возрастать или только убывать, а прямая будет поворачи­ваться в одну сторону. Если угловой коэффициент прямой име­ет положительное значение, то прямая вращается против ча­совой стрелки, при отрицательном значении k — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность за­дачи.

При этом возможны следующие случаи.

1. Область допустимых решений ограничена, максимум и минимум достигаются в ее угловых точках (рис. 1.7).

2. Область допустимых решений неограничена, однако су­ществуют угловые точки, в которых целевая функ­ция принимает максимальное и минимальное значения (рис. 1.8).

3. Область допустимых решений неограничена, имеется один из экстремумов. Например, минимум достигает­ся в одной из вершин области и имеет так называемый асимптотический максимум (рис. 1.9).

4. Область допустимых решений неограничена. Максимум и минимум являются асимптотическими (рис. 1.10).

Алгоритм решения

 

1. Находим область допустимых решений.

2. Определяем угловой коэффициент k и устанавливаем на­правление поворота целевой функции.

3. Находим точку max(min) целевой функции или устана­вливаем неразрешимость задачи.

 

Экономическая интерпретация задач дробно-линейного программирования

 

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

Обозначим: r_j — прибыль предприятия от реализации еди­ницы изделия j -гo вида;

x_j — количество выпущенной продукции j- гo вида;

s_j — цена единицы продукции j- гo вида;

c_j — себестоимость производства единицы изделия j- гoвида;

d_j — затраты на производство одного изделия j -гo вида.

Задача рентабельности (Р _з) затрат на производство изде­лий имеет вид

 

Задача рентабельности (Р_n) продаж имеет вид

 

 

Задача определения затрат (З _р) в расчете на рубль товар­ной продукции записывается в виде

 

Задача нахождения себестоимости изделия записывается как

 

 

Указанные математические модели имеют системы ограниче­ний в зависимости от условий задачи.

 

Применение дробно-линейного программирования для определения себестоимости изделий

 

Рассмотрим использование дробно-линейного программи­рования для нахождении себестоимости изделий.

Пример 6. Для производства двух видов изделий А и В пред­приятие использует три типа технологического оборудования. Каждое из изделий должно пройти обработку на каждом из типов оборудования. Время обработки каждого из изделий, затраты, связанные с производством одного изделия, даны в табл. 1.1

Оборудование I и III типов предприятие может использо­вать не более 26 и 39 ч соответственно, оборудование II типа целесообразно использовать не менее 4 ч.

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

 

Таблица 1.1

 

Решение. Составим математическую модель задачи. Пусть x ₁ — количество изделий вида А, которое следует из­готовить предприятию, x ₂ — количество изделий вида В. Об­щие затраты на их производство составят (2 х ₁ + 3 x ₂) тыс. р., а средняя себестоимость одного изделия будет равна

 

 

Математическая модель задачи примет вид

 

 

при ограничениях:

 

Δ АВС — область допустимых решений (рис. 1.11).

 

Рис. 1.11

 

Найдем x ₂: L = (2 x ₁ + 3 x ₂) / (x ₁ + x ₂), 2 x ₁ + 3 х ₂ = Lx ₁ + Lx ₂, x ₂ (3 - L) = x ₁(L - 2),

 

 

Угловой коэффициент прямой равен k = (L - 2)/(3 — l), тогда

 

 

Так как dk/dL > 0, то функция k = (L - 2)/(3 - L) возрастает. Это соответствует вращению прямой против часовой стрелки. Следовательно, в точке С (рис. 1.11) целевая функция будет иметь наименьшее значение (глобальный минимум).

Найдем координаты точки С. Решая систему

 

 

получим С (3, 1), _опт = (3, 1), L =9/4.

Следовательно, предприятию следует выпускать 3 изделия вида А и 1 изделие вида В. При этом средняя себестоимость одного изделия будет минимальной и равной 2,25 тыс. р.

 

Сведение экономико-математической модели дробно-линейного программирования к задаче линейного программирования

 

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

Обозначим

при условии

 

и введем новые переменные у_j = y ₀ x_j.

Тогда задача примет вид

при ограничениях:

 

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

Пример 7. Дана задача дробно-линейного программирования

 

при ограничениях:

 

Решение. Обозначим: x ₁ + 2 x ₂ + 1 = 1/ у ₀, y ₀ > 0, тогда L = 2 x ₁ y ₀ - x₂y ₀.

Обозначим: x ₁ y ₀ = y ₁, х ₂ у ₀ = у ₂, х ₃ у ₀ = у ₃, х ₄ у ₀ = y ₄.

Преобразуем систему ограничений, умножив обе части всех ограничений на у ₀, и перейдем к переменным у ₀, y ₁, y ₂, y ₃, y ₄. Задача примет вид

 

при ограничениях:

Таблица 1.2

 

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

Получим

тогда

 

Ответ: _опт = (2, 0, 0, 2), L _max = 4/3.

 

Метод множителей Лагранжа

Постановка задачи

 

Дана задача нелинейного программирования

 

при ограничениях:

 

Предположим, что функции f (x ₁, х ₂ ,..., x_п) и g_i(x ₁, x ₂,..., x_п) непрерывны вместе со своими первыми частными про­изводными.

Ограничения заданы в виде уравнений, поэтому для ре­шения задачи воспользуемся методом отыскания условного эк­стремума функции нескольких переменных.

Для решения задачи составляется функция Лагранжа

 

 

где λ _i — множители Лагранжа.

Затем определяются частные производные:

 

Приравняв к нулю частные производные, получим систему

 

 

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

Пример 8. Найти точку условного экстремума функции

 

при ограничениях:

 

 

Решение. Составим функцию Лагранжа

 

 

Найдем частные производные функции Лагранжа по пере­менным x ₁, x ₂, x ₃, λ₁, λ₂. Приравняв к нулю полученные вы­ражения, решим систему

 

Откуда λ₁ = - x ₂, λ₂ = - x ₂/2, х ₁ = -2, x ₂ = -4, x ₃ = 4, L = -8.

Определим характер экстремума, изменяя полученные зна­чения переменных. Измененные значения должны удовлетво­рять заданной системе ограничений. Возьмем х ₁ > -2, напри­мер x ₁ = -1, тогда из системы ограничений получим х ₂ = -3, x ₃ = 7/2, L = -15/2. Возьмем х ₁ < -2, например х ₁ = -3, тогда получим х ₂ = -5, x ₃ = 9/2, L = -15/2. Следовательно, L = -8 — минимальное значение функции.

Ответ. Точка экстремума х ₁ = -2, x ₂ = -4, x ₃ = 4, при этом максимальное значение функции L = -8.

 

Расчет экономико-математической модели при нелинейных реализациях продукции

 

Рассмотрим применение выше приведенных методов на примере решения задачи оптимальной реализации продукции.

Пример 9. Мукомольный комбинат реализует муку двумя способами: в розницу через магазин и оптом через торговых агентов. При продаже x ₁ кг муки через магазин расходы на реализацию составляют х ₁² ден. ед., а при продаже x ₂ кг муки посредством торговых агентов — х ₂² ден. ед.

Определить, сколько килограммов муки следует продавать каждым способом, чтобы затраты на реализацию были мини­мальными, если в сутки выделяется для продажи 5 000 кг муки.

Решение. Составим математическую модель задачи.

Найдем минимум суммарных расходов

 

при ограничениях:

 

Для расчета модели используем метод множителей Лагранжа. Составим функцию Лагранжа

 

 

Найдем частные производные функции F по x ₁, x ₂ и λ, приравняем их к нулю, получим систему уравнений

 

откуда λ = -5 000, x ₁ = 2 500, x ₂ = 2 500, L = 12 500 000 ден. ед.

Давая х ₁ значения больше и меньше 2500, находим L и из определения экстремума функции получаем, что L при х ₁ = x ₂ = 2 500 достигает минимума.

Таким образом, для получения минимальных расходов не­обходимо расходовать в сутки через магазин и торговых аген­тов по 2 500 кг муки, при этом расходы на реализацию составят 12 500 000 ден. ед.