 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Как осуществляется выбор разрешающей строки при поиске допустимого решения линейной задачи?
l По положительному коэффициенту разрешающей строки.
l Нулевому коэффициенту разрешающей строки.
l Минимальному коэффициенту разрешающей строки.
l Отрицательному свободному члену ограничения-равенства.
l Максимальному коэффициенту разрешающей строки.
Как осуществляется выбор разрешающего столбца при поиске допустимого решения линейной задачи?
l По положительному коэффициенту разрешающей строки.
l Нулевому коэффициенту разрешающей строки.
l Минимальному коэффициенту разрешающей строки.
l Максимальному коэффициенту разрешающей строки.
l Отрицательному коэффициенту разрешающей строки.
Как осуществляется выбор разрешающего столбца при поиске минимума целевой функции в линейной задаче?
l По положительному коэффициенту целевой функции.
l Нулевому коэффициенту целевой функции.
l Отрицательному коэффициенту целевой функции.
l Положительному свободному члену ограничений-равенств.
l Отрицательному свободному члену ограничений-равенств.
Как осуществляется выбор разрешающей строки при поиске оптимального решения линейной задачи?
l По отрицательному свободному члену ограничений-равенств.
l Отрицательному коэффициенту целевой функции.
l Минимальному положительному отношению свободных членов ограничений-равенств к коэффициентам разрешающего столбца.
l Максимальному положительному отношению свободных членов ограничений-равенств к коэффициентам разрешающего столбца.
l Положительному коэффициенту целевой функции.
Каково условие оптимального решения при поиске минимума целевой функции в линейной задаче?
l Положительность свободных членов в системе ограничений-равенств.
l Положительность коэффициентов целевой функции.
l Неотрицательность свободных членов в системе ограничений-равенств.
l Неотрицательность коэффициентов целевой функции.
l Минимальное значение целевой функции.
Округление непрерывных переменных до целых чисел, как в большую, так и в меньшую стороны, дает некоторое множество решений, среди которых могут оказаться как допустимые, так и недопустимые решения. Есть ли среди множества допустимых решений оптимальное решение - неизвестно.
n Перебор возможных решений
n x 1=0; х 2=11,76; х 3 =8,82;
n 0 < х 1 < 15;
n 0 < х 2 < 15;
n 0 < х 3 < 15;
n Имеем 153=3375 решений! Для каждого решения нужно проверить все ограничения и вычислить значение целевой функции Z.
n Целочисленныезадачи
n Целевая функция
Z= 8 х 1 + 11 х 2 + 12 х 3 ® max.
n Ограничения
2 х 1+2 х 2+3 х 3 < 50;
6 х 1+5,5 х 2+4 х 3 < 100;
4 х 1+6 х 2+8 х 3 < 150;
x 1 + x 2 + x 3 > 15;
x i – целое, i =1, 2, 3.
n Граничные условия
x i ³ 0, i =1, 2, 3.
n Целочисленные задачи
n Оптимальным решением целочисленной задачи может оказаться такое решение, в котором переменные не являются ближайшими к переменным в оптимальном решении непрерывной задачи.
n Округление непрерывных переменных до целых чисел как в большую, так и в меньшую сторону может привести к недопустимому решению.
n Значение целевой функции Z в целочисленной задаче ухудшилось, поскольку введено дополнительное ограничение: х 1, х 2, х 3 – целые.
l Транспортные задачи энергетики
l Транспортная задача - это задача отыскания таких путей перевозки продукта от пунктов производства к пунктам потребления, при которых общая стоимость перевозок оказывается минимальной.
l В электроэнергетике:
l продукт – электроэнергия;
l путь перевозки – линия электропередачи;
l пункт производства – электростанция или подстанция, в дальнейшем - источник питания;
l пункт потребления – потребитель электроэнергии.
l Минимизации подлежат затраты на электрическую сеть, состоящую из линий электропередачи, связывающих между собой источники и потребители.
l Постановка транспортной задачи
l Имеется i= 1, 2,... n узлов источников питания и j= 1, 2,... m узлов потребителей.
l Мощность каждого источника составляет A i, мощность каждого потребителя составляет B j.
l Между каждыми двумя узлами i и j может быть построена линия электропередачи, по которой будет передаваться мощность х ij.
l Стоимость передачи единицы мощности от узла i к узлу j (удельная стоимость) составляет z ij (z ij= z ji).
l Определить электрическую сеть, отвечающую минимуму затрат.
l Транзит мощности
l Мощность к потребителям В 3 и В 4 передается от источника А 1 через транзитный (промежуточный) узел 2. Величина транзитной мощности, передаваемой через узел 2, равна х 22= х 23+ х 24= В 3+ В 4.
l Затраты на сеть Z = z 12 x 12+ z 23 x 23+ z 24 x 24.
l Затраты на передачу транзитной мощности через 2–й узел z 22=0 (z ii=0).
l Математическая модель задачи
l Целевая функция
l
l i ¹ j
l Ограничения – балансы мощности в узлах (равенство притекающих к узлу и оттекающих от узла мощностей).
l Например, для узлов 1...4 предыдущей схемы
l х 12= А 1; х 12- х 22 = В 2; х 23= В 3; х 24= В 4.
l Транзитные мощности х ii входят в математическую модель со знаком минус.
l Это линейная задача.
l Для выполнения граничных условий
неотрицательности переменных
l Каждой линии между двумя узлами i и j соответствуют две переменные x ij и x ji.
l В процессе решения задачи одна из переменных становится равной нулю, другая будет положительная.
l Пример
l В проектируемой системе электроснабжения имеются 2 узла с источниками питания и 2узла с потребителями. Мощности источников составляют A 1=100и A 2 = 50 е.м., мощности потребителей составляют B 3=90и B 4=60 е.м. Удельные затраты на передачу мощностей по линиям между узлами составляют z 12=10, z 13=5, z 14=2, z 23=4, z 24=3 и z 34=2 у.е./е.м.
l Требуется найти оптимальную схему электрической сети.
l Транспортная матрица
l Матрица квадратная.
l Размерность матрицы определяется суммарным количеством узлов источников и потребителей.
l Строки соответствуют источникам; столбцы – потребителям.
l z ij – в правом нижнем углу каждой клетки.
l х ij – в центре каждой клетки.
l Получение допустимого решения
l Выбирается клетка с наименьшей удельной стоимостью (клетка 14). В эту клетку заносится меньшее из значений А 1 и B 4.
l Потребность в мощности узла 4 (В 4=60) будет полностью покрыта. Баланс мощности для узла 4 выполнен (х 14= В 4). В остальные клетки столбца 4 вписываются нули.
l Получение допустимого решения
l Из оставшихся незаполненных клеток выбирается клетка с наименьшей удельной стоимостью (клетка 23). В эту клетку заносится меньшее из значений А 2 и B 3.
l Мощность узла 2 (А 2=50) будет полностью израсходована. Баланс мощности для узла 2 выполнен (х 23= А 2). В остальные клетки строки 2 вписываются нули.
l Получение допустимого решения
l Из оставшихся незаполненных клеток выбирается клетка с наименьшей удельной стоимостью (клетка 13). В эту клетку заносится остаток мощности узла 1 или недостающая мощность узла 3 (40 ед.).
l Мощность узла 1 (А 1=100) будет полностью израсходована. Потребность в мощности узла 3 (В 3=90) будет полностью покрыта. Балансы мощности для узлов 1 и 3 выполнены (х 23= А 2). В остальные клетки строки 1 и столбца 2 вписываются нули.
l В клетки 31, 32, 41 и 42 вписываются нули.
l Допустимое решение
l В полученном решении:
свободные переменные х 12 = х 21 = х 24 = х 31 = х 32 = х 34 = х 41 = х 42 = х 43 = 0;
базисные переменные х 11 = х 22 = х 33 = х 44= 0, х 13= 40, х 14= 60, х 23=50 е.м.; (все х ii независимо от значения – базисные).
l Значение целевой функции Z=z 13 х 13 +z 14 x 14 +z 23 x 23=5×40+2×60+4×50=520 у.е.
l Допустимое решение
l Балансы мощности во всех узлах выполняются:
узел 1 х 13+ х 14= А 1 (40+60=100);
узел 2 х 23= А 2 (50=50);
узел 3 х 13+ х 23= В 3 (40+50=90);
узел 4 х 14= В 4 (60=60).
l Все переменные неотрицательные.
l Полученное решение является допустимым.
l Оптимизация решения методом потенциалов
l Присвоим каждой строке потенциал V i, а каждому столбцу - потенциал U j. Эти потенциалы таковы, что для всех базисных переменных сумма потенциалов равна удельной стоимости V i + U j = z ij.
l Зададимся произвольно значением одного из потенциалов (например U 1=1). По выражению V i +U j =z ij вычислим значения остальных потенциалов.
l Оптимизация решения методом потенциалов
l Для всех свободных переменных проверим условие V i + Uj < z ij. Например для переменной х 12: V 1 +U 2= -1+2 = 1 < z 12 = 10.
l Для всех свободных переменных это условие выполняется, кроме переменной х 43, для которой V 4 +U 3 = -3 +6 = 3 > z 43= 2.
l Свободную переменную х 43 будем переводить в базис.
l Оптимизация решения методом потенциалов
l Для свободной переменной х 43 строим цикл. Начальная вершина цикла лежит в клетке 43. Остальные вершины цикла лежат в клетках, соответствующих базисным переменным 13, 14и44.
l Начальной вершине присваиваем знак плюс, далее знаки вершин цикла чередуются. Знак плюс соответствует увеличению переменной, знак минус – ее уменьшению.
l Увеличивать свободную переменную х 43 можно до 40. При этом базисная переменная х 13 уменьшается до нуля и становится свободной.
l Новое решение
l В новом решении:
свободные переменные х 12 = х 13 = х 21 = х 24 = х 31 = х 32 = х 34 = х 41 = х 42 = 0;
базисные переменные х 11 = х 22 = х 33 = 0, х 44=40, х 14= 100, х 23= 50, х 43=40, е.м.
l Значение целевой функции
Z=z 14 х 14 +z 23 x 23 +z 42 x 42 = 2×100+4×50+2×40 = 480 у.е.
l Оптимальное решение
l Зададимся произвольно значением одного из потенциалов (например U 1=1). По выражению V i +U j =z ij вычислим значения остальных потенциалов.
l Для всех свободных переменных проверим условие V i + Uj < z ij. Например для переменной х 24 V 2 +U 4= -2+3 = 1 < z 23 = 3.
l Для всех свободных переменных это условие выполняется, следовательно полученное решение оптимальное.
l Оптимальная схема электрической сети
l Балансы мощности во всех узлах выполняются: узел 1 х 14= А 1 (100=100); узел 2 х 23= А 2 (50=50); узел 3 х 23+ х 43= В 3 (50+40=90); узел 4 х 14 - х 44= В 4 (100-40=60).
l Через узел 4 течет транзитная мощность х 44=40.
l Все переменные неотрицательные.
l Значение целевой функции Z =480 у.е.
l Задача 2
l От подстанции промышленного предприятия, расположенной в узле 1, будет осуществляться электроснабжение цехов, расположенных в узлах 2, 3 и 4. Найти оптимальную электрическую сеть по критерию минимума затрат.
l Расчетные мощности всех узлов S i и затраты z ij на передачу единицы мощности по линии между узлами i и j заданы.
l Допустимое решение
l Одним из допустимых решений транспортной задачи с одним источником питания является радиальная сеть, для которой выполняются балансы мощности во всех узлах:
S 12 + S 13 + S 14 = S 1;
S 12= S 2;
S 13= S 3;
S 14= S 4.
l Транзитные мощности через узлы равны нулю.
l Допустимое решение
l Базисные переменные S 12= S 2, S 13= S 3, S 14= S 4, S 11=0, S 22 =0, S 33 =0, S 44 =0.
l Свободные переменные S 23=0, S 32=0, S 24=0, S 42=0, S 34=0, S 43=0, S 21=0, S 31=0, S 41=0.
l Целевая функция Z = z 12 S 12 + z 13 S 13 + z 14 S 14.
l Транспортная матрица
l Потенциалы строк и столбцов определяются по выражению z ij = V i + U j, справедливому для базисных переменных.
l Для всех свободных переменных проверяется условие V i + U j £ z ij.
l Переменная, для которой это условие не выполняется, переводится в базисные. Например, переменная S42.
l Для переменной S42 строится цикл – замкнутая ломаная линия с прямыми углами.
l Транспортная матрица
l Начальная вершина цикла лежит в клетке свободной переменной, переводимой в базис.
l Остальные вершины цикла лежат в клетках базисных переменных, например в клетках 12, 14 и 44.
l Знаки вершин цикла чередуются. Плюс – увеличение переменной, минус – уменьшение.
l Переменную S42 можно увеличивать до значения S2. При этом базисная переменная S12 уменьшится до нуля и станет свободной.
l Для нового решения вся процедура повторяется.
l К какому классу задач относится транспортная задача?
l К линейным задачам.
l Нелинейным задачам.
l Стохастическим задачам.
l Дискретным задачам.
l Целочисленным задачам.
l Для решения какой оптимизационной задачи применим вычислительный аппарат транспортной задачи?
l Для выбора оптимального количества цеховых трансформаторов.
l Для минимизации потерь мощности в схеме электроснабжения.
l Для оптимального размещения компенсирующих устройств в схеме электроснабжения.
l Для выбора оптимальной схемы электрической сети.
l Для выбора оптимального напряжения электрической сети.
l Какие ограничения имеют место в транспортной задаче?
l По потерям мощности.
l Выполнению балансов мощности в узлах.
l Качеству электроэнергии.
l Надежности.
l Экологического характера.
l Какой основной метод используется для решения транспортной задачи?
l Метод Лагранжа.
l Градиентный метод.
l Метод потенциалов.
l Метод Ньютона.
l Метод скорейшего спуска.
l Какова размерность транспортной матрицы в задаче без транзита мощности (n – количество источников, m – количество потребителей)?
l n+m.
l nm.
l (n - m)(n - m).
l (n+m)(n+m).
l (n+m)(n - m) .
l Какова удельная стоимость передачи транзитной мощности через узел электрической сети?
l Равна удельной стоимости передачи мощности до транзитного узла.
l Равна нулю.
l Равна удельной стоимости передачи мощности после транзитного узла.
l Равна единице.
l Отрицательная.
l Какова размерность транспортной матрицы в задаче с транзитом мощности (n – количество источников, m – количество потребителей)?
l n+m.
l nm.
l (n - m)(n - m).
l (n+m)(n+m).
l (n+m)(n - m).
l Выберите выражение целевой функции в транспортной задаче с транзитом мощности
l Каково условие допустимого решения в транспортной задаче?
l Для всех базисных переменных сумма потенциалов больше удельной стоимости передачи мощности.
l Выполнение балансов мощности во всех узлах схемы.
l Минимальное значение целевой функции.
l Для всех свободных переменных сумма потенциалов больше удельной стоимости передачи мощности.
l Равенство нулю свободных переменных, неотрицательность базисных переменных.
l Каково условие оптимального решения в транспортной задаче?
l Выполнение балансов мощности во всех узлах схемы.
l Максимальное значение целевой функции.
l Для всех базисных переменных сумма потенциалов равна удельной стоимости передачи мощности.
l Для всех свободных переменных сумма потенциалов меньше удельной стоимости передачи мощности.
l Равенство нулю свободных переменных, неотрицательность базисных переменных.
l Нелинейные задачи
• Общая задача оптимизации заключается в отыскании экстремума целевой функции
l Z (x 1, x 2 ,... x n) ® extr при ограничениях
l f 1(x 1, x 2 ,... x n, b 1) = 0;
l f 2(x 1, x 2 ,... x n, b 2) = 0;
l..................
l f m(x 1, x 2 ,... x n, b m) = 0;
l и граничных условиях
l х i³ 0, i = 1, 2,... n; n > m.
• Если в целевой функции и (или) ограничениях есть нелинейные зависимости, задача будет нелинейной.
l Экстремумы
l Абсолютный экстремум нелинейной функции – экстремум при отсутствии ограничений.
l Методы нахождения абсолютного экстремума функции известны из курса высшей математики.
l Относительный экстремум нелинейной функции – экстремум при наличии ограничений.
l Графическая иллюстрация нелинейной задачи
l На каждой из замкнутых кривых значение функции неизменно Z = const.
l Полученные замкнутые кривые Z = const называются линиями равного уровня функции Z.
l Абсолютный минимум функции находится в точке с координатами х' 1 и х' 2.
l Графическая иллюстрация нелинейной задачи
l Имеем три ограничения 1, 2 и 3.
l Относительный минимум функции находится в точке d.
l Вывод: в нелинейных задачах оптимальное решение может лежать в любой точке области W (в вершине, на грани, внутри).
l Градиентные методы
Градиентом функции Z(х 1, х 2 ,... х n ) называется вектор
grad Z =
Поиск по сайту: