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

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

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

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

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

Добавлен: 04.07.2024

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

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

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

x i

+

* 2 +

xs

=

6;

 

л-! +

2л-2 +

 

л-4 -

8,5;

 

A'I -1- A-3 =

4;

 

 

jts

+

x, =

3.

 

 

Перепишем

систему

ограничений так, чтобы одна

часть

переменных

была

в ы р а ж е н а через другую часть:

А'з = 6 — А'і

— А'2;

 

дг4 =

8,5 — . Yx -- 2л-,

 

А'5

=

4 — Лу,

 

 

хв

=

3 — х„.

 

 

При такой записи системы ограничений переменные,

стоящие

в левой

части, называют

базисными,

а стоящие

в правой

части,

— свободными.

Значениями

свободных

переменных можно варьировать, при этом базисные пе­ ременные приобретают соответствующие значения. Пусть * i = 0 , х2 = 0. Тогда А'з = 6, А" 4 = 8,5, л-5 = 4, А - 6 = 3.

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

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

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

20

ют т а к ж е методом последовательного

улучшения

плана.

П о д планом

в данном случае понимается

базисное ре­

шение. Такое название, по-видимому, точнее

о т р а ж а е т

суть вычислительного метода.

 

 

 

Итак, идея симплексного метода заключается в после­

довательном

переходе от одной вершины

многогранника

к другой в

направлении улучшения

целевой

функции.

Проиллюстрируем сказанное на нашем примере. С этой целью проверим возможность увеличения целевой функ­

ции за счет изменения значений х х и х 2 . Нетрудно

убедить­

ся, что

увеличение

любой

из

них

приводит

к возра­

станию целевой функции. Будем

увеличивать только Х\.

Увеличение

Х \ допустимо

до тех пор, пока хотя

бы одна

из

базисных

переменных

окажется

равной нулю. Ясно,

Х \

можно увеличивать до 4: при

* i = 4 базисная

перемен­

ная х$

приобретает

нулевое

значение. Меняем

местами

х х

и х 5

, т. е. Х\ переносим

в левую, а х$ — в правую часть

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

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

х 2

и х$. В ы р а ж а я

новые

базисные

пере­

менные

А'з, х\,

Х\, х е и целевую функцию

через

Х2

И Xsr

получим:

 

 

 

 

 

 

 

 

 

max (8 — 2лг5

+

Зл'2 };

 

 

 

 

 

Л'з

=

2 - j - ЛГ5

 

Хп\

 

 

 

 

 

х 4

=

4,5 + хь

— 2ха_\

 

 

 

 

 

* i

=

4 — х Б ;

 

 

 

 

 

 

 

 

л*б= = :

3

л*2*

 

 

 

 

 

 

 

 

Н о в ое базисное

решение равно: * 2 = 0; * 5 = 0;

х3=2;

* 4 = 4,5;

* i

= 4;

* 6 = 3 .

 

 

 

 

 

Значение целевой функции: ^ = 8.

 

 

 

Буде м

теперь

увеличивать

х 2 .

П р и * 2 = 2

получим

*з = 0. Меняем местами х 3 и х 2

и, в ы р а ж а я

целевую

функ­

цию через х 3 и х 5

, получим:

 

 

 

 

 

т а х { 1 4 + х 5 — 3* 3 } ;

 

 

 

 

 

х2 — 2 -f- х5 — х3;

 

 

 

 

 

 

ХІ

=

0,5 — хъ

+

2х3;

 

 

 

 

 

* i

=

4 — х$',

 

 

 

 

 

 

 

 

хв

= 1 — х § -(-

х3.

 

 

 

 

 

 

21

 

Б а з и с н ое

решение: х3

= 0; х5

= 0;

х2 = 2;

ХІ = 0,5; Хі = 4;

x6=l.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ц е л е в а я

 

функция:

F = 1 4 .

х$,

 

 

 

 

 

х5,

Д а л е е , увеличивая

значение

меняя

местами

х 4

и

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

получим:

 

 

 

 

 

 

max

(14,5

—л-3

— л - 4 );

 

 

 

 

 

 

 

 

х2

=

2,5

-J- х3

х 4 ;

 

 

 

 

 

 

 

 

 

хъ

=

0,5

+

2х3 —-л-4 ;

 

 

 

 

 

 

 

 

 

хх

=

3,5 — 2л-3

+ х 4 ;

 

 

 

 

 

 

 

 

 

х6

=

0,5 — х 3 +

х 4 .

 

 

 

 

 

 

 

 

 

Базисное

решение: *з = 0; х6

= 0,5; Хг = 2,5; х 4

= 0;

ху

=

=

3,5;

* 5 = 0 , 5 .

 

 

 

 

 

 

 

 

 

 

Значение целевой функции: 7* =

14,5.

 

 

 

 

 

Полученное решение

является оптимальным,

так

как

дальнейшее изменение свободных переменных не приво­ дит к увеличению целевой функции.

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

рое число

вершин

многогранника, причем к а ж д ы й

пере­

ход от одной вершины к следующей сопровождается

уве­

личением

целевой

функции.

 

§1.3. Алгоритм симплексного метода

Ра с с м о т р и м схему алгебраических преобразований си­ стемы ограничений и оптимизируемой функции при ре­

шении з а д а ч и

симплексным методом. Отметим, что стан­

д а р т н а я вычислительная схема

симплексного

метода бу­

дет

излагаться

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

к. з а д а ч е

минимизации.

Эта

ж е схема

может быть использована

т а к ж е и для

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

но в этом случае требование

максимиза ­

ции следует заменить требованием минимизации. Воз­

можность такой

замены

вытекает из справедливости сле­

дующего соотношения:

 

max | J ] с Л |

= min |

— J j с Л

22

Пусть

з а д а ч а

линейного

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

имеет

вид:

 

 

 

 

 

 

 

 

min F — сххх

+

с2х2 + ... +

спхп;

 

 

ОЦХІ

+ а1гх2

+

... + а1пхп

= Ьг\

 

 

а 2 А

+ «22*2 +

... + а2пх„

= Ь2;

 

 

а / » А

+ flm2*2 + ••• + атпХп

 

—

 

 

' Х ! > 0 , х 2 > 0 , . . . , л - л > 0 .

 

 

 

З д е с ь

т<п.

 

 

 

 

 

 

Если

система

уравнений

независима, то число свобод­

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

равно п—m = k, а число базисных

пере­

менных

— т. Обозначим

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

через

Х\, х2,

 

xk, а базисные переменные — xk+\,

Xk+ч,

 

Xk+m-

П р е д п о л о ж и м , что нам удалось одну

часть

пере­

менных — базисных — выразить через другую часть —

свободных. Тогда задач у

 

линейного программирования

можн о переписать так:

 

 

 

 

 

min F = Y0 +

 

Y | * i + ••• +

У'кх»

 

 

A'ft-и =

а\хх

+

... +

a[kxk

+ pft;

 

 

x k + l

=

a'nxx

+

 

... +

a l k x k

+

ft;

 

 

 

x k + m

=

ixmxx

 

+

... +

a m k x k

+

pm .

 

 

Е с ли

Xt = 0,

x2 = 0,

 

xk=0,

то мы имеем

следующее

допустимое базисное

решение:

 

 

Xk+l =

Pi, Xk+2 = Р2, ... ,

Xk+l — Р/, ... ,

Xk+m

= P m .

П р е ж д е чем излагать

общую схему

перехода к сле­

дующему базисному решению, перепишем задач у в та­ ком виде:

23

min F = Yo — ( — Y > ' i —

*fc + i = P i — ( — a — •

a iuA 'fr);

Xn = P,« — ( - V ' l — -

-

Обозначив — a'.. = a,y, —у'. = y{, получим:

min F = Y0 — ( y ^ +

... +

у„хл);

* t + i =

P x — (au A-! + ... + a17;,v,,);

A'ft+m =

P m — (a,„iA'i +

... +

а „ , Л ) -

Выберем теперь из f одну из переменных Xj, дл я ко­ торой коэффициент у/ в целевой функции положителен . Если увеличивать, то целевая функция будет умень­ шаться . Причем увеличивать Xj можно до тех пор, пока одна из базисных переменных не обратится в нуль. Когда это произойдет? Перепишем систему ограничений, пола­ гая все свободные переменные равными нулю, за исклю­ чением ху.

Л 'й + I = Pi —

aljXp

X'k+i

= Pj —

aijxji

xk+m

— P m

amjXj-

Если a i y -^0, то увеличение Xj не вызывает уменьше ­ ния базисной переменной. Следовательно, на те базисные

переменные, для которых

«£0, можно не о б р а щ а т ь

вни­

мания .

 

 

 

 

Рассмотрим теперь те базисные

переменные,

дл я ко­

торых а ( 7 > 0 . Б а з и с н а я

переменная

о б р а щ а е т с я

в

нуль

24

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