Исследование операций в экономике. Калашникова Т.В. - 18 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

Таблица 1.6
Исходная таблица решения задачи линейного программирования
симплексным методом
β
Х
1
Х
2
Х
3
Х
4
Q
Х
3
8 2 4 1 0 8/2
Х
4
5 5 1 0 1 5/5
f(x)
0 –2 –1 0 0 –
↑
Значения в столбце соответствуют коэффициентам при перемен-
ных,
β
– столбец свободных членов.
Строки соответствуют уравнениям задачи, последняя строка – ли-
нейная форма, она записывается в виде: f(x)=0 – (–2)x
1
– (–1)x
2
. Задача
решается до тех пор, пока все коэффициенты в последней строке не ста-
нут больше или равны 0.
1 итерация.
В последней строке таблицы находим максимальное по абсолют-
ной величине отрицательное число (= –2). Столбец, в котором стоит это
число, называется ведущим. Соответствующая ведущему столбцу сво-
бодная переменная (х
1
) станет базисной. Делим элементы столбца
β
на ведущий столбец – записываем значения в столбец Q. Экономиче-
ский смысл элементов столбца Q: они показывают, на сколько можно
увеличить переменную, вводимую в базис, чтобы остальные перемен-
ные не стали отрицательными. Из элементов столбца Q выбираем мини-
мальное значение 8/2=4, 5/5=1
⇒
min=1, оно соответствует х
4
⇒
строка,
соответствующая этой переменной называется ведущей, ведущая строка
показывает, какая переменная (в данном примере переменная х
4
) станет
свободной. Переменная х
1
вместо х
4
становится базисной. На каждом
шаге решения количество базисных переменных остается неизменным.
Элемент, стоящий на пересечении ведущего столбца с ведущей строкой,
называется ведущим элементом.
Важно помнить. При заполнении столбца Q надо делить только
на положительные коэффициенты ведущего столбца. Так как если бы
один из коэффициентов был отрицателен или равен нулю, соответству-
ющая базисная переменная не стала бы отрицательной ни при каком по-
ложительном значении переменной, вводимой в базис.
Заметим, что в данном примере коэффициенты ведущего столбца
все положительные (стоящие в строках базисных переменных)
⇒
обе
18

Страницы