Page 13 - 6197

яка задовольняє обмеження (1.2), називається допустимим
R
планом, а функція   x , що визначена співвідношенням (1.1)
носить назву функції мети (критерію оптимальності).
Допустимий план, що максимізує функцію мети (1.1) є
оптимальним планом.
 
Бувають задачі, коли замість мінімуму функції R x
необхідно знайти максимум функції мети
n
Z   x   c x . (1.4)
j
j
j 1 
У такому випадку шляхом введення функції
R   x   Z   x задача (1.4) зводиться до задачі (1.1).

1.2 Основні теореми задачі лінійного програмування
Випуклою множиною називається множина, якій разом з
будь-якими її точками належить відрізок, що з’єднує ці точки.
Відрізок, що з’єднує дві точки є геометричне місце точок,
координати яких задовольняють рівняння
  1   2
x   x  1  x . (1.5)
i i i
Крайніми точками випуклої множини називаються точки,
координати яких не можуть бути виражені через відповідні
координати будь-яких інших двох точок множини за
формулою (1.5).
Випукла множина може мати кінцеве або нескінчене число
крайніх точок (багатокутник, круг).
Будемо називати випуклим багатокутником замкнуту
обмежену випуклу множину, якщо сукупність її крайніх точок
кінцева.
Сформуємо без доказу основні теореми лінійного
програмування.
Теорема 1. Множина точок (векторів) (1.3), які
задовольняють умови (1.2) є випуклою.

13