Постановка задачи линейного программирования

Для аналитического решения задачи линейного програм­мирования в общем виде используется форма ее ограничений в виде равенств. Перейти от неравенств к равенствам можно, с помощью дополнительных переменных.

Задача линейного программирования, ограничения которой заданы в виде равенств, называется основной задачей линейного программирования, или ка­нонической формой задачи линейного программирования.

Формулировка задачи

Дана линейная функция

и система линейных ограничений

где ― .

Найти неотрицательные значения , которые удовлетворяют системе ограничений и доставляют линейной функции минимальноезначение.

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию при ограничениях

,

где , ― скалярное произведение, векторы

состоят из коэффициентов при неизвестных и свободных членов.

Матричная форма. Минимизировать функцию при ограничениях

,

где — матрица-строка, — матрица системы,

― матрицы-столбцы.

Запись с помощью знаков суммирования. Минимизировать линейную функцию

при ограничениях

.

Определение 1. Планом или допустимым решением задачи линейного программирования называется вектор , удовлетворяющий системе ограничений.

Определение 2. План называется опорным, если векторы и , входящие в разложение с положительными коэффициентами , являются линейно независимыми.

Определение 3. Опорный план называется невырожденным, если он содержит положительных компонент, в противоположном случае опорный план называется вырожденным.

Определение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.