НЕЛІНІЙНЕ ПРОГРАМУВАННЯ

Задача дробово-лінійного програмування. Геометрична інтерпретація та геометричний метод

Як і у випадку задачі про використання сировини, позначимо через \(x_{k}\) кількість продукції \(P_{k}\), яку планується виробляти, а через \(c_{k}\) – прибуток від її реалізації. Тоді загальний прибуток буде визначатись сумою $$\sum_{k=1}^{n}{c_{k}x_{k}}$$

Через \(d_{k}\) позначимо витрати на виробництво одиниці продукції \(P_{k}\). Тоді загальні витрати визначатимуться сумою \(\sum_{k=1}^{n}{d_{k}x_{k}}\)

Одним з показників економічного стану виробництва є рентабельність $$Z=\frac{\sum_{k=1}^{n}{c_{k}x_{k}}}{\sum_{k=1}^{n}{d_{k}x_{k}}}$$

Розглядаючи рентабельність Z як критерій ефективності виробництва, як правило, шукають її екстремальні значення (максимум та мінімум) за умов виконання обмежень, щодо використання ресурсів:$$\begin{cases} & \sum_{k=1}^{n}{a_{ik}x_{k}} \leq b_{i}, \left( i = 1,...,m\right); x_{k} \geq 0, \left( k = 1,...,n \right), \end{cases}$$

(1)

де \(b_{i} \geq 0\) для всіх \(i = 1,...,m\).

Отже, математична модель задачі про рентабельність виробництва має вигляд: знайти максимум дробово-лінійної функції Z за умов (1)

У загальній постановці задача дробово-лінійного програмування має ви-гляд: знайти максимум (мінімум) дробово-лінійної функції$$F=\frac{c_{0}+\sum_{k=1}^{n}{c_{k}x_{k}}}{d_{0}+\sum_{k=1}^{n}{d_{k}x_{k}}}$$

(2)

за умов, що \(d_{0}+\sum_{k=1}^{n}{d_{k}x_{k}}\neq 0\) , коефіцієнти \(c_{k}\) і \(d_{k}\) не пропорційні, а змінні \(x_{k}, (k = 0, 1, ... , n)\) задовольняють обмеженням$$\begin{cases} & \sum_{k=1}^{n}{a_{ik}x_{k}} \begin{Bmatrix} \leq \\ \geq \end{Bmatrix} b_{i}, \left( i = 1,...,m\right); x_{k} \geq 0, \left( k = 1,...,n \right), \end{cases}$$

(3)

де \(bi \geq 0\) для всіх і = 1, …, n

У загальному випадку цю задачу заміною змінних можна звести до задачі лінійного програмування і розв’язати її симплексним методом. Ми познайомимось з такими перетвореннями пізніш. А зараз розглянемо геометричну ілюстрацією та відповідний метод розв’язування такої задачі: $$z=\frac{c_{1}x_{1}+c_{2}x_{2}}{d_{1}x_{1}+d_{2}x_{2}}\rightarrow max \left( min \right)$$

(4)
$$\begin{cases} \sum_{k-1}^{2}{a_{ik}x_{k}\begin{Bmatrix}\leq \\ \geq \end{Bmatrix}b_{i}}, (i=1,...,m), x_{k} \geq 0, (k = 1,...,n), \end{cases}$$
(5)

де \(b_{i}\geq 0\) для всіх і = 1, …, m.

Мал.1

Умовам (5) у площині \(0x_{1}x_{2}\) відповідає багатокутник (обмежений або необмежений) допустимих розв’язків. Припустимо, що це чотирикутник АВСD (Мал.1).

Візьмемо довільну точку (\(x_{1}, x_{2}\)), яка належить цьому чотирикутнику і обчислимо відповідне значення функції $$z=\frac{c_{1}x_{1}+c_{2}x_{2}}{d_{1}x_{1}+d_{2}x_{2}}$$

(6)

Пряма l, що проходить через початок координат та точку (\(x_{1}, x_{2}\)) має рівняння \(x_{2}=kx_{1}\) , де k – кутовий коефіцієнт. Перетворимо рівність (6), поділивши чисельник і знаменник на \(x_{1}\):$$z=\frac{c_{1}+c_{2}k}{d_{1}+d_{2}k}$$

Звідки знаходимо залежність кутового коефіцієнта k від значення функції z:$$k=\frac{c_{1}-zd_{1}}{zd_{2}-c_{2}k}$$

(7)

При зміні z буде змінюватись і кутовий коефіцієнт k, а пряма \(x_{2}=kx_{1}\) буде обертатись навколо початку координат.

Визначимо умови зростання або спадання коефіцієнту k в залежності від зміни z. Для цього обчислимо похідну$$\frac{dk}{dz}=-\frac{-d_{1}(zd_{2}-c_{2})-d_{2}(c_{1}-zd_{1})}{(zd_{2}-c_{2})^2}=-\frac{c_{1}d_{2}-c_{2}d_{1}}{(zd_{2}-c_{2})^2}$$

(8)

Знак похідної (8) визначається чисельником, який не залежить від z. Отже, похідна має сталий знак і при зростанні z буде або тільки зростати, або тільки спадати. Навпаки, при обертанні прямої в одному напрямку функція z буде також або тільки зростати, або тільки спадати.

Для зручності запишемо чисельник в (8) у вигляді визначника \(\begin{vmatrix} c_{1} & c_{2} \\ d_{1} & d_{2} \end{vmatrix}= c_{1}d_{2}-c_{2}d_{1}\) і встановимо правила пошуку екстремуму функції z.

Нехай \(\begin{vmatrix} c_{1} & c_{2} \\ d_{1} & d_{2} \end{vmatrix}>0\). Тоді похідна \(\frac{dk}{dz}<0\), тобто зростанню z відповідає спадання коефіцієнта k і навпаки зростанню коефіцієнта k відповідає спадання функції z


Правило 1. Якщо \(\begin{vmatrix} c_{1} & c_{2} \\ d_{1} & d_{2} \end{vmatrix}>0\), то для пошуку точки максимуму треба пряму l повертати навколо початку координат за ходом годинникової стрілки, а при пошуку точки мінімуму – проти ходу годинникової стрілки.

Геометрична ілюстрація цього правила представлена на Мал.1. Пряма з найменшим значенням кута φ співпадає з відрізком СD: у точках відрізка СD функція z приймає максимальні значення, а задача має альтернативні розв’язки.

Якщо \(\begin{vmatrix} c_{1} & c_{2} \\ d_{1} & d_{2} \end{vmatrix}<0\), то похідна \(\frac{dk}{dz}>0\), а кутовий коефіцієнт k є зростаючою функцією z.

Правило 2. Якщо \(\begin{vmatrix} c_{1} & c_{2} \\ d_{1} & d_{2} \end{vmatrix}<0\), то для відшукання точки максимуму треба пряму l повертати навколо початку координат проти ходу годинникової стрілки, а для відшукання точки мінімуму – за ходом годинникової стрілки.


2013-05-14 • Просмотров [ 6083 ]