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

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

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

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

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

Добавлен: 29.06.2024

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

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

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

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

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

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

-29 -

Уп р а к н е н и я

Найти экстремальные значения функции цели L (X) при задан­

ной системе ограничений.

I .

L• С

X ) =

IOXJ -

2 х 2

2.

L f

x

>

=

5xj

+

bx2

при

 

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

 

 

при

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

х І

 

 

2хс

 

I ,

 

 

 

2Xj + 7x2

?

 

29,

+

 

X 2 *

 

 

 

 

X I

H

4 2 *

 

7,

2xj

+

 

x 2

^

12,

 

 

 

7xT

+ 2x£ 20

?

 

29,

5 X j

-

 

x2

<z

2 '

 

 

 

 

 

 

x 2

i

 

12.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

L С

X ) =

4Xj

+

6^

4.

L C

X )

=

6Xj

+

9x2

при

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

 

 

при

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

2Xj

+

Зх 2

-, I I ,

 

 

 

4х т

-

9x,

 

 

18,

 

 

 

 

1

 

,

2 _

-

з

,

xT

+

 

2x2

^ 12,

 

 

 

2Xj

+ 3x2

^

 

24,

2xT

 

 

x 2 3 ' -

 

 

 

 

. 2xL

+

l 2

* 9.

 

L ( X ) = 8xj +2x2

 

L (

 

X,)

=

Xj +

x2

при

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

 

 

при

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

3Xj

+

2x2

^30,

 

 

 

-2Xj +

x2

 

 

4,

 

4xT

+

 

x 2

^

4,

 

 

 

X

I

+

X 2

^

I

0 '

 

 

 

 

 

> I 2 ,

 

 

 

 

4xT

+ X 2

 

 

 

Xj - 2x2

^_ 4,

Xj

+

 

2x2

>

.6.

 

 

 

Xj

+

2x2

>

 

8.

7. L

(

 

X )

 

4

+2x.

 

 

L ( X ) =

 

 

 

 

при

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

 

 

при

 

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

 

 

Зх„

 

6,

 

 

 

 

 

 

2x.

-<

 

6,

 

xI

+

 

x 2

^10,

 

 

 

2xT

 

v 2

>$

 

0,

2Xj

+

3x2

^ 30,

 

 

 

Xj

+

x 2

^

15,

X T

 

 

" >

6.

 

 

 

Xj + 2x2

> £0.

 

 

- 3 0 -

§ 4.

МЕТОД ПОСЛЕДОВАТЕЛЬНОГО УЛУЧШЕНИЯ ПЛАНА

Рассмотренный, ранее графический метод имеет некоторую цен­

ность благодаря

своей наглядности, но при II .> 3 он применатьсз

не может. Решение задач линейного программирования с любым числом

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

ется метод последовательного улучшения плана, основные идеи кото­

рого

были разработаны американским

математиком .Данцигом. Этот ме­

тод в литературе фигурирует часто

под названием

с и м п л е к с ­

н ы й

метод (или симплекс-метод).

 

 

 

С геометрической точки зрения этот метод похож на графичес­

кий. Как и л графическом методе значение функции

цели исследуется

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

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

Дана система линейных ограничений - неравенств (4.1):

V •
*t '

a I I x I

+ a I 2 x 2

a 2 I X I

+ a 22x 2

(4.1) < a L l x I

+ a L2X 2

a t I x I

+ a t2 x 2

.+ ... + %

+... + %

+... + ai,J-

+... + 4

. + a ll1

x rt

. + а 2П Xj?

. + a \ n

x n

a tn

*л

 

. a m i x i

+ a n2X 2 + ... +

 

Xj.+ .

аІЛі7 *<1

 

и функции цели

(4.2)

L ( X ) =

cQ

+ C J X J

+ CoXp + . . .

+ C ; Ï | . +

 

 

 

 

 

. . . T C^Xf,.

 

 

 

Требуется найти такое неотрицательное решение

 

(4.3)

X j i . О, х 2

0,

. . . j X j .

?

0, . . .

, х п

^ О

 

системы(4.І),

при котором функция

цели (4.2)

принимает

экстремаль­

ное

значение.

 

 

 

 

 

 

 

 

 

Для определенности

рассмотрим

случай

максимизации

функций

цели. Решение начинается с отыскания допустимого значения опорного

плана (базиса). Для этого от системы неравенств (4.1) переходиы к

системе уравнений (4.Ь) путем введения дополнительных неотрицатель­

ных переменных

 

(4.4)

 

x n +j^0, xn + 2,>Q,,..,xn + L

 

д. 0, ... ,x f ) + l î J ^

0 ;

а

І І

х

І

+

а

І 2

х

2

+

.

+ ат

X: +

• '

+ а

Ы

х

 

•

+—

V i

 

= * Р

 

 

 

 

 

 

 

 

 

 

 

О

 

 

 

^21^1

+ ^22*^2

 

* * * "^" ^2 ^

^ * * * "^"^2^^'"^ "^*

*^іт^"2

„

= в 2 >

а І І х І +

\ 2 Х 2 +

 

+ % %

г

+

...+аи 1 х,-)

+

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a t I x I +

a t2 x 2 +

 

+ а і у х

у

+

. . . + а . „ х ) 7

+

 

 

 

=Bt ,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+ а,т

X +

. .+а.„,х,, +

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

un,

1:

 

 

 

 

Коэффициенты при дополнительных

неотрицательных

переменной

(4.4) образуют

 

единичную матрицу .m -го порядка,поэтому она являют­

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

и,следовательно,

 

составляют

базис,

итак,

неременные

 

(4.4)

принимаем за базисные,

в общем случае кеотркца-'

- 32 -

тельные, а переменные (4.3) за свободные, .равные нулю.

йыракая базисные переменные через свободные, получим:

-11+1 =

х П+2 ~

x n+t =

> m -

- I -

^иН

+ а І 2 х 2

•*•...+ aT-i x '

"г - ( a 2 l x j

+ a 22x 2

+ . . . +

 

\ -

( - U - I

+ a l2 X 2

+ .... +

 

*t -

<

a

t l

x

l

+ a t 2 x 2

+ . . . +

Ч х і -

 

 

 

 

- m " < a m l x l +

a n ,2x 2 + " — + \ * y +

+ . . . +

 

 

+ "... +

a2 n xn

) ,

+ . . . +

V n ,

!

+ . . . + a tn x n ) »

— + V « > -

(4.7)

L С X )

=

c 0

-

(-CJXJ

- c 2 x 2 - . . .

-

c^x^- . . .

- c n

x n

)

=

 

 

 

=

C0

-

(Çj-Xj + C^g + . . .

+ C'X;+ . . . + c'n xn

) ,

ГД e

Cj ~

 

'

^2 =

""^ ^ ' * " * '

—

— С *

Cp —

—С ß »

 

Из системы

ограничений

(4. ь)

и функции

цели

(4.7)

находим,

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

решение:

 

 

 

 

 

 

 

 

 

 

-п+і

- • " - > •

 

 

I

 

 

 

 

 

 

 

 

 

X Q t ? . T . . f 2 .

 

 

 

/

 

 

 

 

 

 

 

 

 

X X ,

=

в

 

 

 

 

 

 

 

 

 

 

 

 

-n+t =

- t

> п

р

и Э І 0 Ы Ф2/НКЦИЯ

Ч ѳ л и

 

L

( X )

= Cp .

 

 

 

 

Можно сформулировать следующий признак оптимальности: в опти

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

максимума

функции цели необходимо

и достаточно, чтобы все коэффи­

циенты ее

C j , с 2 ,

 

с ' , . . . , Ср

были

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

 

 

 

Исследуем коэффициенты

функции цели

(4.7). Если хотя

бы один

из коэффициентов с^

, с£

с':

, . . . , с п

отрицателен,

го

путем

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

- 33 -

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

вилу, при этом значение функции цели (4.7) должно возрасти.

Примечание I . В оптимальном решении задачи линейного про­

граммирования на отыскание минимума функции цели нѳрбходимо и

достаточно, чтобы все коэффициенты ее

C j , с^ , . , с-

были неположительными.

 

Примечание 2. При устранении так

называемого "вырождения",

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

мизации оно ни в коем случае нѳ может уменьшаться, а при миними­ зации - не может увеличиваться.

Допустим, что среди коэффициентов Çj , с 2

имеются отрицательные коэффициенты. Из этих отрицательных чисел

выбираем наибольшее по абсолютной величине, так как введение в

базис соответствующей свободной переменной способствует большему

увеличению функции цели. Предположим,

что таковым является

с' ,

Тогда полагаем х-> ^ О, а все остальные

свободные переменные

У

по-

У

 

 

прежнему имеют нужавыѳ значения. Б этом случае значение функции

цели (4.7)

возрастает.

 

Итак,

переменную х-

необходимо из свободных переменных пѳ-

рѳвести в

число базисных

переменных. Однако х- можно увеличивать

 

 

У

только до

тех пор, пока

впервые не обратится в нуль какая-либо

из базисных переменных (4.4), а остальные базисные переменные

сохранят свои неотрицательные значения. Находим значения базис­

ных переменных из системы (4.ь)

при условии,

что

х«

ê

0,

а

все

 

 

 

У

 

 

 

 

остальные свободные переменные

іт х , ,

і> . |

,

х;,;

,

хп

 

2

у

 

 

У

'

 

по-прежнему нули. Тогда будем иметь:

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