ВУЗ:
Составители:
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
- …
- следующая ›
- последняя »