Линейная алгебра. Линейное программирование. Тарбокова Т.В. - 102 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

102
При этом надо следить за тем, чтобы новые свободные члены уравне-
ний оставались неотрицательными.
Теорема (опти-
мальности реше-
ния)
Допустимое базисное решение является оп-
тимальным, в том и только в том случае, когда
среди коэффициентов индексной строки нет по-
ложительных в задаче на максимум (нет отри-
цательных в задаче на минимум).
Если коэффициенты индексной строки имеют разные знаки, то соот-
ветствующее допустимое базисное решение не является оптимальным как
в задаче не максимум, так и в задаче на минимум, и, следовательно, требу-
ется переходить к другому допустимому базисному решению (плану).
Очередное допустимое базисное решение (план) получается тем же
способом, но с учетом некоторых особенностей. Ограничимся случаем за-
дачи на максимум, поскольку задача на минимум решается по аналогич-
ному алгоритму.
1) Разрешающий столбец надо выбирать так, чтобы не приобре-
тать лишних положительных коэффициентов в индексной строке (хотя это
иногда неизбежно в силу теоремы оптимальности). Иногда в качестве раз-
решающего берут столбец максимального коэффициента индексной стро-
ки.
2) Неправильный выбор разрешающей строки может привести к
недопустимому решению. Правильный ее выбор состоит в следующем.
Предположим, что выбран разрешающий столбец. Составим отноше-
ния
iq
i
iq
a
b
=Θ
(
0
>
iq
a ,
строка
целевой
функции
здесь
не
участвует
).
Най
-
дем
минимальное
из
этих
отношений
,
которое
обозначим
{
}
iq
Θ
=
Θ
min .
Строку
с
числом
Θ
надо
считать
разрешающей
.
Если
таких
строк
несколь
-
ко
,
то
выбор
среди
них
безразличен
.
3)
Если
разрешающий
коэффициент
выбран
правильно
,
то
соот
-
ветствующие
элементарные
преобразования
приводят
только
к
допусти
-
мому
решению
.
При
необходимости
процедура
нахождения
допустимого
базисного
реше
-
ния
повторяется
до
получения
оптимального
решения
,
если
оно
существу
-
ет
.

Страницы