Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
мого начала, необходимо дополнительные данные записать в оптимальную таблицу. Новая исходная матрица коэффициентов A = A P, чтобы привести ее к виду оптимальной таблицы, необходимо умножить ее на В-1. Таким образом, в оптимальной таблице добавляется еще один столбец Р* = В-1Р. При этом свободные члены не изменяются. Осталось записать коэффициент целевой функции, это можно сделать с помощью симплекс - множителей. Умножим коэффициенты Р на соответствующие симплекс - множители и прибавим к коэффициенту целевой функции в стандартном виде:
Cn+1 + = Cn+1*.
Если Cn+1*, то хn+1 останется свободной ( то есть равной нулю), так как сохранится признак оптимальности. Следовательно, план менять не стоит.
Если Cn+1* < 0, то следует улучшить решение, а именно хn+1 ввести в базисные переменные. Следовательно, план изменится. При этом решение продолжается обычным симплекс-методом.
Пример.
5. Включение дополнительных ограничений
Экономическая ситуация, в которой приходится решать производственные и плановые задачи, изменяется. Может оказаться так, что некоторый ресурс, считавшийся ранее неограниченным, окажется лимитирован. Например, введение веерного распределения электроэнергии т.п. Другими словами, необходимо проверить. Удовлетворяет ли рассчитанный план новым ограничениям, и как его изменить, если ограничения нарушаются.
Итак, пусть - новое дополнительное ограничение к уже решенной задаче. То есть х* уже найдено.
Если найденное х* = (х1, х2, … , хn) удовлетворяет поставленному дополнительному ограничению, то план никак не изменится (ограничение не ограничивает данное производство).
Если х* = (х1, х2, … , хn) не удовлетворяет новому ограничению, то необходимо изменить план, то есть продолжить решение.
Чтобы продолжить решение. Необходимо учесть новое ограничение, записав его в каноническом виде, соответствующем оптимальной таблице: дополнительное ограничение должно содержать одну переменную с коэффициентом 1, и чтобы в других уравнениях и выражении целевой функции она отсутствовала, кроме того, это уравнение не должно содержать базисных переменных оптимальной таблицы. Чтобы исключить базисные переменные оптимальной таблицы, используют оптимальный канонический вид. При этом решение продолжается двойственным симплекс-методом.
Пример.
6. Двойственный симплекс-метод
Для решения задачи двойственным симплекс-методом она должна иметь недопустимый канонический вид. И признак оптимальности должен выполняться.
Общая идея: начиная с недопустимого базисного решения при выполнении признака оптимальности, последовательно перейти к допустимому базисному решению, сохранив признак оптимальности.
Правила.
.Недопустимый канонический вид ограничений и оптимальный вид (Сj ) целевой функции записывают в исходную таблицу.
.Среди отрицательных свободных членов выбирают , соответствующую строку помечают * и называют разрешающей.
.Среди всех отношений коэффициентов целевой функции к отрицательным элементам разрешающей строки выбирают , соответствующий столбец помечают, выполняют обычные симплекс-преобразования и называют разрешающим.
Замечание: 1. Обычный симплекс-метод при сохранении допустимости решения переходит последовательно к оптимальному решению. А двойственный симплекс-метод при сохранении оптимальности переходит последовательно от недопустимого решения к допустимому.
. Правила двойственного симплекс-метода отличаются от правил обычного выбором разрешающих столбца и строки.
. Если в разрешающей строке (для двойственного метода) нет ни одного отрицательного элемента, то задача не разрешима.
7. Проблемы вырождения, зацикливания
Как правило, все базисные переменные отличны от нуля (то есть в симплекс-таблице все свободные члены ). Однако, нет никаких ограничений к тому, чтобы одна или несколько базисных переменных обратились в ноль.
Базисное решение (базис) является невырожденным, если оно содержит ровно m отличных от нуля компонент. В противном случае - вырожденным.
Если начальный план задачи невырожден, то никаких сложностей при решении не возникает, при правильном выборе разрешающего элемента. Если хотя бы одна базисная переменная в НДБР приняла нулевое значение, то по правилам симплекс-метода именно она должна будет войти в базис на следующем шаге, так как min bi/aij* = 0. При этом значение целевой функции не изменится.
Лекция 6.
Двойственность в линейном программировании
Вопросы:
1.Понятия двойственности, теневой цены, двойственной оценки.
2.Правила построения двойственной задачи.
.Основные теоремы двойственности и их экономическое содержание.
1.Понятия двойственности, теневой цены, двойственной задачи
Двойственность является одним из фундаментальных понятий в линейном программировании, приводящим к важному результату теоретического и практического характера. Рассмотрим понятие двойственности на примере задачи оптимального использования ресурсов.
На производство n видов продукции предприятие затрачивает m видов ресурсов, имеющихся в ограниченных количествах b = (b1, b2, …, bm). На производство единицы j-го вида продукции требуется aij единиц i-го вида ресурса. Прибыль от реализации единицы продукции Сj, j = . Необходимо определить такой план производства х = (х1, х2,…, хn), при котором прибыль предприятия была ?/p>