3_Моделирование

Линеаризация в математических моделях

Задача о клике максимального веса

Подграф является кликой, тогда и только тогда, когда он не содержит пару вершин, между которыми нет ребра в исходном графе.

Òî åñòü

xi = 1 =) xj = 0 8j : (i; j) 2= E

В виде неравенства:

xj 6 1 xi 8i; 8j : (i; j) 2= E

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

5 / 26

Линеаризация в математических моделях

Задача о клике максимального веса

Для подсчета целевой функции необходимо знать ребра, входящие в клику.

Пусть i < j. Ребро (i; j) 2 E входит в подграф () вершины i è j входят в подграф.

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

6 / 26

Линеаризация в математических моделях

Задача о клике максимального веса

Для подсчета целевой функции необходимо знать ребра, входящие в клику.

Пусть i < j. Ребро (i; j) 2 E входит в подграф () вершины i è j

входят в подграф. Следовательно, yij = xixj.

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

6 / 26

Линеаризация в математических моделях

Задача о клике максимального веса

Для подсчета целевой функции необходимо знать ребра, входящие в клику.

Пусть i < j. Ребро (i; j) 2 E входит в подграф () вершины i è j

входят в подграф. Следовательно, yij = xixj. В виде неравенств:

yij 6 xi

yij 6 xj

xi + xj yij 6 1

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

6 / 26

Линеаризация в математических моделях

Задача о клике максимального веса

Математическая модель

X

max

yijwij

(i;j)2E

xj 6 1 xi 8(i; j) 2= E

yij 6 xi

8i; j 2 V : i < j

yij 6 xj

8i; j 2 V : i < j

xi + xj yij 6 1 8i; j 2 V : i < j

xi; yij 2 f0; 1g; i; j 2 V

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г. 7 / 26

Линеаризация в математических моделях

Линеаризация заменой переменных.

Задача размещения с распределенными закупками

Äàíî:

I множество возможных мест для открытия p магазинов J множество потребителей

uij полезность магазина i для потребителя j Bj бюджет потребителя j

cij удельная прибыль от потраченной потребителем j денежной единицы в магазине i

Найти:

Размещение p торговых центров, максимизирующее суммарную

прибыль при том, что бюджет каждого потребителя делится среди открытых магазинов пропорционально их полезности для данного потребителя.

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

8 / 26

Линеаризация в математических моделях

Задача размещения с распределенными закупками

Переменные:

(

1; если в месте i открывается торговый центр

xi =

0; иначе

yij > 0 сумма, потраченная клиентом j в торговом центре i

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

9 / 26

Линеаризация в математических моделях

Задача размещения с распределенными закупками

Математическая модель

XX

max cijyij i2I j2J

X

xi = p

i2I

uijxi

yij = Bj Pk2I ukjxk ; i 2 I; j 2 J

xi 2 f0; 1g; yij > 0; i 2 I; j 2 J

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

10 / 26

Линеаризация в математических моделях

Задача размещения с распределенными закупками

Математическая модель

XX

max cijyij i2I j2J

X

xi = p

i2I

uijxi

yij = Bj Pk2I ukjxk ; i 2 I; j 2 J

xi 2 f0; 1g; yij > 0; i 2 I; j 2 J

Модель нелинейная. Введем дополнительные переменные:

zj = P

Bj

k2I ukjxk

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г.

10 / 26

Линеаризация в математических моделях

Задача размещения с распределенными закупками

Математическая модель

XX

max

cijyij

i2I j2J

X

xi = p

i2I

yij 6 Bjxi; i 2 I; j 2 J

X

yij = Bj; j 2 J

i2I

yij 6 uijzj; i 2 I; j 2 J

uijzj 6 yij + Bj(1 xi); i 2 I; j 2 J

yij > 0; zj > 0; xi 2 f0; 1g; i 2 I; j 2 J

Кононова П. А. (ФИТ НГУ)

Теория принятия решений. Лекция 3.

24 февраля 2016 г. 11 / 26