Материал: ОиММПР. Лекция 1
Найти подмножество проектов, которые можно реализовать на капитал C и которые в сумме дают максимальную прибыль, то есть
N |
|
max ∑ bk xk |
|
k =1 |
|
при ограничениях |
|
N |
|
∑ atk xk≤ct , |
t = 1,…, T |
k=1 |
|
xk {0, 1}, |
k = 1,…, N |
Замечание 1. При T = 1 получаем линейную распределительную задачу с 0-1 переменными — задачу о рюкзаке.
21 из 28
Задача об отправке грузов
I = {1,…, n} — авиалайнеры, J = {1,…, m} — контейнеры,
pij — доход от доставки авиалайнером i контейнера j, wj — вес контейнера j,
ci — вместимость авиалайнера i,
xi , j =1,если отправитьконтейнер jавиалайнером i ,иначе 0
Модель
max ∑∑ pij xij |
|
i I j J |
|
при ограничениях: |
|
∑ xij≤1, |
j J , |
i I |
|
∑ w j xij≤ci , i I , |
|
j J |
|
xij {0,1}, |
i I, j J. |
22 из 28
Гильотинный раскрой материала
Дано: лист размера L х W и n-типов прямоугольников lj х wj, j=1,…,n
pj > 0 — доход от прямоугольника j, повороты запрещены, разрезы параллельно осям координат от кромки до кромки. Двухстадийная обработка: сначала режем лист параллельно оси y, затем параллельно оси x.
Найти: раскрой листа с максимальным доходом
y
L
W
y |
y |
x |
yk |
12
23 из 28
Пусть
k — число параллельных полос k = L / lmin yi — ширина полосы i, 1 i k,
xij — число j-х прямоугольников в полосе i, xi , j =[1,если0,иначеxij>0]
mj = W / wj — максимально возможное число j-х прямоугольников в полосе.
Модель:
k n |
|
|
max ∑∑ p j xij |
|
|
i=1 j=1 |
|
|
при ограничениях |
|
|
n |
|
|
∑ w j xij≤W , i=1, ... ,k , |
||
j=1 |
|
|
|
k |
|
|
∑ yi≤L , |
|
|
i=1 |
|
lj xij' ≤ yi , |
i=1,... k, |
j=1, ... ,n, |
mj xij' ≥xij , |
i=1,... k , |
j=1,... ,n, |
xij' {0,1}, |
xij {0,...,m j}, yi≥0 . |
|
24 из 28
Математические модели и методы принятия решений как основные компоненты исследования операций
Математическая модель - объективная формализация основных аспектов решаемой задачи или ее описание в математических терминах.
Математическая модель описывает исследуемую систему и позволяет выразить степень качества ее характеристик (эффективность функционирования) в виде
целевой функции
W = f(X,Y), где X = (x1,…, xn) — управляемые переменные,
Y = (y1,…, ym) — неуправляемые переменные (исходные данные).
Связь между переменными X и исходными данными Y выражается с помощью ограничений
(X, Y) 0.
25 из 28