Задачи линейного программирования

Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицыметодом Жордана-Гаусса.Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение. Если последняя строка (значения целевой функции) не содержит отрицательных элементов, следовательно, найдет оптимальный план.[1, 4, 5]3.3 Двойственный симплексный метод задачи линейного программированияДвойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых bi могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».Алгоритм двойственного симплекс-метода включает следующие этапы:Составление псевдоплана. Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».1.1. выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов; 1.2. выбирают разрешающий столбец по наименьшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки;1.3. пересчитывают симплексную таблицу по правилам обычного симплекс-метода;Проверка плана на оптимальность. Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом.Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов.Выбор ведущих строки и столбца. Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.Расчет нового опорного плана. Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса. Далее переход к этапу 2.Замечания:Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима. Если ограничения задачи заданы неравенствами типа «≥», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных.[1, 4, 5]ЗаключениеВ рамках данной работы были рассмотрены и изучены следующие вопросы:сформулирована общая постановка задачи линейного программирования;приведена математическая модель задачи линейного программирования;приведена каноническая форма задачи линейного программирования;перечислены основные методы решения задачи линейного программирования: графический метод, симплекс-метод, двойственный симплекс-метод.Несмотря набольшое многообразие содержания конкретных задач, относящихся к области линейного программирования,можно выделить алгоритм (основные этапы) решения таких задач:Постановка задачи в общем виде.Составлениематематической модели.Выбор метода решения задачи по составленной математической модели.Решение задачи выбранным методом.Анализ полученного решения на его адекватность изучаемому процессу (явлению, объекту) ив случае необходимости корректировка построенной математической модели.Использование найденного решения задачи на практике.Область «линейное программирование» уже достаточно хорошо изучена в настоящее время и, конечно же, имеет большое будущее для решения многих оптимизационных задач.Список использованных источниковВентцель Е. С. Исследование операций: задачи, принципы, методология. / Е.С. Вентцель. – М.: Наука, 1988. – 206 с.Виды задач линейного программирования. [Электронный ресурс]. URL: http://function-x.ru/zadacha_lineinogo_programmirovanija.html (дата обращения: 20.03.2017).Задачи линейного программирования. [Электронный ресурс]. URL: http://matica.org.ua/primery/primery/zadachi-lineinogo-programmirovaniia (дата обращения: 20.03.2017).Мунасыпов Н. А.Линейное программирование. – Оренбург: ООО «Агентство «Пресса», 2015. – 122 с.Палий И. А.Линейное программирование, учебное пособие / И. А. Палий. – М.: Эксмо, 2008. – 256 с.