Решение канонической задачи линейного программирования

Скачать файл - Решение канонической задачи линейного программирования

Если целевая функция и система ограничений линейны , то задача математического программирования называется задачей линейного программирования ЗЛП. Любая задача линейного программирования приводится к стандартной канонической форме основной задачи линейного программирования, которая формулируется следующим образом: При этом также требуется, чтобы правые части равенств были неотрицательны, то есть должны соблюдаться условия:. Приведение к стандартной форме необходимо, так как большинство методов решения задач линейного программирования разработано именно для стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия:. Для решения нашей задачи воспользуемся симплекс-методом, так как этот метод предназначен для решения задач линейного программирования любой размерности. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот. Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:. Приведение к канонической форме задачи линейного программирования:. Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Подставляя данное выражение в систему ограничений и целевую функцию и, записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:. Симплекс-метод и его сходимость. Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, записанную в каноническом виде. Идея симплексного метода последовательного улучшения плана, заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. Значение целевой функции при этом перемещении для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение. Опорным решением называется базисное неотрицательное решение. Алгоритм симплексного метода 1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу 1. Все строки таблицы 1-го шага заполняем по данным системы ограничений и целевой функции. Если хотя бы один коэффициент последней строки отрицателен, а при соответствующей переменной есть хотя бы одно положительное оценочное отношение , то нужно перейти к другому опорному решению. Е сли отрицательных коэффициентов в последней строке несколько, то в столбец базисной переменной БП вводят ту переменную , которой соответствует наибольший по абсолютной величине отрицательный коэффициент. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k — того столбца. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом. Вырожденность в задачах ЛП. Важнейшим свойством любого вычислительного, алгоритма является сходимость, т. FAQ Обратная связь Вопросы и предложения. Upload Опубликованный материал нарушает ваши авторские права? Приведение общей задачи лп к симметричной форме записи. Критерий оптимальности для транспортной задачи. Функциональное уравнение динамического программирования на примерах. Особенности применения динамического программирования. Оптимизация и математические методы принятия решений Теория: Основная форма ЗЛП Симметричная форма ЗЛП Общая задача линейного программирования Любая задача линейного программирования приводится к стандартной канонической форме основной задачи линейного программирования, которая формулируется следующим образом: Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия: Правило приведения задачи линейного программирования к каноническому виду состоит в следующем: Приведение к канонической форме задачи линейного программирования: Подставляя данное выражение в систему ограничений и целевую функцию и, записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме: Возможны следующие случаи при решении задач на максимум: Заполняем симплексную таблицу 2: Если нет, то заполняем симплексную таблицу 8-го шага и так далее.