Файл: Говар В.М. Математическое программирование учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 29.06.2024

Просмотров: 130

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

- 13 -

S2. ПОНЯТИЕ О ВЫПУКЛЫХ МНОЖЕСТВАХ. ОБЩЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАМ­ МИРОВАНИЯ. ОСНОВНЫЕ ТЕОРЕМЫ.

Определение I .

—-

Множество точек

П -мерного пространства, в котором отре­

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

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

Определение £.

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

 

 

 

-Ik -

 

 

 

 

 

 

 

 

 

Определение

3.

 

 

 

 

 

 

 

 

 

 

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

граничные ючки.

"

 

 

 

 

 

 

 

 

 

Определение

k.

 

 

 

 

 

 

 

 

 

 

будем называть выпуклой,если

выполняются

следующие дна

 

условия:

I .

Вое коэффициенты*^), эюй коибинации

неотрицательны,т.е.

к ?

о

и=і.2...,п).

 

 

 

 

 

 

 

 

 

2.

Сумма .всех коэффициентов L_гLA r•

•

•

• •

»

•

(

»

„ *

Определение

5.

 

 

 

 

 

 

 

 

 

 

Точка X, входящая в выпуклое замкнутое множество

W

,

на­

зывается

угловой

(крайней) тонкой этого множества, если

ее

нель-

зя представить в

.виде X = ', •

Хт + (1-1)

х ? ,

где

0 <

 

U <

I , а

*l6W

и

х 2 £ ѵ Ѵ

•

 

 

 

 

 

 

 

 

 

Угловая (крайняя) точка

не может лежать

внутри

отрезка,со­

единяющего любые две точки выпуклого множества.

 

 

 

 

 

Определение

6.

 

 

 

 

 

 

 

 

 

 

Замкнутое выпуклое множество, имеющее конечное число углр^-

вых точек,

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

вершины его

явля­

ются угловыми точками.

 

 

 

 

 

 

 

 

 

Рассмотрим следующие теоремы о выпуклых множествах:

 

 

Теорема I .

 

 

 

 

 

 

 

 

 

 

Любая внутренняя точка отрезка, соединяюдего две

т"очки выпук­

лого множества,является выпуклой линейной

комбинацией

этих

точек.

 

- 15

-

Теорема 2.

(обратная)

 

Любая точка, которую можно представить в Виде выпуклой ли­

нейной комбинации дяух точек

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

кѳ, соединяющем

эти точки.

 

Теорема

3.

 

 

 

 

 

Любая точка выпуклого

замкнутого

ограниченного мноаесгва

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

комбинацией

его

угловых

точек.

 

 

Согласно этой теореме,

точка

А явля­

 

 

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

комбинацией

 

 

вершин многоугольника Aj А2 A3 А^.что

 

 

в векторной форме записывается следу­

 

 

ющим образом : а

й.Ч^с.\+ь; а

а ч ,

Теорема

4. (обратная).

 

 

 

 

 

Любая точка, которую MOSHO представить

в виде выпуклой ли­

нейной комбинации крайних точек'замкнутого выпуклого множества, принадлежит этому множеству.

Теорема Ь.

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

- 16 - ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Общую задачу линейного программирования моино сформулиро­ вать следующим образом:

Найти экстремальное(наибольшееили наименьшее) значение

функции цели

L (

X )

 

 

 

 

( 2 - 1 )

(

X ) = C J X J

+ С2Х2

+ . . .

+ с;

+ с^ x n

при следующих

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

( 2 . 2 ) и

( 2 . 3 ) :

*

 

 

а І І х І +

А І 2 * 2 +

( 2 - 2 )

А 2 І х І +

А 2 2 * 2 F

- - " +

а > х }

+ —

+

а іЛ х п = *І '

— +

Х >

+

+

А 2П Хп = * 2 '

 

V Х ! +

Ѵ Х 2

+

+

4 Х /

+

+ V i 7 r

f » I T T

12.3)

Xj ^ 0 ,

х 2

> 0 ,

. . . , х* ^

0 ,

. . . , х п

^

0.

Функцию цели ( 2 . 1 ) называют также линейной формой или

функционалом.

 

 

 

 

 

 

 

 

 

Система (2.2)

носит, название

системы

уравнений

-

ограниче­

ний задачи

линейного

программирования.

 

 

 

 

Среди

ограничений

системы ( 2 . 2 ) могут

оказаться

неравен­

ства и даже все ограничения могут представлять собой неравен­

ства. Это не

нарушает общности рассуждении, гак как путем

введе­

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

мож­

но перейти к-эквивалентной системе уравнений.

 

Общая задача линейного программирования монет быть запи­

сана в матричной

форме:

 

 

найти

(2.10

L = с х->тах

'(илиmin)

 

 

 

 

 

 

 

*

при следующих

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

 

 

(2.20

А X =

В

и (2.3')

1 >

0 , где

 

 

С =

( O j

, с 2 , .

,

* ••• » " ji ^ —

 

 

матрица -

строка

;

 

 

 

 

 

 

 

17

 

 

 

 

 

a I I

 

3 I2

 

 

 

 

 

 

 

 

3 2І

 

322

 

 

32П

матрица системы

 

 

 

 

 

 

 

 

ограничений (2.2) ;

 

\ a m l

 

am2 /

 

mn

 

 

 

 

 

 

 

 

 

X =

 

 

 

 

 

В =

 

 

 

 

 

 

 

 

 

 

 

in

 

 

 

 

 

 

 

 

 

 

В и X

-

матрицы

- столбцы.

 

 

 

 

 

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

векторной

форме :

 

 

 

 

 

 

 

 

найти

(2.1'')

 

L (I) = с •

х —-> max ( и л и (ПІП )

 

при

следующих

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

 

 

 

 

(2.2, ; )

х2^2

 

 

 

 

 

 

 

(2.3")

О

(j. =1,2,... . Л ) , где

 

 

 

 

и С = ( c I t

c 2 ,

 

,

C j , , . . . , С Q )

-лекторы,

а

 

 

' I I A

 

 

'12

\

 

 

 

 

 

а 2І

 

 

 

а22

 

 

и Б

 

есть

также

лекторы.

 

 

 

 

 

 

.

Определение

I .

Решением системы (2.2)

или эквивалентных

ограничений (2.2')

и (2-2'0 на-зылаегся любой

набор из ц чисел

ХрХ^,• • •

 

I удовлетворяющий однолремеино

леем уралвениям сис-

тѳыы.

 

 

 

 

 

 

 

 

 

 

Определение

2.

.Всякое неотрицательное, решение системы(2«2)

или эклилалентных ограничении (2-2'')

и" (2.2'")

назылается допусти

мым решением.

 

 

 

 

 

 

Гос. публичаг.я

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

!.

научно-таки;;-.'оская

 

 

 

 

 

 

 

библиотека

СС С,°

 

 

 

 

 

 

 

I

 

ЭКЗЕМЛЯЯР

 

 

 

 

 

 

 

І

ЧИТАЛЬЬОГО

я д п д

 

Определение 3.

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

допустимое решение

или вектор X = (Xj,X £ ,•• . , х п

) , когда

векторы

I j ,

в ограничении (2.2'*) при положительных

xj.

линейно-незави­

симы-

 

 

 

 

 

 

 

Если число линейно-независимых лекторов п

(2.2; - ) равно 1 ,

где

? £ г п

» то. из определения опорного решения

(опорного

плана)

следует,

что число

его положительных координат

не более,

z

 

Не ограничивая

общности рассуждений,

можно считать,

что в

ограничении (2.2'') положительными являются первые z

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

тогда X = (х т X,

Xh .. 0,0, ... , 0 ), представляет

собой

базис-

ное

решение, или опорный план.

 

 

 

 

Определение 4. Задача линейного программирования называется невырожденной, если каждый ее опорный план содержит ровно 2 поло­ жительных координат.

Определение Ь. Задача линейного программирования называется вырожденной, если ее опорный план содержит менее, чем J? положи­ тельных координат.

Определение 6. Оптимальным решением задачи (оптимальным пла­

ном) линейного програнмирования называется такое допустимое реше­

ние (план), при котором функция

цели [_ (X) достигает

экстремума.-

 

Определение 7.

Функционал

U ( X ) называется линейным,

если

при(2.4)

1

= а.и

+ в,ѵ

выполняется (2.Ь)ЦК)-0-Ь{и)*е UvJ

для всех вещественных чисел

"а" и "в" и всех векторов

£ и ѵ •

 

Основные

теоремы линейного

программирования

 

 

Рассмотрим

задачу-линейного

программирования в матричной

форме

вида (2.1') -

(2.3').

 

 

•

Смотрите также файлы