Лекция 3: геометрический метод решения задач линейного программирования
1. Понятие геометрического метода 2. Алгоритм решения задачи геометрическим методом. Геометрический метод решения ЗЛП – простой и наглядный способ решения стандартных ЗЛП с двумя переменными:
при условиях
Рассмотрим следующие геометрические объекты. Выпуклые множества и их свойства. Множество точек называется выпуклым, если оно вместе с произвольными двумя своими точками содержит весь отрезок, соединяющий эти точки. Например, четырехугольник
Рис. 3.1 Рис. 3.2 Справедливо утверждение: пересечение любого числа выпуклых множеств есть выпуклое множество. Каждое неравенство системы ограничений (3.2) геометрически определяет полуплоскость с граничной прямой Поясним сказанное. Рассмотрим, например, неравенство Посмотрим прямую L:
Рис. 3.3 Для того чтобы определить, какая полуплоскость удовлетворяет заданному неравенству, необходимо выбрать любую точку, не лежащую на L, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Как правило, в качестве «пробной» берут точку Подставим Полуплоскости, описываемые неравенствами (3.2) – выпуклые множества. Их пересечение – область допустимых решений ЗЛП, которая является также выпуклым множеством. Это множество называют также многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным или неограниченным многоугольником. (Случай вырождения, когда система ограничений (3.2) – пустое множество и ЗЛП не имеет решения, исключается).
Ввиду неравенств Для нахождения экстремума целевой функции F воспользуемся вектором набла
Он показывает направление наискорейшего изменения целевой функции F. Прямая Алгоритм решения ЗЛП геометрическим методом. 1. Строится многоугольник решений. 2. Строится вектор набла, перпендикулярно ему проводятся линии уровня и при этом учитывают, что оптимальное решение ЗЛП находится в угловой точке многоугольника решений. 3. Первая точка встречи линии уровня с многоугольником решений определяет минимум целевой функции (точка 4. Последняя точка встречи линии уровня с многоугольником решений определяет максимум целевой функции (точка 5. Если линия уровня параллельна одной из сторон многоугольника решений (сторона
Рис. 3.5 Рис. 3.6 6. Для нахождения координаты точки экстремума решают систему из двух уравнений прямых, дающих в пересечении эту точку. По описанному алгоритму решим ЗЛП из предыдущей Лекции 2.
Пример 1. Экономико-математическая модель задачи о планировании производства. Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (3.7) в виде
«Пробная» точка
Построим вектор набла Подставив координаты точки Рис. 3.7
Пример 2. Экономико-математическая модель задачи о диете. Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей в виде
«Пробная» точка Построим вектор набла Подставив координаты точки Рис. 3.8
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|