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

т

п

т

1=1

1=1

1=1

т

т а х ( — 2 ^ у ) ;

т

— с4

+

2 а д > о .

Составим

дл я нее т а к ж е

функцию

Л а г р а н ж а :

т

п

т

F *

=

-

2

bjyj

+

V л - Д -

C i

+ V

а .

.у.).

/=1

i=l

/=1

При

записи

функции

Л а г р а н ж а

для прямой

задачи

множители

Л а г р а н ж а обозначили так же, как и перемен­

ные

двойственной

задачи,

а в

функции Л а г р а н ж а

для

двойственной задачи множители

Л а г р а н ж а обозначались,

к а к .переменные прямой задачи .

Из сопоставления обеих функций можно убедиться в

справедливости

соотношения max F o r n a x ( — F 2 ) ,

кото­

рое

у т в е р ж д а е т

равенство

значений

целевой

функции

прямой и двойственной задач .

Выводы

этой

теоремы

оказываются весьма полезны­

ряде случаев целесообразнее решить двойственную

зада ­

чу, а затем перейти к исходной — прямой задаче .

М ы рассмотрели формулировку двойственной

з а д а ч и

для случая, когда в прямой

з а д а ч е ограничения з а д а н ы в

форме неравенств. М о ж н о

привести формулировку

двой­

т

2 a y ^ y < c t (' =

!' 2 - ••• .

/ - і

К а к видно, в таком

случае в двойственной

з а д а ч е отсут­

ствуют требования

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

§ 1.7. Транспортная

з а д а ч а

Формулировка транспортной задачи .

Транспортная

потребления. З а д а н ы объемы производства а:

к а ж д о г о

пункта производства и размеры потребления Ь-}

к а ж д о г о

пункта потребления. Известна стоимость перевозки

сГ;

единицы

продукта из і-го пункта

в /-й. Требуется соста­

вить наиболее экономичный план

перевозок.

Математически задача

формулируется так:

т

п

m i n 2

2 < W ,

(1-13)

1=1 / = і

У1хі]

= аі

(t =

l ,

2,...,

m);

(1.14)

in

2 * . ; = Л

0 ' =

1,

2 , . . . ,

n);

(1.15)

* „ • > ( ) .

(1.16)

Равенства (1.14) гарантируют полный вывоз продукта

из всех пунктов

производства. Равенства (1.15)

обеспе­

В некоторых з а д а ч а х не ставится требование

баланса

производства и потребления, и условия-равенства

(1.14)

в таком

случае заменяются неравенствами

п

< ah

У, хп

ется. Транспортная з а д а ч а

в такой

форме

называется

открытой

транспортной

моделью.

К а к

и л ю б а я другая з а д а ч а линейного

программиро ­

вания,

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

з а д а ч а

может

быть

решена

симп­

лексным

методом. О д н а к о для транспортной

задачи

раз ­

обозначим переменные двойственной

задачи

так: v\,

v2,

vn,—«і,

— и 2 ,

— um. З н а к минус

перед

щ

ставится

ради удобства

изложения .

Тогда задача, двойственная по отношению к транс ­

портной, будет иметь следующий вид:

max |

V 6 / D /

— v a , 4 ;

(1.17)

І /=і

i=i

і

—

( і =

1, 2 , . . . , m\ }= 1,

2 , . . . , л).

(1.18)

Поясним экономический смысл двойственной задачи .

Если величины

—«,-, Vj интерпретировать ка к оценки

еди­

Переменные Vj и uL называются потенциалами.

Решение

задачи сводится к выбору таких потенциалов

пунктов

ную

функцию (1.17). Н а х о ж д е н и е

указанных

потенциа­

лов

можно было бы осуществить

симплексным

методом,

vj — щ =

си,

если

хі}

>

0;

(1.19)

Vj — щ <

Сц,

если

хц

=

0.

(1-20)

Не останавливаясь на выводе этого условия,

дадим

ему экономическое истолкование. Условие (1.20)

означа­

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

Ц меньше транспортных рас­

ходов, то д а н н а я перевозка

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

ж е , где

Ху>0, приращение оценки должно равняться за­

т р а т а м

на транспортировку.

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

Пункты произ-

Пункты

потребления

Запасы

водстаа

Я,

в.

в*

в,

Л

40

60

А,

80

Л3

40

60

80

60

100

Потребность

К

этой таблице

применяем тот

ж е прием.

Потреб ­

ность

пункта В2 за

счет At м о ж н о

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

только