Симплекс-метод. Базисные и свободные переменные. Идея симплексметода. Построение первого допустимого базисного решения (метод искусственного базиса, М-метод, двухшаговый симплекс-метод, двойственный симплекс-метод).

Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. (Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна.) Если новая целевая функция равна нулю, переходим ко второму этапу.Этап 2. Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.Пример 2.2-3Этап 1.Минимизировать r = R1 + R2При наличии ограничений: 3x1 + x2 + R1 = 3,4x1 + 3x2 – x3 + R2 = 6,x1 + 2x2 + x4 = 4,x1, x2, x3, x4, R1, R2, >= 0.Соответствующая таблица имеет следующий вид.Базисx1x2x3R1R2x4Решениеr000-1-100R13101003R243-10106x41200014Как и в М-методе, сначала вычисляется новая r-строка.Старая r-строка: (0 0 0 -1 -1 0 | 0)+ 1 * R1-строка: (3 1 0 1 0 0 | 3)+ 1 * R2-строка: (4 3 -1 0 1 0 | 6)= Новая r-строка: (7 4 -1 0 0 0 | 9)Новая строкаr + 7x1 + 4x2 – x3 + 0R1 + 0R2 + 0x4 = 9используется для решения первого этапа, что приведёт к следующему оптимальному решению (проверьте!).Базисx1x2x3R1R2x4Решениеr000-1-100x1101/53/5-1/503/5x201-3/5-4/53/506/5x40011-111Поскольку достигнут минимум r = 0, значит, на первом этапе получено допустимое базисное решение x1 = 3/5, x2 = 6/5 и x4 = 1. Искусственные переменные полностью выполнили свою «миссию», поэтому из последней таблицы можно удалить их столбцы. Переходим ко второму этапу.Этап 2После удаления искусственных переменных исходная задача будет записана следующим образом:Минимизировать z = 4x1 + x2с ограничениями x1 + 1/5 x3 = 3/5,x2 + 3/5 x3 = 6/5,x3 + x4 = 1,x1, x2, x3, x4 >= 0.После первого этапа над исходной задачей были проведены некоторые изменения, учитывающие полученное базисное решение. Данной трансформированной задаче соответствует следующая таблица:Базисx1x2x3x4Решениеz-4-1000x1101/503/5x201-3/506/5x400111Так как базисные переменные x1и x2 имеют ненулевые коэффициенты в z-строке, эту строку следует преобразовать. Старая z-строка: (-4 -100 | 0)+ 4 * x1-строка: (4 0 4/5 0 | 12/5) + 1 * x2-строка: (0 1 -3/5 0 | 6/5) = Новая z-строка: (0 0 1/5 0 | 18/5)Начальная таблица второго этапа примет следующий вид:Базисx1x2x3x4Решениеz001/5018/5x1101/503/5x201-3/506/5x400111Так как решается задача минимизации, следует ввести переменную x3 в базис. Применение алгоритма симплекс-метода уже на следующей итерации приведёт к оптимальному решению (проверьте!).Удаление искусственных переменных в конце первого этапа имеет смысл только тогда, когда все они являются небазисными (как в примере 2.2-4). Однако возможна ситуация, когда в конце первого этапа искусственные переменные останутся в базисе, но будут иметь нулевые значения. В этом случае такие переменные при необходимости будут формировать часть начального базисного решения для второго этапа. При этом необходимо так изменить вычисления, выполняемые на втором этапе, чтобы искусственные переменные никогда не смогли принять положительные значения ни в каких итерациях симплекс-метода.Существует простое правило, которое гарантирует, что нулевая базисная искусственная переменная на втором этапе никогда не станет положительной. Если в ведущем столбце коэффициент, соответствующий нулевой базисной искусственной переменной, положителен, тогда ведущий элемент определяется автоматически (поскольку ему соответствует минимальное отношение, равное нулю) и искусственная переменная на следующей итерации становится небазисной. Если ведущий элемент равен нулю, следующая итерация оставляет искусственную переменную нулевой. Далее рассмотрим отрицательный ведущий элемент. В данном случае минимальное отношение не ассоциируется с базисной (нулевой) искусственной переменной. Если минимальное отношение будет положительным, то на следующей итерации искусственная переменная примет положительное значение (обоснуйте это утверждение). Чтобы исключить эту возможность, мы принуждаем искусственную переменную всегда оставаться в базисном решении. Поскольку искусственная переменная равна нулю, её удаление из базисного решения не влияет на то, будет ли допустимым решение из оставшихся в базисе переменных. (Было бы полезно для читателя рассмотреть все описанные случаи с помощью симплекс-таблиц) [8, c.90].Таким образом, правило для второго этапа заключается в том, чтобы искусственные переменные оставлять в базисе всегда, когда коэффициент в ведущем столбце положительный или отрицательный. Фактически это правило используется в конце первого этапа, когда проводится удаление нулевых искусственных переменных из базисного решения, перед тем как приступить ко второму этапу[7, c.47].ЗаключениеВ рамках данной работы проведено описание симплекс-метода решения задач линейного программирования. показано, что область использования задач указанного класса связана с поиском решения в указанной области ограничения, приводящего к получению экстремума для целевой функции. Предметные области оптимизационных задач, как правило, связаны с рациональным распределением ограниченных ресурсов для получения наибольшей прибыли, используются в областях экономического планирования, логистики и др.Решение задач указанного может проводиться как аналитическим путем с использованием симплекс-Метода, так и с использованием программных средств, в которых проводятся вычисления с использованием библиотек и подпрограмм с реализованным симплекс-методом.В ходе изучение алгоритмов решения задач линейного программирования было установлено, что применение данных моделей к реальным условиям является затруднительным в силу невозможности четкого определения параметров ограничений, прибыльности и затрат при реализации проекта в реальных условиях. Так как при реализации проектов возможно изменение цен на выполнение работ, перевозок. Возможны форс-мажорные обстоятельства. Иногда доставка по более длинному пути является более предпочтительным вариантом из-за специфики транспортных узлов. таким образом, решение задач с помощью симплекс-методов являются лишь приближением к реальности и практическое их использование возможно в условиях предсказуемости поведения системы и минимизации рисков внешних воздействий.Список использованных источниковДубинин, Д. В. Информатика. Численные методы: учебное пособие / Д. В. Дубинин. - Томск: Изд-во ТУСУРа, 2017. - 116 с.Горбачев, М. В., Макаров М. С. Вычислительная математика. Численные методы: учебно-методическое пособие / М. В. Горбачев, М. С. Макаров. - Новосибирск: Изд-во НГТУ, 2018. – 60с.Елизарова, Н. Н. Математические методы принятия решений. Методы оптимизации: учебное пособие / Н. Н. Елизарова. - Иваново: Ивановский государственный энергетический университет имени В. И. Ленина, 2018. - 187 с. Сафарьян, О. А. Численные методы в задачах математического моделирования и исследования математических моделей объектов: учебно-методическое пособие / О. А. Сафарьян. - Ростов-на-Дону: ДГТУ, 2019. - 84 с.Башмакова, М. Г. Численные методы линейной и нелинейной алгебры: учебно-методическое пособие / М. Г. Башмакова; Министерство образования и науки Российской Федерации. - Брянск: Изд-во БГТУ, 2016. - 128 с.Воронов, М.В. Численные методы решения уравнений и их систем: учебно-методический комплекс по дисциплине: учебное пособие / М. В. Воронова. - Абакан: Изд-во ФГБОУ ВПО "Хакасский государственный университет им. Н. Ф. Катанова", 2014. - 54 с.Галканов, А. Г. Симплекс метод в понятиях, задачах и решениях / А. Галканов, Я. Какалыев. - Москва: Новое время, 2014. - 117 с.Сеисов, Ю. Б.Вырожденные режимы линейного программирования / Ю. Б. Сеисов, Х. А. Гелдиев, А. Т. Аманов, Е. Курамбаев. - Москва: Спутник+, 2015. - 102 с.Заботин, И.Я., Заботин Я.И. Методы и вычислительные приемы в линейном программировании/ И. Я. Заботин, Я. И. Заботин. - Казань : Казанский университет, 2014. - 115 с.Болотникова, О. В.Линейное программирование: симплекс-метод и двойственность: учебное пособие / О. В. Болотникова, Д. В. Тарасов, Р. В. Тарасов. - Пенза: Изд-во ПГУ, 2015. – 82 с.