Определение. Общей ЗЛП называется задача, которая состоит в определении максимального или минимального значения функции
(1)
при условиях 
(2)
где аij,. bi, gj- - заданные постоянные величины и к < m.
Определение. Стандартной или симметричной ЗЛП называется задача, которая состоит в определении максимального (минимального) значения функции
(3)
при условиях
(4)
Определение. Канонической или основной ЗЛП называется задача, которая состоит в определении минимального значения функции
при условиях
(5)
при условиях
(6)
Определение. Функция (5), экстремум которой ищется, называется целевой функцией или функцией цели ЗЛП: системы неравенств (4) или уравнений (6) называются системами ограничения ЗЛП,
Определение. Совокупность чисел х = (x1,х2,...хn), удовлетворяющая системе ограничений (6), называется допустимым решением или планом ЗЛП.
Определение. Совокупность всевозможных допустимых решений ЗЛП называется областью допустимых решений ЗЛП.
Определение. Допустимое решение задачи, при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным решением или оптимальным планом ЗЛП.
Указанные выше три формы записи ЗЛП эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть переписана в форме другой задачи. Это означает, что если имеется способ нахождения решения одной из указанных задач, то тем самым может быть определен оптимальный план любой из трех задач.
Чтобы перейти от одной формы записи ЗЛП к другой, нужно в общем случае уметь, во-первых, сводить задачу максимизации функции к задаче минимизации, во-вторых, переходить от ограничений -неравенств к ограничениям - равенствам и, наоборот, в-третьих, заменять переменные, которые не подчинены условию не отрицательности.
В том случае, когда требуется найти максимум функции
f = c1xl + с2х2 +... + cnxn -> max, (7)
можно перейти к нахождению минимума функции
F = -f = -c1x1 - c2х2 -... - cnxn -> min. (8)
При этом
max(f) = - min(-f). (9)
Ограничения-неравенства, имеющие вид "£", можно преобразовать в ограничения-равенства добавлением к левой части дополнительной неотрицательной переменной, а ограничения-неравенства вида "³" - в ограничение-равенство вычитанием из левой части дополнительной неотрицательной переменной. Эти дополнительные переменные называют балансовыми, и в конкретных задачах они имеют вполне определенный экономический смысл. - Таким образом, ограничение-неравенство
a11x1 + a12x2 + … + alnxn £b1
преобразуется в ограничение-равенство
a11x1 + а12х2 +... + alnxn + x n+1 = b1, x n+1 ³ 0,
а ограничение-неравенство
a11x1 + a12x2 +... + alnxn ³ b1 -
в ограничение-равенство
a11xl + a12x2 + … + a1nxn - x n+1 = b1, x n+1 ³ 0.
Пример. Преобразовать постановку данной задачи в каноническую:
 |
Решить пример самостоятельно.
Ответ:
