2017-11-30
222
ЛАБОРАТОРНАЯ РАБОТА №4
Решение оптимизационных задач электроэнергетики с целочисленными и дискретными переменными
Цель работы: Получение навыков составления математических моделей для решения задач линейного программированияс целочисленными дискретными переменнымив пакете MSExcel. Приобретение навыков решенияоптимизационных задач электроэнергетикис целыми и дискретными переменными.
Краткие теоретические сведения.
B.1. Задачи с целочисленными переменными
В изложенном выше материале по решению оптимизационных задач методами линейного и нелинейного программирования все искомые переменные имели непрерывный характер. Эти переменные в заданном диапазоне изменения могли принимать любые значения.
При решении достаточно большого количества оптимизационных задач все искомые переменные или их часть должны принимать только значения целых чисел. Математическая модель таких задач аналогична рассмотренным выше линейным и нелинейным моделям и содержит целевую функцию, систему ограничений и граничные условия. Однако система ограничений в задачах с целочисленными переменными дополняется ограничениями типа
хk – целое, k = 1, 2, … l, (5.1)
где l – количество целочисленных переменных, l < n;
n – общее количество переменных.
Оптимизационные задачи, в которых искомые переменные или их часть должны быть целыми числами, решаются методами целочисленного программирования.
Введение дополнительных ограничений по целочисленности переменных существенно увеличивает объем вычислений и усложняет мапра вычислительную процедуру при поиске оптимального решения.Однако в заданном диапазоне изменения переменной целочисленная переменная имеет меньшее количество значений, чем непрерывная переменная.В частности, в диапазоне 0 < x < 3 целочисленная переменная х имеет четырезначения (х = 0, 1, 2, 3), а непрерывная переменная – бесконечное количество значений.
Попытка решить целочисленную оптимизационную задачу методом полного перебора значений переменных приводит к очень большему объему вычислений. Так, например, в задаче с тремя целочисленными переменными и диапазоном их изменения 0 < x k < 10, k = 1, 2, 3 количество целочисленных решений составит 113=1331. Ясно, что для реальных оптимизационных задачметод полного перебора не приемлем
B.2.Двоичные переменные
Частным случаем целочисленных задач являются задачи, в которых искомые переменные могут принимать не любые целые значения, а только одно из двух: либо 0, либо 1. Такие переменные называются двоичными или булевыми.
Распространенными задачами с двоичными переменными являются задачи выбора оптимального решения (варианта) из определенного числа заданных решений (вариантов). Если вариант входит в оптимальное решение, то двоичная переменная, соответствующая этому варианту, равна 1. Если вариант не входит в оптимальное решение, то соответствующая двоичная переменная равна 0. Например, если линия электропередачи входит в оптимальную электрическую сеть, то двоичная переменная, соответствующая этой линии равна 1; если линия электропередачи не входит в оптимальную электрическую сеть, то соответствующая двоичная переменная равна 0.
В отличие от традиционных переменных х iдвоичные переменные будем обозначать δi, где i =1, 2, … n.
Применение двоичных переменных позволяет накладывать на решаемую задачу целый ряд логических условий типа «если …, то …».
Если в оптимальное решение должен входить один из двух (i и j) вариантов, то сумма переменных
δ i + δ j = 1.
Если в оптимальное решение должны входить и i –й и j –й варианты, то сумма переменных
δ i + δ j = 2.
Если в оптимальное решение может входить или не входить, каждый из двух (i и j) вариантов, то сумма переменных
δ i + δ j > 0.
Если при входе (не входе) в оптимальное решение i –го варианта в это решение должен войти (не войти) и j –й вариант, то
δ i = δ j.
Аналогичные условия можно записать для трех и более вариантов. Если из n возможных вариантов в оптимальное решение должны входить только m вариантов (m < n), то
δ1 + δ2 + … + δ n = m.
Очевидно, что количество логических условий типа «если …, то …» не ограничено.
