Файл: 1ЭМММ-Линейное программирование.pdf

При этом вектор ai (ai1, ai2 ) , как градиента функции ai1x1 + ai2 x2 , указывает ту полуплоскость, которая определяется

неравенством ³ 0 , а вектор ai (−ai1,−ai2 ) - полуплоскость,

определяемую неравенством £ 0 .

Если система неравенств (6), (7) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Пересечение этих полуплоскостей образует выпуклый многоугольник решений, или область допустимых решений (ОДР).

Таким образом, исходная задача ЛП состоит в нахождении таких точек многоугольника решений, в которых целевая функция Z принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст, и на нем целевая функция ограничена.

Линейная целевая функция достигает точек экстремума только на границе выпуклого многоугольника.

Рассмотрим градиент функции цели Z(x1, x2) . Это будет

вектор n(c1, c2 ) (см. рис.2.), указывающий направление

возрастания функции цели. Очевидно, если взять обратное направление, то это будет направлением убывания функции цели. Если построить произвольную прямую c1x1 + c2x2 = L -

const, то её движение параллельно самой себе в направлении вектора n(c1, c2 ) приведет к возрастанию функции цели. При

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

крайних положения этой прямой в ОДР соответствуют наименьшему и наибольшему значениям целевой функции. При этом могут встретиться случаи, изображенные на рис.2-5, когда исходная задача имеет единственное решение (минимальное и максимальное значение) (рис.2), множество решений (координаты любой точки прямой B1B2 на рис.3), и решение

исходной задачи не существует в силу неограниченности целевой функции (рис.4) или несовместности системы неравенств (6), (7) (рис.5).

12

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

n

4. Графический метод решения задачи линейного программирования

Графическим методом решается стандартная задача линейного программирования:

Z = c1x1 + c2 x2 ® max(min) ai1x1 + ai2 x2 £³ bi , i = 1,m x1 ³ 0 , x2 ³ 0 .

Данный метод основан на приведенной выше геометрической интерпретации задачи ЛП. Нахождение

решения задачи ЛП графическим методом имеет следующие этапы:

13

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

1.Строят прямые (8), уравнения которых получаются в

результате замены в ограничениях знаков неравенств на знаки точных равенств.

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

3.Находят многоугольник решений как пересечение всех полуплоскостей

4.Строят начальную прямую (линию уровня целевой функции), проходящую через начало координат c1x1 + c2x2 = 0 .

5.Строят вектор n(c1,c2) , представляемый градиент

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

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

П р и м е р . Найти наибольшее и наименьшее значения целевой функции z при заданных ограничениях:

Z = 6 × x1 + x2 ® max

ì3× x1 - x2 ³ 9 ïí2 × x1 + 3× x2 £ 50 ïî- x1 + 4 × x2 ³ 18

x1³ 0, x2 ³ 0

1. Строят прямые, уравнения которых получаются в

результате замены в ограничениях знаков неравенств на знаки точных равенств:

3× x1 - x2 = 9 (α )

2× x1 + 3× x2 = 50 (β ) - x1 + 4× x2 = 18 (γ )

14

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

2.Каждое ограничение-неравенство определяет координатную полуплоскость. В зависимости от знака

неравенств при помощи двух стрелок укажем требуемые полуплоскости.

3.В результате пересечения всех полуплоскостей находят многоугольник решений (на рисунке обозначен треугольником ABC).

4.Построим начальную прямую (линию уровня

целевой функции), проходящую через начало координат

6 × x1 + x2 = 0 .

5.Движением прямой 6 × x1 + x2 = 0 параллельно самой

себе в направлении вектора n(6,1) находим два крайних

положения. Первое соответствует минимуму целевой функции (точка А), второе - максимуму (точка С).

Рис.6. Графическая интерпретация задачи линейного программирования

X2

6. Определим координаты точек максимума и

минимума целевой функции и вычислим их значения в найденных точках.

15

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

− Точка минимума лежит на пересечении прямых

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

Zmin = 6 × 4,9 + 5,7 = 35,1.

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

Zmax = 6 ×13,27 + 7,82 = 87,4 .

Вообще, с помощью графического метода может быть решена задача ЛП, система ограничений которой содержит n неизвестных и m линейно-независимых уравнений, если n и m связаны соотношением n − m = 2 .

Действительно, пусть поставлена каноническая задача ЛП: найти наибольшее значение

где все уравнения (13) линейно независимы, и выполняется соотношение n − m = 2 .

Используя метод Жордана-Гаусса, производим m исключений, в результате которых система ограничений примет вид:

xi + ai/1x1 + ai/2x2 = bi/ , i = 3, n

16

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Учитывая неравенства (14), эту систему уравнений

задачу вида (5-7).

5. Симплекс - метод решения задач линейного программирования

В в е д е н и е .

Предположим, что поставлена стандартная задача ЛП:

Каждое из условий типа неравенства определяет полупространство, ограниченное гиперплоскостью (плоскостью в k-мерном пространстве). Пересечение соответствующих полупространств образует выпуклый многогранник (область допустимых решений - ОДР), в котором необходимо найти максимум (минимум) целевой функции. Внутри многогранника условий в силу его выпуклости линейная функция z не может достигать максимума (минимума). Её максимум (минимум), если он существует, достигается обязательно в какой-нибудь вершине многогранника или на одном из его граней.

Теоретически задача ЛП проста. Достаточно найти

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

Однако простой перебор даже при использовании самых современных ЭВМ практически неосуществим из-за чрезвычайно большого числа вершин. Поэтому возникла

17

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com