Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Геометрическая интерпретация ЗЛП

Поиск

Приведём геометрическую интерпретацию ЗЛП. Пусть дана ЗЛП от двух переменных:

c 1 x 1+ c 2 x 2 ® max

(3.1)

Из 3.1.1 и 3.1.2 получаем

3.2.1. Область допустимых решений ЗЛП (3.1) является выпуклым многоугольником (возможно, бесконечным) в R 2 с конечным числом вершин.

3.2.2. Целевая функция ЗЛП (3.1) достигает экстремума в вершине многоугольника допустимых решений. При этом, если целевая функция достигает экстремума в двух вершинах многоугольника решений, то она также достигает экстремума на всей стороне (в любой точке стороны) с концами в этих вершинах.

Наконец, из 3.3.1 вводной Главы 0 получаем

3.2.3. При перемещении линий уровня c 1 x 1+ c 2 x 2= a относительно начала координат в направлении вектора нормали =(c 1, c 2) этих (прямых) линий значение a возрастает, в противоположном направлении a убывает.

Действительно, при перемещении линий уровня c 1 x 1+ c 2 x 2= a относительно начала координат в направлении вектора нормали =(c 1, c 2) значения переменных x 1, x 2 целевой функции c 1 x 1+ c 2 x 2 меняются пропорционально координатам вектора , скажем, с коэффициентом пропорциональности k. И если k растёт, то линии уровня перемещаются относительно начала координат по направлению вектора , а при убывании k линии уровня перемещаются относительно начала координат в противоположном с направлении. Поэтому в первом случае a растёт, во втором a убывает.

На фактах 3.2.1 - 3.2.3 основывается геометрический метод решения задачи (3.1), который заключается в следующем:

1. Построить область (многоугольник) допустимых решений ЗЛП (3.1).

2. Найти крайние положения прямых уровня c 1 x 1+ c 2 x 2= a относительно ОДР. Эти положения будут либо в угловой точке (вершине), либо на стороне ОДР (многоугольника), либо таких точек не существует.

3. По направлению вектора нормали =(c 1, c 2) определить характер экстремума в найденных в пункте 2 точках.

Пример. Решить геометрически ЗЛП:

4 x 1+ x 2 ® max

Решение. 1. Построим область допустимых решений задачи. Для этого построим полуплоскости, определяемые неравенствами системы ограничений. В свою очередь, для построения полуплоскости, определяемой неравенством a 1 x 1+ a 2 x 2b, достаточно построить границу полуплоскости - прямую a 1 x 1+ a 2 x 2= b, и определить, которая из двух полуплоскостей относительно этой прямой является искомой. Для этого подставляем координаты какой-нибудь точки, не лежащей на прямой a 1 x 1+ a 2 x 2= b, в интересующее нас неравенство. Если получается верное числовое неравенство, то та сторона от прямой, в которой лежит точка, является искомой полуплоскостью.

Построим полуплоскость 2 x 1+3 x 2≤24. Прямая 2 x 1+3 x 2=24 пересекает оси Ox 1 и Ox 2 в точках (0, 8) и (12, 0). Подставим координаты начала координат в неравенство: 2×0+3×0≤24. Так как получилось верное неравенство, то начало координат лежит в искомой полуплоскости. Это означает, что та сторона относительно прямой, в которой лежит начало координат О, является полуплоскостью 2 x 1+3 x 2≤24. Цифрами в скобках нумеруем границы полуплоскостей в

в порядке их следования в системе ограничений (Рис.1).

Строим полуплоскость -8 x 1+3 x 2≤24.

Точки (0, 8), (-3, 0) - точки пересечения границы полуплоскости -8 x 1+3 x 2≤24 с осями координат. Далее, -8×0+3×0≤24 - верное числовое неравенство. Значит, искомая полуплоскость - та, в которой лежит начало координат (Рис. 2).

Наконец, (0, -4), (6, 0) - точки пересечения прямой 2 x 1-3 x 2≤12 с осями координат, 2×0-3×0≤12.

Четырёхугольник OABC - ОДР задач. (Рис. 3).

2. Найдём крайние положения прямых уровня 4 x 1+ x 2= a относительно ОДР. Эти прямые перпендикулярны вектору =(4, 1). Из них мы изобразили три: (5), (6), (7). Крайние положения достигаются в точках O и B. Причём прямая, проходящая через O, получается перемещением этих прямых против направления , а прямая, проходящая через B, получается перемещением этих прямых в направлении . Поэтому в точке O достигается минимум целевой функции f (x 1, x 2)=4 x 1+ x 2, а в B - максимум.

Координаты B находим как координаты точки пересечения прямых (1) и (3), составив и решив систему из их уравнений:

Û

f min= f (0, 0)=0, f max=4×9+2=38.

Ответ: При x 1= x 2=0 достигается минимум целевой функции, равной 0; при x 1=9, x 1=2 достигается максимум, равный 38.

3.3. Упражнение. Задания 2) и 3) Упражнения 1.3 решить геометрическим методом.

 



Поделиться:


Последнее изменение этой страницы: 2016-04-08; просмотров: 453; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.143.5.131 (0.005 с.)