Симплекс-метод (М-метод) - программа для решения задач линейного программирования симплекс-методом с искусственным базисом. Утилита сама приводит задачу к каноническому виду, и производит ее итеративное решение с помощью пересчета симплекс-таблицы. Выводится подробный отчет о ходе решения задачи.
Имеется три режима решения задач:
- Автоматический. Программа сама выбирает разрешающий столбец и строку, которые обеспечивают максимальное возрастание или уменьшение целевой функции. А также автоматически пересчитывает все таблицы.
- Пошаговый. Каждая пересчитанная таблица выводится на экран. Этот режим удобен для просмотра промежуточных результатов решения задачи. Разрешающий столбец и строку, в данном режиме, программа также выбирает сама.
- Ручной. Пользователь сам выбирает разрешающую строку и столбец.
Также есть возможность экспорта всех таблиц, полученных в ходе решения задачи, в Excel.
Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности. В работе Л. Исторически общая задача линейного программирования была впервые поставлена в году Джорджем Бернардом Данцигом , Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве.
Лекция 3 Метод искусственного базиса:
Трудности, которые возникали при выделении допустимого базиса симплекс-методом, они явились толчком к разработке модификации симплекс-метода называемого м-методом, его называют методом искусственного базиса. Затем составляем расширенную матрицу. Если при решении М-задачи симплекс-методом, получается симплекс-таблица, дающая оптимальное решение, причем в этой таблице все искусственные элементы являются свободными, то отбросив столбцы для этих переменных, получим симплекс-таблицу, дающую оптимальное решение исходной задачи. Решая М-задачу мы стремимся получить оптимальное решение, в котором значение исходных неизвестных равны 0. Для того чтобы этого достичь, необходимо выбрать последовательность шагов таким образом, чтобы все искусственные неизвестные вышли из базиса, то есть стали свободными, тогда в базисном решении значения этих неизвестных будут нулями, т. Возможны и такие случаи, когда в процессе решения приходиться заменять одно искусственное неизвестное на другое, так как выбор разрешающего элемента по другому не получается, но общим направлением вычислительного процесса во всех случаях остается постепенный вывод искусственных переменных из базиса. Дата публикования: ; Прочитано: Нарушение авторского права страницы. Главная Случайная страница Контакты.
Транспортная задача (Симплекс метод):
Записать матрицу функциональных ограничений так, чтобы в её составе была единичная матрица. При этом получаем допустимое решение. Оптимальное решение то же. Эта задача модель линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x 3 и x 4 :. Запишем матрицу коэффициентов функциональных ограничений. КЗЛП имеет необходимое число единичных столбцов, то есть обладает очевидным начальным опорным планом 0,0,,
Метод искусственного базиса (Основная часть):
Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод или симплекс-метод , разработанный американским ученым Дж. Данцигом около 50 лет назад. Суть этого метода заключается в том, что:. Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный. Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом или М-метод. Решение ведется в симплекс-таблицах:.
Рекомендуем ознакомиться: