2. Задачи линейного программирования (ЗЛП)
11
ЗЛП – задача, математическая модель которой имеет вид:
(2)
Если в задаче (2) целевая функция стремится к min, а
ограничения заданы равенствами, то |
говорят, что задача |
представлена в канонической форме. |
12 |
!!! Любую ЗЛП можно свести к ЗЛП в канонической форме.
Правило приведения ЗЛП к каноническому виду:
1) Если в исходной задаче требуется определить максимум функции, то надо изменить знак этой функции и искать ее
минимум.
2)Если в ограничении правая часть отрицательна, то надо умножить это ограничение на «-1».
3)Если в ограничения имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства.
4)Если некоторая переменная не имеет ограничений по знаку, то она заменяется на разность между двумя новыми
неотрицательными переменными: , где – свободный индекс;
13
3. Графический метод решения ЗЛП
14
Этот метод, как правило, используется тогда, когда необходимо решить задачу с двумя переменными при ограничениях, выраженных неравенствами.
Формально такая задача имеет вид:
(*)
(**)
(***)
15
Каждое ограничение–неравенство задает полуплоскость. Система же ограничений, если же она совместна, определяет область – множество точек, принадлежащих всем полуплоскостям.
Это множество – многоугольник решений. Областью допустимых значений
переменных может быть:
―выпуклый многоугольник;
―выпуклая многоугольная неограниченная область;
―Ø (пустое множество);
―луч; отрезок; точка.
16
Целевая функция определяет на плоскости
семейство параллельных прямых, каждой из которых соответствует определенное значение
.
Вектор , перпендикулярный этим прямым, указывает
направление наискорейшего возрастания
целевой функции, а противоположный вектор
– направление наискорейшего убывания
целевой функции.
17
Алгоритм графического метода:
1.По неравенствам (**) строим ОДЗ.
2.По целевой функции (*) строим линию уровня = c1x1+c2x2=0, проходящую через начало координат и
перпендикулярную вектору .
3.Перемещаем линию уровня в направлении вектора , если ищем максимум функции, и в противоположном направлении, если ищем минимум функции.
4.Точка отрыва линии уровня от ОДЗ - точка оптимума (max; min) - определяет оптимальное решение.
5.Находим значение целевой функции в точке отрыва.
18
!!! Важно
Следует учесть, что при решении ЗЛП графическим методом могут встретиться следующие случаи:
19
x2
А
Fmax
|
Оптимум функции F(x1;x2) |
|
достигается в точке А. |
|
А |
|
Fmin |
F=0 |
x1 20 |
x2
|
Оптимум достигается |
А |
в любой точке отрезка АВ. |
|
В |
|
Fmax |
|
Fmin |
F=0 |
x1 21 |
x2
Оптимум не достижим.
Fmax = ∞
F=0 |
x1 22 |
x2
ОДЗ задает пустую область.
F=0 |
x1 23 |