Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
(3.8)
при условиях
(3.9)
(3.10)
. (3.11)
где - заданные постоянные величины и .
Функция (3.8) называется целевой функцией (линейной формой) задачи (3.8)-(3.11), а условия (3.9)-(3.11) – ограничениями данной задачи.
Стандартной (симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (3.8) при условиях (3.9) и (3.11), где k=m и l=n.
Канонической (основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (3.8) при условиях (3.10) и (3.11), где k= 0 и l=n.
Совокупность чисел , удовлетворяющих ограничениям (3.9)-(3.11), называется допустимым решением (планом).
План , при котором целевая функция (3.8) принимает свое максимальное (минимальное) значение, называется оптимальным.
- оптимальный план задачи, если (в задаче на максимум) и (в задаче на минимум).
Замечание. Все 3 формы задачи линейного программирования эквивалентны:
1) Если требуется найти минимум функции
,
можно перейти к нахождению максимума функции
,
т.к. min z=-max(-z).
2) От знака «» в ограничениях можно перейти к «=» добавлением к левой части ограничения дополнительной переменной, а от знака «» - вычитанием дополнительной неотрицательной переменной.
3) Число вводимых дополнительных переменных равно числу преобразуемых неравенств.
Пример 3.1. Записать в форме основной задачи линейного программирования следующую задачу: найти максимум функции
(3.12)
при условиях
(3.13)
Решение. Чтобы записать в форме основной задачи нужно перейти к ограничениям-равенствам:
(3.14)
Данная задача может быть записана в форме основной таким образом: максимизировать функцию (3.12) при условиях (3.14).
Пример 3.2. Записать задачу, состоящую в минимизации функции
(3.15)
при условиях
(3.16)
в форме основной задачи линейного программирования.
Решение. Вместо нахождения минимума функции z нужно найти максимум функции при ограничениях, получающихся из исходных добавлением к левым частям неравенств «», и вычитанием из левых частей неравенств со знаком «» дополнительных переменных. Тогда исходная задача может быть записана в форме основной задачи линейного программирования так:
при условиях
Пример 3.3. Записать следующую задачу в стандартной форме линейного программирования: найти максимум функции
(3.17)
при условиях
(3.18)
Решение. Выпишем расширенную матрицу системы и с помощью метода исключения неизвестных Жордана-Гаусса приведем ее к ступенчатой форме:
~ ~ ~ ~ .
Таким образом, исходную систему мы свели к следующей:
Выразим и через и и подставим в z
Тогда задача будет состоять в нахождении максимального значения функции
при условиях
Замечание. Вводимые дополнительные переменные имеют вполне экономический смысл. Так, если в ограничениях исходной задачи отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса.