Решение задач линейного программирования графическим методом
Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид: a11x1 + a12x2 + … + a1nxn ≥ b1; a21x1 + a22x2 + … + a2nxn ≥ b2; (1.3.1.) ……………………………… аm1x1 + am2x2 + … + amnxn ≥ bm; и являются линейно-независимыми. Последнее означает, никакое из них нельзя представить в виде линейной комбинации других. Требуется найти xi ≥ 0, которые удовлетворяют неравенствам и обращают в минимум L= Введём уравнения: = = (1.3.2) =
x1 , x2, …, xn являются неотрицательными. Таким образом, имеем общую задачу линейного программирования - найти неотрицательные x1 , x2, …, xn y1, y2, …, yn, чтобы они удовлетворяли системе уравнений (1.3.2.) и обращали в минимум L= Коэффициенты в формуле (1.3.2.) перед yj равны нулю. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и Целевую Функцию задачи. Каждое из неравенств задачи линейного программирования (1.3.1.) определяет на координатной плоскости (x1Ox2) некоторую полуплоскость (рис.1.3.1), а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.3.1.) ОДР является пустым множеством. Все вышесказанное относится и к случаю, когда система ограничений (1.3.1.) включает равенства, поскольку любое равенство ai1x1 + ai2x2 = bi можно представить в виде системы двух неравенств (см. рис.1.3.1) (1.3.3.) ЦФ L(x)=c1x1+c2x2 при фиксированном значении L(x)=L определяет на плоскости прямую линию c1x1+c2x2=L . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня. Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси Ox2 (начальная ордината), а угловой коэффициент прямой tg останется постоянным (см.рис. 1.3.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L. Вектор = (c1, c2) координатами из коэффициентов ЦФ при x1 и x2 перпендикулярен к каждой из линий уровня (см. рис.1.3.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направлениеубывания ЦФ противоположно направлению вектора . Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки x* = (x1* , x2*). Оптимальной считается точка, через которую проходит линия уровня Lmax(Lmin), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне. При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений. Рисунок 1.3.1 Геометрическая интерпретация ограничений и ЦФ задачи.
Задача №1. Пример решения задач линейного программирования симплекс–методом.* Решение. Приводим задачу к каноническому виду. Для этого в левую часть правого ограничения вводим дополнительные переменные Х4 , Х5 и Х6 с коэффициентом +1. В целевую функцию переменные Х4 , Х5 и Х6 входят с коэффициентом 0. Получим:
Находим начальное опорное решение. Для этого свободные переменные приравниваем к 0. Получаем опорное решение. С единичным базисом Б1. Вычисляем оценки разложения векторов условий по базису опорного решения по формуле. : Сб = (с1, с2, ... , сm ) — вектор коэффициентов целевой функции при базисных переменных Xk = (x1k, x2k, ... , xmk ) — вектор разложения соответствующего вектора Аk по базису опорного решения Сk — коэффициент целевой функции при переменной хk.
Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу:
Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "Сб" записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "Сб" оценки единичных векторов, входящих в базис, всегда равных нулю. В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1). Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -52, Δ2= -44, Δ3= -41 для векторов А1, А2 и А3 отрицательные. По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше. Определим, введение какого из двух векторов приведет к большему приращению целевой функции. Приращение функции находится по формуле: Вычислим значение D по формуле: Полученные значения записываем в таблицу. Находим приращение целевой функции при введении в базис первого вектора Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А1 вместо первого вектора базиса А6, так как минимум параметра D01 достигается в третьей строке . Производим преобразование Жордана с элементом Х31 =401 , получаем второе опорное решение Х2 = (2.3;0;0;36.7;281.7;0) с базисом Б2 = (А4, А5, А1).
Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные Δ2 = 15.8, Δ3 = 20.36, Δ6 = 0.13. Ответ: max f(X)=119.6 при Х=(2.3;0;0;36.7;281.7;0)
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (629)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |