Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 2

Многие оптимизационные задачи небольшого! размера (ЛП, игры, ЦЛП …) легко решаются в EXCEL с помощью команд Сервис и Поиск решения.

Алгоритмы решения многих задач предполагают сортировку данных. Метод “пузырька” имеет трудоемкость O(n²), а угадывание одной из n! перестановок требует log(n!)»log(nⁿ)=n·log n вопросов = минимальная теоретическая трудоемкость.

1.1. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ В Â¹.

№1. Задача о p-медиане.

Пусть точки x_i – магазины, w_i – интенсивность продаж в i-ом магазине (). Надо среди них разместить p центров обслуживания c_j (складов), минимизируя функционал или . В первом случае множество C называется P-медианой, а во втором − P-центром.

Рассмотрим наиболее простой случай, когда все точки лежат на прямой, упорядочены, p=1 и единственный центр c размещен на отрезке [x_k, x_k+1]. Тогда

Решение задачи свелось к минимизации на отрезке линейной по cфункции:

1)  если Δ_k< 0, то размещаем центр в точке x_k+1, если Δ_k> 0, то в точке x_k;

2)  если же Δ_k= 0, то центр можно разместить в любой точке отрезка [x_k, x_k+1].

Отсюда вытекает алгоритм отыскания 1-медианы на прямой: движемся по прямой слева направо, подсчитывая Δ_k на каждом интервале и перемещая центр в правый конец интервала, пока Δ_k не станет меньше 0. ~ W_k= > S=(W_n / 2).

Отметим, что здесь важны не расстояния между точками, а порядок точек!!

Пример: Пусть 6 пунктов упорядоченны по координате x и общий вес W₆=195.

S=W₆/ 2=97,5; W₁=30<S Þ переходим к пункту 2;

W₂=30+15=45<S; W₃=45+40=85<S; W₄=85+60=145>S Þ размещаем центр в последнем рассмотренном пункте 4.

Можно предположить, что и для p–медианы расстояния не играют роли. Это неверно. Пусть n=6, p=2, все w_i=1, x_i=i Þ C={2,5}, но если x₆=9, то C={3,6}.

Пример 2. Построение 3-медианы методом динамического программирования. Пусть x_i=i. w_i – см. таблицу.

Значение критерия при оптимальном размещении 1-го центра на интервале [x_i, x_j) = f_ij,

k центров на интервале [x_j, ∞) = F_jk.

Таблица заполняется слева направо и снизу вверх.

Трудоемкость равна O(n²p), а если использовать выпуклость F_jk по параметру j, то O(np·logn).

Например, F₂₂ = min{3: 0+66, 4: 4+54, 5: 16+32=48, 6: 28+16=44,…} = 44.

F₀₃ = min{1: 0+60, 2: 1+44, 3: 9+28=37, 4: 14+22=36, 5: 30+14,…} = 36.