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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(Створена сторінка: '''Постановка задачі та алгоритм розв’язування''' Розв’язуючи економічні задачі, часто з...)
 
 
Рядок 1: Рядок 1:
−
'''Постановка задачі та алгоритм розв’язування'''
+
'''ПОСТАНОВКА ЗАДАЧІ ТА АЛГОРИТМ РОЗВ'ЯЗУВАННЯ'''
  
 
Розв’язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:  
 
Розв’язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:  
Рядок 17: Рядок 17:
 
<center><math> \sum_{j=1}^n d_j y_j - d_0 y_0 = 1  ,  y_{j}\ge 0  (j=\overline{1,n})  ,  y_{0}> 0 </math></center>   
 
<center><math> \sum_{j=1}^n d_j y_j - d_0 y_0 = 1  ,  y_{j}\ge 0  (j=\overline{1,n})  ,  y_{0}> 0 </math></center>   
  
−
Дістали задачу лінійного програмування, яку можна розв’язати симплексним методом. Нехай оптимальний план <math>y_{0j} = y_{01} , y_{02},.., y_{0n}, y_0 </math>
+
Дістали задачу лінійного програмування, яку можна розв’язати симплексним методом. Нехай оптимальний план <math> y_0j = { y_{01} , y_{02} ,.., y_{0n} , y_0 } </math>
−
Оптимальні значення <math>x_j</math> знайдемо за формулою: <math>x_{0j} = {y_{0j} \over y_0} (j=\overline{1,n})</math>  
+
Оптимальні значення <math>x_j</math> знайдемо за формулою: <math>y_{0j} = {y_{0j} \over y_0} (j=\overline{1,n})</math>  
 
----
 
----
−
'''Приклад'''  
+
'''ПРИКЛАД'''  
  
−
Сільськогосподарське акціонерне товариство з обмеженою відповідальністю, яке розміщене в Лісостепу України, має намір оптимізувати структуру виробництва. За критерій оптимальності взято максимізацію рентабельності як відношення прибутку до собівартості. Дані про види діяльності, що їх здійснюватиме товариство, наведено в таблиці:
+
Розв’язати графічно задачу дробово-лінійного прог­рамування:<center><math>Z=\frac{5x_1-2x_2}{2x_1+x_2}\rightarrow max(min)</math> </center>
 +
за умов
 +
<center><math>\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}</math></center>
 +
 
 +
Розв’язання.Побудуємо на площині область допустимих роз­в’язків задачі — трикутник АВС.
 +
 
 +
[[Файл:inx38_clip_image106.gif]]
 +
 
 +
Цільова функція задачі являє собою пряму, яка обертатиметься навколо початку системи координат залежно від змінюваних параметрів х1, х2 так, що точки А і С будуть точками максимуму і мінімуму функції. Виразимо х2 із цільової функції:
 +
 
 +
<center><math> x_2=x_1\frac{5-2Z}{Z+2} </math></center>
 +
 
 +
Кутовий коефіцієнт цільової функції:
 +
 
 +
<center><math> R_Z= \frac{5-2Z}{Z+2} </math></center>
 +
 
 +
Розглянемо похідну:
 +
 
 +
<center><math> \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} </math></center>
 +
 
 +
Оскільки при будь-якому значенні Z вона від’ємна, то функція RZ є спадною (зі зростанням Z кутовий коефіцієнт RZ зменшується), а графік цільової функції обертатиметься навколо початку координат за годинниковою стрілкою. Отже, точка С є точкою максимуму, а точка А — мінімуму досліджуваної задачі.
 +
Знайдемо координати цих точок.
 +
 
 +
<center><math> \begin{cases} 2x_1+3x_2=12 \\ -x_1+2x_2=6 \end{cases} </math></center>
 +
 
 +
Точка А:
 +
 
 +
<center><math> \triangle \ = \begin{vmatrix} 2 & 3 \\ -1 & 2 \end{vmatrix} =4+3=7 </math> ;  <math> \triangle \ _1 = \begin{vmatrix} 12 & 3 \\ 6 & 2 \end{vmatrix} =24-18=6 </math> ; <math> \triangle \ _2 = \begin{vmatrix} 2 & 15 \\ -1 & 6 \end{vmatrix} =12+12=24 </math>
 +
 
 +
Звідси: <math> x_1 = \frac{6}{7} , x_2 = \frac{24}{7} </math>
 +
 
 +
Точка А має координати (<math>\frac{6}{7} </math>; <math>\frac{24}{7}</math>).
 +
 
 +
<center><math> \begin{cases} 2x_1+3x_2=12 \\ 2x_1-x_2=8 \end{cases} </math></center>
 +
 
 +
Точка С:
 +
 
 +
<center><math> \triangle \ = \begin{vmatrix} 2 & 3 \\ 2 & -1 \end{vmatrix} =-2-6=-8 </math> ; <math> \triangle \ _1 = \begin{vmatrix} 12 & 3 \\ 8 & -1 \end{vmatrix} =-12-24=-36 </math> ;  <math> \triangle \ _2 = \begin{vmatrix} 2 & 12 \\ 2 & 8 \end{vmatrix} =16-24=-8 </math>
 +
 
 +
Звідси :<math> x_1 = \frac{-36}{-8} = \frac{9}{2} , x_2 = \frac{-8}{-8} = 1 </math>
 +
 
 +
Точка С має координати (<math>\frac{9}{2} </math>; 1 ).
 +
 
 +
Знайдемо значення цільової функції в цих точках:
 +
 
 +
<math> Z_A= \frac{5 \cdot \frac{6}{7} -2 \cdot \frac{24}{7} }{2 \cdot \frac{6}{7} +  \frac{24}{7}} = - \frac{1}{2} </math>;  <math> Z_C= \frac{5 \cdot \frac{9}{2} -2 \cdot 1 }{2 \cdot \frac{9}{2} +  1} =  \frac{40}{21} </math>;
 +
 
 +
Результати (<math> Z_C > Z_A </math>) підтверджують, що оптимуми знайдено правильно: максимум досягається в точці С, а мінімум — у точці А.
 +
 
 +
== ''Див. також''  ==
 +
----
 +
* [[Постановка цілочислової задачі ЛП. Геометрична інтерпретація]]
 +
* [[Розв’язування дробово-лінійної задачі зведенням до задачі лінійного програмування]]
 +
 
 +
----
 +
[http://ubooks.com.ua/books/000114/inx38.php Джерело]

Поточна версія на 18:47, 17 травня 2012

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

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

Неможливо розібрати вираз (невідома помилка): 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}

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

Inx38 clip image106.gif

Цільова функція задачі являє собою пряму, яка обертатиметься навколо початку системи координат залежно від змінюваних параметрів х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 ) підтверджують, що оптимуми знайдено правильно: максимум досягається в точці С, а мінімум — у точці А.

Див. також

Джерело
Отримано з https://wiki.cusu.edu.ua/index.php?title=Економічна_і_математична_постановка_задачі_дробово–лінійного_програмування._Геометрична_інтерпретація&oldid=68203