Алгоритм графического метода
Алгоритм графического методаГрафический способ решения уравнений
=== Скачать файл ===
На этом уроке будем знакомиться с графическим методом решения задач линейного программирования , то есть, таких задач, в которых требуется найти такое решения системы линейных уравнений и или неравенств системы ограничений , при котором функция цели - линейная функция - принимает оптимальное значение. Ввиду того, что наглядность графического решения достигается лишь на плоскости, мы можем познакомиться с графическим представлением задачи только в двумерном пространстве. Это представление пригодно для системы ограничений-неравенств с двумя переменными или для систем уравнений, в которых число переменных на 2 превышает число уравнений, то есть число свободных переменных равно двум. Поэтому графический метод имеет такие узкие рамки применения, что о нём как об особом методе решения задач линейного программирования говорить нельзя. Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования. Итак, задача линейного программирования. Требуется найти неотрицательные значения переменных и , удовлетворяющих системе неравенств. Из теории и практики решения систем линейных неравенств известно, что множество всех решений данной системы, то есть множество пар чисел и , удовлетворяющих системе, составляет многоугольник этой системы. Допустим, что это пятиугольник ABCDE рисунок внизу. Линейная форма графически означает семейство параллельных между собой прямых. При конкретном числовом значении F линейная форма изобразится в виде некоторой прямой. Каждую из прямых этого семейства принято называть линией уровня. Если исходную линию уровня передвигать вправо, то значение F при этом возрастает. Нужное направление движения исходной линии уровня можно установить следующим образом. Коэффициенты при переменных в уравнении прямой служат координатами вектора, перпендикулярного этой прямой. Таким образом, получаем градиент - вектор на рисунке бордового цвета. Значения функции F возрастают при перемещении исходной линии уровня в направлении вектора. Среди прямых упомянутого семейства параллельных прямых прямые mn зелёного цвета и MN красного цвета , которые назовём опорными. Опорными обычно называют такие прямые, которые имеют с многоугольником ABCDE хотя бы одну общую точку, и многоугольник ABCDE целиком лежит по одну сторону от этой прямой. Как видно из чертежа, прямая mn является опорной, так как она касается многоугольника в точке A и многоугольник целиком лежит правее или выше этой прямой. Прямая MN также является опорной, так как имеет с многоугольником общую точку С и многоугольник целиком лежит левее этой прямой. Из основных теорем линейного программирования известно, что линейная форма достигает максимального и минимального значений в крайних точках многогранника решений. Это значит, что опорные прямые mn и MN характеризуют экстремальные значения линейной формы функции цели , то есть в точках А и С линейная форма достигает оптимальных значений. В точке А , находящейся ближе к началу координат, функция цели достигает минимального значения, а в точке С , находящейся дальше от начала координат, - максимального значения. Начертить из семейства прямых, соответствующих линейной форме, линию равных значений функции цели. Для построения линии равных значений придадим F некоторое числовое значение. Запишем это уравнение прямой в отрезках:. Затем, откладывая на оси число , а на оси - число , найдём точки пересечения линии равных значений с осями координат. Прямая, проведённая через эти точки, и есть искомая прямая. Двигать прямую или линейку вдоль градиента - вектора параллельно линии равных значений в сторону многоугольника решений до соприкосновения с многоугольником решений. Если первая встреча с многоугольником решений произойдёт в крайней точке с координатами , то в этой точке функция цели достигает минимального значения. Если первая встреча произойдёт со стороной многоугольника, то данная функция цели достигает минимума во всех точках этой стороны. Двигаясь дальше, придём к некоторому опорному положению, когда прямая будет иметь одну общую точку с многоугольником решений. В этой точке функция цели достигает своего максимума. Если первоначально построенная линия равных значений пересекает многоугольник решений, то функция цели достигает минимального значения в вершине многоугольника, расположенной ближе к началу координат, а максимального значения - в вершине, более удалённой от начала координат. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях. Для этого начертим граничные прямые. Из первого неравенства запишем уравнение. Это уравнение первой граничной прямой. Найдём точки пересечения этой прямой с осями координат. При из уравнения получим , при получим. Таким образом, первая прямая отсекает от осей координат отрезки и. Аналогично строим остальные граничные прямые. Вторая прямая от осей координат отсекает отрезки, равные 6. Третья прямая проходит параллельно оси , отсекая на оси отрезок, равный 2. Четвёртая прямая имеет уравнение. Она совпадает с осью. Из рисунка ниже видно, что множество точек четырёхугольника ABDE удовлетворяет всем четырём неравенствам системы. Следовательно, четырёхугольник ABDE является многоугольником решений системы заштрихован вовнутрь. Начертим линию равных значений функции цели. Проведём прямую через эти точки на чертеже она чёрного цвета. Двигая эту прямую параллельно самой себе в направлении градиента - вектора бордового цвета , получим опорные прямые. Первая прямая зелёного цвета имеет с многоугольником общую точку A. Здесь функция цели достигает минимума. Двигаясь дальше, придём к точке В. Подставляя в функцию цели координаты точки В , т. Решить графическим методом задачу линейного программирования, в которой требуется найти минимум функции при ограничениях. Многогранником решений является открытая область. Из рисунка видно, что прямая ближайшнее от начала координат опорное положение займёт в точке В. Следовательно, в этой точке функция цели имеет минимум. Подставляя в функцию цели и , получим минимальное значение функции: На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом. До сих пор полученные выводы были основаны на том, что множество решений задачи линейного программирования сконфигурировано так, что оптимальное решение конечно и единственно. Теперь рассмотрим примеры, когда это условие нарушается. В этих примерах многоугольник решений строится так, как показано в предыдущих примерах, остановимся же на признаках, которые отличают эти исключительные примера. Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что. Изображённая на рисунке ниже область не содержит ни одной общей точки, которая бы удовлетворяла всем неравенствам системы ограничений. То есть система ограничений противоречива и не может содержать ни одного решения, в том числе и оптимального. Всем неравенствам системы ограничений удовлетворяют точки треугольника ABC , который и является областью решений. За исходную линию уровня взята прямая на рисунке ниже - чёрного цвета , с тем чтобы она пересекала область решений. При построении треугольника ABC не была использована прямая , соответствующая первому неравенству, хотя все точки треугольника удовлетворяют этому неравенству. Таким образом, этот пример отличается от предыдущих тем, что одно из неравенств системы ограничений оказалось лишним. На рисунке ниже изображены область решений системы ограничений и линия уровня чёрного цвета. Если передвигать линию уровня параллельно исходной в направлении вектора , то она выйдет из области решений не в одной точке, как это было в предыдущих примерах, а сольётся с прямой CD , которая является граничной линией области решений. Все точки отрезка CD дают одно и то же значение функции цели, которое и служит её оптимальным значением: Следовательно, имеется не одно, а бесчисленное множество оптимальных решений, совпадающих с точками отрезка CD , в частности, с двумя угловыми точками C и D. Этот пример показывает, что в некоторых случаях единственность оптимального решения нарушается. Напоследок следует заметить, что строить многогранник решений можно и другим способом, отличающимся о того, который мы рассматривали. Для этого последовательно решаются системы из двух уравнений, так, чтобы решениями были точки пересечения всех прямых. Полученные точки и будут вершинами многогранника решений. Этот способ иногда бывает удобным в случаях, когда точки пересечения прямых с осями координат - дробные числа и, неправильно отложив точку пересечения, можно получить ошибку и в поиске точек пересечения самих прямых. Графический метод решения задач линейного программирования: Требуется найти неотрицательные значения переменных и , удовлетворяющих системе неравенств при которых линейная форма принимает оптимальное значение. Запишем это уравнение прямой в отрезках: Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях Построим многоугольник решений. Нет времени вникать в решение? Решить графическим методом задачу линейного программирования, в которой требуется найти минимум функции при ограничениях Решение. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях Решение. Задача и теоремы линейного программирования, примеры формулировки задач. Пример задачи линейного программирования: Симплекс-метод решения задач линейного программирования: Двойственная задача линейного программирования. Решение задачи целочисленного программирования: Теоретические основы графического метода Схема решения задач линейного программирования графическим методом Примеры решения задач графическим методом Когда нужен графический метод? Теоретические основы графического метода Итак, задача линейного программирования. Схема решения задач линейного программирования графическим методом 1. Построить многоугольник решений системы неравенств. Примеры решения задач графическим методом Пример 1. Начало темы 'Линейное программирование' Задача и теоремы линейного программирования, примеры формулировки задач Пример задачи линейного программирования:
Приказ мю рф 177 от 03.09 2007
Где есть банкоматы россельхозбанка в калининграде
Где находится белорецкий район