1.5.2. Сведение задачи дробно-линейного программирования к задаче линейного программирования
Сформулированная выше задача (1.28) - (1.29) может быть сведена к задаче линейного программирования. Для этого следует обозначить
(1.42)
н ввести новые переменные
(1.43)
Используя введенные обозначения, исходную задачу (1.28) - (1.29) сведем к следующей: найти максимум функции
(1.44)
при условиях
(1.45)
и
Задача (1.44) - (1.45) является задачей линейного программирования, а следовательно, ее решение можно найти известными методами. Зная оптимальный план этой задачи, на основе соотношений (1.43) получаем оптимальный план исходной задачи (1.28) - (1.29).
Таким образом, процесс нахождения решения задачи дробно-линейного программирования включает следующие этапы:
1. Сводят задачу (1.28) - (1.29) к задаче линейного программирования (1.44) - (1.45).
2. Находят решение задачи (1.44) - (1.45).
3. Используя соотношения (1.43), определяют оптимальный план задачи (1.28) - (1.29) и находят максимальное значение функции (1.28).
Задача 1.2:
Найти максимальное значение функции
(1.46)
при условиях
(1.47)
Решение.
Сведем данную задачу к задаче линейного
программирования. Для этого обозначим
и
введем новые переменные
.
В результате приходим к следующей
задаче: найти максимум функции
(1.48)
при условиях
(1.49)
Задача (1.48) - (1.49) является задачей линейного программирования. Ее решение находим симплекс-методом.
Таблица 1.5
|
Б |
Зн |
y1 |
y2 |
y3 |
y4 |
y5 |
y0 |
|
y3 |
0 |
1 |
2 |
-1 |
0 |
0 |
-11 |
|
y4 |
0 |
1 |
-1 |
0 |
1 |
0 |
-8 |
|
y5 |
0 |
-1 |
3 |
0 |
0 |
1 |
-9 |
|
y0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
f(y) |
0 |
-2 |
-1 |
0 |
0 |
0 |
0 |
|
Б |
Зн |
y1 |
y2 |
y3 |
y4 |
y5 |
y0 |
|
y3 |
-1 |
0 |
1 |
-1 |
0 |
0 |
-11 |
|
y4 |
-1 |
0 |
-2 |
0 |
1 |
0 |
-8 |
|
y5 |
1 |
0 |
4 |
0 |
0 |
1 |
-9 |
|
y1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
f(y) |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
| |||||||
|
Б |
Зн |
y1 |
y2 |
y3 |
y4 |
y5 |
y0 |
|
y0 |
1/11 |
0 |
-1/11 |
1/11 |
0 |
0 |
1 |
|
y4 |
-3/11 |
0 |
-30/11 |
8/11 |
1 |
0 |
0 |
|
y5 |
20/11 |
0 |
35/11 |
9/11 |
0 |
1 |
0 |
|
y1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
f(y) |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
| |||||||
|
Б |
Зн |
y1 |
y2 |
y3 |
y4 |
y5 |
y0 |
|
y0 |
1/10 |
0 |
0 |
1/15 |
-1/30 |
0 |
1 |
|
y2 |
1/10 |
0 |
1 |
-4/15 |
-11/30 |
0 |
0 |
|
y5 |
15/10 |
0 |
0 |
5/3 |
7/6 |
1 |
0 |
|
y1 |
9/10 |
1 |
0 |
4/155 |
11/30 |
0 |
0 |
|
f(y) |
19/11 |
0 |
0 |
4/15 |
11/30 |
0 |
0 |
Из таблицы видно, что оптимальным планом задачи (1.48) - (1.49) является y1*=9/10; у2*=1/10; y3*=y4*=0; y5*= 15/10; y0*=1/10.
Учитывая, что yi = y0xi, находим оптимальный план задачи (1.46) —(1.47): Х*=(9; 1; 0; 0; 15). При этом плане Fmax=19/10.