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

Лекция №2. Геометрический метод решения задач линейного программирования Наиболее наглядным методом решения задач линейного программирования является геометрический метод. Исходя из названия метода ясно, что отыскание оптимального плана (оптимального решения) будет происходить в двумерной координатной плоскости (декартовой системе координат). Зная о том, что задача линейного программирования задается системой ограничений и линейной целевой функцией, которой необходимо доставить максимум (минимум), в системе координат необходимо ограничить область допустимых решений и определить точку или множество точек, доставляющих максимум (минимум) линейной целевой функции. Существует некоторая особенность в использовании геометрического метода: он применяется для решения задач ЛП с двумя переменными, заданных в стандартной форме (под стандартной формой подразумевается задача ЛП, в которую входят линейная целевая функция, которую необходимо максимизировать (минимизировать) и система ограничений, представленная неравенствами). Однако сказать о том, что геометрический метод возможно применить только для задач ЛП с двумя переменными нельзя. Решение задач со многими переменными существуют, но в том случае, если они приведены к каноническому виду (при условии, что имеется не более двух свободных переменных). Переход от стандартной формы задачи ЛП к ее каноническому виду и обратно мы рассмотрим в следующей лекции, а сейчас освоим геометрический метод решения задач ЛП. Алгоритм решения задач геометрическим методом следующий: 1. Необходимо построить область допустимых решений (ОДР) исходя из существующей системы ограничений; 2. Необходимо определить вектор-градиент, демонстрирующий направление наискорейшего изменения целевой функции; 3. Необходимо построить перпендикуляр к вектору-градиенту; 4. Необходимо переместить линию уровня целевой функции (перпендикуляр к вектору-градиенту) вдоль вектора-градиента. Линию уровня целевой функции необходимо двигать вдоль вектора-градиента до пересечения с единственной точкой ОДР. Эта точка – точка экстремума целевой функции в ОДР и является оптимальным решением задачи ЛП. 5. Необходимо определить координаты точки экстремума и величину линейной целевой функции. Может сложиться ситуация, когда линия уровня целевой функции параллельна одной из сторон ОДР. Это означает, что задача ЛП имеет бесчисленное множество решений (находящихся на одной из грани ОДР, которой параллельна линия целевой функции). Задача ЛП может не иметь решения, если система ограничений, которая образует ее ОДР, окажется не совместной. Такая ситуация редко достижима, но все-таки возможна. В реальной экономики может быть выражена, например, в неполном учете используемых ресурсов в производстве. Рассмотрим решение задачи ЛП геометрическим методом на примере. Задача 3. Предприятие изготавливает и реализует два вида продукции и . Для производства продукции используются два вида ресурсов – сырье и труд. Максимальные запасы этих ресурсов в сутки составляют 14 и 26 единиц соответственно. Расходов ресурсов на изготовление каждого вида продукции, запасы и оптовые цены продукции приведены в таблице. Ресурсы Расходы ресурсов на 1 ед. продукции Запас ресурсов, ед. Сырье 1 3 14 Труд 4 2 26 Оптовая цена 3 3 1 Известно, что суточный спрос на продукцию , никогда не превышает спроса на продукцию более чем на 5 ед., а спрос на продукцию никогда не превышает 4 ед. в сутки. Как спланировать выпуск продукции предприятия, чтобы доход от ее реализации был максимальным? Решение. Математическая модель задачи примет следующий вид: → (1.7) При ограничениях на целевую функцию: { (1.7.1) (1.7.2) (1.7.3) (1.7.4) Каждое из перечисленных неравенств в двумерной координатной плоскости представляет собой прямую линию и, фактически, разделяет эту самую координатную плоскость на две полуплоскости (этот факт понадобиться в дальнейшем для определения ОДР, сейчас это нужно просто запомнить). После построения всех ограничений на координатной плоскости будет получена некоторая область вследствие пересечения прямых. Пресечение этих прямых и будет определять ОДР. Замечание. ОДР может представлять собой одну из следующих фигур: выпуклый многоугольник, неограниченная многоугольная область, луч, отрезок, точка или пустая область. В случае пустой области ограничения являются не совместными. Для того чтобы изобразить на координатной плоскости ограничения существующей задачи необходимо перейти от системы ограничений-неравенств к системе ограничений-равенств. { Изобразим ограничения, градиент и целевую функцию на графике 1. График 1. Система ограничений, вектор-градиент и уровень линии целевой функции в точке максимума. 2 Отметим, что условие неотрицательности переменных, говорит о том, что решение задачи ЛП может находиться в первом квадранте. Важным, завершающим этапом в построении ограничений является определение ОДР (заштрихованная область). На первый взгляд можно подумать, что заштриховывается та часть пространства, в которой учтены все ограничения. Однако это не так. Чуть выше по лекции мы говорили, что каждая прямая делит координатную плоскость на две полуплоскости. Очевидно, что одна из этих полуплоскостей будет содержать начало координат (точку (0,0)), а другая – нет. Штриховку можно произвести либо в одной полуплоскости, либо в другой. Для того, чтобы определить в какой – необходимо испытать имеющиеся ограничения. Для этого нужно в каждое ограничение подставить нули и, если неравенство выполняется, то заштриховывать необходимо ту полуплоскость, в которой находится начало координат. Соответственно, если ограничение не выполняется, то есть становится неверным, то заштриховывается та полуплоскость, которая не содержит начало координат. Для того чтобы не наносить лишней мешающей заштриховки достаточно вдоль всей прямой начертить насечки. На этом ОДР можно считать определенной. Для определения оптимального плана необходимо построить вектор-градиент (пунктирная линия со стрелкой), вдоль которого будет происходить наискорейшее возрастание целевой функции. Координаты вектора-градиента соответствуют коэффициентам целевой функции. Начало вектор-градиент берет в точке (0,0) – начало координатной плоскости. Двигая линию целевой функции (прямая черного цвета) мы достигнем крайней точки ОДР в случае максимизации. Максимальным допустимым значением целевой функции будет наибольшая (дальняя) крайняя точка ОДР, в рассматриваемой задаче – это точка C. Поскольку теперь нам известно, что максимум в допустимой области (в ОДР) достигается в точке C, то необходимо определить точные координаты этой точки. Нам также известно, что точка C образуется на пересечении прямых, задаваемых первым и вторым неравенством. Выписав систему этих двух ограничений в виде равенств и решив, мы получим точные численные координаты точки максимума – точки C. { Эти значения являются оптимальным соотношение объемов первого и второго товара, которое способно принести максимальный доход в сложившихся экономических условиях, описанных в задаче. Зная координаты точки (объемы производства 1 и 2 товара), доставляющей максимум целевой функции, легко определить максимальный доход. Подставив и в L, получим: Ответ при решении задач ЛП выписывается следующим образом: На этом лекция закончена. На следующем занятии мы научимся проводить анализ задач ЛП на устойчивость полученного решения и освоим процедуру получения решения в MS Excel. Успехов в занятиях! 3