1_Моделирование
.pdf
Основные определения
Смешанно-целочисленные линейные программы
MILP в стандартной форме
A 2 Qm n, B 2 Qm p, b 2 Qm, c 2 Qn, d 2 Qp
cx + dy ! min
x;y
Ax + By > b; x > 0;
y > 0; целые
множество решений
X = fx 2 Rn; y 2 Zp j x > 0; y > 0; Ax + By > bg
значения целевой функции F (x; y) = cx + dy, 8(x; y) 2 X
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
9 / 16 |
Основные определения
Важные частные случаи MIP
задача линейного программирования, LP p = 0
задача полностью целочисленного программирования, ILP n = 0
задача булева (или 0 1) программирования n = 0,
y 2 f0; 1g
задача смешанного булева программирования x > 0,
y 2 f0; 1g
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
10 / 16 |
Примеры
Варианты задачи о рюкзаке
Вещи можно разрезать или сыпать.
Все вещи в единственном экземпляре.
Вещи разрезать нельзя, но их число неограничено.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
11 / 16 |
Примеры
Задача о рационе в общем виде
Имеется множество продуктов, известна их стоимость. Рацион студента должен включать в себя разные полезные вещества. Задана минимальная норма потребления каждого полезного вещества в день, а также количество каждого из них в продуктах.
Необходимо найти рацион минимальной стоимости.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
12 / 16 |
Примеры
Задача о рационе в скучном виде
Имеется множество продуктов J = f1; : : : ; ng, известна их
стоимость cj. Рацион студента должен включать в себя разные полезные вещества I = f1; : : : ; mg. Задана минимальная суточная
норма потребления каждого полезного вещества bi, а также aij содержание полезного вещества i продукте j.
Необходимо найти рацион минимальной стоимости.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
13 / 16 |
Примеры
Модель задачи о рационе
Переменные: xj необходимое количество продукта j.
Математическая модель :
n
X
cjxj ! min
j=1
n
X
aijxj bi; i = 1; : : : ; m;
j=1
xj 0; j = 1; : : : ; n:
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
14 / 16 |
Примеры
Задача о поварах
Ресторан работает 7 дней в неделю. Каждый повар работает 6 часов в день, 5 дней подряд и затем 2 дня отдыхает. У всех поваров одинаковая зарплата. Приготовление каждого блюда занимает определенное время, и для каждого дня недели установлено общее необходимое количество часов для приготовления пищи. Администратору нужно решить, какое количество поваров нанять и в какие дни они должны работать, чтобы нужное количество часов было отработано, а затраты на оплату труда были минимальны.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
15 / 16 |
Примеры
Задача о поварах
Ресторан работает 7 дней в неделю. Каждый повар работает 6 часов в день, 5 дней подряд и затем 2 дня отдыхает. У всех поваров одинаковая зарплата. Приготовление каждого блюда занимает определенное время, и для каждого дня недели d установлено общее
необходимое количество часов для приготовления пищи td. Администратору нужно решить, какое количество поваров нанять и в какие дни они должны работать, чтобы нужное количество часов было отработано, а затраты на оплату труда были минимальны.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 1. |
10.02.2016 |
16 / 16 |