В ходе урока вы сможете самостоятельно изучить тему «Графическое решение уравнений, неравенств». Преподаватель на занятии разберет графические методы решения уравнений и неравенств. Научит строить графики, анализировать их и получать решения уравнений и неравенств. На уроке также будут разобраны конкретные примеры по этой теме.
Тема: Числовые функции
Урок: Графическое решение уравнений, неравенств
1. Тема урока, введение
Мы рассмотрели графики элементарных функций, в том числе графики степенных функций c разными показателями. Также мы рассмотрели правила сдвига и преобразований графиков функций. Все эти навыки необходимо применить, когда требуется графическое решение уравнений или графическое решение неравенств .
2. Решение уравнений и неравенств графическим способом
Пример 1. Графически решить уравнение:
Построим графики функций (Рис. 1).
Графиком функции является парабола, проходящая через точки
График функции - прямая, построим её по таблице.
Графики пересекаются в точке Других точек пересечения нет, т. к. функция монотонно возрастает, функция монотонно убывает, а, значит, их точка пересечения является единственной.
Пример 2. Решить неравенство
a. Чтобы выполнялось неравенство, график функции должен располагаться над прямой (Рис. 1). Это выполняется при
b. В этом случае, наоборот, парабола должна находиться под прямой. Это выполняется при
Пример 3. Решить неравенство
Построим графики функций 
(Рис. 2).
Найдем корень уравнения При нет решений. При существует одно решение .
Чтобы выполнялось неравенство гипербола должна располагаться над прямой Это выполняется при 
.
Пример 4. Решить графически неравенство:
Область определения:
Построим графики функций 
для (Рис. 3).
a. График функции должен располагаться под графиком это выполняется при
b. График функции расположен над графиком при Но т. к. в условии имеем нестрогий знак, важно не потерять изолированный корень
3. Заключение
Мы рассмотрели графический метод решения уравнений и неравенств; рассмотрели конкретные примеры, при решении которых использовали такие свойства функций, как монотонность и четность.
1. Мордкович А. Г. и др. Алгебра 9 кл.: Учеб. Для общеобразоват. Учреждений.- 4-е изд. - М.: Мнемозина, 2002.-192 с.: ил.
2. Мордкович А. Г. и др. Алгебра 9 кл.: Задачник для учащихся общеобразовательных учреждений / А. Г. Мордкович, Т. Н. Мишустина и др. — 4-е изд. — М.: Мнемозина, 2002.-143 с.: ил.
3. Макарычев Ю. Н. Алгебра. 9 класс: учеб. для учащихся общеобразоват. учреждений / Ю. Н. Макарычев, Н. Г. Миндюк, К. И. Нешков, И. Е. Феоктистов. — 7-е изд., испр. и доп. — М.: Мнемозина, 2008.
4. Алимов Ш. А., Колягин Ю. М., Сидоров Ю. В. Алгебра. 9 класс. 16-е изд. - М., 2011. - 287 с.
5. Мордкович А. Г. Алгебра. 9 класс. В 2 ч. Ч. 1. Учебник для учащихся общеобразовательных учреждений / А. Г. Мордкович, П. В. Семенов. — 12-е изд., стер. — М.: 2010. — 224 с.: ил.
6. Алгебра. 9 класс. В 2 ч. Ч. 2. Задачник для учащихся общеобразовательных учреждений / А. Г. Мордкович, Л. А. Александрова, Т. Н. Мишустина и др.; Под ред. А. Г. Мордковича. — 12-е изд., испр. — М.: 2010.-223 с.: ил.
1. Раздел College. ru по математике.
2. Интернет-проект «Задачи» .
3. Образовательный портал «РЕШУ ЕГЭ» .
1. Мордкович А. Г. и др. Алгебра 9 кл.: Задачник для учащихся общеобразовательных учреждений / А. Г. Мордкович, Т. Н. Мишустина и др. — 4-е изд. — М. : Мнемозина, 2002.-143 с.: ил. № 355, 356, 364.
Пусть f(x,y) и g(x, y) - два выражения с переменными х и у и областью определения Х . Тогда неравенства вида f(x, y) > g(x, y) или f(x, y) < g(x, y) называется неравенством с двумя переменными .
Значение переменных х, у из множества Х , при которых неравенство обращается в истинное числовое неравенство, называется его решением и обозначается (x, y) . Решить неравенство - это значит найти множество таких пар.
Если каждой паре чисел (x, y) из множества решений неравенства поставить в соответствие точку М(x, y) , получим множество точек на плоскости, задаваемое этим неравенством. Его называют графиком данного неравенства . График неравенства обычно является областью на плоскости.
Чтобы изобразить множество решений неравенства f(x, y) > g(x, y) , поступают следующим образом. Сначала заменяют знак неравенства знаком равенства и находят линию, имеющую уравнение f(x,y) = g(x,y) . Эта линия делит плоскость на несколько частей. После этого достаточно взять в каждой части по одной точке и проверить, выполняется ли в этой точке неравенство f(x, y) > g(x, y) . Если оно выполняется в этой точке, то оно будет выполняться и во всей части, где лежит эта точка. Объединяя такие части, получаем множество решений.
Задача. y > x .
Решение. Сначала заменим знак неравенства знаком равенства и построим в прямоугольной системе координат линию, имеющую уравнение y = x .
Эта линия делит плоскость на две части. После этого возьмем в каждой части по одной точке и проверим, выполняется ли в этой точке неравенство y > x .
Задача.
Решить графически неравенство
х
2 + у
2 £ 25.
|
Решение.
Сначала заменим знак неравенства знаком равенства и проведем линию х
2 + у
2 = 25. Это окружность с центром в начале координат и радиусом 5. Полученная окружность делит плоскость на две части. Проверяя выполнимость неравенства х
2 + у
2 £ 25 в каждой части, получаем, что графиком является множество точек окружности и части плоскости внутри окружности. Пусть даны два неравенства f 1(x, y) > g 1(x, y) и f 2(x, y) > g 2(x, y) .
Системы совокупностей неравенств с двумя переменными
Система неравенств представляет собой конъюнкцию этих неравенств. Решением системы является всякое значение (x, y) , которое обращает каждое из неравенств в истинное числовое неравенство. Множество решений системы неравенств есть пересечение множеств решений неравенств, образующих данную систему.
Совокупность неравенств представляет собой дизъюнкцию этих неравенств. Решением совокупности является всякое значение (x, y) , которое обращает в истинное числовое неравенство хотя бы одно из неравенств совокупности. Множество решений совокупности есть объединение множеств решений неравенств, образующих совокупность.
Задача.
Решить графически систему неравенств 
Решение.
у = х
и х
2 + у
2 = 25. Решаем каждое неравенство системы.
Графиком системы будет множество точек плоскости, являющихся пересечением (двойная штриховка) множеств решений первого и второго неравенств.
Задача.
Решить графически совокупность неравенств 
Упражнения для самостоятельной работы
1. Решите графически неравенства: а) у > 2x ; б) у < 2x + 3;
в) x 2 + y 2 > 9; г) x 2 + y 2 £ 4.
2. Решите графически системы неравенств:
а) в) 
Графический метод является одним из основных методов решения квадратных неравенств. В статье мы приведем алгоритм применения графического метода, а затем рассмотрим частные случаи на примерах.
Суть графического метода
Метод применим для решения любых неравенств, не только квадратных. Суть его вот в чем: правую и левую части неравенства рассматривают как две отдельные функции y = f (x) и y = g (x) , их графики строят в прямоугольной системе координат и смотрят, какой из графиков располагается выше другого, и на каких промежутках. Оцениваются промежутки следующим образом:
Определение 1
- решениями неравенства f (x) > g (x) являются интервалы, где график функции f выше графика функции g ;
- решениями неравенства f (x) ≥ g (x) являются интервалы, где график функции f не ниже графика функции g ;
- решениями неравенства f (x) < g (x) являются интервалы, где график функции f ниже графика функции g ;
- решениями неравенства f (x) ≤ g (x) являются интервалы, где график функции f не выше графика функции g ;
- абсциссы точек пересечения графиков функций f и g являются решениями уравнения f (x) = g (x) .
Рассмотрим приведенный выше алгоритм на примере. Для этого возьмем квадратное неравенство a · x 2 + b · x + c < 0 (≤ , > , ≥) и выведем из него две функции. Левая часть неравенства будет отвечать y = a · x 2 + b · x + c (при этом f (x) = a · x 2 + b · x + c) , а правая y = 0 (при этом g (x) = 0).
Графиком первой функции является парабола, второй прямая линия, которая совпадает с осью абсцисс О х. Проанализируем положение параболы относительно оси О х. Для этого выполним схематический рисунок.
Ветви параболы направлены вверх. Она пересекает ось О х в точках x 1 и x 2 . Коэффициент а в данном случае положительный, так как именно он отвечает за направление ветвей параболы. Дискриминант положителен, что указывает на наличие двух корней у квадратного трехчлена a · x 2 + b · x + c . Корни трехчлена мы обозначили как x 1 и x 2 , причем приняли, что x 1 < x 2 , так как на оси О х изобразили точку с абсциссой x 1 левее точки с абсциссой x 2 .
Части параболы, расположенные выше оси О х обозначим красным, ниже – синим. Это позволит нам сделать рисунок более наглядным.
Выделим промежутки, которые соответствуют этим частям и отметим их на рисунке полями определенного цвета.
Красным мы отметили промежутки (− ∞ , x 1) и (x 2 , + ∞) , на них парабола выше оси О х. Они являются a · x 2 + b · x + c > 0 . Синим мы отметили промежуток (x 1 , x 2) , который является решением неравенства a · x 2 + b · x + c < 0 . Числа x 1 и x 2 будут отвечать равенству a · x 2 + b · x + c = 0 .
Сделаем краткую запись решения. При a > 0 и D = b 2 − 4 · a · c > 0 (или D " = D 4 > 0 при четном коэффициенте b) мы получаем:
- решением квадратного неравенства a · x 2 + b · x + c > 0 является (− ∞ , x 1) ∪ (x 2 , + ∞) или в другой записи x < x 1 , x > x 2 ;
- решением квадратного неравенства a · x 2 + b · x + c ≥ 0 является (− ∞ , x 1 ] ∪ [ x 2 , + ∞) или в другой записи x ≤ x 1 , x ≥ x 2 ;
- решением квадратного неравенства a · x 2 + b · x + c < 0 является (x 1 , x 2) или в другой записи x 1 < x < x 2 ;
- решением квадратного неравенства a · x 2 + b · x + c ≤ 0 является [ x 1 , x 2 ] или в другой записи x 1 ≤ x ≤ x 2 ,
где x 1 и x 2 – корни квадратного трехчлена a · x 2 + b · x + c , причем x 1 < x 2 .
На данном рисунке парабола касается оси O х только в одной точке, которая обозначена как x 0 a > 0 . D = 0 , следовательно, квадратный трехчлен имеет один корень x 0 .
Парабола расположена выше оси O х полностью, за исключением точки касания координатной оси. Обозначим цветом промежутки
(− ∞ , x 0) , (x 0 , ∞) .
Запишем результаты. При a > 0 и D = 0 :
- решением квадратного неравенства a · x 2 + b · x + c > 0 является (− ∞ , x 0) ∪ (x 0 , + ∞) или в другой записи x ≠ x 0 ;
- решением квадратного неравенства a · x 2 + b · x + c ≥ 0 является (− ∞ , + ∞) или в другой записи x ∈ R ;
- квадратное неравенство a · x 2 + b · x + c < 0 не имеет решений (нет интервалов, на которых парабола расположена ниже оси O x );
- квадратное неравенство a · x 2 + b · x + c ≤ 0 имеет единственное решение x = x 0 (его дает точка касания),
где x 0 - корень квадратного трехчлена a · x 2 + b · x + c .
Рассмотрим третий случай, когда ветви параболы направлены вверх и не касаются оси O x . Ветви параболы направлены вверх, что означает, что a > 0 . Квадратный трехчлен не имеет действительных корней, так как D < 0 .
На графике нет интервалов, на которых парабола была бы ниже оси абсцисс. Это мы будем учитывать при выборе цвета для нашего рисунка.
Получается, что при a > 0 и D < 0 решением квадратных неравенств a · x 2 + b · x + c > 0 и a · x 2 + b · x + c ≥ 0 является множество всех действительных чисел, а неравенства a · x 2 + b · x + c < 0 и a · x 2 + b · x + c ≤ 0 не имеют решений.
Нам осталось рассмотреть три варианта, когда ветви параболы направлены вниз. На этих трех вариантах можно не останавливаться подробно, так как при умножении обеих частей неравенства на − 1 мы получаем равносильное неравенство с положительным коэффициентом при х 2 .
Рассмотрение предыдущего раздела статьи подготовило нас к восприятию алгоритма решения неравенств с использованием графического способа. Для проведения вычислений нам необходимо будет каждый раз использовать чертеж, на котором будет изображена координатная прямая O х и парабола, которая отвечает квадратичной функции y = a · x 2 + b · x + c . Ось O у мы в большинстве случаев изображать не будем, так как для вычислений она не нужна и будет лишь перегружать чертеж.
Для построения параболы нам необходимо будет знать две вещи:
Определение 2
- направление ветвей, которое определяется значением коэффициента a ;
- наличие точек пересечения параболы и оси абсцисс, которые определяются значением дискриминанта квадратного трехчлена a · x 2 + b · x + c .
Точки пересечения и касания мы будет обозначать обычным способом при решении нестрогих неравенств и пустыми при решении строгих.
Наличие готового чертежа позволяет перейти к следующему шагу решения. Он предполагает определение промежутков, на которых парабола располагается выше или ниже оси O х. Промежутки и точки пересечения и являются решением квадратного неравенства. Если точек пересечения или касания нет и нет интервалов, то считается, что заданное в условиях задачи неравенство не имеет решений.
Теперь решим несколько квадратных неравенств, используя приведенный выше алгоритм.
Пример 1
Необходимо решить неравенство 2 · x 2 + 5 1 3 · x - 2 графическим способом.
Решение
Нарисуем график квадратичной функции y = 2 · x 2 + 5 1 3 · x - 2 . Коэффициент при x 2 положительный, так как равен 2 . Это значит, что ветви параболы будут направлены вверх.
Вычислим дискриминант квадратного трехчлена 2 · x 2 + 5 1 3 · x - 2 для того, чтобы выяснить, имеет ли парабола с осью абсцисс общие точки. Получаем:
D = 5 1 3 2 - 4 · 2 · (- 2) = 400 9
Как видим, D больше нуля, следовательно, у нас есть две точки пересечения: x 1 = - 5 1 3 - 400 9 2 · 2 и x 2 = - 5 1 3 + 400 9 2 · 2 , то есть, x 1 = − 3 и x 2 = 1 3 .
Мы решаем нестрогое неравенство, следовательно проставляем на графике обычные точки. Рисуем параболу. Как видите, рисунок имеет такой же вид как и в первом рассмотренном нами шаблоне.
Наше неравенство имеет знак ≤ . Следовательно, нам нужно выделить промежутки на графике, на которых парабола расположена ниже оси O x и добавить к ним точки пересечения.
Нужный нам интервал − 3 , 1 3 . Добавляем к нему точки пересечения и получаем числовой отрезок − 3 , 1 3 . Это и есть решение нашей задачи. Записать ответ можно в виде двойного неравенства: − 3 ≤ x ≤ 1 3 .
Ответ: − 3 , 1 3 или − 3 ≤ x ≤ 1 3 .
Пример 2
− x 2 + 16 · x − 63 < 0 графическим методом.
Решение
Квадрат переменной имеет отрицательный числовой коэффициент, поэтому ветви параболы будут направлены вниз. Вычислим четвертую часть дискриминанта D " = 8 2 − (− 1) · (− 63) = 64 − 63 = 1 . Такой результат подсказывает нам, что точек пересечения будет две.
Вычислим корни квадратного трехчлена: x 1 = - 8 + 1 - 1 и x 2 = - 8 - 1 - 1 , x 1 = 7 и x 2 = 9 .
Получается, что парабола пересекает ось абсцисс в точках 7 и 9 . Отметим эти точки на графике пустыми, так как мы работаем со строгим неравенством. После этого нарисуем параболу, которая пересекает ось O х в отмеченных точках.
Нас будут интересовать промежутки, на которых парабола располагается ниже оси O х. Отметим эти интервалы синим цветом.
Получаем ответ: решением неравенства являются промежутки (− ∞ , 7) , (9 , + ∞) .
Ответ: (− ∞ , 7) ∪ (9 , + ∞) или в другой записи x < 7 , x > 9 .
В тех случаях, когда дискриминант квадратного трехчлена равен нулю, необходимо внимательно подходить к вопросу о том, стоит ли включать в ответ абсциссы точки касания. Для того, чтобы принять правильное решение, необходимо учитывать знак неравенства. В строгих неравенствах точка касания оси абсцисс не является решением неравенства, в нестрогих является.
Пример 3
Решите квадратное неравенство 10 · x 2 − 14 · x + 4 , 9 ≤ 0 графическим методом.
Решение
Ветви параболы в данном случае будут направлены вверх. Она будет касаться оси O х в точке 0 , 7 , так как
Построим график функции y = 10 · x 2 − 14 · x + 4 , 9 . Ее ветви направлены вверх, так как коэффициент при x 2 положительный, и она касается оси абсцисс в точке с абсциссой 0 , 7 , так как D " = (− 7) 2 − 10 · 4 , 9 = 0 , откуда x 0 = 7 10 или 0 , 7 .
Поставим точку и нарисуем параболу.
Мы решаем нестрогое неравенство со знаком ≤ . Следовательно. Нас будут интересовать промежутки, на которых парабола располагается ниже оси абсцисс и точка касания. На рисунке нет интервалов, которые удовлетворяли бы нашим условиям. Есть лишь точка касания 0 , 7 . Это и есть искомое решение.
Ответ: Неравенство имеет только одно решение 0 , 7 .
Пример 4
Решите квадратное неравенство – x 2 + 8 · x − 16 < 0 .
Решение
Ветви параболы направлены вниз. Дискриминант равен нулю. Точка пересечения x 0 = 4 .
Отмечаем точку касания на оси абсцисс и рисуем параболу.
Мы имеем дело со строгим неравенством. Следовательно, нас интересуют интервалы, на которых парабола расположена ниже оси O х. Отметим их синим.
Точка с абсциссой 4 не является решением, так как в ней парабола не расположена ниже оси O x . Следовательно, мы получаем два интервала (− ∞ , 4) , (4 , + ∞) .
Ответ: (− ∞ , 4) ∪ (4 , + ∞) или в другой записи x ≠ 4 .
Не всегда при отрицательном значении дискриминанта неравенство не будет иметь решений. Есть случаи, когда решением будет являться множество всех действительных чисел.
Пример 5
Решите квадратное неравенство 3 · x 2 + 1 > 0 графическим способом.
Решение
Коэффициент а положительный. Дискриминант отрицательный. Ветви параболы будут направлены вверх. Точек пересечения параболы с осью O х нет. Обратимся к рисунку.
Мы работаем со строгим неравенством, которое имеет знак > . Это значит, что нас интересуют промежутки, на которых парабола располагается выше оси абсцисс. Это как раз тот случай, когда ответом является множество всех действительный чисел.
Ответ: (− ∞ , + ∞) или так x ∈ R .
Пример 6
Необходимо найти решение неравенства − 2 · x 2 − 7 · x − 12 ≥ 0 графическим способом.
Решение
Ветви параболы направлены вниз. Дискриминант отрицательный, следовательно, общих точек параболы и оси абсцисс нет. Обратимся к рисунку.
Мы работаем с нестрогим неравенством со знаком ≥ , следовательно, интерес для нас представляют промежутки, на которых парабола располагается выше оси абсцисс. Судя по графику, таких промежутков нет. Это значит, что данное у условии задачи неравенство не имеет решений.
Ответ: Нет решений.
Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
Тип урока:
Вид урока: Лекция, урок решения задач.
Продолжительность: 2 часа.
Цели: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;С2), где C1 и C2 коэффициенты при неизвестных в целевой функции f=C1?X1+C2?X2+C0.. Если при таком перемещении линии уровня существует некоторая точка 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.
Решить графически систему неравенств. Найти угловые решения.
x1>= 0, x2>=0
> with(plots);
> with(plottools);
> S1:=solve({f1x = X6, f2x = X6}, );
Ответ: Все точки 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 Геометрическая интерпретация ограничений и ЦФ задачи.
Методика решения задач ЛП графическим методом
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.
Если неравенство истинное,
то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси, т.е. в I-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
III. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны .
VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора, при поиске минимума ЦФ - против направления вектора. Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.
Решить задачу линейного программирования
1. f(x)=2x1+x2 ->extr
x1>= 0, x2>=0
> plots({a+b<=3,a+3*b<=5,5*a-b<=5,a+b>=0,a>=0,b>=0}, a=-2..5, b=-2..5, optionsfeasible=(color=red),
optionsopen=(color=blue, thickness=2),
optionsclosed=(color=green, thickness=3),
optionsexcluded=(color=yellow));
> with(simplex):
> C:={ x+y <=3, x+3*y <=5, 5*x-y <=5,x+y >=0};
> dp:=setup({ x+y <=3, x+3*y <=5, 5*x-y <=5,x+y >=0});
> n:=basis(dp);
Ш display(C,);
> L:=cterm(C);
Ш X:=dual(f,C,p);
Ш f_max:=subs(R,f);
Ш R1:=minimize(f,C ,NONNEGATIVE);
f_min:=subs(R1,f);
ОТВЕТ: При x 1 =5/4 x 2 =5/4 f_max=15/4; При x 1 =0 x 2 =0 f_min=0;
Урок № 5.Решение матричных игр, используя методы линейного программирования и симплекс метод
Тип урока: урок контроль + урок изучения нового материала. Вид урока : Лекция.
Продолжительность: 2 часа.
Цели:1) Проверить и закрепить знания по прошедшему материалу на прошлых уроках.
2) Изучить новый метод решения матричных игр.
3) развить память, математическое мышление и внимание.
1 этап: проверить домашнее задание в виде самостоятельной работы.
2 этап: дать краткое описание метода зигзага
3 этап: закрепить новый материал и дать домашнее задание.
Ход занятия.
Методы линейного программирования - численные методы решения оптимизационных задач, cводящихся к формальным моделям линейного программирования.
Как известно, любая задача линейного программирования может быть приведена к канонической модели минимизации линейной целевой функции с линейными ограничениями типа равенств. Поскольку число переменных в задаче линейного программирования больше числа ограничений (n > m), то можно получить решение, приравняв нулю (n - m) переменных, называемых свободными . Оставшиеся m переменных, называемых базисными , можно легко определить из системы ограничений-равенств обычными методами линейной алгебры. Если решение существует, то оно называется базисным . Если базисное решение допустимо, то оно называется базисным допустимым . Геометрически, базисные допустимые решения соответствуют вершинам (крайним точкам) выпуклого многогранника, который ограничивает множество допустимых решений. Если задача линейного программирования имеет оптимальные решения, то по крайней мере одно из них является базисным.
Приведенные соображения означают, что при поиске оптимального решения задачи линейного программирования достаточно ограничиться перебором базисных допустимых решений. Число базисных решений равно числу сочетаний из n переменных по m:
С = m n! / n m! * (n - m)!
и может быть достаточно велико для их перечисления прямым перебором за реальное время. То, что не все базисные решения являются допустимыми, существо проблемы не меняет, так как чтобы оценить допустимость базисного решения, его необходимо получить.
Проблема рационального перебора базисных решений задачи линейного программирования была впервые решена Дж. Данцигом. Предложенный им симплекс-метод до настоящего времени является наиболее распространенным общим методом линейного программирования. Симплекс-метод реализует направленный перебор допустимых базисных решений по соответствующим им крайним точкам выпуклого многогранника допустимых решений в виде итеративного процесса, где на каждом шаге значения целевой функции строго убывают. Переход между крайними точками осуществляется по ребрам выпуклого многогранника допустимых решений в соответствии с простыми линейно-алгебраическими преобразованиями системы ограничений. Поскольку число крайних точек конечно, а целевая функция линейна, то перебирая крайние точки в направлении убывания целевой функции, симплекс-метод за конечное число шагов сходится к глобальному минимуму.
Практика показала, что для большинства прикладных задач линейного программирования симплекс-метод позволяет отыскать оптимальное решение за относительно небольшое число шагов по сравнению с общим числом крайних точек допустимого многогранника. В тоже время известно, что для некоторых задач линейного программирования со специально подобранной формой допустимой области, применение симплекс-метода приводит к полному перебору крайних точек. Этот факт в известной мере стимулировал поиск новых эффективных методов решения задачи линейного программирования, построенных на иных, нежели симплекс-метод, идеях, позволяющих решать любую задачу линейного программирования за конечное число шагов, cущественно меньшее числа крайних точек.
Cреди полиномиальных методов линейного программирования, инвариантных к конфигурации области допустимых значений, наиболее распростаненным является метод Л.Г. Хачияна. Однако, хотя этот метод и имеет полиномиальную оценку сложности в зависимости от размерности задачи, тем не менее он оказывается неконкурентноспособным по сравнению с симплекс-методом. Причина этого в том, что зависимость числа итераций симплекс-метода от размерности задачи выражается полиномом 3-го порядка для большинства практических задач, в то время как в методе Хачияна, эта зависимость всегда имеет порядок, не ниже четвертого. Указанный факт имеет решающее значение для практики, где сложные для симплекс-метода прикладные задачи встречаются крайне редко.
Cледует также отметить, что для важных в практическом смысле прикладных задач линейного программирования разработаны специальные методы, учитывающие конкретный характер ограничений задачи. B частности, для однородной транспортной задачи применяются специальные алгоритмы выбора начального базиса, наиболее известными из которых являются метод северо-западного угла и приближенный метод Фогеля, а сама алгоритмическая реализация симплекс-метода приближена к специфике задачи. Для решения задачи линейного назначении (задачи выбора) вместо симплекс-метода обычно применяется либо венгерский алгоритм, основанный на интерпретации задачи в терминах теории графов как задачи поиска максимального по весу совершенного паросочетания в двудольном графе, либо метод Мака.
Решить матричную игру размера 3х3
f(x)=x 1 +x 2 +x 3
x1>= 0, x2>=0, x3>=0
> with(simplex):
> C:={ 0*x+3*y+2*z <=1, 2*x+0*y+1*z <=1, 3*x+0*y+0*z <=1};
Ш display(C,);
> feasible(C, NONNEGATIVE , "NewC", "Transform");
> S:=dual(f,C,p);
ШR:=maximize(f,C ,NONNEGATIVE);
Ш f_max:=subs(R,f);
Ш R1:=minimize(S ,NONNEGATIVE);
> G:=p1+p2+p3;
> f_min:=subs(R1,G);
Найдём цену игры
> V:=1/f_max;
Найдём оптимальную стратегию первого игрока > X:=V*R1;
Найдём оптимальную стратегию второго игрока
ОТВЕТ: При X=(3/7, 3/7,1/7) V=9/7; При Y=(3/7,1/7,3/7) V=9/7;
Каждому ученику даётся один из 20 вариантов, в котором ученику предлагается самостоятельно решить матричную игру 2x2, а остальные примеры в качестве домашнего задания.
Графический метод заключается в построении множества допустимых решений ЗЛП, и нахождении в данном множестве точки, соответствующей 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 смещаются по вектору нормали. Если при таком перемещении линии уровня существует некоторая точка X - первая общая точка области допустимых решений (многогранник ABCDE) и линии уровня, то f(X) - минимум f на множестве ABCDE. Если X - последняя точка пересечения линии уровня и множества ABCDE то f(X) - максимум на множестве допустимых решений. Если при а>-? прямая f=a пересекает множество допустимых решений, то min(f)= -?. Если это происходит при а>+?, то max(f)=+ ?.
Загрузка...
