Математика в экономике. Пучков Н.П - 39 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Рис. 5
Очевидно, что если М
1
расположить на прямой l, то скалярное произведение
(
)
10
, MMN равно нулю, а F (а
0
, b
0
) = F (а
1
,
b
1
), т.е. значения линейной функции во всех точках прямой l равны между собой.
Это свойство линейной функции F (х
1
, х
2
) = Ах
1
+ Вх
2
возрастать в направлении вектора
{}
BAN ,= можно использовать
для нахождения ее наибольшего и наименьшего значений в точках плоскости, ограниченной многоугольником, или
неограниченной многоугольной области.
Рассмотрим первый случай (pис. 6): пусть необходимо найти наибольшее и наименьшее значения функции F
(х
1
, х
2
) =
Ах
1
+ Вх
2
в точках многоугольной области M
1
M
2
M
3
M
4
. Вектор
{
}
BAN ,= . Передвигаясь в направлении вектора ,N мы
войдем в область многоугольника в точке М
1
. Значение F в точке М
1
будет наименьшим, так как другие точки
многоугольной области расположены по направлению вектора
,N а, следовательно, значение функции F в этих точках
будет большим, чем F(М
1
). (Прямая l, перейдя в положение ,l
′
может иметь с областью M
1
M
2
M
3
M
4
не одну общую точку М
1
,
а ребро M
1
M
2
; это не нарушает метода, так как в этом случае во всех точках ребра M
1
M
2
функция F будет принимать
одинаковые значения). Перейдя в положение
l
′′
прямая l окажется на выходе из многоугольной области: М
3
– крайняя
(последняя) точка области при движении в направлении вектора
,N поэтому значение F (М
3
) будет наибольшим по
сравнению с ее значениями в других точках области.
Рис. 6
Таким образом ищутся наименьшее и наибольшее значения линейной функции в точках многоугольной области;
практически эти значения имеют место в вершинах многоугольника.
При постановке задачи в том виде, как мы рассмотрели, схема решения задачи линейного программирования
выглядит следующим образом:
1) используя условие, записать целевую функцию F
(х
1
, х
2
);
2) используя условие, построить многоугольную область возможных значений х
1
и х
2
;
3) найти координаты вершин многоугольника, подсчитать значение функции F в этих точках, сравнить их и выбрать
наименьшее и наи- большее.
Если вершин у многоугольника настолько много, что задача нахождения их координат более трудоемкая, чем
построение вектора
N и "прохождение" им через многоугольник, то целесообразнее построить вектор и найти "крайние"
точки, как это сделано в рассмотренном примере.
Зачастую некоторые или все переменные задачи являются целочисленными, т.е. их значениями могут быть только
целые числа (как во втором разделе данного задачника). В общем случае многих переменных такие задачи решать
достаточно сложно; если же задача целочисленного программирования имеет две переменные, то ее можно решить
графически. Как и при решении обычной задачи линейного программирования, надо двигать линию уровня в направлении
экстремума и уловить последнюю целочисленную точку. Она и дает искомое оптимальное целочисленное решение (см. ниже
задачу 1).
Примеры решения задач
Задача 1.
Найти наибольшее значение функции F (х, y) = 10х + 6y в точках области:
≥≥
≤+
≤+
.0 ,0
;2685
;621615
yx
yx
yх
Х
1
l
′
Х
2
l
′
′
l
M
1
M
2
M
3
M
4
O
N

Страницы