|
Свойства задачи линейного программированияВыше были рассмотрены различные формы задачи линейного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей, канонической или стандартной задачи. В данном разделе будем рассматривать каноническую задачу, в которой система ограничений есть система уравнений. Для обоснования свойств задачи линейного программирования и методов её решения целесообразно рассмотреть ещё два вида записи канонической задачи. Матричная форма записи: при ограничениях AX = B, X ³ 0, где Здесь С – матрица-строка, А – матрица системы, Х – матрица-столбец переменных, В – матрица-столбец свободных членов.
Векторная форма записи:
при ограничениях
где СХ – скалярное произведение векторов С = (с1, с2, …, сn) и Х = (х1, х2, …, хn); векторы
Векторы состоят соответственно из коэффициентов при переменных и свободных членов. Векторное неравенство X ³ 0 означает, что все компоненты вектора Х неотрицательны, т.е. xj ³ 0, j = 1, 2, …, n. В задачах линейного программирования представляют интерес системы, в которых ранг г матрицы системы А=(аij), i = 1,2,..., m; j = 1,2,..., n, или, что то же самое, максимальное число независимых уравнений системы г меньше числа переменных, т.е. r < n. Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные п - m переменных называются неосновными. Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n – m неосновных переменных равны нулю. В задачах линейного программирования особый интерес представляют допустимые базисные решения, или, как их еще называют, опорные планы. Сформулируем ряд теорем. Теорема 2.1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которые в дальнейшем будем называть одним термином -многогранником решений. Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение задачи линейного программирования, дается в следующей фундаментальной теореме. Теорема 2.2. Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек. Будем полагать, что многогранник решений является ограниченным. Требование ограниченности многогранника решений в теореме является существенным, так как в случае неограниченной многогранной области не каждую точку такой области можно представить выпуклой линейной комбинацией ее угловых точек. Данная теорема является фундаментальной, так как она указывает принципиальный путь решения задач линейного программирования. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необходимо исследовать лишь конечное число угловых точек многогранника решений. Следующая теорема посвящена аналитическому методу нахождения угловых точек. Теорема 2.3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений и, наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение. Из теорем 2.2 и 2.3 непосредственно вытекает важное следствие: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений. Итак, оптимум линейной функции задачи линейного программирования следует искать среди конечного числа ее допустимых базисных решений. 5.2.2Геометрическое изображение системы ограничений. Линия уровня линейной функции. Выше говорилось, что множество допустимых решений (многогранник решений) задачи линейного программирования представляет собой выпуклый многогранник (или выпуклую многогранную область), а оптимальное решение задачи находится, по крайней мере, в одной из угловых точек многогранника решений. Рассмотрим задачу в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т.е. n - m = 2. Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 2.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1 + c2x2 принимает максимальное (или минимальное) значение. Рассмотрим так называемую линию уровня линейной функции F, т.е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение а, т.е. F = а, или . (5.2.1)
На многоугольнике решений следует найти точку, через которую проходит линия уровня функции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем. Уравнение линии уровня функции (5.2.1) есть уравнение прямой линии. При различных уровнях а линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами с1 и с2 и, следовательно, равны. Таким образом, линии уровня функции F - это своеобразные "параллели", расположенные под каким-то углом к осям координат. F = Fmax
B C
F = Fmin F = 0
D A
E F = a
Рисунке 5.2.1 Важное свойство линии уровня линейной функции состоит в том, что при параллельном смешении линии в одну сторону уровень только возрастает, а при смещении в другую сторону только убывает. Пусть имеются три линии уровня: F = c1x1 + c2x2 = a1 (I), F = c1x1 + c2x2 = a2(II), F = c1x1 + c2x2 = a3(III), причем линия II заключена между линиями I и II. Тогда a1 < a2 < a3 или a1>a2>a3. В самом деле, на штриховой линии - (перпендикулярной к линиям уровня, (рис. 5.2.2) уровень является линейной функцией, а значит, при смещении в одном из направлений возрастает, а в другом - убывает.
Х 2
III I II
F = a
F = a1 F = a2
0 Х 1
Рисунке 5.2.2
Для определения направления возрастаниия рекомендуется изобразить две линии уровня и определить, на которой из них уровень больше. Например, одну из линий можно взять проходящей через начало координат (если линейная функция имеет вид F = с1х1 + с2х2, т.е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее, определив направление возрастания линейной функции (обозначим его вектором q), найдем точку, в которой функция принимает максимальное или минимальное значение (на рис. 2.1 - это точка С или А). Этапы решения задачи Таким образом, геометрически задача линейного программирования представляет собой поиск такой точки многогранника решений, координаты которой доставляют линейной функции наибольшее (наименьшее) значение, причем допустимыми решениями являются все точки многогранника решений. Графический метод решения задачи линейного программирования состоит из следующих этапов. Этап 1. Сначала на координатной плоскости х1Oх2, строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям. Далее строится вектор q, координаты которого являются частными производными функции F. Вектор показывает направление возрастания линейной функции F в какой-нибудь точке X0, принадлежащей допустимой области. Этап 2. Прямая F = c1x1 + c2x2, перпендикулярная вектору q, передвигается в направлении этого вектора в случае максимизации F до тех пор, пока не покинет пределов многоугольной области. Предельная точка (или точки) области при этом движении и является точкой максимума F. Этап 3. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение F, найденное в получаемой точке, является максимальным. В случае минимизации F прямую F = c1x1 + c2x2 надо двигать в направлении, противоположном вектору q. Ясно, что если прямая F = с1х1 + c2x2 при своем движении не покидает допустимой области, то соответствующий максимум или минимум F не существует. Рассмотрим пример. Решить графическим методом следующую задачу: F = 30 x1 + 60 x2 ®max при ограничениях: Прямые ограничения х1, х2 ³ 0 означают, что область решений будет лежать в первой четверти декартовой системы координат; отметим штриховкой эту область на рисунке 5.2.3. Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой х1 + Зх2 - 21 = 0. Построим прямую по двум точкам (0; 7) и (21; 0), которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим ее цифрой I. Множество решений строгого неравенства - одна из полуплоскостей, на которую делит плоскость построенная прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Подставим координаты (0; 0) в неравенство, получим -21 < 0, т.е. оно выполняется. Следовательно, областью решения неравенства служит нижняя полуплоскость. Аналогичным образом построим области решения двух других неравенств: 3x1 + 2x2 – 21 = 0; x1 = 0, x2 = 10,5; x2 = 0, x1 = 7. (на рисунке прямая II); 3x1 + 2x2 – 21 < 0 при х1 = х2 = 0, – 18 < 0 выполняется, берётся нижняя полуплоскость. Заштрихуем общую область для всех неравенств, обозначим вершины многоугольника латинскими буквами и определим их координаты, решая систему уравнений двух пересекающихся соответствующих прямых. Например, определим координаты точки С, являющейся точкой пересечения второй и третьей прямой: 3x1 + 2x2 = 21, x2 = 3, x1 = 5, 3x1 + x2 =18. Вычислим значение целевой функции в этой точке: F = 30x1 + 60x2 = 150 + 180 = 330. Аналогично поступим для других точек, являющихся вершинами замкнутого многоугольника OABCD, представляющего собой область допустимых решений рассматриваемой задачи. Координаты этих вершин имеют следующие значения: O (0;0), A (0;7), B (3;6), C (5;3), D (6;0). Этап 2. Приравняем целевую функцию постоянной величины а: 30х1+60х2 = а. Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. Пусть а=0, вычислим координаты двух точек, удовлетворяющих соответствующему уравнению 30х1 + 60х2. В качестве одной из этих точек удобно взять точку О (0;0), а так как при х1 = 2х2 = 0, то в качестве второй точки возьмём точку G (2; -1). Через эти две точки проведём линию уровня F = 30x1 + 60x2 = 0 (пунктирная прямая на рис. 5.2.3). Рисунке 5.2.3
Этап 3. Для определения направления движения к оптимуму построим вектор q, координаты которого являются частными производными функции F, т.е. q = (30;60). Чтобы построить этот вектор, нужно соединить точку (30;60) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора q, а при минимизации - в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору q. Так, на рисунке 5.2.3 изображен вектор 1/3 q= (10;20). В нашем случае движение линии уровня будем осуществлять до ее пересечения с точкой В; далее она выходит из области допустимых решений. Следовательно, именно в этой точке достигается максимум целевой функции. Отсюда легко записать решение исходной задачи линейного программирования: max F = 450 и достигается при х1 = 3; x2 = 6. Если поставить задачу минимизации функции F = 30x1 + 60x2 при тех же ограничениях, линию уровня необходимо смещать параллельно самой себе в направлении, противоположном вектору q. Как это видно на рисунке 5.2.3, минимум целевой функции достигается в точке 0 (0;0), следовательно, можно записать min Х = 0 и достигается при х1 = 0; x2 = 0. При решении некоторых задач линейного программирования графическим методом может встретиться случай, когда линия уровня параллельна одной из сторон выпуклого многоугольника допустимых решений, причем эта сторона расположена в направлении смещения линии уровня при стремлении целевой функции к своему оптимуму. В этом случае оптимальное значение целевой функции достигается не в одной, а в двух угловых точках (вершинах) многоугольника решений и, следовательно, во всех точках отрезка, соединяющего эти вершины, т.е. задача будет иметь бесчисленное множество решений. Если область допустимых решений является незамкнутым выпуклым многоугольником в направлении оптимизации целевой функции, то целевая функция будет неограниченной и задача линейного программирования не будет иметь решений. Очевидно также, что задача линейного программирования не будет иметь решений в случае, когда область допустимых решений есть пустое множество, т.е. система ограничений задачи линейного программирования содержит противоречивые неравенства и на координатной плоскости нет ни одной точки, удовлетворяющей этим ограничениям. Рассмотренный в этой главе геометрический метод решения задач линейного программирования обладает рядом достоинств. Он прост, нагляден, позволяет быстро и легко получить ответ. Однако только геометрический метод решения никак не может удовлетворить ни математиков, ни экономистов. Возможны "технические" погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие четкий экономический смысл (такие как остатки ресурсов производства, избыток питательных веществ и т.п.), не выявляются при геометрическом решении задач. Но самое главное - геометрический метод неприемлем для решения практических задач. Его можно применить только в том случае, когда число переменных в стандартной задаче равно двум. Поэтому необходимы: аналитические методы, позволяющие решать задачи линейного программирования с любым числом переменных и выявлять экономический смысл входящих в них величин. Эти методы будут рассмотрены в следующих главах. Симплексный метод ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|