Симплексный метод презентация

СИМПЛЕКСНЫЙ МЕТОД Численные методы решения линейной распределительной задачи требуют преобразования неравенств в равенства Токарная обработка 40x + 25y ≤ 1000 Сверловка 35 x + 28 y ≤ 980 Шлифовка 25 x + 35 y ≤ 875 Неравенства преобразуются в уравнения путем введения свободных переменных и, v и w. Эти переменные представляют собой разность между левой и правой частями неравенств. Таким образом, имеем: 40x + 25y + u = 1000 35 x + 28 y + v = 980 (1) 25 x + 35 y + w =875 Свободные переменные и, v и w должны быть неотрицательными.

В рассматриваемом многоугольнике ОАВС в любой вершине две из пяти переменных (х, у, и, v, w ) равны нулю, а остальные три больше нуля. В рассматриваемом многоугольнике ОАВС в любой вершине две из пяти переменных (х, у, и, v, w ) равны нулю, а остальные три больше нуля. В общей задаче, содержащей п переменных и т ограничений в виде неравенств, требуется т свободных переменных и решение, максимизирующее принятый критерий оптимальности, из общего числа т -\- п переменных, включая свободные, содержит точно т ненулевых значений.

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

Алгоритм можно разбить на четыре шага. Алгоритм можно разбить на четыре шага. 1.Очевидным допустимым решением системы 40x + 25y + u = 1000 35 x + 28 y + v = 980 (1) 25 x + 35 y + w =875 является следующий набор значений переменных: х = у = 0, и = 1000, v = 980 и w = 875.

Это решение можно изменить, увеличив либо х, либо у. Это решение можно изменить, увеличив либо х, либо у. Из целевой функции Z = 1,20 х + 1,40 у видно, что скорость возрастания Z при увеличении х равна 1,2 и 1,4 при увеличении у. Поэтому целесообразно увеличить у. 2. Увеличение у приведет к уменьшению и, v и w, так что у можно увеличивать лишь до тех пор, пока одна из переменных и, v или w не станет равной нулю.

Из системы уравнений Из системы уравнений 40x + 25y + u = 1000 35 x + 28 y + v = 980 (1) 25 x + 35 y + w =875 ясно, что в первом уравнении и = 0, когда у = 40, во втором — что v = 0 при у = 35 и в третьем — что w = 0 при у = 25.

Таким образом, у можно увеличить только до 25, что даст и = 375, v = 280 и w = 0. Эти расчеты выполнить очень просто в силу следующих причин: Таким образом, у можно увеличить только до 25, что даст и = 375, v = 280 и w = 0. Эти расчеты выполнить очень просто в силу следующих причин: а) Z не содержит ненулевых переменных и, v и w: б) каждое из уравнений системы содержит в точности одну ненулевую переменную и, v или w, и коэффициенты при каждой из них равны единице.

Изменим теперь Z и уравнения (1) так, чтобы выполнялись условия а) и б) для новых значений ненулевых переменных у, и и v. Изменим теперь Z и уравнения (1) так, чтобы выполнялись условия а) и б) для новых значений ненулевых переменных у, и и v. Третье уравнение системы (1) является единственным, содержащим переменную w, ставшую равной нулю. Разделив это уравнение на 35, т. е. на коэффициент при новой ненулевой переменной у получаем: 5/7X +Y+ W/35 =25 (2)

Вычтем далее умноженное на соответствующие множители (25 и 28) уравнение (2) из остальных уравнений системы (1 ), чтобы исключить из них у. Имеем: Вычтем далее умноженное на соответствующие множители (25 и 28) уравнение (2) из остальных уравнений системы (1 ), чтобы исключить из них у. Имеем: 155/7X + U + 5/7 W = 375 (3) 15X + V - 4/5 W = 280 (4) Но из (2) получаем 5/7 х + у + (W 35) — 25 = 0. Следовательно, если вычесть кратные этому выражению величины из Z, то Z не изменится. Если же вычесть из Z это выражение, предварительно умножив его на 1,4, то тем самым будет исключена переменная у.

Следовательно, Z = 0,2х — 0,04W + 35. Следовательно, Z = 0,2х — 0,04W + 35. Очевидно, что из двух нулевых переменных х и w только х может увеличивать значение Z при увеличении от нуля. Чтобы определить, насколько можно увеличить х, разделим коэффициенты при х в (2), (3) и (4) на постоянные, стоящие в правой части. Получаем 35, 16• 29/31 и 18•2/3. Увеличение значения х до 16• 29/31 приведет к уменьшению u до нуля при y = 12•28/31 и V= 25•30/31.

Разделив (2) на коэффициент при х и перенеся постоянную в левую часть, получим: Разделив (2) на коэффициент при х и перенеся постоянную в левую часть, получим: X + 7/155 U + W /31 - 16• 29/31 = 0 (5) Если вычесть (5), обе части которого умножены на 0,2 из Z = 0,2х — 0,04W + 35, то получим Z = - 1,4/155 U - 26/755W +38• 12/31

Отсюда можно сделать вывод, что увеличение любой переменной U или W приведет только к уменьшению Z. Отсюда можно сделать вывод, что увеличение любой переменной U или W приведет только к уменьшению Z. Следовательно, максимальное значение Z найдено и равно 38•12/31

Решение оптимизационной задачи в табличной форме Составим таблицу (табл. 1), в которой строки, обозначенные Р3, P4 и Р5, соответствуют первому набору значений ненулевых переменных и, v и w. Столбцы, обозначенные P1 , P2 , P3 P4, и P5 , соответствуют переменным х, у, и, v и w. Добавим еще один столбец P0 соответствующий постоянным (правым частям) уравнений, и строку Δ, в которой проставлены коэффициенты функции Z.

Таблица полностью определяет уравнения Таблица полностью определяет уравнения Z = 1,20 х + 1,40 у и 40x + 25y + u = 1000 35 x + 28 y + v = 980 (1) 25 x + 35 y + w =875 Пустые клетки таблицы соответствуют нулям. Используя таблицу 1, можно вновь применить алгоритм из четырех шагов, соответствующих только что выполненным вычислениям.

1. Выбрать столбец с наибольшим положительным элементом в строке А. В данном случае это столбец P2 с элементом 1,4. 1. Выбрать столбец с наибольшим положительным элементом в строке А. В данном случае это столбец P2 с элементом 1,4. 2. Разделить положительные элементы в выбранном на шаге 1 столбце на соответствующие элементы столбца Ро и выбрать наименьший результат. В этом примере выбран столбец P2 Результаты деления по строкам следующие: для Р3 — 1000/25 = 40, для Р4 —980/28 = 35 и для Р5 — 875/35 = 25. Поэтому выбирается строка Р5

Разделить строку, выбранную на шаге 2, на наибольший элемент столбца, выбранного на шаге 1, и обозначить результат символом этого столбца. В этом примере элементы строки Р5 делятся на 35 и результат получает обозначение P2. Разделить строку, выбранную на шаге 2, на наибольший элемент столбца, выбранного на шаге 1, и обозначить результат символом этого столбца. В этом примере элементы строки Р5 делятся на 35 и результат получает обозначение P2. Это дает:

4. Исключить элементы всех строк (включая строку Δ) 4. Исключить элементы всех строк (включая строку Δ) кроме строки, измененной на шаге 3, вычитая умноженную на соответствующие множители строку, полученную на шаге 3, которой приписано новое обозначение. Если все элементы получающейся в итоге строки А отрицательны или равны нулю, то оптимальное решение найдено. В противном случае нужно вернуться к шагу 1.

В рассматриваемом примере строка Р2 умножается на 25 и результат вычитается из строки Р3. Аналогичную операцию мы производим над строками Р4 (предварительно умножая Р2 на 28) и Δ(предварительно умножая Р2 на 1,4). В результате получается табл. 3 В рассматриваемом примере строка Р2 умножается на 25 и результат вычитается из строки Р3. Аналогичную операцию мы производим над строками Р4 (предварительно умножая Р2 на 28) и Δ(предварительно умножая Р2 на 1,4). В результате получается табл. 3

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

Вследствие того что оба элемента строки Δ теперь отрицательны, приходим к выводу, что при P1 = х = 16• 29/31 и Р2 = у = 12•28/31 Вследствие того что оба элемента строки Δ теперь отрицательны, приходим к выводу, что при P1 = х = 16• 29/31 и Р2 = у = 12•28/31 достигается максимум Z. Отметим, что шаг 2 описанной табличной модификации алгоритма нереализуем, если в выбранном на первом шаге столбце нет ни одного положительного элемента (кроме элемента строки Δ). В этом случае переменную, выбранную на шаге 1, можно, не нарушая ограничения, увеличивать до бесконечности. Когда исходные данные соответствуют реальной задаче, это обычно означает, что-либо реальная задача нелинейная, либо пропущено какое-то ограничение.