Графический способ решения ЗЛП
Графический способ решения применим к ЗЛП в следующей постанвке: 1) целевая функция f→max(min); 2) ограничения должны быть записаны в виде неравенств, не обязательно одного знака; 3) число переменных n≤3. Для простоты изложения рассмотрим случай n=2. Выясним геометрический смысл неравенств, их решений и решений систем неравенств, то есть геометрический смысл системы ограничений. Доказана теорема: множество решений неравенства с двумя переменными является одной из двух полуплоскостей, на которые вся плоскость делится прямой
включая и эту прямую, а другая половина плоскости с той же прямой есть множество решений неравенства Пример. Построить множество решений неравенства: а) Решение. В соответствии с теоремой множество решений неравенства есть полуплоскость. а) Построим границу полуплоскости – прямую Для определения искомой полуплоскости (верхней или нижней) рекомендуется задать произвольную контрольную точку, не лежащую на её границе – построенной прямой. Если неравенство выполняется в контрольной точке, то оно выполняется во всех точках полуплоскости, содержащей контрольную точку, и не выполняется во всех точках другой полуплоскости. И наоборот, в случае невыполнения неравенства в контрольной точке оно не выполняется во всех точках полуплоскости, содержащей контрольную точку, и выполняется во всех точках другой полуплоскости. В качестве контрольной точки удобно взять начало координат
б)Построим границу полуплоскости — прямую 3х1-2х2=0 по двум точкам (рис. 2). Одной из этих точек является начало коорди- Пример, Построить множество решений системы неравенств Для каждой прямой (границы полуплоскости) находим точки пересечения с осями координат и определяем соответствующую полуплоскость:
Множеством всех решений системы неравенств – пересечение соответствующих полуплоскостей – треугольник АВС (рис. 3). (рис. 3) Если учесть условия неотрицательности х1 >о; х2>0, то областью допустимых решений будет та часть треугольника АВС, которая находится в первой четверти, т.е. ОДВСЕ — многоугольник
Итак, в общем случае множество всех допустимых решений системы ограничений ЗЛП при n = 2 — многоугольник решений — является выпуклым многоугольником (рис. З) или, в частности, выпуклой многоугольной областью (рис. 4).
Ответ на вопрос. В какой точке многоугольника решений возможно оптимальное решение ЗЛП, дается следующей Фундаментальной Рассмотрим целевую функцию F(х1,х2)= с1х1+с2х2. Она является линейной функцией двух переменных х1, х2. В математическом анализе функций нескольких переменных вводятся понятия линии уровня функции нескольких переменных и градиента функции нескольких переменных. Линией у ровня функции двух переменных называется множество точек плоскости, в которых функция сохраняет одно и то же значение, т. е. f(х1, х2)= d или f(х1,x2)= с1х1+ с2х2=d, d=const. Линии уровня широко используются, например, на картах прогноза погоды (изотермы). Еще более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты. Он обладает следующими свойствами: 1) 2) Если функция перпендикулярный линиям уровня. Важное свойство линий уровня линейной функции в том, что при параллельном смещении линии в направлении вектора Используя все вышеизложенное, сформулируем порядок решения ЗЛП графическим способом. 1. 3аписать задачу в следующей форме: Г - шах или. - т г., 2. Построить многоугольник решений. 3. Из начала координат построить вектор
4. Решив соответствующую систему уравнений, найти координаты оптимального решения (плана). 5. Вычислить максимальное (минимальное) значение целевой функции и записать ответ. Пример. Решить графически: f = -2x1 – 3x2 → min, при ограничениях x1 – 5x2 ≤ 5, x1 – x2 ≥ -4, x1 + x2 ≤8, x1 ≥ 0, x2 ≥ 0. Решение. 1. Задача поставлена в симметричной форме. 2. Многоугольник решений представлен на рис. 3. 3. Восстановим рис. 3 и из начала координат построим вектор c (-2, -3). Перпендикулярно ему проведём линию уровня, проходящую через начало координат. Перемещаем линию уровня в направлении вектора –с до тех пор, пока она имеет общие точки с многоугольником решений. Минимальное значение целевая функция принимает в точке B. 4. найдём координаты точки B. Для этого решим систему линейных алгебраических уравнений:
5. Вычислим значение целевой функции при x1=2, x2=6: f=-2*2-3*6=-22 Ответ: fmin=-22, xопт=(2,6). Рисунок, иллюстрирующий решение задачи: рис. 9
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|