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

Лекция №4. Симплекс метод решения задач. 10 20 30 В предыдущих лекциях мы научились переходить от словесного описания экономической ситуации к описанию этой же ситуации в математическом виде, в виде задачи линейного программирования; научились отыскивать оптимум геометрическим методом; находить оптимальное решение в MS Excel. Однако решение геометрическим методом подразумевает ряд ограничений и нередко вычисление с его использованием просто невозможно. Отсюда для решения практически любых задач линейного программирования необходимы знания универсальных методов. К таким универсальным методам решения задач относится симплекс метод. Все мы помним, что ОДР (область допустимых решений) представляет собой некоторый многогранник. Также нам известно, что одна из вершин этого многогранника (или сторона) является оптимальной. Используя симплекс метод для решения, мы сможем пройти по каждой из этих вершин и определить ту, которая приносит рассматриваемой целевой функции максимум или минимум. Фактически симплекс метод основан на последовательном улучшении решения. Прежде чем рассмотреть конкретную задачу, введем некоторые понятия и определения, которые помогут нам подготовить исходную математическую модель задачи к решению симплекс методом. В общем случае, когда записывается задача линейного программирования, то в системе ограничений могут находиться как уравнения, так неравенства. В том случае, когда все ограничения являются уравнениями, а все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической. Наша задача состоит в том, что перед тем, как применить симплекс метод для решения – нужно перейти от общей записи ЗЛП к её канонической форме. Для того, чтобы выполнить переход к канонической форме ЗЛП необходимо ввести базисные (дополнительные) переменные в систему ограничений по следующему правилу: 1. Если в ограничении находится знак отношения «  », то базисная переменная в это ограничение входит со знаком «+»; 2. Если в ограничении находится знак отношения «  », то базисная переменная в это ограничение входит со знаком «-». В целом, после перехода к канонической форме ЗЛП, все переменные можно разделить на две категории: первая – неосновные переменные, вторая – базисные переменные. Алгоритм симплекс метода состоит в последовательном введении в базис, состоящий из базисных переменных, неосновных переменных, тем самым, улучшая решение или не ухудшая предыдущего. Процедура улучшения решения ограничена определенным критерием, который отличен в случае поиска максимума и минимума. 1 2 Критерий №1 (максимизация) Если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то найденное решение задачи отыскания максимума линейной функции является оптимальным1. Критерий №2 (минимизация) Если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то найденное решение задачи отыскания минимума линейной функции является оптимальным2. Лукиных И.Г. «Методы оптимальных решений: учебное пособие», г. Киров, 2012, 63 с. Там же, С. 13. 1 40 Рассмотрим решение задачи линейного программирования на конкретном примере. Задача №2. Задача о производстве красок. Фирма изготавливает два вида красок: для внутренних (В) и для наружных (Н) работ. Для их производства используют исходные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы приведены в таблице. Исходный продукт 50 Расход исходных продуктов на 1 кг. краски Суточный запас, кг. Краска Н Краска В Пигмент 1 2 14 Олифа 2 1 18 Изучение рынка сбыта показало, что суточный спрос на краску для наружных работ никогда не превышает 4 кг. в сутки. Цена продажи 1 кг. краски для наружных работ – 60 руб., а для внутренних работ – 90 руб. Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным? Решение. Запишем математическую модель задачи. Целевая функция примет вид: F  60 x1  90 x2  max Система ограничений:  x1  2 x2  14  2 x1  x2  18 x  4  1 x1  0; x2  0 Запишем исходную математическую постановку задачи в канонической форме. Для этого перейдет к системе равенств, и введем дополнительные (базисные) переменные. Тогда математическая модель задачи в канонической форме примет вид: Целевая функция примет вид: F  60 x1  90 x2  max Система ограничений:  x1  2 x2  x3  14  2 x1  x2  x4  18 x  x  4  1 5 x1  0; x2  0 Теперь выразим базисные переменные через неосновные, тогда система получит следующий вид:  x3  14  x1  2 x2   x4  18  2 x1  x2 x  4  x 1  5 2 60 Выпишем первоначальное базисное решение по следующему правилу: переменные, не вошедшие в базис, можно взять равными нулю. А это означает, что x3  14 , x4  18 и x5  4 . Тогда базисное решение выпишется так: F  0;0;14;18; 4 . Поскольку в базисном решении нет отрицательных значений, что в противном случае свидетельствовало бы о недопустимом опорном плане, то текущее базисное решение является допустимым, а целевая функция равна нулю. Перейдем к лучшему решению за счет изменения базиса. Для этого введем в базис ту из неосновных переменных, при которой имеется наибольший положительный коэффициент в целевой функции. Значит, введем в базис неосновную переменную x2 , поскольку коэффициент в целевой функции при этой переменной больше. Теперь необходимо определить, а вместо какой переменной базиса ввести неосновную переменную x2 ? Для этого вычисляются оценочные 70 отношения для каждого из, теперь уже, равенств. Оценочное отношение определяется, как отношение свободного элемента к коэффициенту при переменной, вводимой в базис. После того, как все оценки станут известны, среди них необходимо выбрать минимальную. Собственно, именно из уравнения, которому соответствует минимальная оценка, будет выражена переменная x2 . Итак:  14 18  min  ; ;   2 1  Минимальная оценка соответствует первому уравнению, а это означает, что именно из первого уравнения будет выражена переменная x2 . Важно! Можно заметить, что последняя оценка равна бесконечности (  ). Такое отношение получается в том случае, если, при нахождении оценок, свободный элемент и коэффициент при вводимой переменной одинакового знака или этот самый коэффициент равен 0. Давайте проделаем это вместе. 2 x2  14  x1  x3  x2  7  1 1 x1  x3 2 2 Теперь, после того, как введена в базис (выражена) новая переменная – необходимо подставить x2 в оставшиеся равенства и, в том числе, в целевую функцию. Выполним эти действия, не пропуская ни одного преобразования. x4  18  2 x1  7  80 1 1 3 1 x1  x3  11  x1  x3 2 2 2 2 В последнем равенстве переменная x2 равна нулю и поэтому мы просто перепишем его в новую систему, в новый базис. Тогда окончательно, после подстановки x2 во все равенства (кроме равенства, из которого была выражена переменная x2 ), получим следующего вида систему: 3 1 1   x2  7  2 x1  2 x3  3 1   x4  11  x1  x3 2 2   x5  4  x1   И последнее. Подставим выражение для x2 в целевую функцию. 1 1   F  60 x1  90  7  x1  x3   60 x1  630  45x1  45x3  630  15x1  45x3 2 2   Одна итерация симплекс метода завершена. Теперь пользуясь критерием для задач на максимум, необходимо определить: найдено ли оптимальное решение? Поскольку в нашей целевой функции после подстановки переменной введенной в базис остается неосновная переменная x1 с положительным коэффициентом, то оптимальное решение, доставляющее 90 максимум целевой функции не найдено. Значит, необходимо повторить все действия заново: 1. Определить переменную, которая войдет в базис; 2. Найти уравнение, из которого будет выражена переменная, вводимая в базис; 3. Подставить выражение вновь введенной в базис переменной в оставшиеся уравнения системы, в том числе, в целевую функцию; 4. Определить по критерию – найден ли оптимум? Итак. Мы знаем, что улучшить базис возможно за счет переменной x1 . Теперь найдем оценочные отношения для уравнений.   11 4   7 min  ; ;  1 3  1     2 2 Минимальная оценка соответствует последнему уравнению, а это означает, что переменную x1 нужно выражать из последнего уравнения. Тогда получим:   x1  4  x5  1 1 1 1 1 1   x2  7   4  x5   x3  7  2  x5  x3  5  x5  x3 2 2 2 2 2 2  3 1 3 1 3 1  x4  11   4  x5   x3  11  6  x5  x3  5  x5  x3  2 2 2 2 2 2  Целевая функция примет вид: F  630  15  4  x5   45x3  630  60  15x5  45x3  690  15x5  45x3 100 В целевой функции больше не осталось переменных, имеющих при себе положительные коэффициенты, и, пользуясь критерием для поиска максимума, можно однозначно сказать, что найдено оптимальное решение. Выпишем его. Поскольку в базис НЕ вошли переменные x5 и x3 , то их можно взять равными нулю. Тогда x1  4 , x2  5 и x4  5 . Ответ можно записать так: Fоптим.  4;5;0;5;0  690 . Этот 4 110 ответ означает, что краску для наружных работ необходимо производить в объеме 4 кг., а краску для внутренних работ – в объеме 5 кг. При этом такой план производства принесет максимальный доход в размере 690 рублей. Предлагаю читателю самостоятельно убедиться в правильности решения и самостоятельно выполнить поиск оптимума при помощи геометрического метода или в MS Excel через надстройку «Поиск решения». Успехов в освоении нового материала! 5