АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Как осуществляется выбор разрешающей строки при поиске допустимого решения линейной задачи?

Читайте также:
  1. A) Выборочной совокупностью
  2. FAST (Методика быстрого анализа решения)
  3. I. 2.1. Графический метод решения задачи ЛП
  4. I. Выбор температурных напоров в пинч-пунктах и опорных параметров КУ.
  5. I.5.5. Просмотр и анализ результатов решения задачи
  6. II Выбор схемы станции
  7. II Съезд Советов, его основные решения. Первые шаги новой государственной власти в России (октябрь 1917 - первая половина 1918 гг.)
  8. II этап: запуск программы PowerPoint и выбор режима отображения.
  9. III этап: Анализ решения задачи
  10. III. Из-за чего шла борьба на выборах?
  11. MathCad: способы решения системы уравнений.
  12. V2: ДЕ 53 - Способы решения обыкновенных дифференциальных уравнений первого порядка

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 =


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.029 сек.)