Определение.

Общая форма задачи ЛП

Графический метод решения задач ЛП

При нахождении решения задачи ЛП графическим методом могут встретиться следующие случаи:

Целевая функция не ограничена сверху Система ограничений задачи несовместна

на множестве допустимых решений (некорректная постановка задачи). Нет ОДР

Пусть заданы: множества I={1,2…m} и J={1,2…n}, причем I= I₁U I₂, I₁ Ç I₂ = Æ, J= J₁UJ₂, J₁Ç J₂ = Æ, вещественные числа а_ij, iÎI, jÎJ; b_i , iÎI, с_j , jÎJ.

ЗАДАЧА 1 (прямая со смешанными ограничениями)

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

(1)

на множестве векторов х=( х₁,х₂, …х_n,), (2)

удовлетворяющих условиям:

1. х_j ³0 для jÎJ₂ (3)

2. (4)

Двойственная задача ЛП

ЗАДАЧА 1* (двойственная со смешанными ограничениями).

Минимизировать линейную функцию

(5)

на множестве векторов y=(y₁,y₂,…..y_m), (6)

удовлетворяющих условиям:

1. y_i ≥ 0 для iÎI₂ (7)

2.(8)

Векторы (2), (6), удовлетворяющие условиям (3), (4) и (7), (8) называются допустимым для задачи 1 и задачи 1* соответственно.

Допустимые векторы (2), (6), доставляющие максимум функции (1) и минимум функции (5) соответственно, называются оптимальными.

Правила составления двойственной задачи ЛП

В задаче 1 имеется n-переменных и m- ограничений типа (4). В задаче 1* имеется m –переменных и n-ограничений типа (8). Это значит, что каждой переменной в задаче 1 соответствует ограничение в задаче 1* и каждому ограничению в задаче 1 соответствует переменная в задаче 1*.

В задаче 1 требуется максимизировать целевую функцию на множестве заданных ограничений больше 0. В задаче 1* требуется минимизировать целевую функцию на множестве заданных ограничений меньше 0.

Коэффициенты с_j линейной функции (1) в задаче 1 являются свободными членами ограничений (8) задачи 1*, свободные члены b_i ограничений (4) в задаче 1 являются коэффициентами линейной функции (5) задачи 1*.

Коэффициенты при неизвестных а_ij в задачах 1 и 1* одни и те же, но матрицы из этих коэффициентов транспонированы по отношению друг к другу.

В задаче 1 все неравенства типа ³ , а в задаче 1* все неравенства типа £.

Если на переменную задачи 1 налагается условие неотрицательности, то соответствующее ограничение в двойственной задаче является неравенством, а если условия неотрицательности на переменную нет, то соответствующее ограничение в задаче 1* является уравнением. И наоборот.