Федосеев В.В. и др. Экономико-математические методы и прикладные модели

Подождите немного. Документ загружается.

Основы линейного программирования

менные соответствует одно базисное решение,

количество

способов разбиения

не

превышает величины

п\

т\(п

т)\

Если

все

компоненты базисного решения неотрицательны,

то такое решение называется опорным.

к. Пример

Исследовать систему уравнений методом

Жордана-Гаусса

Запишем расширенную матрицу системы уравнений и

последовательно преобразуем ее элементарными преобразо-

ваниями

(1 -2

—

^Х

~^~ ^XQ

- х

Зх

+ х

4х

+ х

Зх

3*4

+ 2х

+ 4*

+ Зх

-3

-4 2

1 4

-3 0

-3 3

-3

-2

-1

-3

-4

\0 3 -2

-3

-eJ

0 1-2 10

1-11 4

0 2-4 -22

0 1-2 -11

]

-3

-»

1 -1

0 0

0 1

-11

-3

е)

(

0 0

0 10

0 0 1

-1

-2

-7

-11

2 "

*з -

21х

Ч - Чх

~ 4*5

-8

Таким образом, система совместна, имеет бесчисленное

множество решений. Общее решение записывается

виде

42 Глава 2

Х\ = - 8 - 21*5>

Х2 = 3 + #4 + 7X5»

= 6 + 2х

+ 11х

Любое частное решение получается из общего путем

придания конкретных значений свободным переменным х±

и х

- Например, (-8;4;8;1;0) — частное решение. Одно из ба-

зисных решений получаем при х± = х

= 0, т.е. (-8;3;6;0;0).

Число базисных решений не превосходит С

= 10. Перейдем

к другому базисному решению, взяв в расширенной матрице

в качестве базисных векторы А\, Аг, А±; при этом перемен-

ные X\, X2, #4 будут базисными, а хз, Х5 — свободными. Пе-

реход от одного базиса к другому осуществим методом Жорда-

на—Гаусса, т.е. используя элементарные преобразования:

1 0

0 1

0 0

-7

-11

-8)

[1 0

0 1

-0,5

-1

-7

5,5

-8\

-з;

10 0 0 21

0 1 -0,5 0 -1,5

0 0 -0,5 1 5,5

-8\

-з,

Таким образом, получено еще одно базисное решение:

(-8;0;0;-3;0) и т.д. Заметим, что оба полученных базисных

решения не являются опорными решениями. Л

Линейные векторные пространства

Определение 1. Упорядоченная система из га действи-

тельных чисел а.\, а2,.-.,а

называется га-мерным вектором

и обозначается а - А = (a

,...,a

). Числа а

}

(/=1,2,...,га)

называются компонентами вектора а = А .

Определение 2. Совокупность всевозможных га-мерных

векторов с введенными на ней операциями сложения и ум-

ножения на число называется га-мерным векторным про-

странством.

Основы линейного программирования

В матрице из т строк и п столбцов строки являются га-

мерными векторами, столбцы — m-мерными векторами и т.д.

Вектор а - (а

,а

,...,а

) и вектор Ъ = (bj,b

,•

•

•»b

) рав-

ны,

если совпадают их компоненты, стоящие на одинаковых

местах, т.е. если а$ =

Ь-

}

при /' =1,2,...,га.

Суммой векторов а и Ъ называется вектор а

+ Ъ

= (a

+Ь

,...,а

). Роль нуля играет нулевой вектор

6 = (0,0,...,0).

Противоположным вектору а называется вектор -а =

= (-а

,-а

,...,-а

); очевидно, что а + (-а) =

Разность векторов а -Ъ =а

(-&).

Произведением вектора а на число

называется вектор

Ха=(Ха

Да

Ха„). Из этого определения вытекают сле-

дующие важные свойства:

Ца ±Ь)

Ш± kb,

(й ±

Х)а

-Ш± Ха,

k(Xa)

(kX)a.

Следствиями этих свойств являются следующие свойства:

О •

а ~ О, (-1)а = -а, X

•

0 = 0. Скалярным произведением двух

векторов а и Ь (А и В) называется действительное число,

равное сумме произведений соответствующих компонент

этих векторов:

АВ = аф1 + а

+ ... + а

Например, левая часть линейного уравнения а\Х\ + а

+ ... + а

= Ъ может быть представлена в виде скалярного

произведения векторов А • X, где А = (ai,a2,...,a„), X =

= (х

,...,х

Вектор В называется линейной комбинацией векторов

Ai,A

,...,A

если существуют такие числа A,i,

Я.2,...,

, при

которых выполняется соотношение В = X\Ai +

+ ... +

Х„А

Система векторов А\, Аг,..., А

(г > 2) называется

Глава

линейно-зависимой, если хотя бы один

из

векторов системы

является линейной комбинацией остальных,

линейно-не-

зависимой

— в

противном случае. Можно сформулировать

следующие равносильные сказанному определения.

Система векторов

А\,

А.2,...,

— линейно-зависимая, если

существуют такие числа

Xi,

Х2,...,

, не все

равные нулю,

при которых имеет место равенство Х\А\ +

Х2Л2

•••

^-r^r

О-

Если последнее соотношение возможно лишь

случае,

когда все Я.у

= 0 (j

1,г),

то система векторов называется ли-

нейно-независимой. Например, система векторов

А\ ~

(2,4,3),

(2,3,1), А

(5,3,2), А

= (1,7,3) линейно-зависима:

А\ +

+ 2А

= 0.

Рангом системы векторов

= (au,ai

,--->ai

•^2

(

21»

22>'">02п)»

(

т1>

т2>--->

тп)-

называется максимальное число линейно-независимых век-

торов этой системы. Ранг системы векторов равен рангу

матрицы

А,

составленной

из

компонент векторов этой сис-

темы, т.е. наивысшему порядку минора матрицы А, отлич-

ного от нуля.

L Пример

Определить, является

ли

система векторов

(5,4,3,2), А

(3,3,2,2), А

(8,1,3,-4) линейно-за-

висимой; если

она

линейно-зависима,

то

найти

ее

макси-

мальную линейно-независимую подсистему.

Решение. Составим матрицу

из

компонент векторов

и найдем ее ранг.

Имеем

4 3 .2>

3 2 2

Минор второго порядка

1,8

1 3 -4.

3*0.

Рассмотрим

два

минора третьего порядка, которые

его

окаймляют:

Основы линейного программирования

4 3

3 2

1 3

= 118-

-118 = 0,

-4

= 2(59 - 59) = 0.

Ранг матрицы А равен 2, поэтому система векторов является

зависимой. В матрицах, составленных из компонент любых

двух векторов данной системы, содержатся миноры второго

порядка, отличные от нуля, например,

5 4

3 3

3*0,

3 3

8 1

= -21 * 0,

5 4

8 1

= -27 * 0.

Поэтому максимальная линейно-независимая подсистема

состоит из двух любых векторов, а третий вектор является

их линейной комбинацией. i

Базисом га-мерного векторного пространства называется

любая совокупность га линейно-независимых векторов этого

же пространства.

Теорема. Любой вектор га-мерного векторного простран-

ства можно представить как линейную комбинацию векто-

ров базиса, притом единственным образом.

Один из базисов га-мерного векторного пространства обра-

зует система единичных векторов

-0.,0,...,0)

= (0,1,...,0)

Я„=(0,0,...,1).

Компоненты любого га-мерного вектора можно считать

координатами этого вектора в единичном базисе.

Пусть задано га-мерное линейное пространство Е

Определение. Множество X называется выпуклым, если

вместе с любыми точками х\ и Х2 множеству принадлежат

точки (отрезок)

"кх%

+ (l~^)*i при всех 0 < к< 1.

Множество на рис. 2.1а выпуклое, на рис. 2.16 —

невыпуклое.

_Xt x?

Рис. 2.1

Определение. Функция /(X), заданная на выпуклом

множестве X а Е

, называется выпуклой, если для любых

двух точек #i и х

из X и любого числа 0 < X < 1 выполня-

ется соотношение

f[kx

+ (1-ВД < Xf(x

) + (1-Щх!).

Определение. Функция /(X), заданная на выпуклом

множестве X, называется вогнутой, если для любых двух то-

чек Xi и

x<i

из X и любого числа 0 < X < 1 выполняется соот-

ношение

f[Xx

+ (1-Х.)*!] > Xf(x

) + (1~Щ*1).

Если приведенные неравенства считать строгими и они

выполняются при 0 < X < 1, то функция /XX) — строго вы-

пуклая (вогнутая).

Можно показать, что если /(X) — выпуклая функция, то

функция -/(X) — вогнутая, и наоборот.

На рис. 2.2а функция f(X) — выпуклая, на рис. 2.26 —

вогнутая.

f(X)

f(Xj

Рис. 2.2

Основы линейного программирования

Справедливы следующие утверждения относительно вы-

пуклых множеств и функций.

Пересечение выпуклых множеств есть выпуклое мно>

жество.

Сумма вогнутых (выпуклых) функций есть вогнутая

(выпуклая) функция.

Если f(X) — выпуклая функция при Х>0, то множе-

ство всех точек, удовлетворяющих условиям f(X)< b, X

О,

выпукло (если оно не пустое; Ъ — постоянная).

Пусть f(X) — выпуклая (вогнутая) функция, заданная

на замкнутом выпуклом множестве X с Е

, тогда любой

локальный минимум (максимум) f(X) на X является и гло-

бальным.

Приведем необходимое и достаточное условие выпукло-

сти функции многих переменных. Пусть функция

f(X) = f(x

,...,x

) имеет все частные производные второго

порядка, образующие матрицу

Q{X) =

dxf

dxidx

dx-fixz

dxl

dx^x-L дх

дх

дх±дх

дх

dxi J

Эта функция является выпуклой в области X тогда и

только тогда, когда матрица Q для любой точки из этой об-

ласти является неотрицательно (положительно) определен-

ной. Напомним, что квадратная матрица Q=(qij)

xn называ-

ется неотрицательно (положительно) определенной, если

все определители

Глава 2

9п 9i2

921 922

•.A»

9n 9i2

921 922

9in

92re

рядка для /(X): Q(X) Найдем определители

9nl

2 •"• Чпп

т.е.

все главные миноры матрицы Q неотрицательны

(положительны).

L» Пример 5. Показать, что функция f(X) =

2JC*

-6

является выпуклой при х

> 0.

Составим матрицу из частных производных второго по-

°"|

, 0 oj

Ai = 12x

А2 = 0. Так как Ai > 0, А2 = 0 при х^ > 0, то

функция является выпуклой. Л

Дадим определение глобального и локального максимумов.

Функция f(x) достигает на замкнутом (т.е. включающем

свою границу) множестве X глобальный максимум в точке

х , если для любой точки, принадлежащей Х(х е X), выпол-

•it

няется условие f(x)

f(x ).

Функция fix) достигает на замкнутом множестве X ло-

кального максимума в точке х°, если существует некоторая

окрестность этой точки, для каждой точки которой выпол-

няется условие/(лс) < f(x ).

Определения локального

формулируются аналогично.

и глобального минимума

На рис. 2.3 *з — точка

локального минимума; Х

—

глобального минимума;

а,

х%

—

точки локального

максимума; р — точка гло-

бального максимума.

Рис. 2.3

Основы линейного программирования

Необходимые условия экстремума (максимума, минимума).

Если в точке х е X функция f(x) = f(x

,...,x

) имеет

экстремум, то частные производные первого порядка равны

нулю в этой точке:

df(x°) —

— = О, ; =

п.

dXj

Достаточные условия существования экстремума здесь не

формулируются. О самом существовании точек глобального

минимума и максимума говорит следующая теорема.

Теорема Вейерштрасса. Если функция f(x) определена

и непрерывна в ограниченной замкнутой области X, то она

достигает в ней своих точных верхней и нижней границ

(глобальный максимум и глобальный минимум).

Приведенные утверждения относительно выпуклых мно-

жеств и функций, условий существования экстремума поз-

воляют делать выводы о свойствах тех или иных задач опти-

мального программирования, что является основой разработки

и применения математических методов их решения. Напри-

мер,

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

рования использует, в частности, «свойство выпуклости»

этой задачи: не существует локального экстремума, отлич-

ного от глобального.

2.4. Геометрическая интерпретация задачи

Рассмотрим задачу ЛП в стандартной форме

тах(тт)/(Х)= с\Х\ + с

+ ... + с

при ограничениях ацХ\ + ах

+••• + ain

n ^ &i

021*1 + «22*2 + ... +

< b

записи:

(2.18)

(2.19)

xi + a

+ ... + a

< b

Xj > 0,;' = 1,2,...,n.

(2.20)

Глава 2

Рассмотрим эту задачу на плоскости, т.е. при га = 2.

Пусть система неравенств (2.19), (2.20) совместна (имеет хотя

бы одно решение):

ацх

+ a

^ h,

й2\Х\ +

^ Ь

а-т\Х\

+ а

т2

xi >0;х

> 0.

Каждое неравенство этой системы геометрически опреде-

ляет полуплоскость с граничной прямой ацх

+ а^

&i>

l,m. Условия неотрицательности определяют полуплос-

кости соответственно с граничными прямыми х\ = 0, х

= 0.

Система совместна, поэтому полуплоскости, как выпуклые

множества, пересекаясь, образуют общую часть, которая яв-

ляется выпуклым множеством и представляет собой сово-

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

решение данной системы. Совокупность этих точек называют

многоугольником решений. Это может быть точка, отрезок,

луч, замкнутый многоугольник, неограниченная много-

угольная область.

Если в системе ограничений (2.19) - (2.20) га = 3, то каж-

дое неравенство геометрически представляет полупространство

трехмерного пространства, граничная плоскость которого

i +

2 + ai3*3

°u

условия неотрицательности — по-

лупространства с граничными плоскостями соответственно

Xj = 0 (j=l,2,S). Если система ограничений совместна, то

эти полупространства, как выпуклые множества, пересека-

ясь,

образуют в трехмерном пространстве общую часть, ко-

торая называется многогранником решений.

Пусть в системе (2.19) - (2.20) га > 3, тогда каждое нера-

венство определяет полупространство га-мерного пространства

с граничной гиперплоскостью ацХ\ + at

+ ...+ ai

= fy,

i - 1, т , а условия неотрицательности — полупространства с

граничными гиперплоскостями Xj = 0, j = 1, га.

Если система ограничений совместна, то по аналогии с

трехмерным пространством она образует общую часть га-