Общая задача линейного программирования

Стандартной задачей линейного программированияназывается задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условия первого из системы (2) — нетривиального и условия третьего из системы (2) — тривиального.

Канонической (или основной) задачей линейного программированияназывается задача, которая состоит в определении максимальногозначения целевой функции (1) при выполнении второго и третьего условийиз системы(2).

Для перехода от стандартной формы записи задачи линейного программирования к канонической необходимо ограничение - неравенство исходной задачи линейного программирования, имеющее вид «», преобразуется в ограничение — равенство с добавлением к левой части дополнительной неотрицательной переменной. Ограничение — неравенство вида « »преобразуется в ограничение — равенство вычитанием из левой части дополнительной неотрицательной переменной.

В системе из m линейных уравнений с n переменными базисными (основными) называются любые mпеременные, если соответствующий им определитель матрицы коэффициентов отличен от нуля, а остальные (n-m)переменные называются свободными.

В базисном решении все (n-m)свободные переменные равны нулю.

Допустимое базисное решение (опорный план)содержит только неотрицательные переменные, среди которых свободные равны нулю.

Допустимое базисное решение является невырожденным, если все базисные переменные строго положительны, и вырожденным — в противном случае.

Оптимальное решение задачи линейного программированиясовпадает с одним из ее допустимых базисных решений.

Совокупность чисел , удовлетворяющих тривиальным и нетривиальным ограничениям задачи, называется допустимым решением (или в экономических задачах — планом).

Совокупность допустимых решений формирует область допустимых решений (ОДР).

План , при котором целевая функция задачи принимает экстремальное значение, называется оптимальным.

В случае, когда требуется найти минимум функции

можно перейти к нахождению максимума функции

так как

тогда полученное решение целевой функции следует записать с обратным знаком.

Контрольные вопросы

1. Каковы особенности задач линейного программирования?

2. Какое решение системы линейных уравнений является планом?

3. Что называют планом ОЗЛП, опорным планом, оптимальным планом?

4. Какой опорный план называется вырожденным, невырожденным?

5. Как привести к канонической форме ОЗЛП: а) если требуется найти минимум линейной функции цели; б) если функциональные ограничения заданы в виде неравенств разного вида и ?