Занятие №3 Решение систем неравенств графическим методом

Тип урока: урок изучения нового материала.

Вид урока: Лекция, урок решения задач.

Продолжительность: 2 часа.

Цели: 1) Изучить графический метод.

2) Показать применение программы Maple при решении систем неравенств графическим методом.

3) Развить восприятие и мышление по данной теме.

План занятия: 1 этап: изучение нового материала.

2 этап: Отработка нового материала в математическом пакете Maple.

3 этап: проверка изученного материала и домашнее задание.

Ход занятия.

1 этап: Графический метод заключается в построении множества допустимых решений ЗЛП, и нахождении в данном множестве точки, соответствующей max/min целевой функции.

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

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

 

 

 

1. На первом этапе надо построить область допустимых решений. Для данного примера удобнее всего выбрать X2 за абсциссу, а X1 за ординату и записать неравенства в следующем виде:

 

 

Так как  и  графики и область допустимых решении находятся в первой четверти. Для того чтобы найти граничные точки решаем уравнения (1)=(2), (1)=(3) и (2)=(3).

 

Как видно из иллюстрации многогранник ABCDE образует область допустимых решений.

Если область допустимых решений не является замкнутой, то либо max(f)=+ ∞, либо min(f)= -∞.

2. Теперь можно перейти к непосредственному нахождению максимума функции f.

Поочерёдно подставляя координаты вершин многогранника в функцию f и сравнивать значения, находим что f(C)=f(4; 1)=19 – максимум функции.

Такой подход вполне выгоден при малом количестве вершин. Но данная процедура может затянуться если вершин довольно много.

В таком случае удобнее рассмотреть линию уровня вида f=a. При монотонном увеличении числа a от -∞ до +∞ прямые f=a смещаются по вектору нормали[1]. Если при таком перемещении линии уровня существует некоторая точка X – первая общая точка области допустимых решений (многогранник ABCDE) и линии уровня, то f(X)- минимум f на множестве ABCDE. Если X- последняя точка пересечения линии уровня и множества ABCDE то f(X)- максимум на множестве допустимых решений. Если при а→ -∞ прямая f=a пересекает множество допустимых решений, то min(f)= -∞. Если это происходит при а→ +∞, то  max(f)=+ ∞.

 

В нашем примере прямая f=a пересевает область ABCDE в точке С(4; 1). Поскольку это последняя точка пересечения, max(f)=f(C)=f(4; 1)=19.

2 этап.

Задача:

Решить графически систему неравенств. Найти угловые решения.

x ₁ + 2 x ₂ < =10

2 x ₁ + x ₂ < =10

x ₁ +3 x ₂ > =3

5 x ₁ - x ₂ > =-5

x ₁ +6 x ₂ > =6

x ₁ > = 0, x ₂ > =0

> restart;

>

>

>

>

>

>

>

>

>

>

>

>

>

> with(plots);

> with(plottools);

>

 

> S1: =solve( {f1x[1, 1] = X6[1, 1], f2x[1, 1] = X6[1, 2]}, [x, y]);

>

>

>

>

>

>

>

>

>

 

Ответ: Все точки Si где i=1..10 для которых x и y положительна.

Область, ограниченная данными точками: (54/11, 2/11) (5/7, 60/7) (0, 5) (10/3, 10/3)

3 этап. Каждому ученику даётся один из 20 вариантов, в котором ученику предлагается самостоятельно решить неравенство графическим методом, а остальные примеры в качестве домашнего задания.

Занятие №4 Графическое решение задачи линейного программирования

 

Тип урока: урок изучения нового материала.

Вид урока: Лекция + урок решения задач.

Продолжительность: 2 часа.

Цели: 1) Изучить графическое решение задачи линейного программирования.

2) Научить пользоваться программой Maple при решении задачи линейного программирования.

2) Развить восприятие, мышление.

План занятия: 1 этап: изучение нового материала.

2 этап: Отработка нового материала в математическом пакете Maple.

3 этап: проверка изученного материала и домашнее задание.

Ход занятия.

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости  некоторую полуплоскость (рис.2.1), а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.

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

 

можно представить в виде системы двух неравенств (см. рис.2.1)

 

 

ЦФ  при фиксированном значении  определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси  (начальная ордината), а угловой коэффициент прямой  останется постоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор  с координатами из коэффициентов ЦФ при  и  перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора  совпадает с направлениемвозрастания ЦФ, что является важным моментом для решения задач. Направлениеубывания ЦФ противоположно направлению вектора .

Суть графического метода заключается в следующем. По направлению (против направления) вектора  в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

 

Рисунок 2.1 Геометрическая интерпретация ограничений и ЦФ задачи.

⇐ Предыдущая12345Следующая ⇒

Поделиться: