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

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

при ограничениях
,
где сj,dj,bi,aij – постоянные коэффициенты.
d1x1+d2x2+...+dnxn ≠ 0
Целевая функция
Количество ограничений:

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

при ограниченияхдробный линейный программирование

Будем считать, что
d1x1+d2x2 ≠ 0.
Математическая модель задачи дробно-линейного программирования может быть использована для определения рентабельности затрат на производство изделий, рентабельности продаж, затрат в расчете на рубль выпускаемой продукции, себестоимости изделий.

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

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

Оборудование I и III типов предприятие может использовать не более 26 ч и 39 ч соответственно, оборудование II типа целесообразно использовать не менее 4 ч.
Определить, сколько изделий каждого вида следует изготовить предприятию, чтобы средняя себестоимость одного изделия была минимальной.
Решение. Составим математическую модель задачи. Пустьх1 – количество изделий видаА,которое следует изготовить предприятию,х2количество изделий видаВ.Общие затраты на их производство составят (2х1+3х2) тыс. руб., а средняя себестоимость одного изделия будет равна
.

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

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

при условии
и введем новые переменные.Тогда задача примет вид

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

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

Пример №2. Решить задачу дробно-линейного программирования симплексным методом.

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

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

при ограничениях
.
Составляем симплекс-таблицу.

Базис План z
0 -10 4 1 1 0 0
0 -10 1 4 0 1 0
z 2 8 3 2 0 0 1
L -2M -8M -3M-2 -2M-1 0 0 0

В последней оценочной строке есть отрицательные оценки, поэтому нужно делать шаг симплекс-метода. Выбираем столбец с наименьшей оценкой, а затем разрешающий элемент – по наименьшему отношению свободных членов к коэффициентам столбца. Результат шага запишем в таблицу. Аналогично будем повторять шаги.
Базис План z
5/2 0 31/4 7/2 1 0 5/4
5/2 0 19/4 13/2 0 1 5/4
1/4 1 3/8 1/4 0 0 1/8
L 0 0 -2 -1 0 0 M

Базис План z
10/31 0 1 14/31 4/31 0 5/31
30/31 0 0 135/31 -19/31 1 15/31
4/31 1 0 5/62 -3/62 0 2/31
L 20/31 0 0 -3/31 8/31 0 M+10/31

Базис План z
2/9 0 1 0 26/135 -14/135 1/9
2/9 0 0 1 -19/135 31/135 1/9
1/92/3 1 0 0 -1/27 -1/54 1/18
L 0 0 0 11/45 1/45 M+1/3

Получили решение
,,,.
Тогда, возвращаясь к исходным переменным, получим:
,,.

Пример №3. Рассмотрим следующую задачу.
Завод выпускает продукцию n видов p1,…,pn. В процессе производства используются m видов сырья S1,…,Sm, запасы которого ограничены. Требуется составить производственный план таким образом, чтобы обеспечить максимально возможную рентабельность работы заводов. Нормы расхода сырья, его запасы, а также удельные и условно постоянные затраты и прибыль, получаемая заводом от реализации одного изделия, приведены в таблице 2.
Таблица 2 - Исходные данные

Сырье Продукция Запасы
. . . . . . сырья
. . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .

Удельные затраты
на 1 изделие
. . . . . . Условно-постоянные затраты

d0


Прибыль от реализации изделия
. . . . . .

Определения:
1. Рентабельность – показатель, представляющий собой отношение прибыли к сумме затрат на производство (%).
2. Условно-переменные (удельные) затраты – затраты, которые изменяются прямо пропорционально объемам выпуска товаров (затраты на материалы, энергию, комплектующие, зарплату).
3. Условно-постоянные затраты – затраты, которые практически не зависят от изменения количества выпускаемой продукции (затраты на освещение, арендная плата и др.).
Пусть x1,..,xn– объем выпуска продукции p1,…,pn Математическая модель будет иметь вид:



Сведем данную задачу к задаче линейного программирования. Обозначим через 1/δ знаменатель целевой функции, δ>0.

Умножим правую и левую части ограничения модели на δ Получим
;



Обозначим Получим модель линейного программирования с переменными и δ



Пример №4.

(*)
(**)

Решение.











Решаем симплекс-методом. Получим
%.

Тогда
Графическое решение задачи приведено на рис. 1.

Рис. 1- Геометрическая интерпретация задачи
Ограничения задачи – это множество допустимых решений, лежащих в четырехугольнике АВСО. Целевая функция задачи – линии уровня цели, проходящие через точку S. Координаты точки S определяются в результате решения системы уравнений:
(числитель целевой функции);

(знаменатель целевой функции).