Cтраница 3
Доказать, что опорный план X, степень вырожденности которого равна л, обладает не более чем т, различными базисами. [31]
Метод направленного перебора опорных планов, при котором функция цели все время уменьшается, называется симплекс-методом. [32]
Рассмотрим процедуру построения опорного плана и перехода к другому опорному плану. [33]
Идея упорядоченного перебора опорных планов лежит в основе так называемого симплекс-метода, который в отечественной литературе часто называют методом последовательного улучшения плана. [34]
Поэтому, если все опорные планы некоторой задачи линейного программирования цело-численны, то обычный аппарат линейного программирования позволяет найти оптимальный ( опорный) план, удовлетворяющий также и требованию целочисленности и являющийся, следовательно, также оптимальным планом соответствующей задачи целочисленного линейного программирования. [35]
При этом методе вычисляют опорный план и устанавливают критерий, позволяющий проверить оптимальность опорного плана. Метод предлагает способ, позволяющий по найденному неоптимальному плану получить другой, близкий к оптимальному. [36]
Приняв я1 за начальные опорный план, воз-вращаемся к этапу 1 и начинаем новую итерацию. [37]
Предположим, что известен опорный план, соответствующий m векторам Р3 - из первоначальной системы п векторов. [38]
Проверяем, является ли данный опорный план оптимальным или нет. [39]
ХФХ ( даже если опорный план X вырожден. [40]
При переходе от одного опорного плана к другому целочисленность сохраняется. [41]
Существует несколько способов получения опорного плана. Ниже рассмотрен один из них, обладающий достаточной общностью алгоритма. [42]
При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу ( т 2) - и строки. Искусственный вектор, исключенный из базиса в результате некоторой итерации, в дальнейшем не имеет смысла вводить ни в один из последующих базисов и, следовательно, преобразование столбцов этого вектора излишне. Однако если нужно найти решение двойственной задачи для данной ( о чем будет сказано в § 1.6), то такое преобразование необходимо. Может случиться так, что в результате некоторой итерации ни один из искусственных векторов из базиса не будет исключен. [43]
Рассмотрим два метода построения первого опорного плана. [44]
Переменная х2 также является опорным планом. Соответствующая, ему таблица может быть построена преобразованием старой таблицы по направляющему элементу, находящемуся на пересечении ее r - й строки и s - столбца. Процедура преобразования таблицы равносильна сложению и умножению на скаляр строк старой таблицы до тех пор, пока в r - й строке столбца s появится единица, а во всех остальных позициях этого столбца окажутся нули. [45]