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

• Решение онлайн
• Видеоинструкция

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

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

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

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

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

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

при условии d₁·x₁+d₂·x₂+ ... + d_j·x_j ≠ 0
и введем новые переменные y_j=y₀·x_j. Тогда задача примет вид
L=c₁·y₁+c₂·y₂+ ... + c_j·y_j → max(min)
при ограничениях

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

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

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

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

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

Пример №4.

18x₁+0.2x₂≤20 (*)
2.55x₁+1.2x₂≤45 (**)
x₁, x₂≥0

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

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

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