Загальна задача лінійного програмування
Оскільки всі наведені приклади задач
лінійного програмування схожі за математичною моделлю, то
можна сформулювати загальну задачу лінійного програмування.
У кожному з наведених
прикладів задач вхідні дані задовольняють деяку систему
обмежень:
a[1,1]*x[1] + a[1,2]*x[2] + ... + a[1,n]*x[n] <=> b[1]
a[2,1]*x[1] + a[2,2]*x[2] + ... + a[2,n]*x[n] <=> b[2]
-----------------------------------------------------------------
a[m,1]*x[1] + a[m,2]*x[2] + ... + a[m,n]*x[n] <=> b[m]
де a[i,j], b[i] - фіксовані
дійсні числа, а символ « <=> » означає один із знаків «<=», «>=», «=». Саме ця система обмежень описує
умови, які накладаються на вхідні дані задачі.
Для отримання розв'язку задачі потрібно задати
формулу, яка визначає мету досягнення результату
(максимальне або мінімальне значення). У загальному випадку її можна представити так:
L = c[1]*x[1] + c[2]*x[2] + ... + c[n]*x[n]
де c[i] набуває дійсних значень. Наведений вираз
називається цільовою функцією.
Рівняння, яке представляє цільову функцію,
має безліч розв'язків x[1], x[2], ..., x[n]. Однак
серед них потрібно вибрати тільки ті, які
задовольняють систему обмежень даної задачі. Але і таких розв'язків є багато, оскільки система обмежень
має невідомих більше, ніж нерівностей ( n >
m ).
Сукупність таких невід'ємних розв'язків,
які задовольняють систему обмежень, називається допустимими розв'язками або
планами даної задачі.
Задача лінійного програмування полягає у
тому, щоб серед усіх планів вибрати той, при якому цільова
функція набуває оптимального (максимального або мінімального) значення, тобто
зводиться до відшукання оптимального
плану.
Зауважимо, що для задач лінійного програмування
рівняння (цільова функція) і система
нерівностей (обмежень) носять лінійний характер.
Немає коментарів:
Дописати коментар