Cтраница 2
Для полноты нужно описать построение начального допустимого базисного решения. [16]
Отметим, что из лексикографической неотрицательности вектора коэффициентов полинома следует неотрицательность самого полинома при достаточно малых значениях аргумента. Таким образом, метод последовательных улучшений выглядит теперь так: начальное допустимое базисное решение должно быть выбрано таким образом, чтобы все переменные были строго лексикографически положительны. Если мы начинаем с единичной матрицы и неотрицательных значений базисных переменных, то это условие выполняется автоматически. [17]
Метод искусственного базиса достаточно прост и универсален. Однако не следует пренебрегать особенностями конкретных задач, позволяющими получить более качественное начальное допустимое базисное решение. [18]
Из доказанной теоремы следует, что в результате решения вспомогательной задачи (3.32) либо будет определено решение задачи (3.31), либо выяснится, что система ограничений задачи (3.31) противоречива, т.е. множество допустимых решений задачи пусто. Основным свойством задачи (3.32) является то, что для нее можно сразу определить начальное допустимое базисное решение. Нетрудно убедиться, что ( и, 0) - строго допустимый план. [19]
Мы рассмотрим один шаг улучшений, который может повторяться многократно. Однако должно быть какое-то допустимое базисное решение, с которого можно было бы начать - начальное допустимое базисное решение. [20]
В задачах линейного программирования, где все ограничения являются неравенствами типа ( с неотрицательной правой частью), дополнительные ( остаточные) переменные позволяют сформировать начальное допустимое базисное решение. [21]
Двухэтапный метод лишен недостатков, которые присущи М - методу вследствие ошибок округления. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведется поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача. [22]