Файл: Падалко Л.П. Математические методы оптимального планирования развития и эксплуатации энергосистем учеб. пособие.pdf

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

Базисные

Свободные

переменные

члены

х,

xs

4 + 1

P i —

aIs—^ais'xlj

Xk+l

а д — X a / l a-lj

als—lals*ij

а1к—Л"lkal і

xj

X

Xk+m

F

Ik—Ішу

Т а к им образом, при использовании симплексных т а б ­

лиц

нет необходимости к а ж д ы й раз

проделывать

с л о ж ­

ные

алгебраические преобразования .

Стандартный

алго­

многих з а д а ч а х базисное

решение находится

весьма про­

сто, как, в частности, в

используемом нами

иллюстра ­

anXi

+ a12x2

+...+а1пхп

=

Ьг;

&21Х1

~Ь OonXv, -\- ... -f- QonXn

=

Ь2 і

/1 л \

a m l X l

+ am"X1

+

•••

+ amnXn

=

bm- .

Свободные члены д о л ж н ы

быть

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

Если для какого-либо уравнения это не выполняется,

мы

у м н о ж а е м его на —1.

Введем вспомогательные, или искусственные, пере­

менные

уи у%

ут,

связанные

с Х\,

х2,

хп уравне ­

ниями:

у1 =

Ь1 — (а1гхх

+

а1 2 л-2

+

... +

а1пхп);

У-2 =

Ь» — ( « 2 1 * 1

+

й22Х2

+

•••

+ а2„Хп)'<

/1

сч

У,п =

Ьт — (атЛхх

+ ат,х,

+

... +

атпхп).

Очевидно, решению системы

(1.4) д о л ж н о

отвечать

решение системы (1.5) с условием

г/і=0,

(/2 = 0,

ут = 0 .

В системе (1.5) переменные

у2,

Ут

образуют

этого

базиса,

перейти

к

другому,

не

с о д е р ж а щ е м у

уг,

І/2,

Ут- Иными словами,

допустим,

что после

преобра­

зований

мы получим систему:

* i =

P

i — ( a i i - V m + H -

•••

+ a i n * „

+ Y

i i #

i

+

. . .

+У1тУт)\

x2=$2—{a.llxm,l+

... +аіпхп+упу1+

...

+y.lmym);

Xm = $m—(amlxm + l+

••• +атпХп

+ УтіУі +

- +УттУт)-

(1-6)

П о л а г а я здесь tj\,

г/г,

•

Ут

равными нулю,

получим

систему:

* і = Рі — ( « і Л + і +

-

+ « і п - 0 ;

і

(1.7)

Л 'ш =

Рш

( а ш А ! 1 ~Г

•••

" Т " а т ; Л і ) .

j

Э т а система

д о л ж н а быть равносильна

системе

(1.4), и

поэтому з а д а ч а нахождения допустимого базисного

ре­

шения

выполнена.

Д л я

того

чтобы перейти от

системы

(1.4)

к

системе

.(1.7),

необходимо решить

задачу

минимизации:

min F = yl

+ ya + ... + уп

(1.8)

при ограничениях (1.5).

Если

при

рассмотрении

последней

симплекс-таблицы

о к а ж е т с я ,

что переменные

у\, г/2,

Ут

будут

свободны­

ми, то это

означает, что

мы пришли к системе

(1.6),

т. е.

з а д а ч а

решена. Ц е л е в а я

функция

(1.8)

приобретает

при

этом нулевое

значение.

Если

ж е о к а ж е т с я ,

что min F

>

0, то это означает,

что

система

(1.4)

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

решений. Отсю­

да вытекает,

что и задача

линейного

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

т а к ж е

не имеет решения.

Р а с с м о т р им следующую

з а д а ч у

об

использовании

сырья. Д л я

производства

двух

видов продукции

исполь­

зуются четыре вида сырья . З а п а с ы сырья

и его расход на

изготовление единицы к а ж д о г о

вида продукции

з а д а ю т с я

табл .

1.3. Коэффициент

аи- показывает,

сколько

требу­

ется

сырья

1-го вида д л я

производства

единицы

продук­

ции вида /.

Таблица 1.3

Продукция

Виды

сырья

Запас сырья

1

1

ь.

«и

«12

2

«22

3

«31

«32

4

«41

«42

Доход

В

последней строке у к а з а н

доход,

который

получает

Математическая

формулировка задачи

такова:

max

{сххг

+

с2х2);

(1.9)

a i i x i + а и х 2 < Ьх;

азххх

+ а32х2

< b3;

« 4 1 * 1 +

« 4 2 * 2 < bA.

Иными

словами,

требуется

максимизировать

доход

при соблюдении ограничений (1.10). Здесь

х \ и х 2

— ко­

личество продукции

соответственно 1-го и

2-го видов.

Рассмотрим теперь другую задачу . Предположим, что

некоторая

организация ж е л а е т

приобрести

сырье,

кото­

цене предприятие

будет продавать

сырье

организации?

Обозначим через

уи у2,

Уз, УІ цену

к а ж д о г о

вида сырья.

Ясно, что предприятие

не

будет продавать сырье, если

выручка от этой

п р о д а ж и

окажется

меньше дохода, ко-

3 Л. П. Падалко

33

min

+

b„y„ + b3tj3

+ biiji);

(1.11)

вцУі

+

а»гУі +

апУз

+ СЦ\УІ

>

сі,

)

(1.12)

вііУі

+

« 2 2 0 2 +

аз°Уз

+

a^JJi

>

с».

)

Сравнивая

данную

задачу

с предыдущей, мы заме ­

чаем следующие

особенности:

1) матрица

w 1 2

а 2 ї а32

а 4 „/

^21

^ 2 °

а 3 1

а32

с 4 1

а 4 2

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

строк столбцами;

2) неравенства в системах ограничений направлены в.

разные

стороны;

3)

роль свободных членов

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

(1.12) выполняют коэффициенты

максимизируемой функ-

чений

(1.10);

4)

в .первой

задач е

целевая

функция

максимизирует­

ся, во второй — минимизируется.

Д в е

задачи

линейного

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

имеющие

такие связи м е ж д у собой, называются взаимно

двойствен­

ными.

Таким образом, если п р я м а я

з а д а ч а

линейного про­

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

имеет такой вид:

max

+ с2 *2 +

... +

спхп);

% Л + а12х„

+ ... + а1ах„

< V .

°ПХ1

+ ^22*2 +

••• + а2пХП

<

Ь „ \

а « Л

+ а„.2х2

+

••• + a m n x n <

Ьт;

* х > 0 , - v 2 > 0 ,

... ,

л - „ > 0 ,

то двойственная к ней будет следующей:

min [Ьш + b2y2 + ... +

bmijm}\

ОііУі

+ аиУг

+

••• +

ат\Ут>с\>

аігУі

+ а-ігУг +

••• +

атіут

> с3 ;

ащУі

+ а2пУ2

+

••• + атпут

>

ст.

Основой теории двойственности является

следующая

теорема: если

одна

из двойственных

задач

линейного

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

имеет решение,

то и

другая

задача

также

имеет решение,

при

этом

максимум

одной

задачи

равен

минимуму

другой.

Эту

теорему можно доказать,

прибегнув

к

множите­

л я м Л а г р а н ж а . С этой

целью составим

функцию

Л а г р а н -

ж а для прямой

задачи:

m

п

п

^ і = 2 с Л + 2 yfti

- 2

Ч*Ъ-

i=\

/=1

1=1

3*

35