КП_Тишинский. 5. Решение задачи линейного программирования вручную 10
Скачать 5.67 Mb.
|
Содержание Введение 2 1.Постановка задачи линейного программирования 3 2.Обзор алгоритмов решения задач линейного программирования 3 2.1.Графический способ решения задачи линейного прогаммированя 3 2.2.Решение задач линейного программирования симплекс-методом 7 2.3.Метод искусственного базиса решения задач линейного программирования 9 3.Постановка задачи линейного программирования 9 4.Построение математической модели задачи 10 5.Решение задачи линейного программирования вручную 10 5.1.Графический способ решения задачи линейного программированя 10 5.2.Решение задачи линейного программирования симплекс методом 14 6.Реализация модели задачи на компьютере 18 6.1.Реализация модели задачи линейного программирования в MS Excel 18 6.2Реализация модели задачи линейного программирования в MathCAD 21 7.Анализ полученных результатов 22 ВведениеВажнейшим математическим инструментарием современных экономистов и менеджеров, позволяющим найти оптимальное решение в условиях ограниченности ресурсов, является линейное программирование. Существует множество математических методов, позволяющих реализовывать линейные экономико-математические модели. Использование компьютерных технологий освобождает от рутинной вычислительной работы и позволяет сконцентрировать внимание не на алгоритме вычисления, а непосредственно на анализе результатов моделирования, что заметно повышает «коэффициент полезного действия» затраченного времени. Поэтому, в курсовой работе вместе с ручными методами реализации математической модели представлены возможности ИТ. Целью данной курсовой работы является систематизация, закрепление и расширение теоретических знаний и практических навыков при решении конкретной задачи линейного программирования. Задачами данной курсовой работы является разработка математической модели задачи, составление сопряженной задачи, решение задач линейного программирования методами: симплексным, допустимого базиса, а также реализация алгоритма поставленной задачи на компьютере с использованием программ Microsoft Office Excel и MathCAD.
Расчетные методы, которые могут быть эффективно применены при анализе и расчете производственных планов, опираются на специально разработанный математический аппарат. Математическая теория таких расчетов известна под названием линейного программирования. Линейное программирование (ЛП) - наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения. Линейное программирование описывает условия принятия экономических решений с помощью линейных функций, линейных уравнений и неравенств. Оно позволяет в достаточно простой и математически строгой форме отделить допустимые решения от недопустимых, проанализировать множество допустимых решений и однозначно ответить на вопрос о существовании или не существовании самого лучшего, оптимального решения. Если такое оптимальное решение существует, то методы линейного программирования позволяют его найти. Соответствующие расчеты и анализ полученных результатов могут быть проведены на компьютере. Линейная функция, используемая для нахождения искомого решения, называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений. В общем виде математическая модель задачи линейного программирования (ЗЛП) записывается как при ограничениях: Где xj - неизвестные; aij, bi, cj - заданные постоянные величины.
Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции задачи. Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством. Все вышесказанное относится и к случаю, когда система ограничений включает равенства, поскольку любое равенство можно представить в виде системы двух неравенств Целевая функция при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня. Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным. Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L. Вектор с координатами из коэффициентов целевой функции при и перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания целевой функции, что является важным моментом для решения задач. Направление убывания целевой функции противоположно направлению вектора . Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне. Рисунок 2 1 Построение графиков, и выявление общей области решения Рисунок 2 2 Построение вектора градиента и вспомогательной Рисунок 2 3 Определение точек экстремума Особые случаи При поиске оптимального решения задач линейного программирования возможны могут возникнуть следующие ситуации, когда:
Рисунок 2 4 Бесконечное множество решений (альтернативный оптиум) Рисунок 2 5 Целевая функция не ограничена Рисунок 2 6 Отсутствует общая область допустимых решений Методика решения задач линейного программирования графическим методом.
|