Линейное программирование. Азарнова Т.В - 18 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
20
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 x 3 −2 x 4 +x5 → max
                       � −x1 +x 2 +x3            =1
                        �
                          � x1 −x 2 + x 4       =1
                       �    x1 +x 2 +         x 5 =2
                       �
                      xi ≥0, i =1,5
Решение. Оформим решение задачи в виде таблицы. В первом столбце по-
местим текущие базисные переменные, во втором - их коэффициенты в це-
левой функции, в третьем - базисные координаты текущей точки x B . Далее
переписываем элементы матрицы aij , помещая над каждым столбцом ко-
эффициент соответствующей переменной в целевой функции. Последний
столбец предназначается для определения значения Θ. В отдельной строке
вычисляются оценки векторов 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. Решить задачу



                                         20

Страницы