Оптимизационные задачи в электроэнергетике

 

2.Теоретическое описание решения оптимизационной задачи при помощи пакетов прикладных программ  

 

 Для решения системы уравнений можно использовать различные пакеты прикладных программ (MathCad, MatLab, Maple, Mathematica и др.), но наибольший эффект при решении оптимизационных задач дает использование  Excel. Этот пакет прикладных программ даёт возможность не только найти оптимальное решение, но и исследовать полученное решение, пользователь может проанализировать решение, изменять значения исходных данных, снять или ослабить какие-то ограничения и повторить решение.

 Для аналитического решения задачи линейного программирования, которая является частным случаем оптимизации, разработан специальный алгоритм, который называется симплекс-методом.

Для решения оптимизационных задач в Excel предназначена надстройка поиск решения

Средство поиска решения Microsoft Excel использует алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University). Поиск решений является частью блока задач, который иногда называют анализ "что - если". Процедура поиска решения позволяет найти оптимальное значение формулы содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки.

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

Для решения общей оптимизационной задачи в Excel с использованием настройки Поиск решения следует выполнить следующие действия:

Ввести формулу целевой  функции, ссылающуюся на влияющие ячейки;

Ввести формулы ограниченй оптимизационной задачи;

Выбрать в Excel пункт меню Сервис/Поиск решения;

В окне Поиск решения выбрать целевую ячейку, изменяемые ячейки и добавить ограничения;

Нажать кнопку Выполнить, после чего будет получено решение оптимизационной задачи.

Также среди оптимизационных задач можно выделить некоторые частные виды задач например: транспортная задача и задача о назначениях. При решения транспортной задачи или задачи о назначениях в Excel с использованием настройки Поиск решения.

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

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

 Предположим, что предприятие может выпускать продукцию четырех видов Прод1-Прод4 (n=4). Для их изготовления требуются ресурсы трех видов (m=3), например, трудовые ресурсы, сырьё и финансы. Известно количество ресурса каждого вида, необходимое для выпуска единицы продукции каждого вида, т.н. нормы расхода ресурсов. Кроме того, известны ограниченные объёмы этих ресурсов на планируемый период, т.н. запасы ресурсов. Известна прибыль, получаемая от реализации единицы продукции каждого вида - единичная прибыль. Заданы также граничные значения объёмов выпуска каждого вида продукции (верхняя или/и нижняя границы) и соотношения в выпуске отдельных видов продукции. Требуется определить оптимальное количество выпуска каждого вида продукции, при котором будут получена максимальная прибыль.

Для построения математической модели задачи введем следующие обозначения:

x_j - количество выпускаемой продукции j-го типа, j = 1, n;

b_i - количество располагаемых ресурсов i-го вида, i = 1,m;

a_ij - норма расхода ресурса i-го вида для выпуска единицы продукции j-го типа;

g_i - ограничение на количество располагаемых ресурсов i-го вида;

k_j - нижняя граница объёма производства продукции j-го типа;

v_j - верхняя граница объёма производства продукции j-го типа.

Тогда математическая модель может быть представлена в виде набора следующих уравнений (2.1):

Целевая функция

Ограничения на ресурсы

Ограничения на объёмы производства

                      (2.1)

 

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

В линейном программировании фундаментальное  значение имеет теория двойственности. Именно на основе этой теории выполняется анализ полученных оптимальных решений.

Рассмотрим кратко основные положения  этой теории.

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

1. Каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи, которую называют двойственной переменной.
2. Каждой переменной исходной задачи соответствует  ограничение двойственной задачи.
3. Матрица коэффициентов при двойственных переменных в ограничениях двойственной задачи является транспонированной матрицей коэффициентов при переменных в ограничениях исходной задачи (строки одной матрицы являются соответствующими столбцами другой).
4. Если в исходной задаче ограничения имеют знаки неравенства ³, то в двойственной они будут £.
5. Правые части ограничений в двойственной задаче равны коэффициентам при переменных в целевой функции и исходной задачи.
6. Коэффициенты при двойственных переменных в целевой функции двойственной задачи равны правым частям ограничений исходной задачи.
7. Максимизация целевой функции исходной задачи заменяется минимизацией целевой функции двойственной задачи.

Таким образом, исходной задаче в общем  виде:

 

                                         

                                                     (2.2)

                                          x_j ³ 0    

 

соответствует двойственная:

 

                                       

                                              (2.3)

                                        

 

В соответствии с правилом п.7 – 

, а т.к. ;

Тогда последнюю формулу  для  наглядности можно записать так:

                                              (2.4)

Из (2.4) видно, что двойственная переменная z_i является коэффициентом  при b_i и, следовательно, показывает, как изменится целевая функция при изменении ресурса b_i на единицу.

 В литературе по оптимизации двойственные переменные z_i принято называть двойственными оценками. В отчетах Excel двойственная оценка называется теневой ценой.

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

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

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

Значения двойственных переменных специально вычислять не надо, они  определяются автоматически в процессе поиска оптимального решения.

 

3.Пример решения задачи при помощи программного обеспечения

 

Рассмотрим пример, исходные данные которого заданы таблицей 1.

 

Таблица 1. Исходные данные

Ресурс\Продукция	Прод1	Прод2	Прод3	Прод4	Знак	Наличие
Прибыль	60	70	120	130	max	-
Ресурс1(Трудовые)	1	1	1	1	<=	16
Ресурс2(Сырьё)	6	5	4	3	<=	110
Ресурс3(Финансы)	4	6	10	13	<=	100

Как видно из таблицы, для выпуска единицы продукции  Прод1 требуется 6 единиц сырьевого ресурса, следовательно для выпуска всей продукции Прод1 требуется 6*х₁ таких единиц, где х₁ - количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции ограничения аналогичны, ограничение по сырьевому ресурсу  будет иметь вид:

 

6 х₁ + 5 х₂ + 4 х₃ + 3 х₄ <= 110

 

В этом ограничении левая  часть показывает величину потребного ресурса, меньшего или равного имеющемуся ресурсу (правая часть).

Аналогично можно составить  ограничения для других видов  ресурсов и написать зависимость для целевой функции.

Ограничения на объёмы производства по видам продукции, поскольку они  не могут быть отрицательными, заданы следующими соотношениями:

Тогда математическая модель для решения  задачи контрольного примера будет иметь вид:

                          F = 60x₁ + 70х₂ + 120х₃ + 130х₄ → max

                          х₁ + х₂ + х₃ + х₄ <= 16

                          6х₁ + 5х₂ + 4х₃ + 3х₄ <= 110                                       (3.1)

                          4х₁ + 6х₂ + 10х₃ + 13х₄ <= 100

                          x_j ³ 0;  j=

Введем в систему  дополнительные переменные y_i и выполним переход от системы неравенств к системе уравнений. С точки зрения содержания задачи величина y_i равна величине неиспользованного ресурса.

 

                         F = 60x₁ + 70х₂ + 120х₃ + 130х₄ → max

                         х₁ + х₂ + х₃ + х₄ + y₁ = 16

                         6х₁ + 5х₂ + 4х₃ + 3х₄ +y₂ = 110                                    (3.2)

                         4х₁ + 6х₂ + 10х₃ + 13х₄ +y₃ = 100

                         x_j ³ 0; y_i ³ 0; i= ;j=

 

Систему (3.2) можно переписать в следующем виде:

 

                         F = 0 - ( - 60x_{1 -} 70х_{2 -} 120х_{3 -} 130х₄) → max

                         y₁ = 16 - (х₁ + х₂ + х₃ + х₄)

                           y₂ = 110 - (6х₁ + 5х₂ + 4х₃ + 3х₄)                                   (3.3)

                         y₃ = 100 - (4х₁ + 6х₂ + 10х₃ + 13х₄)

                         x_j ³ 0; y_i ³ 0; i= ;j=

 

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

Итак, после построения математической модели, необходимо перенести её в Excel. Этот процесс, как для данного контрольного примера, так и для всех последующих решаемых задач оптимизации, может быть реализован в виде последовательности следующих этапов.

- Продумайте организацию исходных данных модели и введите их (коэффициенты целевой функции и ограничения) в ЭТ, снабдив понятными названиями.

- Зарезервируйте n отдельных ячеек для независимых переменных математической модели.

- В одной из ячеек создайте формулу, определяющую целевую функцию.

- Выберите ячейки и создайте в них формулы, соответствующие правым частям ограничений.

- Запустите программу Поиск решения для решения задачи.

- Проанализируйте полученное решение и отчеты, и определите возможные пути улучшения решения за счет снятия каких-либо ограничений.

- Вновь решите задачу с измененными исходными данными (возможно несколько раз, до получения наилучшего решения).

 Для ввода исходных  данных создайте таблицу, как указанно на рисунке 1