1.5. Решение задач дробно-линейного программирования

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

Общая задача дробно-линейного программирования состоит в определении максимального значения функции

(1.25)

при условиях

(1.26)

где c_j, d_j, b_i и a_ij – некоторые постоянные числа,

и (1.27)

в области неотрицательных решений системы линейных уравнений.

При этом будем предполагать, что (такое условие не нарушает общности задачи, поскольку в том случае, когда эта величина отрицательна, знак минус можно отнести к числителю).

Как и в случае основной задачи линейного программирования, свое максимальное значение целевая функция задачи (1.25) - (1.26) принимает в одной из вершин многогранника решений, определяемой системой ограничений (1.26) (естественно, при условии, что эта задача имеет оптимальный план). Если максимальное значение целевая функция задачи (1.25) принимает более чем в одной вершине многогранника решений, то она достигает его также во всякой точке, являющейся выпуклой комбинацией данных вершин.

Рассмотрим задачу, состоящую в определении максимального значения функции

(1.28)

при условиях

(1.29)

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

Чтобы найти решение задачи (1.28) - (1.29), сначала находим многоугольник решений, определяемый ограничениями (1.29). Предполагая, что этот многоугольник не пуст, полагаем значение функции равным некоторому числу h, так что прямая

(1.30)

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

Итак, процесс нахождения решения задачи (1.28) - (1.29) включает следующие этапы:

1. В системе ограничений задачи заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые.

2. Находят полуплоскости, определяемые каждым из неравенств системы ограничений задачи.

3. Находят многоугольник решений задачи.

4. Строят прямую (1.30), уравнение которой получается, если положить значение целевой функции (1.28) равным некоторому постоянному числу.

5. Определяют точку максимума или устанавливают неразрешимость задачи.

6. Находят значение целевой функции в точке максимума.

Задача 1.1:

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

Таблица 1.4

Тип оборудования	Затраты-времени (ч) на обработку одного изделия
	А	В
I II III	2 1 12	8 1 3
Затраты на производство одного изделия (руб)	2	3

Оборудование I и III типов предприятие может использовать не более 26 и 39 ч. При этом оборудование II типа целесообразно использовать не менее 4 ч. Требуется определить, сколько изделий каждого вида следует изготовить предприятию, чтобы себестоимость одного изделия была минимальной.

Решение. Предположим, что предприятие изготовит х₁ изделий вида А и х₂ изделий вида В. Тогда общие затраты на их производство равны 2х₁+3х₂ руб., а себестоимость одного изделия в рублях составит

(1.31)

Затраты времени на обработку указанного количества изделий на каждом из типов оборудования соответственно составят 2х₁ + 8x₂ часов, х₁ + х₂ часов и 2х₁ – Зх₃ часов. Так как оборудование I и III типов может быть занято обработкой изделий вида А и В не более 26 и 39 ч, а оборудование II типа — не менее 4 ч, то должны выполняться следующие неравенства:

(1.32)

По своему экономическому смыслу переменные х₁ и х₂ могут принимать только лишь неотрицательные значения:

(1.33)

Таким образом, математическая постановка задачи состоит в определении неотрицательного решения системы линейных неравенств (1.32), реализующего минимум функции (1.31). Чтобы найти решение задачи, прежде всего построим многоугольник решений. Как видно из рис. 1, им является треугольник ВСD. Значит, функция (1.31) принимает минимальное значение в одной из точек: В, С или D.

Рис. 1.5

Чтобы определить, в какой именно, положим значение функции F равным некоторому числу, например 11/4. Тогда

(1.34)

или

(1.35)

Уравнение (1.35) определяет прямую, проходящую через начало координат. Координаты точек, принадлежащих этой прямой и многоугольнику решении, являются планами задачи, при которых значение функции (1.31) равно 11/4. В данном случае к указанным точкам относится лишь одна точка В (1; 3). Ее координаты определяют план задачи, при котором значение функции равно 11/4.

Возьмем теперь h=5/2, т.е. положим

(1.36)

или

(1.37)

Уравнение (1.37), так же как и (1.35), определяет прямую, проходящую через начало координат. Ее можно рассматривать как прямую, полученную в результате вращения по часовой стрелке вокруг начала координат прямой (1.35). При этом координаты точек, принадлежащих прямой (1.37) и многоугольнику решений, являются планами задачи, при которых значение функции (1.31), равное 5/2, меньше, чем в точках прямой (1.35). Следовательно, если положить значение функции (1.31) равным некоторому числу h₀:

(1.38)

а прямую (1.38), проходящую через начало координат, вращать в направлении движения часовой стрелки вокруг начала координат, то получим прямые

где (1.39)

Найдем последнюю общую точку вращаемой прямой с многоугольником решений. Это точка D (3; 1), в которой достигается минимум функции (96).

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

(1.40)

При нахождении угловой точки многоугольника решений, в которой целевая функция задачи принимает наименьшее значение, мы полагали значение функции равным некоторым двум постоянным числам и установили направление вращения прямой, определяющее уменьшение значения функции. Это можно было сделать и по-другому. А именно: полагая значение функции F равным некоторому числу h, т. е.

(1.41)

и получив некоторую прямую, проходящую через начало координат и имеющую угловой коэффициент, зависящий от h, можно, используя производную, установить направление вращения прямой (1.41) при возрастании h.

Практически же дело обстоит гораздо проще. Найдя точки В (1; 3) и D (3;1), в которых функция (1.31) может принимать минимальное значение, вычислим ее значения в этих точках: F(В)=11/4, F(D)=9/4. Так как F(В)>F(D), то можно утверждать, что в точке D целевая функция принимает минимальное значение. Одновременно с этим заметим, что в точке В функция F принимает максимальное значение.

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

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

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

3. Многогранник решений не ограничен, и один из экстремумов достигается. Например, минимум достигается в одной из вершин многогранника решений и функция F имеет так называемый асимптотический максимум (рис. 1.8).

4. Многогранник решений не ограничен, как максимум, так и минимум являются асимптотическими (рис. 1.9).

Рис.1.6 Рис. 1.7

Рис.1.8 Рис. 1.9