Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Построение области допустимых решений задачи






Для этого:

- отобразить в прямоугольной системе координат условия неотрицательности переменных (3). В двумерном пространстве уравнению соответствует прямая, а неравенству – полуплоскость, лежащая по одну сторону от прямой. Построим прямые Х1 = 0, Х2 = 0, которые лежаи на границах полуплоскостей и совпадают с осями координат. Полуплоскости Х1 > 0, X2 > 0 лежат соответственно справа от оси ОХ2 и выше оси ОХ1. Множество точек, удовлетворяющих одновременно неравенствам Х1 > 0 и X2 > 0, представляет собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти;

- построить ограничения задачи (2). Для этого построить по порядку прямые (рис.1):

10X1 + 3X2 = 30 (1)

-X1 + X2 = 3 (2)

X1 - X2 = 4 (3)

X1 + X2 = 10 (4)

 

 

 


Рис.1. Графическое решение задачи

 

 

- установить, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют строгим неравенствам:

 

10X1 + 3X2 > 30 (1)

-X1 + X2 < 3 (2)

X1 - X2 < 4 (3)

X1 + X2 < 10 (4)

 

Сторона, в которой располагается полуплоскость от прямой, указывается стрелкой. Убедиться в том, с какой стороны от прямой лежит полуплоскость, точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Когда прямая, ограничивающая полуплоскость, не проходит через начало координат, удобнее всего подставлять точку с координатами (0, 0). Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству будет соответствовать другая полуплоскость;

- определить область определения задачи. Она будет представлять собой пересечение всех построенных полуплоскостей. В данном случае – это пятиугольник АВСDЕ. Каждая точка этого многоугольника, включая и точки, лежащие на его границах, будет удовлетворять ограничениям задачи.

 

2. 2 Построение целевой функции

Для этого присвоить целевой функции Z значение нуль и построить прямую

Z = Х1 - 3Х2 = 0.

 

Эта прямая, проходящая через начало координат, строится следующим образом. Легко заметить, что в левой части данного уравнения стоит скалярное произведение двух векторов:

N = (с1, с2) = (1, -3) и Х = (х1, х2).

 

Скалярное произведение равно нулю когда векторы перпендикулярны.

Построим вектор N – вектор нормали. Он проходит через начало координат и точку (1, -3). Перпендикулярно ему через начало координат проведем прямую. Это и будет прямая целевой функции Z = 0.

Вектор N всегда показывает направление возрастания (максимизации) значения целевой функции, а противоположный ему вектор (- N) – направление убывания (минимизации) значения целевой функции.

Передвигая прямую Z = 0 по области допустимых решений параллельно самой себе в направление вектора N, значения целевой функции будут возрастать. Передвижение ее в направлении вектора (- N) дает убывание целевой функции.

Передвижение на графике прямой Z = 0 равносильно изменению значения b в уравнении Х1 - 3Х2 = b. Каждому значению b соответствует прямая. Полученные прямые параллельны между собой и называются линиями уровня. Особенность линии уровня состоит в том, что целевая функция принимает на ней одинаковые значения, т.е. подставив координаты любой точки линии уровня в целевую функцию, ее значение изменяться не будет.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал