Економічна і математична постановка задачі дробово–лінійного програмування. Геометрична інтерпретація

ПОСТАНОВКА ЗАДАЧІ ТА АЛГОРИТМ РОЗВ'ЯЗУВАННЯ

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

Неможливо розібрати вираз (невідома помилка): Z = \frac {\sum_{j=1}^n {c_j x_j+ c_0}}{\sum_{j=1}^n {d_j x_j+ d_0}}\to max(min) за умов:Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n {a_{ij} x_j = b_i(i=\overline{1,n})}, Неможливо розібрати вираз (невідома помилка): x_{j}\ge 0(j=\overline{1,n})

Припускають, що знаменник цільової функції в області допустимих розв’язків системи обмежень не дорівнює нулю. Алгоритм розв’язування задачі дробово-лінійного програмування передбачає зведення її до задачі лінійного програмування. Щоб виконати таке зведення, позначимо:

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n d_i x_j + d_0=\frac{1}{y_0} ,

зробимо заміну змінних Неможливо розібрати вираз (невідома помилка): y_j = y_0 x_j (j=\overline{1,n}) ,

 і запишемо економіко-математичну модель:

Неможливо розібрати вираз (невідома помилка): max(min) Z=\sum_{j=1}^n c_j y_j + x_0 y_0

за умов:

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n a_{ij} y_j - b_i y_0 = 0 , (i=\overline{1,n}) Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n d_j y_j - d_0 y_0 = 1 , y_{j}\ge 0 (j=\overline{1,n}) , y_{0}> 0

Дістали задачу лінійного програмування, яку можна розв’язати симплексним методом. Нехай оптимальний план Неможливо розібрати вираз (невідома помилка): y_0j = { y_{01} , y_{02} ,.., y_{0n} , y_0 }

Оптимальні значення Неможливо розібрати вираз (невідома помилка): x_j

знайдемо за формулою: Неможливо розібрати вираз (невідома помилка): y_{0j} = {y_{0j} \over y_0} (j=\overline{1,n})

---

ПРИКЛАД

Розв’язати графічно задачу дробово-лінійного прог­рамування:Неможливо розібрати вираз (невідома помилка): Z=\frac{5x_1-2x_2}{2x_1+x_2}\rightarrow max(min)

за умов

Неможливо розібрати вираз (невідома помилка): \begin{cases} 2x_1+3x_2 \ge \ 12 \\ -x_1+2x_2 \le \ 6 \\ 2x_1-2x_2 \le \ 8 \\ x_j \ge \ 0 , j=\overline{1,2} \end{cases}

Розв’язання.Побудуємо на площині область допустимих роз­в’язків задачі — трикутник АВС.

Цільова функція задачі являє собою пряму, яка обертатиметься навколо початку системи координат залежно від змінюваних параметрів х1, х2 так, що точки А і С будуть точками максимуму і мінімуму функції. Виразимо х2 із цільової функції:

Неможливо розібрати вираз (невідома помилка): x_2=x_1\frac{5-2Z}{Z+2}

Кутовий коефіцієнт цільової функції:

Неможливо розібрати вираз (невідома помилка): R_Z= \frac{5-2Z}{Z+2}

Розглянемо похідну:

Неможливо розібрати вираз (невідома помилка): \frac{dR_Z}{dZ} = \left ( \frac{5-2Z}{Z+2} \right )' = \frac{(5+2Z)'(Z+2)-(Z-2)'(5-2Z)}{(Z+2)^2} = - \frac{9}{(Z+2)^2}

Оскільки при будь-якому значенні Z вона від’ємна, то функція RZ є спадною (зі зростанням Z кутовий коефіцієнт RZ зменшується), а графік цільової функції обертатиметься навколо початку координат за годинниковою стрілкою. Отже, точка С є точкою максимуму, а точка А — мінімуму досліджуваної задачі. Знайдемо координати цих точок.

Неможливо розібрати вираз (невідома помилка): \begin{cases} 2x_1+3x_2=12 \\ -x_1+2x_2=6 \end{cases}

Точка А:

Неможливо розібрати вираз (невідома помилка): \triangle \ = \begin{vmatrix} 2 & 3 \\ -1 & 2 \end{vmatrix} =4+3=7

;  Неможливо розібрати вираз (невідома помилка):  \triangle \ _1 = \begin{vmatrix} 12 & 3 \\ 6 & 2 \end{vmatrix} =24-18=6 
; Неможливо розібрати вираз (невідома помилка):  \triangle \ _2 = \begin{vmatrix} 2 & 15 \\ -1 & 6 \end{vmatrix} =12+12=24 

Звідси: Неможливо розібрати вираз (невідома помилка): x_1 = \frac{6}{7} , x_2 = \frac{24}{7}

Точка А має координати (Неможливо розібрати вираз (невідома помилка): \frac{6}{7}

Неможливо розібрати вираз (невідома помилка): \frac{24}{7}

).

<center>Неможливо розібрати вираз (невідома помилка): \begin{cases} 2x_1+3x_2=12 \\ 2x_1-x_2=8 \end{cases}

Точка С:

Неможливо розібрати вираз (невідома помилка): \triangle \ = \begin{vmatrix} 2 & 3 \\ 2 & -1 \end{vmatrix} =-2-6=-8

; Неможливо розібрати вираз (невідома помилка):  \triangle \ _1 = \begin{vmatrix} 12 & 3 \\ 8 & -1 \end{vmatrix} =-12-24=-36 
;  Неможливо розібрати вираз (невідома помилка):  \triangle \ _2 = \begin{vmatrix} 2 & 12 \\ 2 & 8 \end{vmatrix} =16-24=-8 

Звідси :Неможливо розібрати вираз (невідома помилка): x_1 = \frac{-36}{-8} = \frac{9}{2} , x_2 = \frac{-8}{-8} = 1

Точка С має координати (Неможливо розібрати вираз (невідома помилка): \frac{9}{2}

1 ).

Знайдемо значення цільової функції в цих точках:

Неможливо розібрати вираз (невідома помилка): Z_A= \frac{5 \cdot \frac{6}{7} -2 \cdot \frac{24}{7} }{2 \cdot \frac{6}{7} + \frac{24}{7}} = - \frac{1}{2}

Неможливо розібрати вираз (невідома помилка): Z_C= \frac{5 \cdot \frac{9}{2} -2 \cdot 1 }{2 \cdot \frac{9}{2} + 1} = \frac{40}{21}

Результати (Неможливо розібрати вираз (невідома помилка): Z_C > Z_A ) підтверджують, що оптимуми знайдено правильно: максимум досягається в точці С, а мінімум — у точці А.

Див. також

---

• Постановка цілочислової задачі ЛП. Геометрична інтерпретація
• Розв’язування дробово-лінійної задачі зведенням до задачі лінійного програмування

---

Джерело