24.4План. Опорный план. Оптимальный план

Определение 1. Планом или допустимым решением задачи ЛП называется вектор X = (x1; :::; xn), удовлетворяющий условиям (7:18) и (7:19)

Определение 2. План X = (x1; :::; xn) называется опорным, если векторы Ai, входящие в разложение (7:21) с положительными коэффициентами xi являются линейно-независимыми. Так как векторы Ai являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m

Определение 3. Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае опорный план называется вырожденным

Определение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение

25 Выпуклые многогранники

Пусть задано некоторое множество и в нем имеется m точек A1; A2; :::; Am. Ai(x(1i); x(2i); :::; x(ni)) i = 1; 2; :::; m Точка A называется выпуклой линейной комбинацией точек A1; A2; :::; Am если ее можно представить

в виде

m

P

A = 1A1 + 2A2 + ::: + mAm i > 0 i = 1; 2; :::; m i = 1 (7:24)

i=1

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

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

Определение. Выпуклым многогранником называется замкнутое ограниченное выпуклое множество n-мерного пространства, имеющее конечное число угловых точек. Угловые точки многогранника называются его вершинами

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

26 Геометрическая интерпретация задачи ЛП

Пусть дана задача ЛП. Найти минимальное значение ф-и

f = c1x1 + c2x2 + ::: + cnxn (7:25)

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

8

>a11x1 + a12x2 + ::: + a1nxn 6 b1

>

>

<a21x1 + a22x2 + ::: + a2nxn 6 b2

(7:26)

>:::

>

>

:am1x1 + am2x2 + ::: + amnxn 6 bm

xj > 0 j = 1; 2; :::; n (7:27)

Предполагаем, что система (7:26) (7:27) - совместная.

Рассмотрим частный случай системы, а именно совместную систему линейных неравенств на плоскости

8

>a11x1 + a12x2 6 b1 a21x1 + a22x2 6 b2

>

>

>

>

>

<

::: (7:28)

>

>

>am1x1 + am2x2 6 bm

>

>

>

:x1 > 0; x2 > 0

Каждое неравенство системы (7:28) определяет полуплоскость. Так как система (7:28) совместна, то пересение этих полуплоскостей не пусто. Оно называется многоугольником решений. В частных случаях многоугольник решений может быть лучом, отрезком или точкой.

При произвольном конечном n каждое неравенство системы (7:26)-(7:27) определяет полупространство n-мерного пространства с граничной гиперплоскостью

50

ai1x1 + ai2x2 + ::: + ainxn = bi i = 1; 2; :::; m

xj > 0 j = 1; 2; :::; n

Если система (7:26)-(7:27) совместна, то пересечение этих полупространств также непустое множество, называемое многогранником решений. Следовательно, геометрически задача ЛП представляет собой отыскание такой точки многогранника решений, координаты которой доставляют минимальное (максимальное) значение целевой ф-и f(x), причем допустимыми решениями являются все точки многогранника решений.

26.1Свойства решения задачи ЛП

Если целевая ф-я задачи ЛП ограничена на многограннике решений, то

1.существует такая угловая точка многранника решений, в которой целевая ф-я задачи ЛП достигает своего минимума (максимума);

2.каждый опорный план соотвествует какой-либо угловой точке многогранника решений и каждая угловая точка многогранника решений соотвествует какому-либо опорному плану, поэтому для решения задачи ЛП достаточно исследовать только угловые точки многогранника решений т.е. опорные планы

26.2Графический метод решения задачи ЛП

Графическим методом можно решать задачи только на плоскости n = 2 и в трехмерном пространстве n = 3. При n > 3 графическое решение задачи невозможно.

Пусть дана задача: Найти минимальное значение ф-и

f = c1x1 + c2x2(8:1)

8

>a11x1 + a12x2 6 b1

>

>

<a21x1 + a22x2 6 b2

(8:2)

>:::

>

>

:an1x1 + an2x2 6 bn

x1 > 0 x2 > 0 (8:3)

Допустим, что система неравенств (8:2) и (8:3) совместна, и ее многоугольник решений ограничен. Каждое из неравенств (8:2) и (8:3) определяет полуплоскость с граничной прямой

ai1x1 + ai2x2 = bi i = 1; 2; :::; m x1 = 0 x2 = 0

У-ние (8:1) - у-ние прямой линии, если

c1x1 + c2x2 = const

тогда задачу ЛП можно интерпретировать так: найти точку многоугольника решений, в которой прямая

c1x1 + c2x2 = const

является опорной и при этом целевая ф-я f достигает минимума. Значение ф-и f возрастает в направлении градиента N(c1; c2)

@f = c1 @f = c2 @x1 @x2

Поэтому минимум ф-и f достигается в точке A

Координаты точки A(x1; x2) находим, решая систему у-ний прямых AB и AE Пример задачи, решаемой графическим методом. Найти минимум ф-и

f = 4x1 + 6x2

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

51