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

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

(6.37)

(6.38)

(6.39)

. (6.40)

 

Будем считать, что на допустимом множестве X задачи (6.37)…(6.40) знаменатель целевой функции из (6.37) не обращается в нуль и, соответственно, сохраняет знак. Если этот знаменатель отрицателен, то умножим числитель и знаменатель дроби из (6.44) на -1 и будем в дальнейшем считать, что > 0 для всех xÎX.

Обозначим (очевидно, y0 > 0 при xÎX) и введем новые переменные В новых переменных задача (6.44)…(6.47) принимает следующий вид:

i = 1:l,

(6.41)

т.е. превращается в задачу линейного программирования. Отметим, что требование , включенное в условие задачи (6.41), не ограничивает возможного изменения переменной , так как > 0 при xÎX.

Найдем решение задачи линейного программирования (6.41) и, используя равенства:

(6.42)

получим решение исходной задачи дробно − линейного программирования (6.37)…(6.40).

Если то допустимое множество X задачи (6.37)…(6.40) не ограниченно и минимум целевой функции f(x) на нем не достигается.

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

(6.43)

при условиях (6.38)…(6.40).

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

. (6.44)

Из (6.44) найдем

или

где ; уравнение разрешающей прямой, проходящей через начало координат. С изменением h разрешающая прямая вращается относительно начала координат. Направление вращения разрешающей прямой определяется по знаку производной . Отрицательный знак производной соответствует вращению разрешающей прямой по часовой стрелке, а положительный – против часовой стрелки. Вращая построенную прямую (6.44) вокруг начала координат, либо определяем вершину (вершины), в которой функция (6.43) принимает максимальное значение, либо устанавливаем неограниченность функции на множестве планов задачи.

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

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

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

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

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

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

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

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

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

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

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

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

 

 

Рис. 6.11. Ограниченный Рис. 6.12. Неограниченный многогранник

многогранник решений решений (max и min существуют)

 

 

Рис. 6.13. Неограниченный многогранник Рис. 6.14. Неограниченный много-

решений (асимптотический max) гранник решений (асимптотический

max и min)