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

 

 

 

 

 

 

 

 

Симплексный метод

Данный метод является методом целенаправленного перебора опорных решений задачи линейного  программирования. Он позволяет за конечное число шагов либо найти  оптимальное решение, либо установить, что оптимальное решение отсутствует.

Основное  содержание симплексного метода заключается  в следующем:

1. Указать способ нахождения оптимального опорного решения
2. Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения
3. Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения.

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

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:

1. Привести задачу к каноническому виду
2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения  задачи симплексным методом

Пример 26.1

Решить симплексным методом  задачу:

Решение:

Приводим задачу к каноническому  виду.

Для этого в левую часть  первого ограничения-неравенства  вводим дополнительную переменную x₆ с коэффициентом +1. В целевую функцию переменная x₆ входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное  решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δ_k = C_бX_k — c_k

Где:

• C_б = (с₁, с₂, ... , с_m ) — вектор коэффициентов целевой функции при базисных переменных
• X_k = (x_1k, x_2k, ... , x_mk ) — вектор разложения соответствующего вектора А_к по базису опорного решения
• С_к — коэффициент целевой функции при переменной х_к.

Оценки векторов входящих в базис всегда равны нулю. Опорное  решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу:

Сверху над таблицей для  удобства вычислений оценок записываются коэффициенты целевой функции. В  первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных  неизвестных в уравнениях ограничениях. Во втором столбце таблицы "С_б" записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "С_б" оценки единичных векторов, входящих в базис, всегда равных нулю.

В последней строке таблицы  с оценками Δ_k в столбце "А₀" записываются значения целевой функции на опорном решении Z(X₁).

Начальное опорное решение  не является оптимальным, так как  в задаче на максимум оценки Δ₁ = -2, Δ₃= -9 для векторов А₁ и А₃ отрицательные.

По теореме об улучшении  опорного решения, если в задаче на максимум хотя бы один вектор имеет  отрицательную оценку, то можно найти  новое опорное решение, на котором  значение целевой функции будет  больше.

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции  находится по формуле: .

Вычисляем значения параметра  θ₀₁ для первого и третьего столбцов по формуле:

Получаем θ₀₁ = 6 при l = 1, θ₀₃ = 3 при l = 1 (таблица 26.1).

Находим приращение целевой  функции при введении в базис  первого вектора ΔZ₁ = — 6*(- 2) = 12, и третьего вектора ΔZ₃ = — 3*(- 9) = 27.

Следовательно, для более  быстрого приближения к оптимальному решению необходимо ввести в базис  опорного решения вектор А3 вместо первого  вектора базиса А6, так как минимум параметра θ₀₃ достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого  вычисляем параметр θ₀₂ для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х₂₂ = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ₁ = 7/2, Δ₄ = 2, Δ₆ = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

 

Метод линейного программирования в экономическом  анализе

Метод линейного  программирования дает возможность обосновать наиболее оптимальное экономическое решение в условиях жестких ограничений, относящихся к используемым в производстве ресурсам (основные фонды, материалы, трудовые ресурсы). Применение этого метода в экономическом анализе позволяет решать задачи, связанные главным образом с планированием деятельности организации. Данный метод помогает определить оптимальные величины выпуска продукции, а также направления наиболее эффективного использования имеющихся в распоряжении организации производственных ресурсов.

При помощи этого метода осуществляется решение так называемых экстремальных задач, которое заключается  в нахождении крайних значений, то есть максимума и минимума функций  переменных величин.

Этот период базируется на решении системы линейных уравнений  в тех случаях, когда анализируемые  экономические явления связаны  линейной, строго функциональной зависимостью. Метод линейного программирования используется для анализа переменных величин при наличии определенных ограничивающих факторов.

Весьма распространено решение  так называемой транспортной задачи с помощью метода линейного программирования. Содержание этой задачи заключается  в минимизации затрат, осуществляемых в связи с эксплуатацией транспортных средств в условиях имеющихся ограничений в отношении количества транспортных средств, их грузоподъемности, продолжительности времени их работы, при наличии необходимости обслуживания максимального количества заказчиков.

Кроме этого, данный метод  находит широкое применение при  решении задачи составления расписания. Эта задача состоит в таком  распределении времени функционирования персонала данной организации, которое  являлось бы наиболее приемлемым как  для членов этого персонала, так  и для клиентов организации.

Данная задача заключается  в максимизации количества обслуживаемых  клиентов в условиях ограничений  количества имеющихся членов персонала, а также фонда рабочего времени.

Таким образом, метод линейного  программирования весьма распространен  в анализе размещения и использования  различных видов ресурсов, а также  в процессе планирования и прогнозирования  деятельности организаций.

Все же математическое программирование может применяться и в отношении  тех экономических явлений, зависимость  между которыми не является линейной. Для этой цели могут быть использованы методы нелинейного, динамического  и выпуклого программирования.

Нелинейное программирование опирается на нелинейный характер целевой  функции или ограничений, либо и  того и другого. Формы целевой  функции и неравенств ограничений  в этих условиях могут быть различными.

Нелинейное программирование применяется в экономическом  анализе в частности, при установлении взаимосвязи между показателями, выражающими эффективность деятельности организации и объемом этой деятельности, структурой затрат на производство, конъюнктурой рынка, и др.

Динамическое программирование базируется на построении дерева решений. Каждый ярус этого дерева служит стадией  для определения последствий  предыдущего решения и для  устранения малоэффективных вариантов  этого решения. Таким образом, динамическое программирование имеет многошаговый, многоэтапный характер. Этот вид программирования применяется в экономическом  анализе с целью поиска оптимальных  вариантов развития организации как в настоящее время, так и в будущем.

Выпуклое программирование представляет собой разновидность  нелинейного программирования. Этот вид программирования выражает нелинейный характер зависимости между результатами деятельности организации и осуществляемыми  ей затратами. Выпуклое (иначе вогнутое) программирование анализирует выпуклые целевые функции и выпуклые системы  ограничений (точки допустимых значений). Выпуклое программирование применяется  в анализе хозяйственной деятельности с целью минимизации затрат, а  вогнутое — с целью максимизации доходов в условиях имеющихся  ограничений действия факторов, влияющих на анализируемые показатели противоположным  образом. Следовательно, при рассматриваемых  видах программирования выпуклые целевые  функции минимизируются, а вогнутые — 

 

 

 

 

 

 

 

Выбрать язык ​ ▼

Лекции Инструкции к сервису Примеры решений Заказать Поиск Симплексный метод  решения задач линейного программирования Симплекс-метод - это итеративный процесс  направленного решения системы  уравнений по шагам, который  начинается с опорного решения  и в поисках лучшего варианта  движется по угловым точкам  области допустимого решения,  улучшающих значение целевой  функции до тех пор, пока  целевая функция не достигнет  оптимального значения. Назначение сервиса   Сервис предназначен для решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи: базовой форме записи; в виде симплексной таблицы (метод жордановых преобразований); модифицированным симплекс-методом; в столбцовой форме; в строчечной форме. При решении автоматически  определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода. ИНСТРУКЦИЯ для  решения задач симплексным методом   Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле MS Word. Выберите количество переменных Выберите количество строк (количество ограничений)   При этом ограничения типа xi ≥ 0 не учитывайте. Программа автоматически рассматривает данное ограничение при решении. Если в задании для некоторых xi отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом. Алгоритм симплекс-метода включает следующие этапы: Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных. Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.

 

Симплекс-метод

[править]

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 1937 году.

Содержание   [убрать]  1 Описание 2 Алгоритм симплекс-метода 2.1 Усиленная постановка задачи 2.2 Алгоритм 3 Двухфазный симплекс-метод 3.1 Причины использования 3.2 Модификация ограничений 3.2.1 Различия между дополнительными и вспомогательными переменными 3.3 Фазы решения 4 Модифицированный симплекс-метод 5 Мультипликативный вариант симплекс-метода 6 Другие варианты симплекс-метода 7 Двойственный симплекс-метод 8 Вычислительная эффективность 9 Примечания 10 Литература 11 Ссылки

[править] Описание

Переход от одной вершины  к другой

Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем  линейном пространстве. В результате все неравенства ограничивают некоторый  многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.