Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 19 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
21
B
x - единственное решение задачи .
10. Выписать ответ: задача решений не имеет из-за неограниченности целе-
вой функции на допустимом множестве: +∞= )(
sup
xz
Ω
Пример 2. Решить задачу
5,1,0
2
1
1
max232
521
421
321
54321
=≥
=++
=+−
=++−
→
+
−
+
−
ix
xxx
xxx
xxx
xxxxx
i
Решение. Оформим решение задачи в виде таблицы . В первом столбце по-
местим текущие базисные переменные, во втором - их коэффициенты в це-
левой функции, в третьем - базисные координаты текущей точки
B
x . Далее
переписываем элементы матрицы
,
ij
a
помещая над каждым столбцом ко-
эффициент соответствующей переменной в целевой функции. Последний
столбец предназначается для определения значения Θ . В отдельной строке
вычисляются оценки векторов A
j
. В ячейке, находящейся на пересечении
оценочной строки и столбца
x
, помещаем значение целевой функции в те-
кущей базисной точке.
2 -1 3 -2 1
B
C
B
x
A
1
A
2
A
3
A
4
A
5
Θ
x
3
3 1 -1 1 1 0 0 ―
x
4
-2 1 1 -1 0 1 0 1
x
5
1 2 1 1 0 0 1 2
j
∆
3 -6 7 0 0 0
x
3
3 2 0 0 1 1 0
x
1
2 1 1 -1 0 1 0
x
5
1 1 0 2 0 -1 1
j
∆
9 0 1 0 6 0
Поскольку на первой итерации Δ
1
<0, в базис вводится вектор A
1
.
1},min{
1
2
1
1
=
=
Θ
, т.е. в качестве направляющего элемента выбирается
21
a .
Так как на второй итерации все Δ
j
≥0, то останов , получена оптимальная
точка
)(1,0,2,0,1x =
*
. Поскольку на небазисных векторах
0
>
j
∆
, то реше-
ние в задаче единственно.
Пример 3. Решить задачу 
                                                       Линейное программирование


 x B - единственное решение задачи.
10. Выписать ответ: задача решений не имеет из-за неограниченности целе-
вой функции на допустимом множестве: sup z ( x ) =+∞
                                                Ω
Пример 2. Решить задачу
                     2 x1 −x 2 +3 x3 −2 x 4 +x 5 → max
                       � −x1 +x 2 +x 3         =1
                        �
                          � x1 −x 2 + x 4      =1
                       �   x1 +x 2 +         x 5 =2
                       �
                      x i ≥0, i =1,5
Решение. Оформим решение задачи в виде таблицы. В первом столбце по-
местим текущие базисные переменные, во втором - их коэффициенты в це-
левой функции, в третьем - базисные координаты текущей точки x B . Далее
переписываем элементы матрицы a ij , помещая над каждым столбцом ко-
эффициент соответствующей переменной в целевой функции. Последний
столбец предназначается для определения значения Θ. В отдельной строке
вычисляются оценки векторов Aj. В ячейке, находящейся на пересечении
оценочной строки и столбца x , помещаем значение целевой функции в те-
кущей базисной точке.

                            2          -1       3     -2     1
  B       CB       x        A1         A2       A3    A4     A5       Θ
  x3       3       1        -1          1       1      0     0        ―
  x4      -2       1         1         -1       0      1     0        1
  x5       1       2        1           1       0      0     1        2
          ∆j       3        -6          7       0      0     0
  x3       3       2        0           0        1     1      0
  x1       2       1        1          -1        0     1      0
  x5       1       1        0           2        0    -1      1
          ∆j       9        0           1        0     6      0

Поскольку на первой итерации Δ1 <0, в базис вводится вектор A1.
Θ =min{11 , 12} =1 , т.е. в качестве направляющего элемента выбирается a 21 .
Так как на второй итерации все Δj ≥0, то останов, получена оптимальная
точка x * =(1,0,2,0,1 ) . Поскольку на небазисных векторах ∆ j >0 , то реше-
ние в задаче единственно.

Пример 3. Решить задачу



                                        21

Страницы