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

З д е сь /г+ 1 — дополнительный, фиктивный пункт потре­ бления.

Предварительные потенциалы определяются в резуль­ тате решения этой системы. Основой метода решения ее является простой способ решения систем уравнений вида:

« 1 1 , «12. •••> «1л !

«21, «22, «2л1

50

столбцов. Не приводя вывода этого метода, перейдем к рассмотрению метода решения системы (1.35).

тельных элементов, соответствующих исходному базисно­

П о л о ж и т е л ь н ы е элементы вычеркиваемых линий ну­ меруются в порядке вычеркивания соответствующих ли­ ний. Процесс вычеркивания линий длится либо до ис­ черпания всех элементов матрицы, либо до получения такой подматрицы из неотмеченных элементов, в к а ж д о й линии которой содержатся два положительных элемента .

В первом случае, когда все положительные элемен­ ты отмечены, н а х о ж д е н и е потенциалов начинается с вы­

нение (1.36), полагаем потенциал соответствующей стро­

один за другим отмеченные элементы матрицы в порядке убывания их номеров и используя уравнения системы (1.35), определяем все предварительные потенциалы.

Во втором случае неотмеченные положительные эле­ менты составляют одну или несколько замкнутых цепей вида

Xiljl> XiZjl> X12J2< ••• > Xit—ljt—l> XiXjl—X-

Пользуясь уравнениями системы (1.35), соответствую­ щими элементам цепи, можно один за другим выразить

ветствующим рекуррентным соотношениям — остальные потенциалы.

После определения предварительных потенциалов про­ веряется выполнимость следующих условии:

4 ' =сц — (hFj — Щ)>Ь

и , > 0 .

Эти условия отвечают признаку оптимальности. Если условия не соблюдаются, то осуществляется переход ко второму этапу.

Второй этап

Расчет на втором этапе начинается с выявления наи­ меньшего отрицательного числа с*0 /•:

c ? 0 / o = min 4- .

З а т е м осуществляется перераспределение поставок путем заполнения клетки с отрицательным числом. Н и ж е будет показано, как это осуществляется, но прежде для лучшего уяснения сущности метода поясним его на при­ мере транспортной задачи . Пусть условие транспортной задачи записано в табл . 1.8.

Таблица 1.8

В этой таблице показано исходное допустимое базис­ ное решение (цифры в правых нижних углах клеток) . Попытаемся осуществить перераспределение. Это можно

52

Перераспределение поставок осуществляется в резуль­ тате просмотра четырех клеток. Путь просмотра образо ­ вал цепь, которая показана на рис. 1.3. Свободная ранее клетка, в которую мы поместили поставку, отмечена пря­

моугольником, а остальные — к р у ж к а м и . В вершинах этой цепи у к а з а л и величину з а т р а т с1} с соответствую­ щим знаком (увеличение или снижение поставки) . Ал­ гебраически просуммируем числа, находящиеся в вер­ шинах цепи ( + 3 — 2 + 1 — 4 = — 2 ) .

Нетрудно убедиться в том, что сумма показывает, на­ сколько изменится значение целевой функции при уве­ личении поставки по маршруту 2—1 на 1. В данном слу­

53