На этом шаге мы рассмотрим понятие искусственного начального решения.
В примере с компанией "Русские краски" при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа "≤" (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение.
Естественно, возникает вопрос: как найти начальное допустимое базисное решение в задачах линейного программирования, где есть ограничения в виде равенств или неравенств типа "≥"?
Наиболее общим способом построения начального допустимого базисного решения задачи линейного программирования является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод и двухэтапный метод.
На следующем шаге рассмотрим М-метод решения задач линейного программирования.
