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

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

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

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

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

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

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

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

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

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

Прямая x ₂ = kx ₁ проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k прямой тоже фиксирован и прямая займет определенное поло­жение. При изменении значений L прямая х ₂ = 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 вида.

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

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

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

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

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

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

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

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

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

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

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

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

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

Δ АВС — область допустимых решений (рис. 28.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) возрастает. Это соответствует вращению прямой против часовой стрелки. Следовательно, в точке С (рис. 28.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 ₄. Задача примет вид

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

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

Получим

тогда

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