ВУЗ:
Составители:
8 9
Далее выполняются элементарные преобразования над
строками матрицы, в результате которых на месте ведущего
столбца окажется столбец единичной матрицы:
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
−−
−−
−
++−−−−
5001000010
30
4
1
010
4
1
0
2
1
0
41
2
1
001
2
1
020
30
4
1
000
4
1
1
2
1
0
1540
4
5
2
3
00
4
5
2
1
0
2
1
21
MMMMM
Базисные переменные:
2652
,,,, rxxxF .
Свободные переменные:
1431
,,, rxxx .
Шаг 2. Составление следующей симплекс-таблицы
Так как в базисе осталась еще одна искусственная пе-
ременная, то новая таблица соответствует второму искусст-
венному базисному решению.
Симплекс-таблица 2
БП
F
1
x
2
x
3
x
4
x
5
x
6
x
1
r
2
r
Реше-
ние
Отноше-
ние
F
1
2
1
2 −M
0
4
5
2
1
−M
-M 0 0
4
5
2
3
+− M
0
154
+
M
2
x
0
2
1
1
4
1
−
0 0 0
4
1
0 3
3:
2
1
=6
2
r
0 2 0
2
1
-1 0 0
2
1
−
1 4 4:2=2
5
x
0
2
1
−
0
4
1
0 1 0
4
1
−
0 3
3:
2
1
−
<0
6
x
0 1 0 0 0 0 1 0 0 5 5:1=5
Комментарий к симплекс-таблице 2.
Решение (искусственное базисное) в 8-мерном про-
странстве
X
=(0,3,0,0,3,5,0,4).
Решение в двумерном пространстве
X
=(0,3). Данная
точка также находится за пределами многоугольника реше-
ний.
Значение целевой функции
F (0,3)=4
M
+15 – «штраф-
ное», так как точка не принадлежит многоугольнику реше-
ний.
Проверка критерия оптимальности: задача на мини-
мизацию, в строке целевой функции имеются положитель-
ные коэффициенты при свободных переменных
1
x и
3
x ,
следовательно, оптимальное решение не достигнуто. Необ-
ходимо выбрать среди свободных включаемую в базис пе-
ременную.
Выбор включаемой в базис переменной: наибольший
положительный коэффициент
2
1
2
1
−= Mс при переменной
1
x .
Проверка критерия допустимости: среди оценочных
отношений (последний столбец таблицы) встречаются ко-
нечные положительные, следовательно, возможен выбор
исключаемой из базиса переменной.
Выбор исключаемой переменной: среди оценочных
отношений минимальным является отношение, соответст-
вующее переменной
2
r , которая и будет исключена из бази-
са на этом шаге.
Ведущим элементом при пересчете будет элемент,
стоящий на пересечении ведущей строки, соответствующей
исключаемой переменной
2
r
, и ведущего столбца, соответ-
ствующего включаемой переменной
1
x .
Пересчет таблицы в матричной записи.
Далее выполняются элементарные преобразования над Комментарий к симплекс-таблице 2.
строками матрицы, в результате которых на месте ведущего Решение (искусственное базисное) в 8-мерном про-
столбца окажется столбец единичной матрицы: странстве X =(0,3,0,0,3,5,0,4).
Решение в двумерном пространстве X =(0,3). Данная
⎛ 1 1 5 3 5 ⎞ точка также находится за пределами многоугольника реше-
⎜ 1 2M − 0 M− −M 0 0 − M + 0 4M + 15 ⎟
⎜ 2 2 4 2 4 ⎟ ний.
⎜0 1 1 1 Значение целевой функции F (0,3)=4 M +15 – «штраф-
1 − 0 0 0 0 3⎟
⎜ 2 4 4 ⎟ ное», так как точка не принадлежит многоугольнику реше-
⎜ 1 1 ⎟
⎜0 2 0 −1 0 0 − 1 4⎟ ний.
⎜ 2 2 ⎟ Проверка критерия оптимальности: задача на мини-
⎜0 1 1 1
− 0 0 1 0 − 0 3⎟ мизацию, в строке целевой функции имеются положитель-
⎜ 2 4 4 ⎟
⎜ ⎟ ные коэффициенты при свободных переменных x1 и x3 ,
⎜0 1 0 0 0 0 1 0 0 5⎟ следовательно, оптимальное решение не достигнуто. Необ-
⎝ ⎠
Базисные переменные: F , x 2 , x5 , x 6 , r2 . ходимо выбрать среди свободных включаемую в базис пе-
ременную.
Свободные переменные: x1 , x3 , x 4 , r1 . Выбор включаемой в базис переменной: наибольший
1
Шаг 2. Составление следующей симплекс-таблицы положительный коэффициент с1 = 2M − при переменной
2
Так как в базисе осталась еще одна искусственная пе- x1 .
ременная, то новая таблица соответствует второму искусст-
Проверка критерия допустимости: среди оценочных
венному базисному решению.
отношений (последний столбец таблицы) встречаются ко-
нечные положительные, следовательно, возможен выбор
Симплекс-таблица 2
исключаемой из базиса переменной.
БП F x1 x2 x3 x 4 x5 x6 r1 r2 Реше-
ние
Отноше-
ние Выбор исключаемой переменной: среди оценочных
1 1 5 3 5 отношений минимальным является отношение, соответст-
F 1 2M − 0 M− -M 0 0 − M+ 0 4M + 15
2 2 4 2 4 вующее переменной r2 , которая и будет исключена из бази-
1 1 1 1 са на этом шаге.
x2 0 1 − 0 0 0 0 3 3: =6
2 4 4 2
Ведущим элементом при пересчете будет элемент,
1 1
r2 0 2 0 -1 0 0 − 1 4 4:2=2 стоящий на пересечении ведущей строки, соответствующей
2 2
исключаемой переменной r2 , и ведущего столбца, соответ-
1 1 1 1
x5 0 − 0 0 1 0 − 0 3 3: − <0 ствующего включаемой переменной x1 .
2 4 4 2
x6 0 1 0 0 0 0 1 0 0 5 5:1=5
Пересчет таблицы в матричной записи.
8 9
Страницы
- « первая
- ‹ предыдущая
- …
- 3
- 4
- 5
- 6
- 7
- …
- следующая ›
- последняя »
