3_Моделирование
.pdf
Лекция 3. Моделирование с помощью булевых переменных
Кононова Полина Александровна
Новосибирский Государственный Университет vk.com/tpr_ t_2016
24 февраля 2016 г.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
1 / 26 |
Линеаризация в математических моделях
Линеаризация произведения переменных
Как сделать эквивалентную линейную переформулировку? xixj, ãäå xi; xj 2 f0; 1g
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
2 / 26 |
Линеаризация в математических моделях
Линеаризация произведения переменных
Как сделать эквивалентную линейную переформулировку? xixj, ãäå xi; xj 2 f0; 1g
Пусть yij = xixj
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
2 / 26 |
Линеаризация в математических моделях
Линеаризация произведения переменных
Как сделать эквивалентную линейную переформулировку? xixj, ãäå xi; xj 2 f0; 1g
Пусть yij = xixj
yij = 1 , xi = 1 è xj = 1
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
2 / 26 |
Линеаризация в математических моделях
Линеаризация произведения переменных
Как сделать эквивалентную линейную переформулировку? xixj, ãäå xi; xj 2 f0; 1g
Пусть yij = xixj
yij = 1 , xi = 1 è xj = 1
yij = 1 ) xi = 1 yij 6 xi
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
2 / 26 |
Линеаризация в математических моделях
Линеаризация произведения переменных
Как сделать эквивалентную линейную переформулировку? xixj, ãäå xi; xj 2 f0; 1g
Пусть yij = xixj
yij = 1 , xi = 1 è xj = 1
yij = 1 ) xi = 1 |
yij 6 xi |
yij = 1 ) xj = 1 |
yij 6 xj |
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
2 / 26 |
Линеаризация в математических моделях
Линеаризация произведения переменных
Как сделать эквивалентную линейную переформулировку? xixj, ãäå xi; xj 2 f0; 1g
Пусть yij = xixj
yij = 1 , xi = 1 è xj = 1
yij = 1 ) xi = 1 |
yij 6 xi |
yij = 1 ) xj = 1 |
yij 6 xj |
xi = 1 è xj = 1 ) yij = 1 |
xi + xj yij 6 1 |
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
2 / 26 |
Линеаризация в математических моделях
Задача о клике максимального веса
Äàíî:
G = (V; E) взвешенный неориентированный граф.
Найти:
полный подграф (клику) графа G максимального веса.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
3 / 26 |
Линеаризация в математических моделях
Задача о клике максимального веса
Переменные:
(
1; если вершина i входит в клику
xi = ; 8i 2 V
0; иначе
yij = |
(0; |
иначе |
; 8i; j 2 V : i < j |
|
1; |
если ребро (i; j) входит в клику |
|
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
4 / 26 |
Линеаризация в математических моделях
Задача о клике максимального веса
Подграф является кликой, тогда и только тогда, когда он не содержит пару вершин, между которыми нет ребра в исходном графе.
Òî åñòü
xi = 1 =) xj = 0 8j : (i; j) 2= E
В виде неравенства:
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 3. |
24 февраля 2016 г. |
5 / 26 |