Линейное программирование. Филькин Г.В. - 14 стр.

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

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

Рубрика: 

13
72/9=8, 24/(1/2)=48, 108/(3/2)=72, следовательно разрешающим элемен-
том будет 9, и из базиса выйдет вектор A
4
.Пересчитываем таблицу 2 по вы-
шеуказанным правилам и получаем следующую таблицу.
9 10 16 0 0 0
Базис С
б
А
0
А
1
А
2
А
3
А
4
А
5
А
6
А
2
10 8 1 1 0 1/0 -1/6 0
А
3
16 20 1/4 0 1 -1/18 5/24 0
А
6
0 96 5/4 0 0 -1/6 -1/8 1
Z
j
-C
j
400 5 0 0 2/9 5/3 0
Таблица 3. Третье опорное решение.
Получили третье опорное решение X
3
=(0,8,20,0,0,96), z=400. Следова-
тельно, первая продукция не производится, вторая выпускается в объеме 8
единиц, третья в объеме 20 единиц, первого сырья не осталось, второе сырье
также закончилось, третьего осталось 96 единиц. План оптимальный, так как
в строке Z
j
- C
j
отрицательных чисел нет.
ОСОБЫЙ СЛУЧАЙ ПРИ РЕШЕНИИ ЗАДАЧ ЛП СИМПЛЕКС-
МЕТОДОМ ( ЦЕЛЕВАЯ ФУНКЦИЯ НЕОГРАНИЧЕНА НА ОБЛАСТИ
ДОПУСТИМЫХ ЗНАЧЕНИЙ).
При решении задач ЛП симплекс-методом также возникают особые
случаи, рассмотрим следующий пример
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=≥
=+−−
=++−−
=+++−
→+−=
6,1,0
18123
2432
202
max562
6521
5421
5321
521
jx
xxxx
xxxx
xxxx
xxxz
j
Данная задача является канонической, так как выполняются все необ-
ходимые условия, выпишем соответствующую симплексную таблицу.
2 -6 0 0 5 0
Базис Сб А
0
А
1
А
2
А
3
А
4
А
5
А
6
А
3
0 20 -2 1 1 0 1 0
← А
4
0 24 -1 -2 0 1 3 0
А
6
0 18 3 -1 0 0 -12 1
Z
j
-C
j
0 -2 6 0 0 -5 ↑ 0
Таблица 4. Первое опорное решение. 
     72/9=8, 24/(1/2)=48, 108/(3/2)=72, следовательно разрешающим элемен-
том будет 9, и из базиса выйдет вектор A4.Пересчитываем таблицу 2 по вы-
шеуказанным правилам и получаем следующую таблицу.

                                 9      10        16     0        0     0
Базис           Сб    А0
                                А1      А2        А3     А4      А5     А6
  А2            10     8         1      1         0     1/0     -1/6    0
  А3            16     20       1/4     0         1    -1/18    5/24    0
  А6            0      96       5/4     0         0     -1/6    -1/8    1
        Zj-Cj         400        5      0         0     2/9     5/3     0

        Таблица 3. Третье опорное решение.

      Получили третье опорное решение X3 =(0,8,20,0,0,96), z=400. Следова-
тельно, первая продукция не производится, вторая выпускается в объеме 8
единиц, третья в объеме 20 единиц, первого сырья не осталось, второе сырье
также закончилось, третьего осталось 96 единиц. План оптимальный, так как
в строке    Zj - Cj отрицательных чисел нет.

    ОСОБЫЙ СЛУЧАЙ ПРИ РЕШЕНИИ ЗАДАЧ ЛП СИМПЛЕКС-
МЕТОДОМ ( ЦЕЛЕВАЯ ФУНКЦИЯ НЕОГРАНИЧЕНА НА ОБЛАСТИ
ДОПУСТИМЫХ ЗНАЧЕНИЙ).

     При решении задач ЛП симплекс-методом также возникают особые
случаи, рассмотрим следующий пример
        z = 2 x1 − 6 x2 + 5 x5 → max
        ⎧− 2 x1 + x2 + x3 + x5 = 20
        ⎪− x − 2 x + x + 3x = 24
        ⎪ 1          2    4    5
        ⎨
        ⎪3x1 − x2 − 12 x5 + x6 = 18
        ⎪ x j ≥ 0, j = 1 , 6
        ⎩
     Данная задача является канонической, так как выполняются все необ-
ходимые условия, выпишем соответствующую симплексную таблицу.

Базис      Сб        А0      2         -6        0     0       5       0
                             А1        А2        А3    А4      А5      А6
    А3     0         20      -2        1         1     0       1       0
← А4       0         24      -1        -2        0     1       3       0
    А6     0         18      3         -1        0     0       -12     1
Zj-Cj                0       -2        6         0     0       -5 ↑    0

        Таблица 4. Первое опорное решение.


                                            13

Страницы