Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





Выше были рассмотрены различные формы задачи линейного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей, канонической или стандартной задачи.

В данном разделе будем рассматривать каноническую задачу, в которой система ограничений есть система уравнений.

Для обоснования свойств задачи линейного программирования и методов её решения целесообразно рассмотреть ещё два вида записи канонической задачи.

Матричная форма записи:

при ограничениях

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. Сначала на координатной плоскости х12, строится допус­тимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям. Далее строится вектор 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 км? Что будет с Землей? - задался я вопросом...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.