Применение графического метода и симплекс-метода для решения задач линейного программирования
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
Содержание
Введение
Задание
1. Графический метод решения задачи линейного программирования
2. Решение задачи линейного программирования симплекс-методом
3. Решение задачи двойственной к исходной
4. Решение транспортной задачи
Выводы
Введение
Исследование операций - это математическая дисциплина, занимающаяся разработкой и применением методов нахождения наилучших решений в различных областях человеческой деятельности.
Под операциями обычно понимают целенаправленные управляемые процессы. Природа их может быть различной - это могут быть военные действия, производственные процессы, коммерческие мероприятия, административные решения, и т.д. Что интересно - операции эти (совершенно несхожие по своей природе) могут быть описаны одними и теми же математическими моделями, более того, анализ этих моделей позволяет лучше понять суть того или иного явления и даже предсказать его дальнейшее развитие. Мир, как оказалось, устроен необычайно компактно (в информационном смысле), поскольку одна и та же информационная схема реализуется в самых разных физических (и не только физических) проявлениях. В кибернетике это называется термином "изоморфизм моделей".
Если бы не изоморфизм моделей, для каждой конкретной ситуации пришлось бы отыскивать собственный, уникальный метод решения, и исследование операций как научное направление не сформировалось бы. К счастью, дело обстоит иначе. Благодаря наличию общих закономерностей в развитии самых разных систем возможно исследование их математическими методами. Исследование операций как математический инструментарий, поддерживающий процесс принятия решений в самых разных областях человеческой деятельности, как совокупность средств, позволяющих обеспечить лицо, принимающее решение, необходимой количественной информацией, полученной научными методами, сформировалось на стыке математики и разнообразных социально-экономических дисциплин. Свой вклад в его становление внесли представители самых различных областей науки.
Одним из разделов исследования операций является линейное программирование. Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.
Итак, линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции.
Рассмотрим вкратце два метода решения задач линейного программирования: графический и симплекс-метод; также рассмотрим транспортную задачу, которая тоже является задачей линейного программирования и может быть решена симплекс-методом, но поскольку она имеет своеобразную матрицу ограничений, то для нее разработаны специальные методы решения.
Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции задачи.
Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру.
Вектор C = (c1, c2) с координатами из коэффициентов целевой функции при x1 и x2 перпендикулярен к каждой из линий уровня. Направление вектора C совпадает с направлением возрастания целевой функции, что является важным моментом для решения задачи. Направление убывания целевой функции противоположно направлению вектора C.
Суть графического метода заключается в следующем. По направлению (против направления) вектора C в ОДР производится поиск оптимальной точки x* = (x1*, x2*). Оптимальной считается точка, через которую проходит линия уровня Lmax (Lmin), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
Суть симплекс-метода состоит в следующем:
. Находят какое-либо допустимое базисное решение. Его можно найти, приняв какие-либо m-n переменные за свободные, приравняв их к нулю и решив получившуюся систему уравнений. Если при этом некоторые из базисных переменных окажутся отрицательными, то нужно выбрать другие свободные переменные, т.е. перейти к новому базису.
. Проверяют, не достигнут ли уже максимум целевой функции при найденном допустимом базисном решени