Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1. ЦЕЛЬ РАБОТЫ: приобрести навыки решения задач линейного программирования с использования графического метода, а также закрепления полученных навыков решения задачи с использованием среды MS EXCEl
СОДЕРЖАНИЕ РАБОТЫ
2.1 Ознакомиться с теоретическими предпосылками изложенными в данной лабораторной работе, углубить знания с использованием дополнительной литературы
2.2 Изучить и разобрать пример расчета.
2.3 Для исходных данных индивидуального задания выполнить расчеты.
2.4. Выполнить анализ результатов и сделать выводы
Теоретическое введение
Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое из неравенств задачи ЛП (1.1) определяет на координатной плоскости некоторую полуплоскость (рис. 2.1), а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучем, одной точкой. В случае несовместности системы ограничений задачи (1.1) ОДР является пустым множеством.
Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство можно представить в виде системы двух неравенств (см. рис. 1)
ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см. рис. 2.1).
Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис. 2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.
Дата публикования: 2014-11-04; Прочитано: 499 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!