Симплексный метод – метод последовательного улучшения плана.
Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.
Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений конечно, то через конечное число шагов получим оптимальное решение.
1.Математическую модель задачи привести к каноническому (стандартному) виду.
2. Построить начальную симплекс-таблицу исходя из стандартного вида.
3. Найти разрешающий столбец.
В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.
4. Вычислить разрешающую строку и ведущий элемент.
Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей. Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.
5.Построить новую симплекс-таблицу-второй шаг.
При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.
-Построение ведущей строки в новой таблице.
Почленно поделить все элементы разрешающей строки на ведущий элемент.
-Построение других строк в новой таблице.
Почленно умножить ведущую строку на соответствующие этим строкам элементы разрешающего столбца из предыдущей таблицы и прибавить к соответствующим строкам в старой таблице.
6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.
Прямая задача на минимум решается следующим образом:
-Написать математическую модель двойственной задачи в стандартном виде
-Решить двойственную модель симплекс - методом
-Записать ответ.
Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой.
Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.
2 2. Алгоритм, используемый для отыскания опорного решения задачи линейного программирования.
Универсальным методом решения задач линейного программирования является симплекс-метод, который состоит из алгоритма отыскания какого-нибудь опорного среди решений системы и алгоритма последовательного перехода от полученного уже опорного решения к некоему новому. Этот процесс продолжается до получения оптимального решения.
Рассмотрим симплекс метод:
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки, осуществляется последовательный переход к другой точке (смежной). Выбор каждой последующей точки определяется правилами:
1. каждая последующая угловая точка должна быть смежной предыдущей.
2. Обратный переход к предшествующей точке производиться не может (иначе зацикливание).
Смежные угловые точки отличаются только одной переменной в каждой группе переменных. Эти группы переменных соответственно называются БАЗИСНЫМИ и СВОБОДНЫМИ.
Симплекс-метод требует приведения задачи к стандартному виду, в котором нет ограничений в виде неравенств (все ограничения имеют вид равенств).
Основная Задача Линейного Программирования (ОЗЛП): Z=CX
AX=B
X≥0
!!! В стандартной постановке все bi≥0. К такому виду следует приводить (домножить на -1)
!!! Приведение ограничения к форме равенства достигается путем введения в выражение такого ограничения дополнительной переменной: она прибавляется к левой части, если был знак ≤, и вычитается из левой части, если был знак ≥.
Когда выполняются условия Z=CX, AX=B, X≥0 и bi≥0, то задача задана в канонической форме.
Все условия системы для симплекс-метода надо записать в виде одного уравнения:
Приравниваем уравнения к нулю:
Z = CX => CX-Z0 = 0; AX = B => AX-B = 0, т.е.
| C | Z | * | X | = 0 |
| A | B | -1 |
Матрицу А преобразовать так, чтобы получить единичную матрицу (I):
┌ ┐┌ ┐
│ I ^B ││ X │= 0 I X = ^B
│ ││ -1 │
└ ┘└ ┘C – тоже преобразуется в ^C и ¯C
┌ ┐┌ ┐
│ ^C ¯C ^Z0 ││ X │= 0,
│ I ¯А ^B ││ -1 │
└ ┘└ ┘то есть векторы С и А разбились каждый на два:
(^C+¯C) X - ^Z0 = 0
(I+¯A) X - ^B = 0
Переменные, входящие в уравнения:
^C Х - ^Z0 = 0
I Х - ^B = 0
являются базисными, остальные – свободными. Если в результате построения мы получили все В≥0, то текущее решение является ДОПУСТИМЫМ. Теперь надо определить, нашли ли мы ОПТИМАЛЬНОЕ РЕШЕНИЕ. Если решается задача на min, то оптимум – при всех С≥0, если на max, то при С≤0. Если оптимум не найден, то нужно найти следующую смежную точку:одну из базисных переменных переместить в число свободных, а свободную – в базисные.
При этом выбирают ту переменную, которая оказывает максимальное влияние на целевую функцию.
По max(| ¯сi |) выбирается столбец i. А чтобы найти строку j: выбирается min (^bj/ai)
На месте разрешающего элемента ij должна стать 1, а остальные значения в этом столбце – обратиться в нуль.
Для этого:
1. разрешающая строка нормируется – делиться на значение разрешающего элемента;
2. разрешающий столбец преобразовывается в единичный с единицей в разрешающем элементе (домножением на некоторое число, такое, чтобы последующее сложение с опорной строкой давало 0 в опорном столбце).
После этого делается проверка на выполнение условий достижения оптимума (цикл).
Для отыскания первого опорного решения может быть использовано несколько способов:
1. Введение дополнительных переменных (для приведения неравенств к виду уравнений).
Эти дополнительные переменные собираются во вспомогательную функцию min w = ∑i xn+i
Первым шагом решения является минимизация этой функции. После чего дополнительные переменные можно исключить и решать дальше.
2. Метод штрафов
Дополнительные переменные вводятся в систему уравнений ограничений и одновременно в целевую функцию, причем эти переменные вводятся в целевую функцию с такими весовыми коэффициентами Мi, чтобы УХУДШИТЬ целевую функцию. (М отрицательные для поиска max и положительные для поиска min – обычно назначается как максимальный по модулю коэффициент во всех уравнениях, умноженный на 10)
3. Использование свойства двойственности.
Этот метод используется обычно тогда, когда получено опорное решение, но некоторые коэффициенты bi оказались отрицательными. Тогда, если в строке матрицы с этим коэффициентом есть элементы aij<0, то решение может быть получено. Иначе – решения нет.
При решении – если коэффициенты уменьшаются по модулю и количество отрицательных элементов уменьшается, то решение будет найдено. Иначе – зацикливание.
ИНТЕРПРЕТАЦИЯ СИМПЛЕКС-ТАБЛИЦЫ
По остаточным переменным определяется статус ресурса: если переменные не находятся в базисе (т.е. = 0) или в базисе, но b=0, то ресурсы – дефицитные. Остальные – недефицитные.
Ценность ресурсов – определяется по строке Z: коэффициенты в этой строке являются коэффициентами ценности ресурса.
Исследование на чувствительность требует перерасчетов: при определении изменения ограничений решение считается остающейся в той же точке, пока коэффициенты bi остаются положительными.
При изменении коэффициентов целевой функции нужно следить за знаком коэффициентов: для min они должны быть все >0 (для max - наоборот).
Методика расчета, используемая для анализа на чувствительность задачи линейного программирования с помощью симплекс таблиц (анализ чувствительности к изменению правых частей ограничений; ценность ресурсов; анализ чувствительности к изменению коэффициентов целевой функции).
Хотя сам оптимальный план очень полезен, часто бывает интересно знать,как можно изменить те или иные параметры системы (до этого постоянные), чтобы улучшить решение, получить еще большую прибыль или уменьшить издержки. Значение параметров определяет оптимальное значение переменных и целевой функции. С целью улучшения решения многие параметры могут быть изменены. В наших примерах трудно поменять параметры, характеризующие технологический процесс, но изменить количество ресурсов (запасы), а также отпускные цены на товары вполне возможно. Обычно это связывают с привлечением дополнительных финансовых ресурсов, при этом необходимо ответить на ряд вопросов: - какой ресурс наиболее сильно влияет на изменение прибыли (издержек)? как изменится решение и целевая функция при изменении количества того или иного ресурса? - если какой-либо продукт не входит в оптимальный план, а по каким-то причинам желательно, чтобы он в него входил, то какой параметр, и в каком направлении следует изменить? - как повлияет на оптимальный план изменение цен на товары, и можно ли бесконтрольно увеличивать цены? и т.д. Поиск ответов на подобные вопросы и составляет сущность анализа решения. В задачах ЛП существенную информацию о влиянии изменений параметров можно получить из --отчета об устойчивости| в ходе поиска решения в MS Excel. Для ответа на другие вопросы типа --что, если| необходимо дополнительное исследование. Некоторое представление о том, как может меняться решение ЗЛП при изменении параметров, можно получить из анализа графического решения задачи.
I. Изменение оптимального решения при изменении целевых коэффициентов
В задаче №1 целевая функция имеет вид: P=200x +100x. 1 2
Если уменьшить цену шкафа от 200у.е. до 150у.е. и далее до 50у.е., линия уровня будет менять наклон. Проведем линию уровня 200x+100x=10000, (1) на рис.1.1, а теперь 150x+100x=10000, (2) на рис.1.1. В этом случае т.C остается оптимальной. Изменим цену шкафа на 50у.е., оптимальной станет т.B(60;90). Отсюда вывод: --существует определенный интервал устойчивости, в котором изменение целевых коэффициентов не приводит к изменению оптимального решения|. Конечно, значение целевой функции в точке оптимума изменится (за счет коэффициентов). Но дальнейшее изменение коэффициентов целевой функции (цены) может привести к изменению оптимального решения и целевой функции. Т.е., если значение целевого коэффициента выходит за пределы интервала устойчивости, оптимальное значение резко изменится, перейдет в другую угловую точку области допустимых планов. В этом случае надо заново решать ЗЛП. В нашей задаче, если C =150; C =100; P=150•80+100•70=12700. 1 2
Вывод: 1. Изменение коэффициентов целевой функции c не изменяют область допустимых решений. В этом случае изменяется вектор и направление линий уровня, изображающих целевую функцию.
2. До тех пор, пока изменение наклона вектора не превышает некоторых пределов, оптимальное решение задачи не меняется, значение самой целевой функции конечно изменится.
3. При выходе значений коэффициентов c за пределы устойчивости, j решение задачи перемещается в другую угловую точку и может очень сильно измениться.
4. --Допустимое увеличение| и --Допустимое уменьшение| для каждого целевого коэффициента c, при котором оптимальное решение не изменится, j приводится в табл.1.9 --Изменяемые ячейки| отч?таExcel об устойчивости. При этом: а) если x?0, т.е. товар входит в оптимальный план, имеется верхний и j нижний пределы для изменения соответствующего j - того коэффициента целевой функции; б) если x =0, то |Допустимое уменьшение| может быть как j угодно велико (товар вс? равно не войд?т в оптимальный план). Верхний предел --Допустимое увеличение| покажет, насколько надо увеличить c, чтобы j – тый j продукт вошел в оптимальный план. Величина, противоположная этому увеличению, называется нормированной стоимостью и показывает, насколько нынешняя цена товара ниже минимальной цены (или издержки выше максимальной), при которой этот товар может войти в оптимальный план. Если некоторый продукт не входит в оптимальный план, его нормированная стоимость <0, а е? величина показывает, на сколько надо увеличить норму прибыли этого продукта, чтобы он вош?л в оптимальный план.
5. Пределы устойчивости для изменения c даются в отч?те при условии, j что все остальные c (k?j) остаются неизменными. Одновременное изменение j двух или более коэффициентов может привести к изменению оптимального плана. Для оценки влияния одновременного изменения нескольких c, надо j вычислить относительное изменение, где - это предел либо увеличения, либо уменьшения c, и вычислить сумму этих относительных j изменений. Если сумма >1, оптимальное решение изменится, если <1 – нет.