Нахождение минимума линейной функции симплексным методом

Размещено на http://www.allbest.ru/

[Введите текст]

Контрольная работа

по дисциплине: «Математические методы»

тема: Нахождение минимума линейной функции симплексным методом

Введение

Симплекс или n-симплекс (от лат. simplex - простой) - геометрическая фигура, являющаяся n-мерным обобщением треугольника. Определяется как выпуклая оболочка n+1 точек, не лежащих в одной n-мерной гиперплоскости. Эти точки называются вершинами симплекса. Симплекс называется правильным, если все его рёбра имеют одинаковую длину. Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.

Рис. 1

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

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

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

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

Цель работы определяет задачи: изучить алгоритм решения задачи «нахождение минимума линейной функции симплексным методом».

Постановка задачи

Найдем наименьшее значение линейной функции симплексным методом.

Найдем наименьшее значение линейной функции симплексным методом

Решение задачи

Решение:

Умножим коэффициенты исходной функции на -1.

G = - x1 + x2 + 3 x3

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

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

Свободные члены системы ограничений должны быть неотрицательными. Умножим коэффициенты ограничения 2 на -1, свободный член ограничения станет положительным.

Свободные члены системы ограничений неотрицательные.

Система ограничений должна быть приведена к каноническому виду.

К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x4 - преобразуем неравенство 1 в равенство.

К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x5 - преобразуем неравенство 2 в равенство.

К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x6 - преобразуем неравенство 3 в равенство.

Система ограничений приведена к каноническому виду, т.е. все условия системы представляют собой уравнения.

Определимся с начальным опорным решением.

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

Переменная x4 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x4 - базисная переменная.

Переменная x5 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x5 - базисная переменная.

Переменная x6 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x6 - базисная переменная.

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

задача линейный функция симплекс

X нач = (0, 0, 0, 3, 6, 15)

Вернемся к рассмотрению функции G.

Функция G не содержат базисных переменных.

Для составления начальной симплекс таблицы мы выполнили все условия.

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

Обратите внимание:

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

Шаг 1

За ведущий выберем столбец 3, так как -3 наименьший элемент в G строке. Элемент G строки, принадлежащий столбцу свободных членов не рассматриваем.

За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 3.

От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на -1.

От элементов строки 3 отнимает соответствующие элементы строки 1.

От элементов строки G отнимает соответствующие элементы строки 1, умноженные на -3.

X 1 = (0, 0, 3, 0, 9, 12)

Значение функции G для данного решения: G (X 1) = 9

Шаг 2

За ведущий выберем столбец 2, так как -4 наименьший элемент в G строке. Элемент G строки, принадлежащий столбцу свободных членов не рассматриваем.

За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2.

От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на -1.

От элементов строки 3 отнимает соответствующие элементы строки 2.

От элементов строки G отнимает соответствующие элементы строки 2, умноженные на -4.

X 2 = (0, 9, 12, 0, 0, 3)

Значение функции G для данного решения: G (X 2) = 45

Шаг 3

За ведущий выберем столбец 1, так как -1 наименьший элемент в G строке. Элемент G строки, принадлежащий столбцу свободных членов не рассматриваем.

За ведущую выберем строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 1.

Разделим элементы строки 3 на 3.

От элементов строки 2 отнимает соответствующие элементы строки 3, умноженные на -2.

От элементов строки G отнимает соответствующие элементы строки 3, умноженные на -1.

X 3 = (1, 11, 12, 0, 0, 0)

Значение функции G для данного решения: G (X 3) = 46

Учитывая, что все xi0, по условию задачи, наибольшее значение функции G равно свободному члену 46, т.е. мы получили оптимальное решение.

X опт = (1, 11, 12, 0, 0, 0)

Значение функции: L = -46

Заключение

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

Список использованных источников

1. http://www.reshmat.ru/example_simplex_3.html

Размещено на Allbest.ru