Геометрический метод

Свойства основной задачи линейного программирования свя­заны со свойствами выпуклых множеств.

Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую комбинацию.

Геометрический смысл этого определения состоит в том, что множеству вместе с его произвольными точками полностью при­надлежит и прямолинейный отрезок, их соединяющий. Примера­ми выпуклых множеств являются прямолинейный отрезок, полу­плоскость, круг, шар, куб, полупространство и др.

Угловыми точками выпуклого множества называются точки, не являющиеся выпуклой комбинацией двух произвольных точек множества.

Например, угловыми точками треугольника являют­ся его вершины, круга — точки окружности, которые его ограничи­вают.

Множество планов основной задачи линейного программиро­вания является выпуклым (если оно не пусто). Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной.

Если основная задача линейного программирования имеет оп­тимальный план, то целевая функция задачи принимает максималь­ное значение в одной из вершин многогранника решений.

Если максимальное значение достигается более чем в одной вершине, то целевая функция принимает его во всякой точке, являющейся вы­пуклой линейной комбинацией этих вершин.

Непустое множество планов основной задачи линейного про­граммирования образует выпуклый многогранник, каждая верши­на которого определяет опорный план.

Для одногоиз опорных планов (т.е. в одной из вершин многогранника решений) значение целевой функции является максимальным (при условии, что функ­ция ограничена сверху на множестве планов).

Вершину многогранника решений, в которой целевая функция принимает максимальное значение, можно найти достаточно про­сто, если задача в стандартной форме содержит не более двух пере­менных:

F(X) = (c1x1 + c2x2) -> max при условиях

ai1x1 + ai2x2 £ bi i=

xj ³ 0, j=1,2

Каждое из неравенств системы ограничений геометри­чески определяет полуплоскость допустимых значений переменных соответственно с граничными

прямыми

ai1x1 + ai2x2 = bi i=

Если система неравенств совместна, то областью допустимых решений задачи являются выпуклое множество, которое называет­ся многоугольником решений.

Стороны этого многоугольника ле­жат на прямых, уравнения которых получаются из исходной систе­мы ограничений заменой знаков неравенств на знаки точных ра­венств.

Решение задачи линейного программирования геометрическим методом включает следующие этапы.

1. На плоскости Х1OX2 строят прямые, уравнения которых по­лучаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограни-че­ний задачи.

3. Строят многоугольник решений.

4. Строят вектор (c1,c2), который указывает направле-ние воз­растания целевой функции.

5. Строят начальную прямую целевой функции c1x1 + c2x2 = 0 и затем передвигают ее в направлении вектора до крайней угловой точки многоугольника решений.

В результате находят точку, в ко­торой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов (F(X) ® ¥ ).

6. Определяют координаты точки максимум функции и вычис­ляют значение целевой функции в этой точке.

Минимальное значение целевой функции находится передвижением начальной прямой c1x1 + c2x2 = 0 в направле­нии, противоположном вектору (c1, с2).

Пример 1. Найдите максимум и минимум линейной функции

F(X) = (-2x1 + 4х2) -> extr

при условиях-ограничениях:

6x1 - 2x2 £ 12

-x1 + 2x2 £ 5

x1 + x2 ³ 1

x1,x2 ³ 0,

Решение. Построим на плоскости X1 O X2 многоугольник реше­ний (рис.3.1). Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

6x1 - 2x2 = 12 (1)

-x1 + 2x2 = 5 (2)

x1 + x2 = 1 (3)

x1 = 0 (4)

x2 = 0, (5)

Построив прямые системы, найдем соответствующие полупло­скости и их пересечение.

Многоугольником решений задачи является пятиугольник АВСДЕ, координаты точек которого удовлетворяют условию неот­рицательности переменных и неравенствам системы ограничений задачи.

Рис. 3.1. Построение многоугольника решений

Для нахождения точек экстремума построим начальную прямую

F(x)= -2x1 + 4x2 = 0 и вектор N(-2,4).

Передвигая прямую F(X) = О в направлении вектора N, найдем точку С, в которой начальная прямая принимает положение опорной прямой.

Следовательно, в точке С целевая функция имеет максимальное значение.

Так как точка С получена в результате пересечения прямых 1 и 2, то ее ко­ординаты удовлетворяют уравнениям этих прямых:

6x1 - 2х2 = 12,

-x1 + 2х2 = 5.

Решив систему уравнений, получим:

x1 = 3,4;

x2 = 4,2;

откуда найдем максимальное значение целевой функции Fmax(X) = - 2•3,4 + 4•4,2 = 10.

По условию задачи начальная прямая параллельна прямой (2), так как коэффициенты при переменных x1,x2 пропорциональны: -2/-1=4/2=2.

Следовательно, начальная прямая займет положе­ние опорной прямой в точках В, С и в любой точке отрезка ВС, в которых F(X) принимает одно и то же максимальное значение.

Для определения координат точки В решим систему двух линейных уравнений:

-x1 +2x2 = 5 x1 = 0

x1 = 0 x2 = 2,5

Максимальное значение целевой функции в точке В равно:

F(X) = -2 • 0 + 4 • 2,5 = 10.

Запишем множество оптимальных решений как линейную вы­пуклую комбинацию углов точек отрезка ВС:

x1* = a·x1^(B) + (1-a)·x1^(C)

x2* = a·x2^(B) + (1-a)·x2^(C)

где O£ a £ 1.

Подставив координаты угловых точек, получим:

x1* = a·3.4 + (1-a)·0 = 3,4a

x2* = a·4.2 + (1-a)·2.5 = 2,5 + 1,7a

Тогда * = {3,4a; 2,5 + l,7a}, где O£ a £ 1.

Подставляя любые значения в от 0 до 1, получим координаты множества точек отрезка ВС, в каждой из которых целевая функ­ция принимает максимальное значение, равное 10. /Бесчисленное множество решений/

Для нахождения минимального значения целевой функции за­дачи перемещаем начальную прямую в направлении, противопо­ложном вектору (c1, с2).

Начальная прямая займет положение опорной прямой в вершине Д, где x1 = 2, х2 = 0, а минимальное значение целевой функции равно:

F(X) = -2 • 2 + 4 • 0 = -4.

Пример 2. Геометрический метод решения ЭЛП рассмотрим на примере построенной ранее модели коммерческой деятельности предприятия.

Для двух переменных, задачу можно решить геометрическим ме­тодом.

Построим на плоскости X1 O X2 (рис.3.2) многоугольник допус­тимых решений задачи. Для этого в неравенствах системы ограни­чений знаки неравенств заменим на знаки точных равенств:

0,5x_н+x_в ≤ 3 (1) 0,5x_н+x_в ≤ 3 (1)

x_н + 0,5x_в≤ 4 (2) x_н + 0,5x_в≤ 4 (2)

x_в - х_н ≤ 1,5 (3) x_в - х_н ≤ 1,5 (3)

x_в≤ 2 (4) x_в≤ 2 (4)

x_н ≥ 0,25 (5) x_н ≥ 0,25 (5)

x_в ≥ 0,5 (6) x_в ≥ 0,5 (6)

F()=(2x_н+3x_в) -> max

Построив полученные граничные прямые, найдем соответству­ющие полуплоскости допустимых значений переменных и их пере­сечение (рис.3.2).

Рис. 3.2. Построение области допустимых решений

Направление стрелок от каждой граничной прямой определя­ется путем непосредственной подстановки в неравенство коорди­нат произвольно взятой точки, например (0,0).

При удовлетворе­нии данного неравенства направляем стрелки в сторону контроль­ной точки, в противном случае - наоборот.

Полученное пространство решений есть многоугольник ABCDEF.

Угловые точки многоугольника решений имеют следующие ко­ординаты:

A(0,25;0,5), B(0,25;1,75), С(0,5;2), D(2;2), E(3'/з;l'/з), F(3,75;0,5).

Для нахождения минимума и максимума целевой функции стро­им начальную прямую и вектор-градиент N (2; 3) (рис.3.3).

Рис.3.3. Определение экстремальных значений целевой функции

Коор­динатами вектора N являются коэффициенты целевой функции при переменных x_н и x_в.

Для построения графика целевой функции задаем произвольное значение F(X) = 0 - прямая про­ходит через начало координат.

Для ее построения, полагая x_н =1, получим x_в =-2/3, а при x_в =1, получим x_н =-3/2 (рис.3.3).

Полагая F(X) = 6, таким же образом построим линию целевой функции.

Затем для x_н = 0,25 и x_в = 0,5 определяем минимальное значе­ние F(X) = 2.

Таким образом построим на графике ряд парал­лельных прямых, рис.3.3, где вектор-градиент N(2;3) показывает направление возрастания целевой функции.

Максимальное значение F(X) будет в точке Е. Так как точка Е получена в результате пересечения прямых (1) и (2), то для опреде­ления ее координат решим систему уравнений:

0,5x_н + x_в = 3

x_н + 0,5x_в = 4 x_н^*=3¹/₃; x_в^*=1¹/₃

Максимальное значение целевой функции

2x_н + 3x_в = 2•З'/з + 3•1'/з = 10²/₃ (тыс. руб.).

Целевая функция 2x_н + 3x_в = 10²/₃ пересекает ось x_в в точке

x_в= 3⁵/₉,

а ось x_н = 5¹/₃

Таким образом, суточный объем производства краски для на­ружных работ должен быть равен З'/з т, а для внутренних работ — 1'/з т.

Доход от продажи в этом случае будет максимальным и со­ставит 10²/₃ тыс.руб.

Вполне реально предположить, что полученное статическое решение устареет еще до момента его реализации.

Поэтому сле­дует предусмотреть динамический характер условий производст­ва и продажи красок.

Например, важно знать, как повлияет на оптимальное решение увеличение или уменьшение спроса, из­менение рыночных цен или запасов исходного сырья.

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

АЛГОРИТМ СИМПЛЕКСНОГО МЕТОДА.