Виды задач линейного программирования

Задачей линейного программирования называется задача минимизации (максимизации) линейной функции при линейных ограничениях. В зависимости от вида ограничений говорят о различных формах задачи линейного программирования.

Общей задачей линейного программирования называется следующая задача: найти.

или.

при условиях.

где йу, Ь₍, Cj — заданные постоянные величины ик<�т.

Совокупность чисел X* = (xj, х₂,…, х^), удовлетворяющих условиям (14.2) — (14.5), называется допустимым решением задачи линейного программирования. Подчеркнем, что решением является именно вектор Х в то время как выражение L (X) = maxL (x_1; х₂,…, х") — условие правильности решения задачи, т. е. критерий.

Стандартной задачей линейного программирования называется такая задача, которая содержит лишь условия (14.1), (14.2), (14.5). Поскольку здесь допускаются неравенства только в одну сторону, то эту задачу иногда называют симметричной.

Задача (14.1) при условиях.

называется основной (канонической) задачей линейного программирования (ОЗЛП).

На практике может возникнуть задача линейного программирования в так называемой исходной форме, которая может оказаться самой различной. В то же время методы решения задач линейного программирования разрабатываются, как правило, только для ОЗЛП. Поэтому надо уметь переводить любую исходную задачу линейного программирования к каноническому виду.

Чтобы перейти от исходной формы к канонической, необходимо выполнить следующие действия:

1) задача на минимум (mini!) переводится к задаче на максимум (maxL). Это обеспечивается умножением функции L_a на (-1), т. е.

2) ограничения вида «» — путем вычитания из левой части соответствующего ограничения дополнительной неотрицательной новой переменной, т. е.

и.

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

Пример 14.1.

Задачу найти минимум функции при условиях

привести к канонической форме.

Решение. Соответствующая задача линейного программирования в канонической форме (ОЗЛП) имеет вид.

при условиях.

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

при условиях где.

или.

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