Лінійна оптимізація курсу - Рурський університет, Бохум

Навчання

дати в літній термін

• початок: четвер, 23.04.2020
• лекція: див. "Різне"

Усі заяви, що стосуються режимів іспиту (на літній/зимовий період 2020 року), подаються із застереженнями. Про зміни, обумовлені новими вимогами університету, буде повідомлено якомога швидше.

Буде 5 аркушів вправ із теоретичними підзадачами загалом 12 балів та додатково 4 вправи програмування по 10 балів кожна. Іспит завершується, коли за теоретичні завдання набрано 30 балів, а за завдання з програмування - 20 балів.

цілі

Студенти цього курсу вивчають основні аспекти лінійної оптимізації, зокрема:

• моделювання проблем, пов’язаних з інформаційними технологіями (таких як розподіл енергії) та повсякденних життєвих проблем (таких як проблема рюкзака, газу, дієта)
• подвійність, а також необхідні та достатні умови
• методи, що допомагають ефективному розрахунку рішень

зміст

Багато інженерних (але також неінженерних) аспектів вимагають вирішення проблем із цілями та обмеженнями. Оптимізація використовується як систематичний інструмент для ефективного вирішення цих проблем.

1. Вступ та огляд

Мотивація, формулювання лінійних задач, варіанти, приклади, частково лінійні цільові функції

Графічний опис та рішення Лінійна алгебра: огляд та позначення 2. Геометрія в лінійній оптимізації

Системне повідомлення: ERROR/3 (, рядок 10)

Опуклі множини, багатогранники, екстремальні точки

1. Метод симплексного методу Умови оптимальності, розробки, реалізації
2. Теорія подвійності Мотивація, подвійна задача, теорема подвійності
3. Теорія ігор
4. Аналіз чутливості (місцевий)
5. Формулювання проблем мережевого потоку, проблеми: найкоротший шлях/максимальний потік, алгоритм сімплексних мереж
6. Методи внутрішніх точок Аффінне масштабування alogirthm
7. Методи формулювання змішаного цілочисельного лінійного програмування: Розгалуження та зв’язок, площина різання
8. Програми

вимоги

рекомендовані знання

Зміст курсу: Математика I.

матеріалів

різне:

література

1. Бойд С., Ванденберге, Л. "Опукла оптимізація", Cambridge University Press, 2004

різне

Додаткова література: • Берстімас, Д., Ціцікіліс, Дж. Н., “Вступ до лінійної оптимізації”, Athena Scientific, 1997 • Хамачер, Х. В., Кламрот, К., “Лінійна оптимізація та оптимізація мережі”, 2-е видання, Vieweg Verlag, 2006

Сценарій для лекції: • Верфурт, Р., “Оптимізація”, сценарій 2014 (http: //www.ruhr-uni-bo¬chum.de/num1/skripten.html)

Є 5 домашніх завдань з теоретичним завданням по 12 балів кожна. Крім того, є 4 завдання на програмування по 10 балів. Цей курс проходить, як тільки ви наберете 30 балів з теоретичних завдань і 20 балів з завдань з програмування.

Захід буде запропонований востаннє в зимовому семестрі 2023/2024.

---