Клюшин В.Л. Высшая математика для экономистов
Подождите немного. Документ загружается.
111
кую-нибудь точку M
0
(x
0
, y
0
, z
0
), принадлежащую прямой, и на-
правляющий вектор. Координаты точки M
0
найти просто: это
любое решение системы (9.10). Например, положив z
0
= 0, из сис-
темы (9.10) найдем x
0
и y
0
и получим M
0
(x
0
, y
0
, 0). Координатами
направляющего вектора
s
, как доказывается в аналитической гео-
метрии, могут быть числа
l
B C
B C
m
C A
C A
n
A B
A B
= = =
1 1
2 2
1 1
2 2
1 1
2
, ,
22
.
Рассмотрим теперь взаимное расположение прямой и плоско-
сти в пространстве. Пусть даны прямая L
x x
l
y y
m
z z
n
−
=
−
=
−
0 0 0
и плоскость P
Ax + By + Cz + D = 0.
Очевидно, прямая L параллельна плоскости P, когда направ-
ляющий вектор прямой
s
= (l, m, n) перпендикулярен нормально-
му вектору плоскости
N
= (A, B, C), т.е. условием п а р а л л е л ь -
н о с т и прямой L и плоскости P является условие
Al + Bm + Cn = 0.
(9.11)
Условие пропорциональности этих векторов есть условие
п е р п е н д и к у л я р н о с т и прямой L и плоскости P:
A
l
B
m
C
n
= = .
(9.12)
Угол между прямой и плоскостью есть угол между прямой и ее
проекцией на плоскость, а это угол, дополнительный к углу между
прямой L и нормальным вектором
N
плоскости P:
sin cos , .ϕ = =
+ +
+ + + +
N s
Al Bm Cn
A B C l m n
2 2 2 2 2 2
(9.13)
Расстояние от точки до плоскости вычисляется с помощью
формулы, аналогичной формуле расстояния от точки до прямой
на плоскости [см. (7.15)]. Покажем, что расстояние d от точ-
ки M
0
(x
0
, y
0
, z
0
) до плоскости
Ax + By + Cz + D = 0
(9.2)
вычисляется по формуле
d
Ax By Cz D
A B C
=
+ + +
+ +
0 0 0
2 2 2
.
(9.14)
112
Напишем уравнение прямой, проходящей через точку
M
0
(x
0
, y
0
, z
0
) перпендикулярно плоскости (9.2). Для этого вос-
пользуемся параметрическими уравнениями (9.9):
x = x
0
+ lt, y = y
0
+ ml, z = z
0
+ nt.
Для того чтобы прямая (9.9) была перпендикулярна плоско-
сти (9.2), надо, чтобы ее направляющий вектор
s
= (l, m, n) был
параллелен вектору
N
= (A, B, C), т.е. чтобы координаты векторов
s
и
N
были пропорциональны. Проще всего, конечно, взять в ка-
честве
s
вектор
N
, т.е. взять l = A, m = B, n = C. Тогда параметричес-
кие уравнения (9.9) будут выглядеть так:
x = x
0
+ At, y = y
0
+ Bt, z = z
0
+ Ct. (9.9′)
Прямая (9.9′) перпендикулярна плоскости (9.2) и проходит че-
рез точку M
0
. Следовательно, расстояние от точки M
0
до плоско-
сти (9.2) есть расстояние между точкой M
0
и точкой M пересече-
ния прямой (9.9′) с плоскостью (9.2). Найдем координаты этой
точки М. Для этого надо решить совместно уравнения (9.2) и
(9.9′). Проще всего это сделать, подставив выражения для x, y и z
из (9.9′) в (9.2). Получим:
A(x
0
+ At) + B(y
0
+ Bt) + C(z
0
+ Ct) + D = 0,
(A
2
+ B
2
+ C
2
)t + (Ax
0
+ By
0
+ Cz
0
+ D) = 0.
Отсюда находим t:
t
Ax By Cz D
A B C
= −
+ + +
+ +
0 0 0
2 2 2
.
Это значение t определяет координаты точки M, являющейся
основанием перпендикуляра, опущенного из точки M
0
на плос-
кость (9.2). Подставим найденное t в (9.9′):
x x A
Ax By Cz D
A B C
= + −
+ + +
+ +
0
0 0 0
2 2 2
,
y y B
Ax By Cz D
A B C
= + −
+ + +
+ +
0
0 0 0
2 2 2
,
(9.9″)
z z C
Ax By Cz D
A B C
= + −
+ + +
+ +
0
0 0 0
2 2 2
.
11
Расстояние d от точки M
0
до плоскости (9.2) есть длина пер-
пендикуляра M
0
M, или, что то же самое, расстояние между точка-
ми M
0
(x
0
, y
0
, z
0
) и M(x, y, z), т.е.
d x x y y z z= − + − + −( ) ( ) ( ) .
0
2
0
2
0
2
Учитывая, что x, y и z определяются равенствами (9.9″), полу-
чаем
d A B C
Ax By Cz D
A B C
= + +
( )
−
+ + +
+ +
=
=
2 2 2
0 0 0
2 2 2
2
AA B C
Ax By Cz D
A B C
2 2 2
0 0 0
2 2 2
+ +
+ + +
+ +
,
или
d
Ax By Cz D
A B C
=
+ + +
+ +
0 0 0
2 2 2
,
что и требовалось доказать.
П р и м е р 9.2. Н
айти расстояние от точки M
0
(1, 0, 2) до
плоскости x + 2y - 2z + 9 = 0.
Р е ш е н и е:
d =
+ ⋅ − ⋅ +
+ + −
= =
1 2 0 2 2 9
1 2 2
6
3
2
2 2 2
( )
.
П р и м е р 9.3. Найти расстояние от прямой
x y z+
=
−
=
1
2
2
2 1
до плоскости 4x - 2y - 4z + 9 = 0.
Р е ш е н и е. Прямая параллельна плоскости. Действительно,
скалярное произведение ее направляющего вектора и нормально-
го вектора плоскости равно нулю: 2
⋅
4 + 2
⋅
(-2) + 1
⋅
(-4) = 0. Следо-
вательно, расстояние от прямой до плоскости равно расстоянию
от любой точки M
0
этой прямой до плоскости. Удобнее всего в
качестве M
0
взять точку (-1, 2, 0), координаты которой фигуриру-
ют в уравнении прямой. Получаем
d =
⋅ − − ⋅ − ⋅ +
+ − + −
=
4 1 2 2 4 0 9
4 2 4
1
6
2 2 2
( )
( ) ( )
.
11
П р и м е р 9.4. Найти расстояние от точки M
0
(1, 2, 3) до
прямой
x y z−
=
−
=
−6
2 2
7
1
.
Р е ш е н и е. Напишем уравнение плоскости, которая прохо-
дит через данную точку M
0
и перпендикулярна данной прямой,
и найдем координаты точки М пересечения прямой и плоскости.
Очевидно, M
0
М – перпендикуляр, опущенный из точки M
0
на
данную прямую. Его длина и есть искомое расстояние.
Уравнение плоскости, проходящей через M
0
и перпендикуляр-
ной данной прямой, есть
2(x - 1) - 2(y - 2) + 1(z - 3) = 0,
или
2x - 2y + z - 1 = 0.
()
Запишем уравнение данной прямой в параметрической форме:
x = 6 + 2t, y = -2t, z = 7 + t.
()
Найдем точку пересечения прямой () и плоскости (). Для
этого сначала подставим x, y и z из (
) в () и найдем t:
2(6 + 2t) - 2(-2t) + 7 + t - 1 = 0,
9t + 18 = 0, t = -2.
Теперь, подставляя найденное значение t = -2
в (), получим
x = 2, y = 4, z = 5. Итак, точка M(2, 4, 5) есть основание перпенди-
куляра M
0
М. Поэтому
d M M= = − + − + − =
0
2 2 2
2 1 4 2 5 3 3( ) ( ) ( ) .
Заметим, что существует другой способ решения этой и подоб-
ных ей задач, основанный на понятии векторного произведения
векторов, которое здесь не рассматривается.
вопросы
Что называется нормальным вектором плоскости в простран-
стве?
Будет ли прямым угол между плоскостями 3x + y - z = 0 и
x - y + 2z + 5 = 0?
1.
2.
Будут ли параллельны плоскости 3x - 2y + z = 0 и 6x - 3y + 2z +
+ 12 = 0?
Принадлежит ли точка M
0
(1, 2, 3) плоскости 2x - 3y + z + 1 = 0?
Чему равно расстояние от начала координат до плоскости
2x - y + 2z + 9 = 0?
Какие координаты имеет точка прямой
x t
y t
z t
= +
= −
= +
2
1 2
3 2
,
,
,
соответ-
ствующая значению параметра t = -1?
Принадлежит ли точка M
0
(1, 3, 2) прямой
x t
y t
z t
= −
= +
= − +
3
1
4 3
,
,
?
Если
принадлежит, то чему равно соответствующее значение пара-
метра t?
Будет ли вектор
a
= (2, -1, 3) параллелен прямой
x t
y t
z t
= −
= +
= −
3 4
1 2
5 6
,
,
?
Какая точка прямой
x t
y t
z t
= +
= −
= − +
1
2 3
3 2
,
,
соответствует значению пара-
метра t = 2?
Пересекаются ли прямая
x t
y t
z t
= +
= +
= − −
2
3 2
1 2
,
,
и плоскость x + 2y - 5z +
+ 2 = 0? Если пересекаются, то каковы координаты точки пере-
сечения?
Параллельна ли прямая
x y z−
=
+
−
=
−
−
1
2
2
1
3
2
плоскости 3x + 2y +
+ 2z - 7 = 0?
Как определить координаты направляющего вектора прямой,
заданной парой плоскостей
A x B y C z D
A x B y C z D
1 1 1 1
2 2 2 2
0
0
+ + + =
+ + + =
,
?
Как найти расстояние между параллельными плоскостями?
Проходит ли прямая
x y z−
=
+
−
=
−1
2
1
1
3
3
через точки M
1
(-1, 0, 0)
и M
2
(5, -3, 9)?
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
11
раздел III
лиНеЙНЫе Модели
в
ЭкоНоМике
Глава 10
оБщие сведеНия о лиНеЙНоМ
ПроГрАММировАНии
В этой книге не предусмотрено систематическое изложение
линейного программирования. Здесь мы рассмотрим лишь неко-
торые примеры оптимизационных задач с ограничениями, зада-
ваемыми линейными неравенствами.
10.1. зАдАчА оБ исПользовАНии ресурсов
В экономической деятельности предприятия или отрасли по-
стоянно возникают такие ситуации, когда надо определить, как
использовать имеющиеся в распоряжении ресурсы, чтобы до-
биться максимального выпуска продукции. При большом количе-
стве возможных решений этой задачи естественно выбрать наи-
лучшее. Математически эта задача обычно сводится к нахожде-
нию наибольшего или наименьшего значения некоторой функции
на множестве, определяемом системой неравенств.
Пусть предприятие из m видов ресурсов производит n видов
продукции. Пусть для производства одной единицы j-го вида про-
дукции расходуется a
ij
единиц i-го вида ресурса. Матрица A = (a
ij
)
называется технологической.
Пусть c
j
– удельная прибыль от реализации одной единицы
j-й продукции. Эти удельные прибыли образуют вектор C =
= (c
1
, c
2
, …, c
n
). Тогда произведение CX = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
есть
11
величина прибыли, полученной при реализации X единиц произведен-
ной продукции, где
X
x
x
x
n
=
1
2
.
Обозначим эту прибыль f(X ).
Пусть b
i
– число единиц i-го ресурса, имеющегося в распоря-
жении предприятия. Тогда необходимость учитывать ограничен-
ность запасов ресурсов при составлении планов производства
выражается системой неравенств
a
i1
x
1
+ a
i2
x
2
+ … + a
in
x
n
≤ b
i
, i = 1, 2, …, m. (10.1)
Требуется при данных ресурсах выпустить такую комбинацию
товаров, при которой доход предприятия оказался бы максималь-
ным. Иначе говоря, требуется найти наибольшее значение функции
f(X ) = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
при условиях (10.1). Определенная таким
образом задача называется задачей оптимизации. Ее записывают так:
f(X ) = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
→ max, (10.2)
a x a x a x b
a x a x a x
n n
n n
11 1 12 2 1 1
21 1 22 2 2
+ + + ≤
+ + + ≤
…
…
,
bb
a x a x a x b
m m mn n m
2
1 1 2 2
,
,
…+ + + ≤
(10.3)
x
1
≥ 0, x
2
≥ 0, …, x
n
≥ 0. (10.4)
Функция f(X ) называется целевой функцией.
О п р е д е л е н и е. Допустимым решением (планом) данной за-
дачи называется любой вектор X , удовлетворяющий системе огра-
ничений (10.3) и условиям неотрицательности (10.4).
Множество допустимых решений задачи образует область до-
пустимых решений.
О п р е д е л е н и е. Оптимальным решением (планом) задачи на-
зывается такое допустимое решение, при котором целевая функ-
ция достигает максимума (минимума).
10.2. оБщАя зАдАчА
лиНеЙНоГо ПроГрАММировАНия
Сформулируем в общем виде задачу линейного программирова-
ния: найти экстремум линейной функции при линейных же ограниче-
ниях на переменные.
11
При этом множество значений переменных, удовлетворяющих
всем линейным ограничениям задачи, называется допустимым
множеством, а линейная функция, экстремум которой ищется, –
целевой функцией.
На практике нередко приходится решать такие задачи линей-
ного программирования, в которых и виды ресурсов, и виды про-
дукции исчисляются сотнями и тысячами. Самый распространен-
ный алгоритм решения задач линейного программирования – это
так называемый симплекс-метод. Изложение этого метода выхо-
дит за рамки нашего курса. Приведем без доказательства лишь две
теоремы, составляющие теоретическую основу симплекс-метода
(и вообще линейного программирования).
Т е о р е м а 10.1. Задача
линейного программирования имеет
оптимальное решение тогда и только тогда, когда целевая функ-
ция ограничена на допустимом множестве в направлении экстре-
мума.
Прежде чем сформулировать вторую теорему, заметим, что до-
пустимое множество, на котором ищется экстремум, – это много-
гранное тело (при n = 2 – многоугольник, при n = 3 – многогран-
ник в трехмерном пространстве). Вершины этого многогранного
тела называются угловыми точками.
Т е о р е м а 10.2. Е
сли экстремум целевой функции в задаче
линейного программирования достигается, то он достигается в
некоторой угловой точке допустимого множества.
Заметим, что угловых точек – конечное число. Симплекс-ме-
тод представляет собой направленный перебор угловых точек до-
пустимого множества.
Рассмотрим решение задачи линейного программирования с
двумя переменными графическим методом.
П р и м е р 10.1. Р
ешить задачу линейного программирова-
ния:
f(X ) = 3x
1
+ 2x
2
→ max,
x x
x x
x
1 2
1 2
2
2 0 1
3 2 6 0 2
3 0 3
− + ≥
− − ≤
− ≤
, ( )
, ( )
, ( )
x
1
≥ 0, x
2
≥ 0.
11
Р е ш е н и е. На плоскости возьмем прямоугольную систему
координат Ox
1
x
2
(рис. 10.1).
x
2
x
1
0
−1
1
2
3
4
−1−2 1
(1)
(2)
(3)
2 3 4 5
D
C
B
A
−2
−3
n = ( , )3 2
рис. 10.1
Строим прямую x
1
- x
2
+ 2 = 0, соответствующую первому огра-
ничению. Чтобы выбрать нужную полуплоскость, надо подста-
вить в неравенство (1) координаты какой-нибудь точки, не лежа-
щей на прямой, например точки O(0, 0): 0 - 0 + 2 > 0. Получаем
верное неравенство. Следовательно, точка O лежит в полуплос-
кости решений.
Аналогично строим прямые 3x
1
- 2x
2
- 6 = 0 и x
2
- 3 = 0 и выби-
раем соответствующие полуплоскости.
Учитываем еще условия неотрицательности x
1
≥ 0, x
2
≥ 0.
Пересечение всех пяти полуплоскостей дает искомое допусти-
мое множество – пятиугольник OABCD.
Строим линию уровня 3x
1
+ 2x
2
= l, например, при l = 0:
3x
1
+ 2x
2
= 0. Перемещаем линию уровня в направлении нормали.
Последняя точка, по которой линия уровня еще пересекает допус-
тимое множество, и будет точкой максимума. В нашем случае это
точка C. Ее координаты найдем, решая совместно уравнения пря-
мых, которые пересекаются в точке C:
3 2 6 0
3 0
1 2
2
x x
x
− − =
− =
,
,
получаем x
1
= 4, x
2
= 3. Вычисляем f
max
= f(4, 3) = 18.
120
Нередко бывает, что переменные в задачах линейного про-
граммирования являются целочисленными. Такие задачи решать
сложнее, для них разработаны специальные методы. Но если та-
кая задача содержит две переменные, то ее можно решить графи-
чески. Надо двигать линию уровня в направлении экстремума и
найти последнюю целочисленную точку.
10.. ЭлеМеНТЫ Теории двоЙсТвеННосТи
Центральной частью линейного программирования является
теория двойственности. Любой задаче линейного программиро-
вания можно поставить в соответствие другую задачу, которая
называется двойственной (или сопряженной). Обе задачи (исход-
ная и двойственная к ней) образуют пару двойственных задач ли-
нейного программирования. Каждая из задач является двойствен-
ной к другой задаче рассматриваемой пары.
Рассмотрим задачу об использовании ресурсов. Пусть для изго-
товления n видов продукции P
1
, P
2
, …, P
n
используют m видов
ресурсов S
1
, S
2
, …, S
m
(это могут быть различные виды сырья,
электроэнергия, полуфабрикаты и т.п.). Объем каждого вида ре-
сурсов известен; иначе говоря, известен вектор запасов ресурсов
B = (b
1
, b
2
, …, b
m
)′. Известна также норма a
ij
расхода i-го ресурса на
производство единицы j-го вида продукции, т.е. известна техно-
логическая матрица A = (a
ij
), i = 1, 2, …, m; j = 1, 2, …, n. Кроме того,
известна прибыль, получаемая от реализации единицы каждого
вида продукции, т.е. известен вектор прибылей C = (c
1
, c
2
, …, c
n
).
(Здесь B – вектор-столбец, а С – вектор-строка.)
Производитель составляет план выпуска продукции, обеспе-
чивающий максимальную прибыль. Математическая модель дан-
ной задачи, как уже отмечалось, в развернутой форме имеет вид
f(X ) = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
→ max, (10.2)
a x a x a x b
a x a x a x
n n
n n
11 1 12 2 1 1
21 1 22 2 2
+ + + ≤
+ + + ≤
…
…
,
bb
a x a x a x b
m m mn n m
2
1 1 2 2
,
,
…+ + + ≤
(10.3)
x
1
≥ 0, x
2
≥ 0, …, x
n
≥ 0. (10.4)
Здесь x
j
, j = 1, 2, …, n – объем производства j-го вида продукции.