ЛП: найти такие значения x1,x2…xn, удовлетворяющие системе ограничений, условиям неотрицательности и обеспечивающие минимум (максимум) линейной функции Z, называемой целевой. Вектор xx1,x2…xn называют решением или планом задачи линейного программирования. Допустимое решение – решение, которое не противоречит условиям задачи. План, при котором целевая функция достигает своего максимального (минимального) значения, называется оптимальным.
Непустое множество планов канонической задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.
Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым. Совокупность решений системы ограничений при условии их совместности, образует выпуклые множества с конечным числом угловых точек. В частном случае, когда в систему ограничений – неравенств входят только две переменные x1 и x2 это множество можно изобразить на плоскости.
Теорема 2. (о выпуклости планов). Множество всех планов задачи линейного программирования выпукло (если оно не пусто).
Теорема 3. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.
Теорема 4. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений, и наоборот.
Сформулированные теоремы позволяют сделать следующие выводы:
1) существует такая угловая точка многогранника G, в которой линейная функция достигает своего оптимального решения (минимума);
2) каждый опорный план соответствует угловой точке G;
3) с каждой угловой точкой G связаны m линейно независимых векторов из данной системы n векторов.
Из этого можно заключить, что необходимо исследовать лишь угловые точки многогранника решений, т. е. только опорные планы.
Распространенные методы решения ЗЛП – симплексный и графический.
Например. Графический метод
Найти максимум целевой функции L =6x+y при следующих ограничениях:
x-2y≤38x+13y≤104x≤5y≤2,5x≥0;y≥0
Решить задачу при дополнительном условии (ДУ):
ДУ: Найти минимум целевой функции L1=x-y при тех же ограничениях.
На странице представлен фрагмент работы. Его можно использовать, как базу для подготовки.
Часть выполненной работы
Решим неравенство графическим способом. Введем на плоскости прямоугольную систему координат XOY, в которой точки с координатами x≥0;y≥0 находятся в первом квадранте этой координатной плоскости.
Графическое решение неравенства типа ax+by≤c определяет одну из полуплоскостей, на которые прямая ax+by=c делит координатную плоскость. Решением неравенства будет та полуплоскость все точки которой будут ему удовлетворять.
Исходя из этого, рассмотрим каждое, из приведенной выше системы, неравенство. Решением каждого из них будет соответствующая ему полуплоскость, а решением системы будет область, образованная пересечением всех найденных полуплоскостей – область допустимых решений. Графическое решение нашей системы приведено на рисунке 1.
Здесь прямая a, соответствует уравнению x-2y=3. Построена она по двум точкам (3;0) и (5;1) и точка A(1;1), удовлетворяющая нашему первому неравенству x-2y≤3, определяет в качестве решения полуплоскость, лежащую выше прямой a. Аналогично решением второго неравенства 8x+13y≤104 является полуплоскость, лежащая ниже прямой b, соответствующей уравнению 8x+13y=104, решением третьего неравенства является полуплоскость , находящаяся слева от прямой c: x=5, а решением четвертого, полуплоскость ниже прямой d: y=2,5. Решением же системы является в нашем случае область BCDE, которая была образована пересечением четырех, выше найденных полуплоскостей. Область BCDE образует область допустимых решений или допустимых планов нашей задачи, в которой мы и будем искать оптимальное решение L =6x+y→max. Для этого построим вектор n=grad L(x,y), который укажет направление наибольшего возрастания целевой функции. n=6;1.
Линии, перпендикулярные этому вектору – L(x,y)=const, которые называются линиями уровня, задают одно из возможных значений целевой функции. На графике одно из этих уравнений, например 6x+y=31, задает прямую (показана пунктиром), которой соответствует значение L=31. Максимальное же значение целевой функции будет соответствовать, такой линии уровня, которая будет получена путем параллельного переноса одной из линий уровня, проходящей через область допустимых планов BCDE, в пограничную область BCDE в направлении вектора n=6;1=grad L. В нашем случае максимум целевой функции достигается в точке C, которая является точкой пересечения прямых c-x=5 и d-y=2,5. Координаты точки C=(4;2,5) и Lmax=6∙5+2,5=32,5.
1143031432500Рисунок 1.
Графическое решение неравенства типа ax+by≤c определяет одну из полуплоскостей, на которые прямая ax+by=c делит координатную плоскость. Решением неравенства будет та полуплоскость все точки которой будут ему удовлетворять.
Исходя из этого, рассмотрим каждое, из приведенной выше системы, неравенство. Решением каждого из них будет соответствующая ему полуплоскость, а решением системы будет область, образованная пересечением всех найденных полуплоскостей – область допустимых решений. Графическое решение нашей системы приведено на рисунке 1.
Здесь прямая a, соответствует уравнению x-2y=3. Построена она по двум точкам (3;0) и (5;1) и точка A(1;1), удовлетворяющая нашему первому неравенству x-2y≤3, определяет в качестве решения полуплоскость, лежащую выше прямой a. Аналогично решением второго неравенства 8x+13y≤104 является полуплоскость, лежащая ниже прямой b, соответствующей уравнению 8x+13y=104, решением третьего неравенства является полуплоскость , находящаяся слева от прямой c: x=5, а решением четвертого, полуплоскость ниже прямой d: y=2,5. Решением же системы является в нашем случае область BCDE, которая была образована пересечением четырех, выше найденных полуплоскостей. Область BCDE образует область допустимых решений или допустимых планов нашей задачи, в которой мы и будем искать оптимальное решение L =6x+y→max. Для этого построим вектор n=grad L(x,y), который укажет направление наибольшего возрастания целевой функции. n=6;1.
Линии, перпендикулярные этому вектору – L(x,y)=const, которые называются линиями уровня, задают одно из возможных значений целевой функции. На графике одно из этих уравнений, например 6x+y=31, задает прямую (показана пунктиром), которой соответствует значение L=31. Максимальное же значение целевой функции будет соответствовать, такой линии уровня, которая будет получена путем параллельного переноса одной из линий уровня, проходящей через область допустимых планов BCDE, в пограничную область BCDE в направлении вектора n=6;1=grad L. В нашем случае максимум целевой функции достигается в точке C, которая является точкой пересечения прямых c-x=5 и d-y=2,5. Координаты точки C=(4;2,5) и Lmax=6∙5+2,5=32,5.
1143031432500Рисунок 1.
Аналогично будем искать минимум целевой функции L1=x-y.
Для этого построим вектор n=grad L1(x,y), который укажет направление наибольшего убывания целевой функции. n=1;-1.
И одну из линий уровня L1, имеющую уравнение x-y=0 (на рисунке показана пунктиром). Далее будем перемещать ее против направления вектора n=1;-1 (так как ищем минимум), перпендикулярно ему, до границы области допустимых планов BCDE. Последней точкой этой области, через которую проходит наша прямая L1 и в которой она достигает своего минимального значения будет точка B. Эта точка является пересечением прямых d_y=2,5 и x=0. Координаты точки D0;2,5.
L1min=0-2,5=-2,5.
Ответ. Lmax=32,5; L1min=-2,5….
maxprov 3.9
Окончил СГУПС, прошел курсы по психологии общения, основам современного менеджмента. Особый интерес проявляю к юриспруденции (Уголовное, гражданское право, прокурорский надзор). Прекрасно владею гуманитарными науками!
На странице представлен фрагмент
Уникализируй или напиши новое задание с помощью нейросети
