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

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

Найти вектор X=(x₁,x₂,…,x_n), который удовлетворяет системе линейных ограничений и обеспечивает экстремальное (минимальное или максимальное) значение целевой функции. Ограничения могут быть сформулированы в виде равенств или неравенств. В зависимости от этого различают различные формы записи задач линейного программирования.

1. Общая форма записи ЗЛП.

Дано: система линейных ограничений, в которой S равенств и (m-S) неравенств

(2)

(3)

Требуется найти такое решение системы (1) X=(x₁,x₂,…,x_n), которое удовлетворяет условию (2), и на котором целевая функция достигает экстремума (максимума или минимума).

1. Симметричная форма.

В ней ограничение (1) содержит только неравенства

(3)

(1) i=1,2,…,m

(2)

(3)

(1) i=1,2,…,m

(2)

1. Каноническая форма.

Ограничение (1) содержит только равенства

(3)

(1) i=1,2,…,m

(2)

Определение. Вектор X=(x₁,x₂,…,x_n), координаты которого являются решением ограничений (1) и (2), называется допустимым решением ЗЛП. Множество всех допустимых решений задачи называется областью допустимых решений (ОДР). Допустимое решение X, на котором целевая функция достигает максимума или минимума, называется оптимальным решением задачи.

Переход от одной формы записи ЗЛП к другой.

Теорема. Пусть дано линейное неравенство с n переменными (4)

и переменная (5)

такая, что , (6)

тогда .

Доказательство: (достаточность)→:

Пусть X=(α₁, α ₂,…, α _n) – решение (4), т.е. (4’)

Введём α_n+1 =b_i- , (5’)

при этом . (6’)

Пусть выполняется (5’) и (6’). Отбросив в левой части уравнения (6’) , получим неравенство (4’).

Теорема позволяет от неравенств в системе ограничений перейти к уравнениям и, наоборот, от уравнения перейти к неравенству.

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

Этот метод имеет ограниченную область применения. Этим методом можно решать следующие задачи:

1. Задачи с двумя переменными, имеющими симметричную форму записи.
2. Задачи с n переменными, имеющие каноническую форму записи, если выполняется условие n-r≤2, где n – число неизвестных, r – ранг системы линейных уравнений (1).

Задача типа 2 сводится к задаче типа 1, для чего нужно перейти от канонической к симметричной форме записи.

Рассмотрим решение задач типа 1.

Найти X=(x₁,x₂), который является решением (1), удовл. (2),

(2) x₁≥0, x₂≥0

и на котором целевая функция f(X)=c₁x₁+c₂x₂ (3) достигает экстремума (максимума или минимума).

Решение задачи содержит два этапа:

I. Построим ОДР

ОДР находится в 1-й координатной четверти

система (1) содержит линейные неравенства с двумя переменными

(7)

Решением такого неравенства является любая пара чисел (x₁;x₂), которая при подстановке в (7) обращает его в верное числовое равенство.

На координатной плоскости (x₁;x₂) – точка .

Множество решений (7) – некоторое множество точек на x₁Ox₂.

Выясним, какую область на плоскости x₁Ox₂ образуют точки, которые являются решением ограничений (1) и (2).

Заменим неравенство (7) соответствующим ему равенством.

- (8)

это уравнение определяет на плоскости x₁Ox₂ прямую линию. Эта линия делит плоскость x₁Ox₂ на 2 полуплоскости π₁ и π₂.

Утверждение. Точки одной из этих полуплоскостей являются решением

, (*)

а точки другой полуплоскости являются решением неравенства . (**)

Докажем это утверждение.

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

Возьмём т. M₁ (x₁’, x₂’), М₁ m

М₀ – проекция т. М₁

={x₁’- x₁⁰; x₂’- x₂⁰}

М₀ m;

Выясним знак выражения в зависимости от того, в какой из полуплоскостей (π₁,π₂) находится данная точка.

т.

(*)

Знак выражения зависит от знака

1)

2)

Тогда

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

Если неравенство удовлетворяется, то областью решения будет полуплоскость, в которой находится эта точка; если нет – то в другой.

Чтобы построить ОДР на координатной плоскости x₁0x₂, нужно построить граничные прямые и области решений каждого неравенства системы; пересечение областей решения этих неравенств, взятое в первом квадранте и будет областью решений данной задачи.

II. Нахождение ОДР оптимального решения задачи.

Рассмотрим уравнение (3) При конкретном значении f это уравнение определяет на плоскости прямую линию. При изменении f мы получим семейство параллельных прямых (прямые ||, т.к. они все имеют один угловой коэффициент ). Каждую из этих прямых называют линией уравнения, т.к. согласно равенству (3) на каждой такой прямой функция f сохраняет постоянное значение.

- это вектор, перпендикулярный линиям уровня, и он показывает направление, по которому нужно перемещать линию уровня, чтобы значение f возрастало. Обозначим

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

Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей, на которые данная линия уровня делит координатную плоскость, называется опорной прямой.

Чтобы найти ОДР оптимального решения, выполним:

1. Строим в начале координат.

2. Перпендикулярно проводим одну из линий уровня, имеющую общие точки с ОДР.

3. Перемещая эту линию уровня в направлении в задаче на max или в противоположном направлении в задаче на min, находим опорную прямую.

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

Пример.

Решим совместно уравнения прямых BC и DC, и имеющих общую точку с опорной прямой, найдём оптимальное решение.

Не нашли, что искали? Воспользуйтесь поиском по сайту: