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

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

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

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

где cj, dj, bi, aij — постоянные коэффициенты и djxj ≠ 0.

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

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

Будем считать, что d1x1 + d2x2 ≠ 0.

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

Найдем х2:

Прямая x2 = kx1 проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k прямой тоже фиксирован и прямая займет определенное положение. При изменении значений L прямая х2 = kx1 будет поворачиваться вокруг начала координат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Найдем x2: L = (2x1 + 3x2) / (x1 + x2), 2x1 + 3х2 = Lx1 + Lx2, x2 (3 – L) = x1 (L – 2),

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

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

Найдем координаты точки С.

Решая систему

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

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

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

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

Обозначим

при условии

и введем новые переменные уj = y0xj.

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

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

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

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