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

Таблица

1.5

Пунктункты

Пункты потребления

Запасы

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

В .

|

В 3

В ,

20

20

80

А3

60

80

60

100

Потребность

Таблица

1.6

Пункты

Пункты

потребления

Запасы

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

Во

|

В,

|

ВІ

л„

40

80

АІ

40

80

60

100

Потребность

частично — на 20 единиц. В

результате получаем новую

таблицу, без первой строки (табл.

1.6).

Аналогичным приемом, п р о д о л ж а я

удовлетворять

по­

требности

всех

пунктов

потребления,

мы

окончательно

получим

т а б л .

1.7.

Таблица

1.7

Пункты

Пункты

потребления

в,

Запасы

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

в,

Вз

в.

Ах

40

20

40

60

А,

40

80

А3

40

60

40

60

100

Потребность

80

60

Заполненные

клетки

этой таблицы

характеризуют

ба­

зисное

решение

(хп

= А0,

xl2 = 20,

х 2 2 = 4 0 , л-2 з=40, л-3 3

=

40,

хи=60).

Незаполненные

клетки

определяют набор

сво­

бодных

переменных.

методом

«северо-за­

Д а н н ы й

алгоритм

называется

падного

угла»

в

соответствии со

способом

заполнения

таблицы,

согласно

которому

к а ж д ы й шаг заполнения

на­

чинается

с левой верхней (северо-западной)

клетки.

Алгоритм метода потенциалов. Вычислительная схема

метода

потенциалов позволяет, отправляясь

от некоторо-

го допустимого

базисного

решения,

получить

решение

задачи

за конечное

число

шагов. Схема вычислений по.

к а ж д о м у шагу

состоит в следующем. П о данному

базис ­

ному

решению

к а ж д о м у

пункту

задачи

придается

число,

называемое

его потенциалом.

Потенциалы

выби­

раются

так,

чтобы их разность для к а ж д о й пары

пунк­

тов, у которых

хи>

0, была равна си—

стоимости

пере ­

возки м е ж д у

этими

пунктами единицы

продукции.

Таким образом, к а ж д ы й шаг решения можно считать

состоящим из двух этапов . Н а первом этапе

проверяется

решение на оптимальность. В случае неоптимальности;

осуществляется переход ко второму этапу.

Н а втором

транспортными

расходами .

Поясним

методику

вычисле­

ний на к а ж д о м

этапе.

Пусть

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

базисное

решение..

Д л я

проверки

его на оптимальность

придаем

к а ж д о ­

му

пункту

потенциал: v h

...,vn, —щ,

—

u m . Д л я

к а ж ­

дой базисной переменной

составляем

уравнения v}— щ =

=

Сф

число которых

равно числу

базисных

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

т. е. m + n—1.

Число

переменных

т + п

превышает на

единицу число

уравнений.

Д л я разрешимости

системы

уравнений

полагаем

одну

из переменных равной

произ­

вольному

числу, например

щ = 0 . Тогда значения

осталь ­

ных переменных определяются однозначно.

П о с л е этого осуществляется проверка

решения на оп­

тимальность. Если дл я всех свободных

переменных вы­

полнено неравенство

Vj — « г < с , 7

, то говорят, что систе­

ма

потенциалов v u v2,

...,v/lt

—щ,

—иг,

—

и т

потен­

циальна и полученное

решение оптимально.

Если ж е д л я

c7l=cIi-{v,-ui).

(1.21)

О п р е д е л я е м

пару

индексов г'о, /о из

условия

с?,/. = min с?/.

•Соединим пункты

Ас0 и Bj0

маршрутом из

коммуника­

ций, составляющих базис.

Пусть данный м а р ш р у т проходит последовательно че­

рез пункты

Aia,

Bh,

Аіг,

ВІ2,

BJs_l0,

Bjt.- Р а с ­

значим через

ЭА . Введем

в базисное решение следующие

изменения:

на

тех

коммуникациях пути Д - 0 ,

Ви,

...

Bj0,

вдоль

которых

перевозки осуществляются в

поло­

жительном

направлении,

уменьшаем

их на

0,,,

на

ос­

тальных коммуникациях увеличиваем их на

Э/ ( . Кроме

того, введем

новую

коммуникацию А-0 —В,-а

с перевоз­

кой,

равной

Qk. В результате получим новую совокуп­

ность

коммуникаций, определяющую базисное

решение,

д л я которого сохраняется баланс вывозимого

и

ввози­

мого

продукта. В то ж е

время отметим

без доказатель ­

ства, что новое базисное решение приводит к

меньшим

транспортным

расходам, т. е. к уменьшению

целевой

функции.

И т а к , метод

потенциалов позволяет, отправляясь от

v — щ < с,7 ,

если х и =

0;

(1.22)

Vj

—

Щ > с-ф

если

xi}

=

d,f,

(1.23)

Ь

; —

щ = сч,

если

0 <

хц < dir

(1.24)

Потенциалы

Vj и

ut

можно, как и прежде,

считать

тации условия

(1.22) — (1.24) имеют следующее истолко­

вание: если

приращение

оценки

продукта v-s — иг

при его

перевозке

по

соответствующей

коммуникации

меньше

транспортных

расходов

с/ у -, то д а н н а я перевозка

эконо­

мически нецелесообразна. Поэтому ее значение

д о л ж н о

быть равным

нулю. Если указанное приращение

оценки

ка целесообразна,

и она

д о л ж н а

иметь

максимальное

значение, т. е. равное пропускной

способности коммуни­

кации

<іи.

О б щ а я схема

метода

потенциалов

применительно к

данной

з а д а ч е остается такой же,

как

и в

случае обыч­

серии

итераций. К а ж д а я

итерация

распадается

на

два

этапа .

Н а первом

этапе

решение,

полученное на

преды­

дущей

итерации,

проверяется на

оптимальность.

В

слу­

транспортным

расходам .

Расчет начинается с получения исходного допустимо­

го базисного

решения. Д л я этой цели может быть ис­

пользовании

его необходимо

учитывать ограниченную

пропускную способность некоторых коммуникаций.

Н а первом

этапе

итерации

определяются

предвари­

тельные потенциалы

из системы уравнений

vf — щ = Сц

для всех элементов Cjj, для которых выполняется

соотно­

шение

0<xlf<dtr

(1.25)

чений. Если

сц Г^О д л я всех х^ = 0

и с%- s£0 для всех

Xij

= djj,

то

решение оптимально. Этот вывод вытекает

из

критерия

оптимальности.

Если

ж е

решение неоптимально, осуществляется пе­

реход ко

второму этапу итерации. Н а

этом этапе произ­

тельных

чисел

С*ц (для хч

= 0)

II —

С*ц (для х,7

=

dij).

В результате

имеем

минимальное

значение

с*0/„ .

Так же, к а к и в обычной транспортной

задаче,

строится

цепочка

из

базисных коммуникаций,

начинающаяся

в г'о

и кончающаяся в / 0 .

Возможны два

случая:

хц

1) Ф о

принадлежит

с*/

(для

=

0);

2 ) с*о/о принадлежит—с*,-

(для

хц

=

du).

В первом случае улучшение

решения осуществляется

т а к ж е ,

как

и в обычной транспортной

з а д а ч е :

вводится

новая коммуникация і0 /о с потоком

Qk.

На тех

комму­

никациях цепочки, которые идут в

положительном

на­

правлении,

перевозки уменьшаем

на

Qk, на остальных

коммуникациях увеличиваем на

Qk.

Величина

Qk

выби­

каций, на которых предполагается увеличение

перево­

зок, т. е.

Qk = min(Qk,

Ql

dij,),

(1.26)

где

Q'k = min Хц

— для

положительных

направлений

це­

почки;

Q"k

= min(d; - — X;)

— для

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

направлений

це­

dij0

почки;

— предельная

пропускная способность

коммуникации

i 0 / 0 .

осуществляется

Во втором случае улучшение решения

за

счет уменьшения

размера перевозки

м е ж д у

пунктами