ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1093
Скачиваний: 2
41
Из
определения
скалярного
произведения
следуют
:
1.
(
Г
,
Х
) = 0
Cos
φ
= 0
φ
=
π
/2
Г┴Х
.
При
этом
уравнение
γ
1
x
1
+
γ
2
x
2
= 0
задает
на
плоскости
(x
1
,
О
, x
2
)
прямую
,
проходящую
через
начало
координат
перпендикулярно
вектору
Г
.
2.
(
Г
,
Х
) > 0
0 < Cos
φ
< 1
0 <
φ
<
π
/2.
При
этом
неравенство
γ
1
x
1
+
γ
2
x
2
> 0
определяет
на
плоскости
(x
1
,
О
, x
2
)
полуплоскость
с
той
стороны
прямой
,
заданной
соотношением
γ
1
x
1
+
γ
2
x
2
= 0,
куда
направлен
вектор
Г
.
3.
(
Г
,
Х
) < 0
–1 < Cos
φ
< 0
π
/2 <
φ
<
π
.
При
этом
неравенство
γ
1
x
1
+
γ
2
x
2
<0
определяет
на
плоскости
(x
1
,
О
, x
2
)
полуплоскость
с
той
стороны
прямой
,
заданной
соотношением
γ
1
x
1
+
γ
2
x
2
= 0,
куда
направлен
вектор
,
противоположенный
вектору
Г
.
4.
(
Г
,
Х
)
max
Cos
φ
= 1
φ
= 0.
При
этом
векторы
Г
и
Х
направлены
в
одну
сторону
.
5.
(
Г
,
Х
)
min
Cos
φ
=–1
φ
=
π
.
При
этом
векторы
Г
и
Х
направлены
в
разные
стороны
.
Теперь
данную
линейную
функцию
(1)
можно
представить
:
либо
в
виде
f(x
1
, x
2
) = (
Г
,
Х
)+
γ
0
, (3)
либо
в
виде
f(x
1
, x
2
) =
Г
Пр
Г
Х
+
γ
0
, (4)
В
соотношении
(4)
величины
Г
и
γ
0
являются
постоянными
.
Поэтому
возможные
значения
функции
f(x
1
, x
2
)
определяются
значениями
величины
–
Пр
Г
Х
(
проекции
вектора
Х
на
вектор
Г
),
которая
зависит
от
расположения
точки
Х
(x
1
, x
2
)
на
множестве
W.
Из
соотношения
(3)
следует
,
что
точка
Х
(x
1
, x
2
)
принадлежит
также
прямой
линии
L,
задаваемой
уравнением
γ
1
x
1
+
γ
2
x
2
= f(x
1
, x
2
) –
γ
0
.
Абсолютное
значение
величины
Пр
Г
Х
совпадает
с
величиной
–
ρ
(0, L),
равной
расстоянию
от
начала
координат
до
прямой
L.
Поэтому
,
изменяя
положение
прямой
L,
а
вместе
с
ней
и
положение
точки
Х
(x
1
, x
2
),
на
множестве
W,
можно
изменять
расстояние
от
прямой
линии
L
до
начала
координат
,
и
,
согласно
(4),
изменять
значение
функции
f(x
1
, x
2
).
Если
угол
между
векторами
Г
и
Х
острый
,
то
прямая
L
находится
с
той
стороны
от
прямой
,
задаваемой
уравнением
γ
1
x
1
+
γ
2
x
2
= 0,
куда
направлен
вектор
Г
,
и
значение
функции
f(x
1
, x
2
)
определяется
величиной
ρ
(0, L),
взятой
со
знаком
плюс
.
Если
угол
между
векторами
Г
и
Х
тупой
,
то
прямая
L
расположена
с
той
стороны
от
прямой
,
задаваемой
уравнением
γ
1
x
1
+
γ
2
x
2
= 0,
куда
направлен
вектор
,
противоположенный
к
вектору
Г
,
и
значение
функции
f(x
1
, x
2
)
определяется
величиной
ρ
(0, L),
взятой
со
знаком
минус
.
Следовательно
,
перемещая
прямую
L
вместе
с
точкой
Х
(x
1
, x
2
)
по
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
42
множеству
W
в
направлении
вектора
Г
,
мы
увеличиваем
значения
функции
f(x
1
, x
2
)
на
множестве
W ,
а
,
перемещая
в
обратном
направлении
–
уменьшаем
значение
этой
функции
на
рассматриваемом
множестве
.
Наибольшее
и
наименьшее
значения
функция
достигает
в
точках
,
где
прямая
L
становиться
касательной
(
опорной
)
к
множеству
W.
Пример
1
.
Найти
наибольшее
значение
функции
f(x
1
, x
2
)=x
1
+x
2
на
множестве
W = { X
R
2
: f
i
(x
1
, x
2
)
0, i = 1,2,3,4},
где
f
1
(x
1
, x
2
) = x
1
+ x
2
– 4 ,
f
2
(x
1
, x
2
) = x
1
+ 3x
2
– 6, f
3
(x
1
, x
2
) = –x
1
, f
4
(x
1
, x
2
) = – x
2
.
▲
Множество
W
изображено
на
рис
2.
X
2
grad f(X)=
Г
4
2
W
0 2 4 6 x
1
L
Рис
.2
Через
это
множество
перпендикулярно
вектору
градиента
Г
= (1,1)
функции
f(x
1
, x
2
)
проводим
прямую
линию
L,
задаваемую
уравнением
x
1
+x
2
+
γ
0
= 0.
Перемещая
прямую
линию
L
в
направлении
вектора
градиента
до
тех
пор
,
когда
она
станет
касательной
(
опорной
)
к
множеству
W
в
каждой
точке
отрезка
[
Х
1
0
,
Х
2
0
] = W
L.
Координаты
точек
Х
1
0
,
Х
2
0
находятся
из
решения
соответствующих
систем
уравнений
,
а
именно
,
x
1
+ x
2
= 4 , x
1
+ x
2
= 4,
x
1
+ 3x
2
= 6 , x
2
= 0.
Любая
точка
Х
=
αХ
1
0
+ (1 –
α
)
Х
2
0
,
где
α
[0,1],
данного
отрезка
будет
являться
точкой
глобального
максимума
функции
f(x
1
, x
2
)
на
множестве
W.
■
Пример
2. (
портфель
акций
)
.
Инвестор
решил
вложить
1800
д
.
е
.
в
акции
двух
компаний
:
в
топливно
-
нефтяную
компанию
(
ТНК
)
и
в
компанию
по
производству
компьютеров
(
КПК
).
Стоимости
акций
этих
компаний
соответственно
равны
4
д
.
е
.
и
8
д
.
е
.
При
этом
обещают
,
что
прибыль
от
1
д
.
е
.,
инвестированная
в
акции
ТНК
,
будет
равна
0,115
д
.
е
.,
а
от
1
д
.
е
.,
инвестированной
в
акции
КПК
,
будет
равна
0,12
д
.
е
.
за
год
.
На
рынке
продажа
продукции
компании
ТНК
более
устойчива
,
чем
компании
КПК
.
Поэтому
инвестор
решает
приобрести
акций
ТНК
не
меньше
,
чем
акций
КПК
.
Х
0
1
Х
0
2
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
43
Однако
ТНК
продает
каждому
будущему
акционеру
не
более
325
своих
акций
,
в
то
время
как
КПК
продает
свои
акции
в
количествах
не
менее
60
штук
.
Формализуйте
условия
вложения
денег
в
акции
указанных
компаний
с
учетом
того
,
что
инвестор
желает
получить
при
этом
наибольшую
прибыль
.
Изобразите
на
плоскости
множество
инвестиционных
возможностей
.
Найдите
инвестиционные
возможности
,
которые
соответствуют
желаниям
инвестора
.
▲
Предположим
инвестор
приобретет
х
1
акций
ТНК
и
х
2
акций
КПК
.
Тогда
множество
инвестиционных
возможностей
можно
записать
в
виде
W ={ X (x
1
, x
2
)
R
2
: 0
x
1
325, 60
x
2
,
х
2
х
1
, 4
х
1
+ 8
х
2
1800},
а
прибыль
от
такой
сделки
в
виде
функции
f(x
1
, x
2
) = 0,115(4x
1
) + 0,12(8x
2
).
Математическая
постановка
задачи
:
Найти
наибольшее
значение
функции
f(x
1
, x
2
) = 0,115(4x
1
) + 0,12(8x
2
)
на
множестве
W.
Множество
W
изображено
на
рис
. 3.
Через
это
множество
перпендикулярно
вектору
градиента
Г
= (0,46;0,96)
функции
f(x
1
, x
2
) = 0,115(4x
1
) + 0,12(8x
2
)
проводим
прямую
линию
L,
задаваемую
уравнением
0,46x
1
+ 0,968x
2
+
γ
0
= 0.
Перемещая
эту
прямую
в
направлении
вектора
градиента
,
находим
точку
Х
0
(150,150),
в
которой
функция
f(x
1
, x
2
)
достигает
наибольшего
значения
.
■
Замечание
.
Графическим
методом
можно
решать
задачу
линейного
программирования
,
если
число
переменных
– n
и
число
уравнений
– m
в
системе
ограничений
этой
задачи
удовлетворяют
соотношению
1
n – m
2.
Для
этого
необходимо
:
-
найти
методом
Гаусса
общее
решение
системы
линейных
уравнений
,
которая
является
системой
ограничений
исходной
задачи
линейного
программирования
;
-
исключив
разрешенные
переменные
из
полученного
общего
решения
,
получить
систему
из
m
неравенств
с
(n–m)
переменными
;
-
из
полученного
общего
решения
выразить
разрешенные
переменные
через
x
2
grad f(X)=
Г
225
150 -----------
L W
60
0 325 450 x
1
Рис
.3
X
0
(150,150)
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
44
свободные
переменные
и
подставить
их
в
целевую
функцию
,
которая
станет
функцией
(n–m)
свободных
переменных
;
-
решить
графическим
методом
полученную
задачу
линейного
программирования
с
(n–m)
свободными
переменными
,
с
ограничениями
в
виде
m
неравенствами
,
а
также
с
ограничениями
на
знак
переменных
;
-
найденные
свободные
переменные
подставить
в
общее
решение
,
вычислить
значения
разрешенных
переменных
и
записать
оптимальное
решение
исходной
задачи
.
Пример
4
.
Найти
наименьшее
значение
функции
f(X) = 4x
1
– 2x
2
+ x
3
– x
4
на
множестве
W,
заданном
системой
уравнений
:
x
1
– x
2
+ 4x
3
– 2x
4
= 2,
3x
1
+ 2x
2
– x
3
+ 4x
4
= 3,
х
j
0, j = 1, 2, 3, 4.
▲
Разрешим
систему
ограничений
относительно
первых
двух
переменных
и
получим
общее
решение
системы
уравнений
в
виде
х
1
+ 7/5 x
3
=
7/5,
x
2
– 13/5 x
3
+ 2 x
4
= –3/5,
из
которого
следует
,
что
х
1
= –7/5 x
3
+
7/5,
x
2
= 13/5 x
3
– 2 x
4
– 3/5.
Исключаем
разрешенные
переменные
из
общего
решения
получаем
систему
неравенств
с
переменными
х
3
и
х
4
.
Подставляем
переменные
х
1
и
х
2
,
выраженные
через
переменные
х
3
и
х
4
в
целевую
функцию
.
Получаем
задачу
линейного
программирования
с
двумя
переменными
х
3
и
х
4
и
с
ограничениями
в
виде
неравенств
,
а
именно
,
найти
наименьшее
значение
целевой
функции
f(X) = – 9,8x
3
+ 3x
4
+6,8
на
множестве
,
заданном
системой
неравенств
:
Решаем
задачу
графическим
методом
.
Найденные
значения
переменных
х
3
0
=1,
х
4
0
=0
подставляем
в
выражения
для
А
1
А
2
А
3
А
4
В
1
–1 4
–2
2
3 2 –1 4 3
1 –1
4
–2 2
0
5
– 13
10
–3
1 0 1,4 0 1,4
0
1
– 2,6
2 –0,6
х
3
≤
1,
– 2,6 x
3
+ 2 x
4
≤
–0,6,
х
3
≥
0,
х
4
≥
0.
х
4
L
grad f(X)=(-9,8;3) W
0 0,27 1
х
3
Рис
.4
х
3
0
=1,
х
4
0
=0
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
45
первых
двух
переменных
и
выписываем
оптимальное
решение
исходной
задачи
Х
0
=(0,2,1,0)
и
соответствующее
ему
значение
целевой
функции
f(X
0
) = –3.
■
При
решении
экономических
задач
переменная
х
j
, j = 1, 2, …, n,
соответствует
ресурсу
j-
го
вида
(
сырье
,
труд
,
деньги
,
время
и
т
.
п
.).
Неравенства
f
i
(X)
0, i
I; f
i
(X)=0, i
M\I
х
j
0, j=1,2, … , n
задают
ограничения
на
использование
этих
ресурсов
.
Функция
f
(X)
определяет
цель
(
качество
)
использования
ресурсов
.
На
этапе
развития
методов
решения
таких
задач
каждое
решение
системы
ограничений
на
использование
ресурсов
называли
планом
(
или
программой
)
.
План
(
программа
),
доставляющий
экстремальное
значение
целевой
функции
,
называли
оптимальным
.
Поэтому
направление
науки
,
занимающееся
постановкой
таких
задач
и
разработкой
методов
нахождения
оптимальных
решений
,
назвали
математическим
программированием
(
планированием
).
В
зависимости
от
вида
целевой
функции
и
вида
функций
в
ограничениях
таких
задачах
различают
направления
математического
программирования
:
линейное
,
нелинейное
,
выпуклое
,
дискретное
,
стохастическое
и
т
.
п
.
Мы
начнем
изучение
математического
программирования
с
наиболее
разработанных
и
доступных
задач
–
задач
линейного
программирования
.
Ответьте
на
вопросы
1.
Дайте
определение
замкнутого
множества
.
2.
Какие
из
множеств
[a,b], [a, b), (–
∞
, b], (a, b), (a, +
∞
)
являются
замкнутыми
,
а
какие
не
являются
замкнутыми
?
3.
Дайте
определение
предельной
точки
множества
.
Укажите
множество
всех
предельных
точек
для
множеств
из
пункта
2.
4.
Какие
из
множеств
п
.2
являются
ограниченными
,
а
какие
не
являются
ограниченными
?
5.
Дайте
определение
градиента
функции
нескольких
переменных
.
6.
Напишите
формулу
для
нахождения
расстояния
от
начала
координат
до
прямой
линии
,
заданной
уравнением
Ax+By+C=0.
7.
Когда
прямая
линия
является
опорной
к
некоторому
множеству
?
8.
При
поиске
графическим
методом
глобального
минимума
линейной
функции
f(X)
в
каком
направлении
и
до
какого
положения
необходимо
перемещать
прямую
f(X)=0
относительно
градиента
этой
функции
?
9.
Какие
задачи
линейного
программирования
можно
решать
графическим
методом
?
10.
Дайте
определения
общего
решения
системы
линейных
уравнений
,
разрешенных
переменных
и
свободных
переменных
.
11.
Опишите
последовательность
решения
задачи
линейного
программирования
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.