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

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

Задача дробно-линейного программирования (ЗДЛП) в общем виде записывается следующим образом: при ограничениях: , , где - постоянные коэффициенты и .

Рассмотрим ЗДЛП в виде при ограничениях , .

Будем считать . Найдем ОДР. Пусть она не пустое множество.

Из найдем : , .

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

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

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

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

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

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

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

4. ОДР неограничена. Максимум и минимум являются асимптотическими.

Алгоритм решение ЗДЛП:

· Находим ОДР.

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

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

Пример. Для производства двух видов изделий А и В пред

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

приятие использует 3 типа технологического оборудования. Каждое из изделий должно пройти обработку на каждом из типов оборудования.

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

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

Математическая модель задачи: при ограничениях .

ОДР – треугольник АВС.

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

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

Дата добавления: 2014-12-27