Лекции 4
.doc
Алгоритм перевода одной переменной в базисную,
а другой переменной в небазисную
Пусть по результатам
-
строки нам необходимо переменную
перевести в базисную, а по результатам
-
столбца переменную
надо сделать небазисной. Для этого
необходимо сделать следующее.
1. Делим все
строки (все коэффициенты
и
)
на
,
где
-
номер строки,
-
номер новой базисной переменной.
2. Строку с
номером
оставляем без изменений и её вычитаем
из остальных строк (эти действия позволяют
добиться, чтобы переменная
входила в одну строку, т.е. в одно
уравнение, с коэффициентом +1).
3. Делим все
строки (кроме строки с номером
)
на
,
где
-
номер строки, соответствующей базисной
переменной
(это позволяет добиться, чтобы остальные
базисные переменные входили в уравнении
(строки) с коэффициентами +1).
4. Проверяем,
что
и все
.
Теперь переменная
становится базисной, а переменная
становится не базисной.
Например, в рассматриваемом примере таблица симплекс-метода имеет следующий вид.
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
4 |
1.5 |
24 |
|
|
|
0 |
1 |
0 |
1200 |
150 |
6000 |
|
|
|
0 |
0 |
1 |
20 |
20 |
200 |
|
-
Разделим все строки на
(в данном случае
)
|
|
|
|
|
|
|
|
|
|
1/4 |
0 |
0 |
1 |
3/8 |
6 |
|
|
0 |
1/1200 |
0 |
1 |
1/8 |
5 |
|
|
0 |
0 |
1/20 |
1 |
1 |
10 |
Теперь все
коэффициенты перед
равны единице.
-
Вычитаем вторую строку (соответствующую переменной
)
из первой и третьей строки.
|
|
|
|
|
|
|
|
|
|
1/4 |
-1/1200 |
0 |
0 |
1/4 |
1 |
|
|
0 |
1/1200 |
0 |
1 |
1/8 |
5 |
|
|
0 |
-1/1200 |
1/20 |
0 |
7/8 |
5 |
Теперь базисной
стала переменная
т.к. входит только в одно уравнение (во
вторую строку) с коэффициентом +1. Поэтому
вторая строка будет соответствовать
новой базисной переменной
(а не
).
Однако другие
базисные переменные (
)
входят в уравнения с коэффициентами,
отличными от +1.
-
Делим первую и третью строки на
(первую на
,
третью на
).
|
|
|
|
|
|
|
|
|
|
1 |
-1/300 |
0 |
0 |
1 |
4 |
|
|
0 |
1/1200 |
0 |
1 |
1/8 |
5 |
|
|
0 |
-1/60 |
1 |
0 |
35/2 |
100 |
Теперь базисные
переменные
входят
только в одну сторону с коэффициентом
+1, и все
>
.
-
Далее можно вначале расположить базисные переменные.
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
-1/300 |
4 |
|
|
1 |
0 |
0 |
1/8 |
1/1200 |
5 |
|
|
0 |
0 |
1 |
35/2 |
-1/60 |
100 |
Строки так же можно расположить в порядке возрастания индекса.
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
1/8 |
1/1200 |
5 |
|
|
0 |
1 |
0 |
1 |
-1/300 |
4 |
|
|
0 |
0 |
1 |
35/2 |
-1/60 |
100 |
Хотя в рабочей программе этого можно и не делать, что кстати и не делается в контрольном примере.