Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Метод Гомори Графический метод Теория игр
Симплекс-метод M-задача Теоремы двойственности
Одноканальные СМО Задача коммивояжера Транспортная задача

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

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

при ограничениях
,
где с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) тыс. руб., а средняя себестоимость одного изделия будет равна .

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

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

при условии d1·x1+d2·x2+ ... + dj·xj ≠ 0
и введем новые переменные yj=y0·xj. Тогда задача примет вид
L=c1·y1+c2·y2+ ... + cj·yj → max(min)
при ограничениях

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

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

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

при ограничениях
.
Обозначим , yj=y0·xj, j=1,4.
Тогда задача принимает вид L=2y1+y2 → max
при ограничениях
.
Решим полученную задачу симплекс-методом. Введем дополнительную переменную, чтобы получить единичный базис:
L=2y1+y2-Mz → max
при ограничениях
.
Составляем симплекс-таблицу.

Базис План y0 y1 y2 y3 y4 z
y3 0 -10 4 1 1 0 0
y4 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

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

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

Базис План y0 y1 y2 y3 y4 z
y1 2/9 0 1 0 26/135 -14/135 1/9
y2 2/9 0 0 1 -19/135 31/135 1/9
y0 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 - Исходные данные

Сырье Продукция Запасы
p1 . . . pj . . . pn сырья
S1 a11 . . . a1j . . . a1n b1
. . . . . . . . . . . . . . . . . .
Si ai1 . . . aij . . . ain bi
. . . . . . . . . . . . . . .
Sm am1 . . . amj . . . amn bm

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

d0


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

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


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

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


xj≥0, δ>0, j=1,n
Обозначим yj=xj·δ. Получим модель линейного программирования с переменными xj, j=1,n и δ.


∑dj·yj+d0·δ=1
yj≥0, j=1,n, δ>0.

Пример №4.

18x1+0.2x2≤20 (*)
2.55x1+1.2x2≤45 (**)
x1, x2≥0

Решение.
0.01x1+0.04x2+1=1/δ
Z=0.012x1δ+0.008x2δ → max
18x1δ+0.2x2δ≤20δ
2.55x1δ+1.2x2δ≤45δ
0.01x1δ+0.04x2δ+δ=1
x1≥0, x2≥0, δ>0

y1=x1δ, y2=x2δ
18y1+0.2y2-20δ≤0
2.55y1+1.2y2-45δ≤0
0.01y1+0.04y2+δ=1
y1≥0, y2≥0, δ>0
Решаем симплекс-методом. Получим
y1=5, y2=10, z=14%.
δ=1-0.01y1-0.04y2 = 0.55
Тогда x1=5/0.55 = 9.09, x2=10/0.55 = 18.18.
Графическое решение задачи приведено на рис. 1.

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