Задачи ЛП и методы их решения
.pdf
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вершины, "лучшие" |
|
|
|
|
|
|
|
|
|
|
|
|
чем X0 |
(f > f0) |
|
|
|
|
|
|
|
|
|
X4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
X5 |
|
Направление |
|
|
|
|
|
|
|
|
|
|
|
возрастания f |
|
|
|
|
|
|
|
|
|
X3 |
Мн-во |
|
||
|
|
|
Конус возможных |
|
|
|
|
|
||||
|
|
|
|
|
|
|
Решений |
|
|
|||
|
|
|
направлений |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
ЗЛП |
f = f0 |
|
||
|
|
|
улучшения решения X0 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
X2 |
1 |
X0 |
|
Начало |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
координат |
|
X4 |
|
|
|
|
|
|
|
|
X1 |
|
|
|
|
|
|
|
|
|
Вершины, "худшие" |
|
|
|
0 |
|
|
|
X5 |
|
|
|
|
чем X0 |
(f < f0) |
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-Z2 |
-Z3 |
|
|
|
|
|
|
|
|
|
X3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
-Z1 |
|
|
|
|
|
2. В противном случае определяются |
|||||
|
|
|
|
|
|
|
||||||
X2 |
2 |
|
X0 |
|
|
|
направления на “лучшие” вершины (здесь -z1, - |
|||||
|
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
z2, -z3), которые |
образуют |
конус |
возможных |
||
|
|
X1 |
|
|
|
|
направлений улучшения текущего решения x0. |
|||||
|
|
|
|
|
|
|
||||||
3. |
Далее |
выбирается |
одно |
из |
направлений |
|
X4 |
|
|
|||
улучшения |
решения |
(например |
-z1 |
). |
С помощью |
|
|
|
||||
|
|
|
X5 |
N |
||||||||
положительного числового коэффициента θ вектор -z1 |
|
|
|
|
||||||||
|
|
|
|
|
||||||||
растягивается (или сжимается) таким образом, чтобы |
X3 |
- θZ1 |
|
|
||||||||
вектор -θz1 “упирался” в “лучшую” вершину (здесь x3). |
|
-Z1 |
|
|
||||||||
|
|
|
|
|
2 Z |
X2 |
3 |
X0 |
|
|||
Z |
|
|
|
0.5 Z |
|
|
X1 |
- Z |
|
|
|
|
|
|
0 |
Умножение вектора на число θ >1 геометрически представляет растяжение вектора в θ раз, если же θ <1, то умножение на θ сжимает вектор в θ раз (см. рис.)
После выбора переход к “лучшей” вершине совершается по правилу (см.рис.) x3 = x0 − θ z1
Теперь в качестве текущего решения имеем вершину x3 , в которой значение целевой функции больше, чем в предыдущей вершине x0.
f (x3 ) = f1 > f0 = f (x0 )
|
N |
X4 |
|
|
|
|
X5 |
f = f1 |
|
|
|
|
X3 |
|
|
f = f0 |
X2 |
1 |
X0 |
|
|
||
|
|
|
X1 |
f = f1-f0 |
|
|
|
“Скачок” целевой функции в сторону увеличения равен f . Таким образом, мы опять
пришли к случаю , но текущее значение
целевой функции увеличилось. Описанные шаги повторяются до тех пор, пока не будет достигнута оптимальная вершина (в данном случае это x4). Так как число вершин конечно и целевая функция каждый раз не убывает, то через конечное число шагов будет получено оптимальное решение ЗЛП.
20
3.3. Алгоритм прямого симплекс-метода
Запишем алгоритм симплекс-метода в виде последовательности шагов и разберем на примере одну из его численных реализаций (так называемый прямой симплекс-метод). Итак, алгоритм состоит из следующих шагов:
ШАГ 0. ВЫБОР НАЧАЛЬНОГО БАЗИСНОГО РЕШЕНИЯ И ЗАПОЛНЕНИЕ НАЧАЛЬНОЙ СИМПЛЕКС-ТАБЛИЦЫ.
(выполняется один раз)
ШАГ 1. ПРОВЕРКА ТЕКУЩЕГО РЕШЕНИЯ НА ОПТИМАЛЬНОСТЬ. (если решение оптимально, то конец)
ШАГ 2. ВЫБОР НАПРАВЛЕНИЯ УЛУЧШЕНИЯ РЕШЕНИЯ И ОПРЕДЕЛЕНИЕ ПАРАМЕТРА θ.
ШАГ 3. ПЕРЕХОД К НОВОМУ (“ЛУЧШЕМУ”) ТЕКУЩЕМУ РЕШЕНИЮ.
ВОЗВРАЩЕНИЕ К ШАГУ 1.
Переходим к подробному описанию шагов алгоритма прямого симплекс-метода, иллюстрируя их примером о планировании выпуска продукции.
Итак, пусть ЗЛП записана с ограничениями-равенствами.
f = 4x1 + 5x2 |
|
|
|
→ max |
|||
4x1 + 6x2 + x3 |
|
|
= 24 |
||||
|
|
+ 2x2 |
+ x4 |
|
= 12 |
||
3x1 |
|
||||||
|
x |
+ x |
2 |
|
+ x |
5 |
= 8 |
|
1 |
|
|
|
|
||
|
|
xi ≥ 0 |
|
(i 1:5) |
ШАГ 0. ВЫБОР НАЧАЛЬНОГО БАЗИСНОГО РЕШЕНИЯ
Выберем в качестве базисных переменных дополнительные переменные x3 , x4 , x5 . Тогда x1 = x2 = 0 и начальное базисное решение будет иметь вид
X 0 = (0, 0, 24, 12, 8)
Заметим, что дополнительные переменные имеют совершенно ясное содержательное истолкование:
x3 - это остаток сырья 1-го вида, x4 - 2-го, а x5 - 3-го вида. Тогда начальное решение можно интерпретировать следующим образом “если ничего не выпускать ( x1 = x2 = 0 ), то все запасы сырья перейдут в остаток ( x3 = 24, x4 = 12, x5 = 8). При этом будет получена нулевая прибыль ( f (X 0 ) = 0 )”.
Запишем исходные данные ЗЛП и информацию о начальном решении в таблицу, которая называется симплекс-таблицей (n - число переменных, m - число ограничений).
|
|
|
|
|
|
|
|
21 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Коэфф. целевой функции |
|
|||
|
|
|
Значения базисных |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
переменных |
|
|
|
C |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Номера базисных |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
переменных |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
NБ |
CБ |
XБ |
|
A |
(i 1:n) |
|
|
Столбцы коэфф. в |
|
|||
|
|
|
|
|
|
|
|
i |
|
|
|
|
системе ограничений |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Коэфф. целевой |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
функции при |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
базисных |
|
|
|
f |
|
|
|
|
|
|
Строка |
|
|
||
|
переменных |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
Значение целевой |
|
|
|
оценок |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
функции |
|
|
|
|
|
|
|
||
|
Начальная симплекс-таблица для нашего примера с базисным решением примет вид, |
|||||||||||||||
|
представленный |
ниже. Значение |
целевой |
функции на начальном шаге определяется |
||||||||||||
|
|
|
1 |
2 |
3 |
4 |
5 |
подстановкой решения X0 в целевую функцию |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
NБ CБ XБ |
4 |
5 |
0 |
0 |
0 |
|
f (X0 ) = 4 0 |
+ 5 0 + 0 24 + 0 12 + 0 8 = 0 |
||||||||
|
|
|
|
|
|
|
|
|
||||||||
3 |
0 |
24 |
4 |
6 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
4 |
0 |
12 |
3 |
2 |
0 |
1 |
0 |
Оценки |
для |
каждого |
столбца |
(величины, |
||||
служащие |
для |
проверки |
решения |
на |
||||||||||||
|
|
|
|
|
|
|
|
оптимальность) |
|
на |
начальном |
шаге |
||||
5 |
0 |
8 |
1 |
1 |
0 |
0 |
1 |
определяются по формуле |
|
|
|
|
||||
|
|
0 |
-4 |
-5 |
0 |
0 |
0 |
|
|
j |
|
= CБ Aj |
− C j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
Так для подсчета оценки |
1 нужно столбец |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Б = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
скалярно умножить на столбец |
|
|
|
|
|
|
|
|
|
|
4 А1 = 31
и из результата вычесть коэффициент с1 = 4 т.е.
0 4 1 = 0 3 − 4 = 4 0 +3 0 +1 0− 4 = −4
0 1
Оценка 1 записывается в первый элемент строки . Аналогично вычисляются остальные оценки.
22
|
0 |
|
6 |
|
|
0 |
1 |
|
2 = |
|
|
|
|
|
|
|
|
0 |
|
2 |
−5 = −5 , |
3 = 0 |
0 |
− 0 = 0 |
||
|
|
|
|
|
|
|
|
|
|
0 |
|
1 |
|
|
0 |
0 |
|
|
0 |
|
0 |
|
|
0 |
0 |
|
4 = |
|
|
|
|
5 = |
|
|
|
0 |
|
1 |
− 0 = 0 , |
0 |
0 − 0 = 0 |
|||
|
|
|
|
|
|
|
|
|
|
0 |
|
0 |
|
|
0 |
1 |
|
Удобнее всего вычислять оценки прямо в таблице. Столбец Аj , оценку которого надо вычислить, умножается скалярно на столбец CБ . Из полученного числа вычитается коэффициент целевой функции, стоящий над столбцом Аj . Результат записывается в строку оценок под столбцом Аj . Заметим, также. что на начальном шаге (т.к.
CБ = (0, 0, 0) ) оценки равны коэффициентам целевой функции с обратным знаком.
Оценки и значение целевой функции вычисляются только на начальном шаге, а в дальнейшем пересчитываются автоматически. Заполнением начальной симплекс-таблицы завершается нулевой шаг симплекс-метода.
ШАГ 1. ПРОВЕРКА ТЕКУЩЕГО РЕШЕНИЯ НА ОПТИМАЛЬНОСТЬ
Критерием оптимальности (или условием того, что имеющаяся вершина является оптимальной) является выполнение условия
j ≥ 0 ( j 1: n)
для всех |
оценок в строке . |
||
Если |
решается ЗЛП на min, то знак неравенства меняется на обратный и условие |
||
принимает вид |
j ≤ 0 |
( j 1:n) |
При работе с симплекс-таблицей проверка решения на оптимальность сводится к просмотру строки оценок . Если все элементы строки оценок больше или равны нулю, то текущее решение оптимально и вычисления на этом заканчиваются. Если же среди элементов строки оценок имеется хотя бы один отрицательный, то текущее решение не оптимально и может быть улучшено.
Проверим на оптимальность текущее решение в рассматриваемом примере.
1 |
2 |
3 |
4 |
5 |
NБ CБ XБ
0 |
-4 -5 |
0 |
0 |
0 |
|
|
|
|
|
Просмотр элементов строки оценок убеждает нас в том, что среди элементов имеются
отрицательные (отмечены знаком ), а,
значит, текущее решение не является оптимальным и может быть улучшено. На этом шаг проверки решения на оптимальность завершается.
23
ШАГ 2. ВЫБОР НАПРАВЛЕНИЯ УЛУЧШЕНИЯ РЕШЕНИЯ И ОПРЕДЕЛЕНИЕ ПАРАМЕТРА θ
−Z1 ≡A1
NБ CБ
1 |
2 |
3 |
4 |
5 |
XБ |
|
|
|
|
4 |
6 |
|
|
|
3 |
2 |
|
|
|
1 |
1 |
|
|
|
-4 |
-5 |
|
|
|
−Z2 ≡A2
Количество возможных направлений для улучшения текущего решения определяется количеством отрицательных оценок в строке . Так в нашем примере имеется два направления улучшения решения.
Каждой отрицательной оценке |
j соответствует |
свой вектор направления |
− Z j ≡ Aj . В |
приведенной таблице возможные направления в таблице задаются векторами.
|
|
|
4 |
|
|
|
6 |
||
− Z |
1 |
≡ A = |
3 |
и − Z |
2 |
≡ A = |
2 . |
||
|
1 |
|
|
|
2 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
Для улучшения решения выбирается одна из отрицательных оценок, т.е. одно из возможных направлений. (Более точный выбор направления будет описан ниже в замечании). Выберем в примере в качестве направления то, которое отвечает оценке
1 = −4 (в таблице отмечено стрелкой).
После выбора направления − Z j0 проверяется критерий неограниченности целевой
функции на множестве решений (см. случай неразрешимости ЗЛП в разд. 2). Он состоит в следующем:
Если среди элементов выбранного направления − Z j0 ≡ Aj0
нет положительных, то целевая функция не ограничена на множестве решений и ЗЛП неразрешима.
Если же среди элементов Aj0 есть положительные, то решение по выбранному направлению можно улучшить. Для выбранного нами направления в примере
|
|
|
|
|
4 |
|
|
|
|
|
|
A |
= 3 |
|
|
||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
все компоненты положительны. |
|
|
|
|
|
|
|
|
Теперь остается |
определить |
параметр |
θ, |
растягивающий (сжимающий) вектор |
||||
− Z j0 ≡ Aj0 . Значение этого параметра выбирается по следующему правилу: |
||||||||
|
|
|
|
|
|
|
|
|
|
X |
Бi |
|
|
|
|
||
|
θ = min |
|
Aj0i |
> 0 |
|
|||
|
|
|
|
|
||||
|
A |
j0i |
|
|
|
|
||
|
|
|
|
|
|
|
||
В симплекс-таблице |
выбирается наименьшее |
из |
отношений элементов столбца X Б к |
соответствующим положительным элементам вектора направления. Проиллюстрируем сказанное фрагментом симплекс-таблицы.
24
|
|
1 |
2 |
3 |
4 |
5 |
|
|
NБ |
XБ |
|
|
|
|
Минимум достигается в |
строке |
|
|
|
|
|
|
|
|||
3 |
24 |
4 |
6 |
|
|
i0 , соответствующей некоторой |
||
|
|
базисной переменной (в примере |
||||||
|
|
|
|
|
|
|||
4 |
12 |
3 |
2 |
|
|
это переменная |
x4 . Ее |
строка |
|
|
отмечена стрелкой). На этом |
||||||
|
|
|
|
|
|
|||
5 |
8 |
1 |
1 |
|
|
ШАГ 2 завершается. |
|
|
|
|
|
|
|
θ = min 24 ,12 , 8 = min{6,4,8}4 3 1
1. Собственно для перехода к новому решению нам важно знать не саму величину θ, а,
именно, строку i0 , где этот минимум достигается. |
|
2. Величина θ может быть использована для |
более точного выбора направления. |
Известно, что скачок целевой функции, при переходе к “лучшему” решению равен. |
|
f = − j0 θ |
(*) |
(j0 - выбранная оценка, θ - соответствующий ей параметр).
Естественно, хотелось бы при улучшении решения получить максимальный скачок целевой функции. Для этого необходимо:
а). Найти значения θ , соответствующие каждой из отрицательных оценок. б). Выбрать из полученных величин f наибольшую. Ту оценку, которая
отвечает максимальной величине скачка f , и надо выбирать для определения
направления улучшения решения.
Рассмотрим, для нашего примера, какую из двух оценок следует выбрать:
Оценка |
1 |
= −4, θ = min{ 24 / 4, 12 / 3, |
8/1} = 4 , |
f |
= −(−4) 4 =16 |
Оценка |
2 |
= −5, θ = min{ 24 / 6, 12 / 2, |
8/1} = 4, |
f |
= −(−5) 4 = 20 |
Значит сделанный нами выбор был не самым удачным. Если в качестве направления мы выбрали бы то, которое отвечает оценке 2 = −5, значение целевой функции увеличилось бы на 20 единиц, а не на 16, как при выборе оценки 1 = −4. Часто в литературе можно
встретить такое правило выбора оценки: ”Выбирается оценка максимальная по абсолютной величине”. Соотношение (*) показывает, что оно не всегда справедливо (хотя в нашем примере оно выполняется). Другими словами, максимальной по абсолютной величине оценке не обязательно соответствует максимальный скачок целевой функции (θ может быть очень мало). Правило выбора наилучшего направления можно сформулировать в следующем виде: “Выбирать то направление, которому соответствует максимальная абсолютная величина произведения оценки на θ.
3. При реализации симплекс-метода на ЭВМ использование правил выбора направления, как по максимальному модулю оценки, так и по максимуму скачка целевой функции, требует дополнительных вычислений, приводит к дополнительным затратам и машинного времени и к усложнению программы. В этом случае часто используют правило, по которому выбирают первую отрицательную оценку .
25
ШАГ 3. ПЕРЕХОД К НОВОМУ РЕШЕНИЮ.
Переход к новому решению связан с заменой одних базисных переменных на другие. В симплекс-методе такая замена выглядит следующим образом:
|
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
NБ CБ XБ |
4 |
5 |
0 |
0 |
0 |
1. Новой базисной переменной становится |
|||||||
|
|
|
|
|
|
|
|
||||||
3 |
0 |
24 |
4 |
6 |
1 |
0 |
0 |
переменная x j0 |
,соответствующая |
выбранной |
|||
отрицательной |
оценке |
j0 (столбец |
отмечен |
||||||||||
|
|
|
|
|
|
|
|
||||||
4 |
0 |
12 |
3 |
2 |
0 |
1 |
0 |
стрелкой). В примере этого переменная x1 . |
|||||
|
|
|
|
|
|
|
|
2. Из базисных переменных исключается та |
5 |
0 |
|
|
8 |
1 |
|
1 |
|
0 |
|
0 |
1 |
|
|
xi0 , |
которая |
соответствует |
строке, |
где |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
определялась величина θ |
(строчка отмечена |
|||||||||||
|
|
|
|
|
0 |
-4 |
|
-5 |
|
0 |
|
0 |
0 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
стрелкой). В примере это переменная x4 . |
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
5 |
|
||
|
Поэтому |
новую |
|
симплекс-таблицу |
|
|
NБ |
CБ |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
4 |
5 |
|
0 |
|
0 |
|
0 |
|
||||||||||||||||
|
начинают заполнять с того, что в |
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
столбцах NБ и CБ заменяют номер i0 |
на |
3 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
номер |
j0 |
и элемент |
ci |
на |
cj . |
(В |
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
примере номер 4 заменяют на номер 1 и |
1 |
4 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
c4 |
= 0 |
|
заменяют |
в |
|
столбце |
CБ |
на |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
c1 |
= 4 ). |
|
Далее |
|
|
сохраняют |
5 |
0 |
|
|
|
|
|
|
|
|
|
|
|
коэффициенты целевой функции в строке С (как не изменяющиеся исходные данные). Оставшуюся (выделенную) часть “старой” симплекс-
таблицы пересчитывают по методу полного исключения Гаусса-Жордана с ведущим элементом, стоящим на пересечении отмеченной строки (ведущая строка) и отмеченного столбца (ведущий столбец).
Пересчет по методу Гаусса-Жордана подразумевает выполнение следующих действий. 1. Ведущая строка делится на ведущий элемент
1 |
2 |
3 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
NБ CБ XБ |
4 |
5 |
0 |
0 |
0 |
NБ CБ XБ |
|
|
|
|
|
3 |
0 |
24 |
4 |
6 |
1 |
0 |
0 |
|
3 |
0 |
|
0 |
|
|
|
|
|
1 |
4 |
12 |
3 |
2 |
0 |
1 |
0 |
1 |
1 |
4 |
4 |
1 |
2/3 |
0 |
1/3 |
0 |
|
3 |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
5 |
0 |
8 |
1 |
1 |
0 |
0 |
1 |
|
5 |
0 |
|
0 |
|
|
|
|
|
|
|
0 |
-4 |
-5 |
0 |
0 |
0 |
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
26 |
|
|
Оставшиеся элементы ведущего столбца заполняются нулями. |
|||||||||||
2. Остальные элементы пересчитываются по формуле “прямоугольника” |
|||||||||||
|
|
a* |
= a |
|
− |
aij |
ai |
j |
|
||
|
|
ij |
0 |
|
|
0 |
|
|
|||
|
|
ij |
|
|
ai |
|
|
|
|
||
|
|
|
|
|
|
j |
0 |
|
|
||
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Строка ( i ) |
a |
ij |
|
|
|
|
|
|
|
|
aij |
|
|
|
|
|
|
|
|
|
|
|
0 |
|
Ведущая |
|
|
|
1 умножить |
|
|
|
|
|||
строка ( i0 ) |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
2 разделить |
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Ведущий |
|
|
|
|
|
|
|
|
|
|
|
элемент |
ai |
|
|
|
3 вычесть |
|
|
ai |
|
|||
j |
|
|
|
|
|
|
|
j |
|||
|
0 |
|
|
|
|
|
|
|
|
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Ведущий |
|
|
Столбец ( j ) |
|
|
|
|
|
столбец ( j0 ) |
Здесь а* - элемент новой симплекс-таблицы, а - элемент “старой” симплекс-таблицы.
(Номера строк и столбцов берутся по оставшейся части таблицы ).
Формулу “ прямоугольника” легко запомнить, пользуясь приведенным рисунком. “Для
того, чтобы определить элемент aij* новой симплекс-таблицы, необходимо взять элемент aij в старой таблице, найти ведущий элемент и построить (мысленно) прямоугольник, как указано на рис.. Затем вычесть из aij произведение элементов противоположной диагонали прямоугольника (ai0 j aij0 ), деленное на ведущий элемент (ai0 j0 )”.
Пересчитаем элементы первой строки в оставшейся части таблицы.
27
1 |
|
Для ускорения счета |
|
||
24 |
4 |
6 |
1 |
0 |
0 |
12 |
3 |
2 |
0 |
1 |
0 |
8 |
1 |
1 |
0 |
0 |
1 |
0 |
-4 |
-5 |
0 |
0 |
0 |
|
|
24 − |
12 4 |
= 6 |
|
2 |
|
|
3 |
|
|
24 |
4 |
6 |
1 |
0 |
0 |
12 |
3 |
2 |
0 |
1 |
0 |
8 |
1 |
1 |
0 |
0 |
1 |
0 |
-4 |
-5 |
0 |
0 |
0 |
|
|
|
|
1 |
2 |
3 |
4 |
5 |
|
NБ CБ |
|
XБ |
|
|
|
|
|
|
|
|
4 |
5 |
0 |
0 |
0 |
|
|||
3 |
0 |
8 |
|
|
|
-4/3 |
|
|
|
0 |
10/3 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
1 |
4 |
4 |
1 |
2/3 |
0 |
1/3 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
5 |
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
24 |
4 |
6 |
1 |
0 |
0 |
12 |
3 |
2 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
8 |
|
1 |
|
1 |
0 |
|
0 |
|
1 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
0 |
|
-4 |
|
-5 |
0 |
|
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
4 2 |
|
|
|
0 − |
4 1 |
= − |
4 |
|
|
|
|
|||
|
10 |
|
|
|
|
|
|
можно |
|
||||||
6− |
|
3 |
|
3 |
|
|
|||||||||
|
|
= |
|
пользоваться |
двумя |
|
|
|
|
|
приемами. |
|
|
||
|
3 |
3 |
|
|
|
|
|
|
|
||||||
1. Если |
в |
ведущей строке есть нулевые |
|
|
|
|
1 |
2 |
3 |
4 |
5 |
||||
элементы, то соответствующие им столбцы |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
||||||
переносятся в новую таблицу без изменений. |
NБ CБ XБ |
4 |
5 |
0 |
0 |
0 |
2.Если в ведущем столбце (старой
|
таблицы) |
есть |
|
нулевые |
|
элементы, |
то |
3 |
|
0 |
8 |
0 |
|
|
10/3 |
1 |
-4/3 |
|
0 |
|
|||||||||||||||
|
соответствующие им строки переносятся в новую |
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
таблицу без изменений. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
1 |
|
4 |
4 |
1 |
|
|
|
|
2/3 |
0 |
1/3 |
|
0 |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
Воспользовавшись |
первым |
из |
этих |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
правил, перенесем без изменений в новую |
|
5 |
|
0 |
4 |
|
|
0 |
|
|
|
|
1/3 |
0 |
-1/3 |
|
1 |
|
||||||||||||||||
|
таблицу |
|
|
старые |
|
|
|
столбцы, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
соответствующие 3-й и 5-й переменным. |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
0 |
|
||||||||||||||
|
После пересчета 1-й строки новая таблица |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
примет вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
24 |
|
4 |
|
6 |
|
1 |
|
0 |
|
0 |
|
|
|
0 − |
1 1 |
= − |
1 |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналогично |
|
|
3 |
|
3 |
|
|
пересчитываются |
||||||||||||||
12 |
|
3 |
|
2 |
|
0 |
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
элементы |
|
|
|
|
|
|
|
|
|
|
|
|
|
третьей строки. |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
1− |
1 2 |
= |
1 |
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
8 |
|
1 |
|
1 |
|
0 |
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
3 |
|
3 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
-4 |
|
-5 |
|
0 |
|
0 |
|
0 |
|
И, |
|
наконец, |
|
8 − |
1 12 |
|
элементы последней |
||||||||||||||||
|
|
|
|
|
|
|
|
|
3 |
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
28
строки (значение целевой функции и оценки):
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
NБ CБ |
|
XБ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
5 |
0 |
0 |
0 |
|
|||
24 |
4 |
6 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
0 |
8 |
0 |
|
1 |
|
0 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
3 |
2 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
4 |
4 |
1 |
|
0 |
|
0 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
5 |
0 |
4 |
0 |
|
0 |
|
1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
-4 |
-5 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
0 |
-7/3 |
0 |
4/3 |
0 |
|
1− |
1 2 |
= |
1 |
|
|
|
|
3 |
|
3 |
|
1 12 |
|
|
|
|
8 |
− |
= 4 |
|
|
|
|
|
|
3 |
|
0 − |
1 1 |
= − |
1 |
|
3 |
|
3 |
Пересчет закончен. Построена новая симплекс-таблица, отвечающая новому базисному решению (или новой вершине множества решений). На этом ШАГ 3, а вместе с ним и полная итерация симплекс-метода завершается.
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|||
NБ CБ XБ |
|
|
|
|
|
|
|
|
|
|
|
||||
4 |
5 |
0 |
0 |
0 |
|
|
C |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
0 |
8 |
|
|
|
|
|
1 |
|
-4/3 |
|
|
|
|
|
|
0 |
10/3 |
|
0 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
4 |
4 |
|
1 |
2/3 |
0 |
|
1/3 |
0 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
0 |
4 |
|
0 |
1/3 |
0 |
-1/3 |
1 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
-7/3 |
0 |
4/3 |
0 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f
Вполученном новом текущем решении базисными неизвестными являются неизвестные
x3 , x1 и x5 (столбец NБ), их значения равны 8, 4, 4 соответственно (столбец ХБ).
Значение целевой функции на этом решении равно 16. Переходим к следующей итерации симплекс-метода, т.е. возвращаемся на ШАГ 1.
ШАГ 1. Анализ строки |
оценок |
показывает, |
что текущее решение не является |
|
оптимальным (оценка |
2 |
= −7 / 3 < 0). |
|
|
ШАГ 2. Так как отрицательная оценка одна ( 2 < 0 |
), ее и выбираем для определения |
направления (значит, в число базисных будем вводить переменную x2 ). Находим θ :