Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 58 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
58
проходить при уменьшении (увеличении)
a
, является решением задачи
линейного программирования на минимум (максимум). Величина
(
)
,
II
aa
*
*
==
, соответствующая этому положению линии уровня, будет
минимальным (максимальным) значением целевой функции
I
на множестве
U
.
Очевидно, что точку
÷
÷
ø
ö
ç
ç
è
æ
*
*
y
x
следует искать среди вершин многоугольника
U
.
Точное значение ее координат находится как решение системы двух линейных
алгебраических уравнений, задающих стороны многоугольника, пересечением
которых является указанная точка.
Возможна ситуация, когда линия уровня целевой функции, отвечающая
значению
*
= I
a
(
)
a
*
=
, будет иметь не одну общую точку с множеством U , а
целую сторону, однако и в этом случае вершина многоугольника войдет во
множество решений задачи линейного программирования.
Если множество U неограниченно, то не исключается, что линия уровня
целевой функции будет иметь общую точку с множеством U при всех
(
)
+¥
¥
-
Î
,
a
. Это означает, что
(
)
II
*
*
=-¥=+¥
, т.е. решение задачи
неограниченно.
Итак, возможны следующие ситуации:
1) -¥>ƹ
*
IU ,
(
)
I
*
<+¥
, ƹ
*
U
(
)
U
*
¹Æ
,
*
U
(
)
U
*
содержит ровно одну
точку;
2) -¥>ƹ
*
IU , ,
(
)
I
*
<+¥
, ƹ
*
U
(
)
U
*
¹Æ
,
*
U
(
)
U
*
совпадает со стороной
многоугольника;
3) -¥=ƹ
*
IU ,
(
)
I
*
=+¥
, Æ=
*
U
(
)
U
*
=Æ
;
4)
Æ
=
U .
Аналогичные результаты имеют место и при 2
>
n . 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


проходить при уменьшении (увеличении) a , является решением задачи
линейного               программирования    на        минимум   (максимум).      Величина
a = I* , (a = I * ) ,    соответствующая этому положению линии уровня, будет

минимальным (максимальным) значением целевой функции I на множестве U .
                               æx ö
Очевидно, что точку çç * ÷÷ следует искать среди вершин многоугольника U .
                     è y* ø

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

      Возможна ситуация, когда линия уровня целевой функции, отвечающая
значению a = I * (a = I * ) , будет иметь не одну общую точку с множеством U , а

целую сторону, однако и в этом случае вершина многоугольника войдет во
множество решений задачи линейного программирования.

      Если множество U неограниченно, то не исключается, что линия уровня
целевой функции будет иметь общую точку с множеством U при всех
a Î (- ¥,+¥ ) . Это означает, что I* = -¥ ( I * = +¥) , т.е. решение задачи
неограниченно.

      Итак, возможны следующие ситуации:

      1) U ¹ Æ, I * > -¥ ( I * < +¥) , U * ¹ Æ (U * ¹ Æ) , U * (U * ) содержит ровно одну

точку;

      2) U ¹ Æ, I * > -¥ , ( I * < +¥) , U * ¹ Æ (U * ¹ Æ) , U * (U * ) совпадает со стороной

многоугольника;

      3) U ¹ Æ, I * = -¥ ( I * = +¥) , U * = Æ (U * = Æ) ;

      4) U = Æ .

      Аналогичные результаты имеют место и при n > 2 .




                                                 58

Страницы