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

при х.-=

ft

о

. Выберем среди всех отношений

'

наи-

меньшее, и пусть оно соответствует 1-му базисной

пере­

менной:

А _ =

п і і п - Ь _

( а ; - > 0 ) .

Тогда при возрастании Xj 'первой обращается в н у л ь

базисная

переменная

хь+с при значении х- равном

..

цательны. Коэффициент а/ ; -

называется

генеральным-

элементом.

Таким

образом,

для того

чтобы

определить

макси ­

мально

допустимое

значение

свободной

переменной

Xjy

мы д о л ж н ы найти

генеральный

элемент

<х(.;-. Д а л е е

сле­

дует

свободную

переменную

х}

и

базисную

.переменную

Xk+i

поменять

местами и выразить

новый

набор

базис­

ных Переме'ННЫХ

Л'А+1,

Xk+l-u

Xj,

Xk+i+U

Xk+m

через

новый

набор

свободных

переменных

Х\,

Лу _ и

З а п и ш е м

i-e

уравнение:

x k

+ i

- р,. — (адЛ-j + а/ 2 л\, -Ь ...

+

а , / _ ,

лу_і

+

a^-Xj

+

+

а</+1*7+1 +

••• +

а ; Л ) -

Поменяем

Xk+i

и xf

местами:

Xj

=

—

(Р, — ОдЛ"! —

... —

а,7 _1

л-/_1

—

—

аи

—

ац+ixj+i

—

aikxk).

И с к л ю ч им переменную Xj

из свободных переменных IB.

остальных

уравнениях

системы. Д л я

Z-ro уравнения

по ­

лучим

xk+i

=

Pi

—

Ia a

* i +

... +

a,;-_i x}-i

+

atj

ГГ 0Р/

I

L <ч

—

*1

" Г

•••

4

* / - !

" I

Л'А+І

І

+ l

+

+

+

+

c t / / + i

л : / + і

+

... +

alkxk\.

а и а п

х\

+

...+

< W - i

+ ( а / / - 1 -

Xj-i

— ~ x k . b

i

+

\a,j+i

аи

xI+l + ... +

[а1к

'-—

\х„

(1.3)

Ц е л е в а я

функция

в

результате

подстановки будет

•иметь вид

ъ

— -hr-

k i +

•••

+

+

l Y , - . - ^ k 1 au - ^ - M - M ^

Y; a«7±i

xi+i + ...

П р и н и м а я свободные переменные равными нулю, на­

ходим

новое базисное решение:

хх

=

0, ... ,

xk~i = 0, ... ,

хк =

0;

+ / = Р;

О/А

Р.'

а,

И«7

Т а к

ка к Xj = 0, х2 = 0,

хк

= 0, то целевая

функция

F = Уо

—•

Н а

этом

заканчивается

первый ша г решения. З а т е м

процесс решения повторяется

аналогично.

Критерием

ному относительно какого

-либо исходного

базиса.

2. В ы р а ж а е м

целевую

функцию через

свободные пе­

ременные. Если

в полученном в ы р а ж е н и и

все коэффици­

коэффициентов при Xj в правых частях

системы

ограни­

чений. Если

все числа

этого

столбца

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

то з а д а ч а не имеет

решения.

4. Пусть в столбце коэффициентов, упомянутых вы­

ше,

имеются

отрицательные. Д л я к а ж д о г о из них нахо-

о

дим

отношение

——. Выбираем

среди

этих

отношений

р

наименьшее. Пусть

оно соответствует

. Элемент

а,--

aU

называется

генеральным.

5. Переходим к новому базису, исключая из старого

Xk+i

и вводя

вместо него

Xj.

Д л я этой

цели

уравнение,

с о д е р ж а щ е е

Xk+i,

разрешается

относительно

xJt

и полу­

ченное таким

путем в ы р а ж е н и е

для х(

подставляем

во

все

остальные

уравнения

системы

ограничений.

После этого

в о з в р а щ а е м с я

к выполнению

п. 2.

К а к видно, изложенная процедура решения

является

довольно трудоемкой . В следующем

п а р а г р а ф е будет из­

л о ж е н о такое

решение с п о м о щ ь ю

симплексных

таблиц,

позволяющих

наиболее трудную часть вычислений свести

К а ж д а я строка

симплексной таблицы

соответствует

одному

уравнению

системы

ограничений

задачи . По ­

следняя

строка соответствует

целевой функции. Отметим,

ниях соответствующих

клеток.

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

таб ­

лице в следующей

последовательности.

1. Выберем генеральный элемент и найдем

величину

* = - L ,

З а п и ш е м А в клетку

ij.

2. Умножим на

X все коэффициенты

(кроме

а у )

из

верхних отделений

і-й

строки и

поместим

полученные

произведения в нижние отделения

соответствующей клет­

ки этой ж е строки.

3. Умножим на —X все коэффициенты

(кроме

а/ у -)

из

верхних отделений

у-го

столбца и

поместим

полученные

нием записанных

подчеркнутых чисел из той ж е

1-й стро­

ки и того

ж е s-ro

столбца.

После

заполнения указанным образом всех

клеток

бодной переменной X: в базисную вместо Xk+i,

а послед­

ней — в свободную. Система соответствующих

алгебраи ­

ставим в ы р а ж е н и е (1.3) д л я

базисной

переменной

x^+i

со строкой k + l, то заметим

полное их

совпадение.