- Описание метода
- Построение области допустимых решений
- Нахождение экстремума целевой функции
- Пример решения задачи линейного программирования графическим методом
- Теоретические основы графического метода
- Примеры решения ЗЛП симплекс методом
- Решить задачи графическим методом самостоятельно, а затем посмотреть решения
- Схема решения задач линейного программирования графическим методом
- Пример 2
Описание метода
Если в задаче линейного программирования всего две переменные, то ее можно решить графически.
Рассмотрим задачу линейного программирования с двумя переменными. Вот произвольные числа. Задача может заключаться в том, чтобы найти максимум (max) или найти минимум (min). В системе ограничений могут присутствовать как знаки, так и знаки .
Построение области допустимых решений
Графический метод решения задачи (1) следующий.
- Сначала нарисуем оси координат и выберем масштаб. Каждое из неравенств системы ограничений (1.2) определяет полуплоскость, ограниченную соответствующей линией.
- Следовательно, первое неравенство в (1.2.1) определяет полуплоскость, ограниченную прямой.
- По одну сторону от этой прямой и по другую. По прямой.
- Чтобы выяснить, с какой стороны выполняется неравенство (1.2.1), выберем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1).
- Если неравенство верно, полуплоскость содержит выбранную точку. Если неравенство не выполняется, полуплоскость находится с другой стороны (не содержит выбранной точки). Затенение полуплоскости, для которой выполняется неравенство (1.2.1). Проделаем то же самое с остальными неравенствами системы (1.2).
- Это даст нам заштрихованные полуплоскости. Точки области допустимых решений удовлетворяют всем неравенствам (1.2). Следовательно, графически область допустимых решений (ADS) — это пересечение всех построенных полуплоскостей. ODT-штриховка.
- Это выпуклый многоугольник, грани которого принадлежат построенным линиям. Кроме того, ODR может иметь неограниченную выпуклую форму, линейный сегмент, радиус или прямую линию.
- Может возникнуть ситуация, когда полуплоскости не содержат общих точек. Тогда область допустимых решений — пустое множество. У этой проблемы нет решения.
Метод можно упростить. Заштриховывать каждую полуплоскость необязательно, а сначала построить все прямые (2)
Затем выберите произвольную точку, которая не принадлежит ни одной из этих линий. Заменим координаты этой точки в системе неравенств (1.2). При выполнении всех неравенств область допустимых решений ограничивается построенными линиями и включает выбранную точку. Заштриховываем область допустимых решений по границам линий так, чтобы она включала выделенную точку.
Если хотя бы одно неравенство не выполняется, выбираем другую точку. И так далее, пока не найдем точку, координаты которой удовлетворяют системе (1.2).
Нахождение экстремума целевой функции
Итак, у нас есть заштрихованная область жизнеспособных решений (ODS). Он ограничен ломаной линией, состоящей из отрезков и лучей, принадлежащих построенным прямым (2). ODR — это всегда выпуклое целое. Это может быть ограниченное или неограниченное множество вдоль некоторых направлений.
Теперь мы можем найти экстремум целевой функции.
- Для этого выберите любое число и постройте прямую (3).
- Для удобства дальнейшего изложения мы предполагаем, что эта строка проходит через ODR. На этой линии целевая функция постоянна и равна этой прямой, которая называется линией уровня функции. Эта прямая делит плоскость на две полуплоскости. То есть по одну сторону линии (3) целевая функция увеличивается.
- И чем дальше мы удаляем точку от прямой (3), тем больше значение. По другую сторону линии (3) целевая функция уменьшается. И чем больше мы перемещаем точку от прямой (3) к другой стороне, тем меньше будет значение. Если провести линию, параллельную линии (3), то новая линия также будет линией уровня целевой функции, но с другим значением .
Следовательно, чтобы найти максимальное значение целевой функции, необходимо провести линию, параллельную линии (3), наиболее удаленную от нее в смысле увеличения значений и проходящую хотя бы через одну точку ODR. Чтобы найти минимальное значение целевой функции, необходимо провести линию, параллельную линии (3) и более удаленную от нее в порядке убывания значений и проходящую по крайней мере через одну точку ODR.
Если ГДР не ограничена, может возникнуть случай, когда эту прямую линию провести нельзя. То есть, как бы мы ни убирали прямую от линии уровня (3) в сторону увеличения (уменьшения), прямая линия всегда будет проходить через ODR. В этом случае он может быть сколь угодно большим (маленьким). Следовательно, не существует максимального (минимального) значения. У проблемы нет решения.
Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через вершину многоугольника ODR. По графику определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
Также может быть случай, когда прямая линия параллельна одной из граней ODR. Затем линия проходит через две вершины многоугольника ODR. Определите координаты этих вершин. Для определения максимального (минимального) значения целевой функции можно использовать координаты любой из этих вершин.
Проблема имеет бесконечное количество решений. Решением является любая точка, расположенная на отрезке между точками и, включая сами точки.
Пример решения задачи линейного программирования графическим методом
Компания производит одежду двух моделей А и Б. При этом используются три вида ткани. Для изготовления костюма модели А требуется 2 м ткани первого типа, 1 м ткани второго типа и 2 м ткани третьего типа. Для изготовления костюма модели B требуется 3 м ткани первого типа, 1 м ткани второго типа, 2 м ткани третьего типа. Запасы ткани первого типа — 21 м, второго типа — 10 м, третьего типа — 16 м. Выпуск изделия типа А приносит доход 400 ед. Ден, изделия типа Б — 300 ед. Ден
Разработайте производственный план, который обеспечит компании максимальный доход. Решите проблему графически.
Решение
- Пусть переменные и указывают количество произведенных платьев моделей A и B соответственно. Таким образом, количество израсходованной ткани первого типа будет: (м)
- Количество израсходованной ткани второго типа составит: (м)
- Количество израсходованной ткани третьего типа составит: (м)
- Потому что количество произведенной одежды не может быть отрицательным.
- Доход от произведенной одежды составит: (денежные единицы.)
Тогда экономико-математическая модель проблемы имеет вид:
- Решаем это графически.
- Рисуем оси координат и .
Построим прямую .
Проведите прямую линию через точки (0; 7) и (10,5; 0).
Построим прямую .
Проведите прямую линию через точки (0; 10) и (10; 0).
Построим прямую .
Проведите прямую линию через точки (0; 8) и (8; 0).
Прямые линии — оси координат.
Область возможных решений (ODS) ограничена построенными прямыми и осями координат. Чтобы узнать, с какой стороны, отметим, что точка принадлежит ODR, поскольку удовлетворяет системе неравенств:
Заштрихуйте область так, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.
Построим произвольную линию уровня целевой функции, например (П1.1) .
Проведите прямую линию через точки (0; 4) и (3; 0).
Отметим также, что, поскольку коэффициенты at и целевой функции положительны (400 и 300), то они увеличиваются с увеличением e. Мы проводим линию, параллельную прямой (A1.1), наиболее удаленную от нее в восходящем направлении и проходящую хотя бы через одну точку четырехугольника OABC. Эта линия проходит через точку C. По построению определяем ее координаты. То есть для получения наибольшего дохода необходимо изготовить 8 платьев модели А. В этом случае доход составит 3200 ден
Теоретические основы графического метода
Отсюда проблема линейного программирования. Необходимо найти неотрицательные значения переменных и, удовлетворяющие системе неравенств, для которых линейная форма принимает оптимальное значение.
из теории и практики решения систем линейных неравенств известно, что множество всех решений данной системы, то есть множество пар чисел, удовлетворяющих системе, составляет многоугольник этой системы. Допустим, это пятиугольник ABCDE (фото ниже).
Под линейной формой мы понимаем графически семейство прямых, параллельных друг другу. Для определенного числового значения F линейная форма будет представлена в виде определенной прямой линии. Каждую из прямых линий этого семейства обычно называют линией уровня. На рисунке показана линия уровня (черная, проходящая через начало координат), соответствующая значению F = 0.
Если линия исходного уровня сдвинута вправо, значение F увеличивается. Желаемое направление движения линии опорного уровня можно задать следующим образом. Коэффициенты переменных в уравнении прямой служат координатами вектора, перпендикулярного этой прямой. Таким образом, у нас получается градиент — вектор (на фото бордовый). Значения функции F увеличиваются по мере перемещения исходной линии слоя в направлении вектора .
Между линиями вышеупомянутого семейства параллельных прямых находятся линии mn (зеленый) и MN (красный), которые мы будем называть опорными. Опорными линиями обычно называют те линии, которые имеют хотя бы одну общую точку с многоугольником ABCDE, а многоугольник ABCDE полностью лежит по одну сторону от этой линии.
Как видно из рисунка, линия mn является опорной линией, поскольку она касается многоугольника в точке A, и весь многоугольник находится справа (или выше) от этой линии. Линия MN также является линией поворота, поскольку у нее есть точка C, общая с многоугольником, и многоугольник находится полностью слева от этой линии.
из основных теорем линейного программирования известно, что линейная форма достигает своих максимальных и минимальных значений в крайних точках многогранника решений. Это означает, что опорные линии mn и MN характеризуют крайние значения линейной формы (целевой функции), т.е в точках A и C линейная форма достигает своих оптимальных значений. В точке A, наиболее близкой к началу координат, целевая функция достигает своего минимального значения, а в точке C, наиболее удаленной от начала координат, достигает своего максимального значения.
Примеры решения ЗЛП симплекс методом
Пример 1. Решите следующую задачу линейного программирования:
Матрица решений коэффициентов
система уравнений имеет вид:
Правая часть системы уравнений ограничений выглядит следующим образом:
Реализация симплексной таблицы. Столбец x0 содержит правую часть ограничений. Справа запишите матрицу коэффициентов A. Последняя строка — это целевая функция, умноженная на -1. Последние три вектора-столбца образуют основу в трехмерном пространстве. Следовательно, основные переменные и свободные переменные :
Запишем текущий базовый план:
Этот базовый план не оптимален, потому что в последней строке есть отрицательные элементы. Наибольший отрицательный элемент по модулю (-3), поэтому вектор x2 включен в базу. Определите, какой вектор покидает базу. Для этого рассчитаем к . min (40: 6, 28: 2) = 20/3 соответствует строке 1. Вектор x3 выходит из основания. Мы выполняем исключение Гаусса для столбца x2, так как сводная точка соответствует строке 1. Она очищает все элементы этого столбца, кроме стержня. Для этого сложите строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2 соответственно. Далее делим линию булавкой на булавку.
Симплексная таблица будет выглядеть так:
Запишем текущий базовый план:
Эта базовая плоскость не является оптимальной, так как последняя строка содержит отрицательный элемент (-3), поэтому вектор x1 включен в базу. Определите, какой вектор покидает базу. Для этого рассчитаем к . min (44/3: 11/3, 62/3: 5/3) = 4 соответствует строке 2. Вектор x4 выходит из основания. Мы выполняем исключение Гаусса для столбца x1, так как сводная точка соответствует строке 2. Она очищает все элементы этого столбца, кроме стержня. Для этого сложите строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11 соответственно. Далее делим линию булавкой на булавку.
Симплексная таблица будет выглядеть так:
Запишем текущий базовый план:
Текущая опорная плоскость оптимальна, как показано в строках 4 под переменными
нет отрицательных элементов.
Решение можно записать так:
.
Значение целевой функции в этой точке: F (X)=
.
Пример 2. Найти максимум функции
в состоянии
Матрица решений коэффициентов
система уравнений имеет вид:
Правая часть системы уравнений ограничений выглядит следующим образом:
Реализация симплексной таблицы. Столбец x0 содержит правую часть ограничений. Справа запишите матрицу коэффициентов A. Последняя строка — это целевая функция, умноженная на -1:
Базовыми векторами являются x4, x3, поэтому все элементы в столбцах x4, x3 ниже горизонтальной линии должны быть нулевыми.
Установите все элементы столбца x4 на ноль, кроме оси поворота. Для этого добавьте строку 3 со строкой 1, умноженной на 4. Обнулите все элементы столбца x3, кроме стержня. Для этого добавьте строку 3 со строкой 2 на 1.
Симплексная таблица примет вид:
Запишем текущий базовый план:
Эта базовая плоскость не оптимальна, так как последняя строка содержит отрицательный элемент (-11), поэтому вектор x2 включен в базу. Определите, какой вектор покидает базу. Для этого рассчитаем
к … Все
следовательно, целевая функция не ограничена сверху. Те проблема линейного программирования неразрешима.
Решить задачи графическим методом самостоятельно, а затем посмотреть решения
Пример 3. Графическое решение задачи линейного программирования, в которой необходимо найти максимум функции при ограничениях
Пример 4. Графическое решение задачи линейного программирования, в которой необходимо найти минимум функции при ограничениях
Схема решения задач линейного программирования графическим методом
- Постройте многоугольник решений системы неравенств.
- Проведите линию равных значений целевой функции из семейства прямых линий, соответствующих линейной форме. Чтобы построить линию равных значений, мы даем F числовое значение. Во многих задачах удобно считать, что F = 1. Тогда получаем. Запишем это уравнение прямой отрезками:
- Затем, откладывая число на оси и число на оси, находим точки пересечения линии равных значений с осями координат. Линия, проведенная через эти точки, является необходимой линией.
- Переместите прямую (или линейку) вдоль вектора градиента, параллельного линии равных значений, в сторону многоугольника решения, пока она не коснется многоугольника решения. Если первое столкновение с многоугольником решений происходит в крайней точке с координатами, то в этой точке целевая функция достигает минимального значения. Если первая встреча происходит с одной стороной многоугольника, эта целевая функция достигает своего минимума во всех точках на этой стороне.
- Двигаясь дальше, мы приходим к определенной опорной позиции, когда линия будет иметь общую точку с многоугольником решения. В этот момент целевая функция достигает максимума.
- Если первоначально построенная линия равных значений пересекает многоугольник решения, целевая функция достигает своего минимального значения в вершине многоугольника, ближайшего к исходной точке, и своего максимального значения в вершине, наиболее удаленной от исходной точки.
Пример 2
Решите задачу линейного программирования с помощью графического метода.
Решение
- Решаем это графически. Рисуем оси координат.
- Построим прямую .Проведите линию через точки (0; 6) и (6; 0).
- Построим прямую .
- Проведите линию через точки (3; 0) и (7; 2).
- Построим прямую .
- Строим прямую (ось абсцисс).
- Область допустимых решений (ODD) ограничена построенными линиями. Чтобы узнать, с какой стороны, отметим, что точка принадлежит ODR, поскольку удовлетворяет системе неравенств:
- Заштрихуем участок по границам построенных линий так, чтобы точка (4; 1) попала в заштрихованную часть. Получается треугольник ABC.
- Построим произвольную линию уровня целевой функции, например,
- Проводим прямую линию уровня через точки (0; 6) и (4; 0).Поскольку целевая функция увеличивается с увеличением e, то мы
- проводим прямую линию, параллельную линии уровня и как можно дальше от нее в направлении увеличения, проходящую хотя бы через одну точку треугольника ABC. Эта линия проходит через точку C. По построению определяем ее координаты.