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

Задача планирования производства m(х) = max (30 х1 + 40 х2 ) x 1) х1, х2 ³ 0 2) 12х1 + 4 х2 £ 300 4 х1 + 4 х2 £ 120 3 х1 + 12 х2 £ 252

Основные этапы графического метода решения задач ЛП 1. Строятся прямые, уравнения которых получаются в результате замены в ограничениях 1) и 2) знаков неравенств на знаки точных равенств. 2. Находятся полуплоскости, определяемые каждым из ограничений задачи 3. Определяется область допустимых решений - ОДР (многоугольник решений) 4. Строится вектор С =(С1;С2) (C1 и C2 – коэффициенты при неизвестных в целевой функцииm(x)) 5. Строится линия уровня – как перпендикуляр к вектору С, проходящая через ОДР 6. Линия уровня передвигается в направлении вектора С (если задача поставлена на max) или в противоположном направлении (если задача поставлена на min). В результате находится либо точка оптимума (граничная точка линии уровня с ОДР), либо устанавливается неограниченность функции на множестве допустимых решений. 7. Определяются координаты точки оптимума, и вычисляется значение целевой функции в этой точке.

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

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

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

 

Целевая функция m принимает Целевая функция m принимает max в любой

max в единственной точке А точке отрезка АВ

 

 

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

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

 

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

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

 

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

Пусть заданы: множества 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* является уравнением. И наоборот.

 

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

Пример 1. Записать двойственную задачу к следующей задаче линейного программирования. ЗАДАЧА1. Найти х = (х1, х2, х3, х4), удовлетворяющий условиям:

Решение. Заметим, что т.е все переменные связаны условием неотрицательности, и все ограничения выполняются как неравенства. Двойственная задача имеет вид: ЗАДАЧА 1^* Найти удовлетворяющие условиям:

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

Пример 2. ЗАДАЧА 1. Требуется мак­симизировать линейную функцию =2x1 — х2 + Зх3 + х4 — 5x5 на множестве пятимерных векторов х = (х1, х2, х3, х4, х5), удовлетворяющих условиям , , , Зх1 + 2х2 - 5х3 + х5 - 7 0, 3х2 - 4х3 - 2х4 + 1 = 0, 2х1 + 2х3 - 3х4 + х5 0.

Решение. ЗАДАЧА 1^* Требует­ся минимизировать линейную функцию на множестве трехмерных векторов, удовлетворяющих условиям , , 3y1 + 2y3 + 2 0, 2y1 + 3y2 -1 = 0, - 5y1 + 4y2 + 3y3 + 3 0, - 2y2 - 3y3 +1 0, y1 + y3 - 5 = 0.

Связь между задачами 1 и 1^*

 

Связь между парой двойственных задач устанавливает следующая лемма 1:

Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства

µ(x) £ (у), (9)

причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:

(10)

(11)

 

 

Связь между задачами 1 и 1^*

Доказательство. Имеем:

х_j ³0 для jÎJ₂

(12)

 

Суммируя полученные соотношения, получим с учетом того, что (13)

 

 

Связь между задачами 1 и 1^*

Доказательство (продолжение). Имеем:

y_i ≥ 0 для iÎI₂

(14)

(15)

Правые части в соотношени­ях (13) и (15) отличаются лишь порядком суммирова­ния и, следовательно, равны между собой, т.е. выполняется µ(x) £ (у) (9). Для достижения равенства в (9), очевидно, не­обходимо и достаточно, чтобы достигались равенства во всех неравенствах (13) и (15). Последнее эквива­лентно выполнению соотношений (10) и (11) ▄