Формулировка задачи. Даны линейная функция (1.1) Z = С 1 х 1 +С 2 х 2 + +С N x N и система линейных ограничений a 11 x 1 + a 22 x 2 + + a 1N Х N = b 1 a 21 x 1 + a 22 x 2 + + a 2N Х N = b 2 a i1 x 1 + a i2 x 2 + + a iN Х N = b i (1.2) a M1 x 1 + a M2 x 2 + + a MN Х N = b M (1.3) x j 0 (j = 1, 2, ,n) где а ij , Ь j и С j - заданные постоянные величины.
Найти такие неотрицательные значения х 1 , х 2 , х n, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1)минимальное значение.
Общая задача имеет несколько форм записи. Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях (1.4) А 1 х 1 + А 2 x 2 + + А N x N = А о , X 0 где С = (с 1 , с 2 , с N ); Х = (х 1 , х 2 , х N ); СХ - скалярное произведение; векторы A 1 , A 2 A N , A 0 состоят соответственно из коэффициентов при неизвестных и свободных членах. Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А 0 , Х 0, где С = (с 1 , с 2 , с N ) - матрица-cтрока; А = (а ij ) - матрица системы; Х - матрица-столбец, А 0 - матрица-столбец Запись с помощью знаков суммирования.
Минимизировать линейную функцию Z = С j х j при ограничениях 0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х 1 , х 2 , х N ), удовлетворяющий условиям (1.2) и (1.3). 0пределение 2. План Х = (х 1 , х 2 , х N ) называется опорным, если векторы А (i = 1, 2, N), входящие в разложение (1.4) с положительными коэффициентами х, являются линейно независимыми.
Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М. 0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным. 0пределение 4 . Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.
В дальнейшем рассмотрено решение задач линейного программирования, связанных с нахождением минимального значения линейной функции. Там, где необходимо найти максимальное значение линейной функции, достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней функции. Заменяя на противоположный знак полученного минимального значения, определяем максимальное значение исходной линейной функции. 2.