ВУЗ:
Составители:
10 11
Элементы ведущей строки делятся на ведущий эле-
мент:
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
−−
−−
−
++−−−−
5001000010
30
4
1
010
4
1
0
2
1
0
2
2
1
4
1
00
2
1
4
1
010
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
Далее выполняются элементарные преобразования над
строками матрицы, в результате которых на месте ведущего
столбца окажется столбец единичной матрицы:
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
−−
−−
−−
−−
+−+−−−
3
2
1
4
1
10
2
1
4
1
000
4
4
1
8
3
01
4
1
8
3
000
2
2
1
4
1
00
2
1
4
1
010
2
4
1
8
3
00
4
1
8
3
100
16
4
1
8
9
00
4
1
8
9
001 MM
Базисные переменные:
6521
,,,, xxxxF .
Свободные переменные:
2143
,,, rrxx .
Шаг 3. Составление очередной симплекс-таблицы
Искусственных переменных в базисе нет, следователь-
но, новая таблица соответствует первому допустимому ба-
зисному решению.
Симплекс-таблица 3
БП
F
1
x
2
x
3
x
4
x
5
x
6
x
1
r
2
r
Реше-
ние
F
1 0 0
8
9
−
4
1
−
0 0
8
9
+−
M
4
1
+− M
16
2
x
0 0 1
8
3
−
4
1
0 0
4
1
4
1
−
2
1
x
0 1 0
4
1
2
1
−
0 0
2
1
−
2
1
2
5
x
0 0 0
8
3
4
1
1 0
4
1
−
4
1
4
6
x
0 0 0
4
1
−
2
1
0 1
4
1
2
1
−
3
Комментарий к симплекс-таблице 3.
Решение (допустимое базисное) в 8-мерном простран-
стве
X
=(2,2,0,0,4,3,0,0).
Решение в двумерном пространстве
X
=(2,2). Данная
точка является угловой точкой многоугольника решений.
Значение целевой функции
F
(2,2)=16 свободно от
«штрафа», так как точка принадлежит многоугольнику ре-
шений.
Проверка критерия оптимальности: задача на мини-
мизацию, в строке целевой функции все коэффициенты при
свободных переменных отрицательны, следовательно, по-
лучено оптимальное решение.
Таким образом, решение
X
=(2,2), при котором целе-
вая функция достигает своего минимального значения
F
(2,2)=16, будет ответом в данной задаче.
Шаг 3. Составление очередной симплекс-таблицы
Элементы ведущей строки делятся на ведущий эле- Искусственных переменных в базисе нет, следователь-
мент: но, новая таблица соответствует первому допустимому ба-
зисному решению.
⎛ 1 1 5 3 5 ⎞
⎜ 1 2M − 0 M− −M 0 0 − M + 0 4 M + 15 ⎟
⎜ 2 2 4 2 4 ⎟ Симплекс-таблица 3
⎜0 1 1 1
1 − 0 0 0 0 3⎟ x3 x 4 x5 x6 Реше-
⎜ 2 4 4 ⎟ БП F x1 x 2 r1 r2 ние
⎜ 1 1 1 1 ⎟
⎜0 1 0 − 0 0 − 2⎟ −
9
−
1
−M +
9
−M +
1
4 2 4 2 F 1 0 0 0 0 16
⎜ ⎟ 8 4 8 4
⎜0 1 1 1
− 0 0 1 0 − 0 3⎟ 3 1 1 1
⎜ 2 4 4 ⎟ x2 0 0 1 − 0 0 − 2
⎜ ⎟ 8 4 4 4
⎜0 1 0 0 0 0 1 0 0 5⎟ 1 1 1 1
⎝ ⎠ x1 0 1 0 − 0 0 − 2
4 2 2 2
3 1 1 1
Далее выполняются элементарные преобразования над x5 0 0 0 1 0 − 4
8 4 4 4
строками матрицы, в результате которых на месте ведущего 1 1 1 1
столбца окажется столбец единичной матрицы: x6 0 0 0 − 0 1 − 3
4 2 4 2
⎛ 9 1 9 1 ⎞ Комментарий к симплекс-таблице 3.
⎜1 0 0 − − 0 0 −M + −M + 16 ⎟
⎜ 8 4 8 4 ⎟ Решение (допустимое базисное) в 8-мерном простран-
⎜0 3 1 3 1
0 1 − 0 0 − 2⎟ стве X =(2,2,0,0,4,3,0,0).
⎜ 8 4 8 4 ⎟
⎜ 1 1 1 1 ⎟ Решение в двумерном пространстве X =(2,2). Данная
⎜0 1 0 − 0 0 − 2⎟ точка является угловой точкой многоугольника решений.
⎜ 4 2 4 2 ⎟
⎜0 3 1 3 1 Значение целевой функции F (2,2)=16 свободно от
0 0 − 1 0 − 4⎟
⎜ 8 4 8 4 ⎟ «штрафа», так как точка принадлежит многоугольнику ре-
⎜ 1 1 1 1 ⎟ шений.
⎜0 0 0 − 0 1 − 3⎟
⎝ 4 2 4 2 ⎠ Проверка критерия оптимальности: задача на мини-
мизацию, в строке целевой функции все коэффициенты при
Базисные переменные: F , x1 , x 2 , x5 , x6 . свободных переменных отрицательны, следовательно, по-
лучено оптимальное решение.
Свободные переменные: x3 , x 4 , r1 , r2 .
Таким образом, решение X =(2,2), при котором целе-
вая функция достигает своего минимального значения
F (2,2)=16, будет ответом в данной задаче.
10 11
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
