Дробно-линейное программирование. Математическая модель задачи. Использование дробно-линейного программирования в управлении.

 

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

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

(4)

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

(5)

(6)

где с_j, d_j, b_i, a_ij - постоянные коэффициенты и .

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

(7)

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

(8)

(9)

Будем считать, что .

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

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

где

Прямая x₂ = kx₁ проходит через начало координат.

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

При изменении значений L прямая x₂ = kx₁ будет поворачиваться вокруг начала координат (рис. 28.6).

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

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

Если угловой коэффициент прямой имеет положительное значение, то прямая вращается против часовой стрелки, при о трицательном значении k - по часовой стрелке.

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

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

1. ОДР ограничена, максимум и минимум достигаются в ее угловых точках (рис. 28.7).

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

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

4. ОДР неограничена. Максимум и минимум являются асимптотическими (рис. 28.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 вида.

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

(10)

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

(11)

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

(12)

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

(13)

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

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

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

Тип оборудования	Затраты времени на обработку одного изделия, часы
А	В
І
ІІ
ІІІ
Затраты на производство 1 изделия, тыс. грн.

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

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

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

Пусть X₁ - количество изделий вида А, которое следует изготовить предприятию, X₂ — количество изделий вида В.

Общие затраты на их производство составят (2Х₁ + 3X₂) тыс. грн., а средняя себестоимость одного изделия будет равна:

.

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

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

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

Найдем X₂:

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

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

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

X₁=3, X₂=1,

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

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