Системы линейных неравенств. Зоркальцев В.И - 85 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

85
Согласно теореме 3.16 (Гейла), система уравнений и неравенств (27)
– (29) не имеет решения в том и только том случае, если имеет решения
система линейных уравнений и неравенств
)(,0))(( xJjuAxf
j
∈=−∇
Τ
,
)(,0))((
0
xJjuAxf
j
∈≥−∇
Τ
относительно вектора переменных
m
R
u
∈
, т.е. если выполняются условия
(24), (25).
Теорема 4 доказана.
Задачи к главе 5
1.
Построить задачи, двойственные к данным:
а)
123
12 3
12
1
23 min
41,
2,
0.
xxx
xx x
xx
x
++→
+− ≥
−=
≥
б)
12345
1345
145
15
125
2345 min
0,
0,
1,
0, 0, 0.
xxxxx
xxx x
xxx
xx
xxx
+
+++→
+++≥
++≤
−=
≥≥≤
2.
Используя теорию двойственности, найти оптимальное решение задач
линейного программирования, относительно внутренние точки
оптимальных решений и определить с их помощью единственность
или неединствееность оптимальных решений данных задач и
двойственных им. Определить, какие переменные прямой и
двойственной задач ограничены и неограниченны на множествах
допустимых решений соответствующих задач.
а)
12 3
12
3min
,1,
0, 1,
n
i
j
xx x nx
xx xii n
xjn
++ ++ →
+++≥ =
≥=
K
K
б)
1234
12
12345
min
0,
1,
0, 1, , 5.
i
xxxx
xx
xxxxx
xi
+
++→
−≥
+
−+−≥
≥=
K
3.
К данной задаче линейного программирования сконструировать
двойственную. Установить ограниченность или неограниченность
целевых функций этих взаимно-двойственных задач ЛП.
12 34 5
123 45
12345
45 2 2 min,
35 4 2 21,
46 3 1,
0, 1, ,5.
j
xx xx x
xx x x x
xxxxx
xj
++++→
−++++=
−− −++ =−
≥=K
      Согласно теореме 3.16 (Гейла), система уравнений и неравенств (27)
– (29) не имеет решения в том и только том случае, если имеет решения
система линейных уравнений и неравенств
                             (∇f ( x) − AΤu ) j = 0, j ∈ J ( x) ,

                             (∇f ( x) − AΤu ) j ≥ 0, j ∈ J 0 ( x)

относительно вектора переменных u ∈ R m , т.е. если выполняются условия
(24), (25).
Теорема 4 доказана.

Задачи к главе 5

   1. Построить задачи, двойственные к данным:
                                     x1 + 2 x2 + 3 x3 + 4 x4 + 5 x5 → min
       x1 + 2 x2 + 3 x3 → min
                                     x1 + x3 + x4 + x5 ≥ 0,
       x1 + x2 − 4 x3 ≥ 1,
    а)                            б) x1 + x4 + x5 ≤ 0,
       x1 − x2 = 2,
                                     x1 − x5 = 1,
       x1 ≥ 0.
                                     x1 ≥ 0, x2 ≥ 0, x5 ≤ 0.
 2. Используя теорию двойственности, найти оптимальное решение задач
    линейного программирования, относительно внутренние точки
    оптимальных решений и определить с их помощью единственность
    или неединствееность оптимальных решений данных задач и
    двойственных им. Определить, какие переменные прямой и
    двойственной задач ограничены и неограниченны на множествах
    допустимых решений соответствующих задач.

                                                        x1 + x2 + x3 + x4 → min
      x1 + x2 + 3 x3 + K + nxn → min
                                                        x1 − x2 ≥ 0,
   а) x1 + x2 + K + xi ≥ i, i = 1, n               б)
                                                        x1 + x2 − x3 + x4 − x5 ≥ 1,
      x j ≥ 0, j = 1, n
                                           xi ≥ 0, i = 1, K, 5.
3. К данной задаче линейного программирования сконструировать
   двойственную. Установить ограниченность или неограниченность
   целевых функций этих взаимно-двойственных задач ЛП.
     4 x1 + 5 x2 + 2 x3 + x4 + 2 x5 → min,
     −3 x1 + 5 x2 + 4 x3 + 2 x4 + 2 x5 = 1,
     −4 x1 − 6 x2 − x3 + x4 + 3 x5 = −1,
             x j ≥ 0, j = 1, K,5.



                                              85

Страницы