Условие оптимальности выполняется, поэтому получено оптимальное решение

ƒ(α_опт)=270+520+330+720+20+440=2300

α_опт=

Задача о назначениях

Является частным случаем транспортной задачи. Известно, что каждую из m работ могут выполнять любые из n исполнителей. Стоимость выполнения j работы i исполнителем равна C_ij. Нужно распределить исполнителей по рабочим местам так, чтобы минимизировать затраты или если C_ij – эффективность работы j исполнителя на i месте, нужно распределить исполнителей с целью оптимизации эффективности.

Математическая модель задачи, если сводить ее к транспортной примет вид:

X_ij≥0

Однако улучшенным алгоритмом решения этой задачи является Венгерский алгоритм.

Пример:

Разместить датчики на 4 объектах так, чтобы стоимость размещения была минимальна. Известна матрица стоимости назначений.

1.Редукция матрицы:

min

С = → →

min

2. Назначения.

3. Модификация.

Общая стоимость= (9+4+11+4)=28

Задачи нелинейного программирования (знлп) знлп – это задача вида

ƒ(x₁,x₂,…,x_n)→opt.

g(x₁,x₂,…,x_n)≤≥=b_i; i=1,n (1)

x_j≥0; j=1,n;

Если система ограничений содержит только уравнения и функции ƒ_i и g_i непрерывны вместе со своими частными производными, то задача является задачей на условный экстремум и решается методом множителей Лагранжа:

1. Рассматриваем дополнительную функцию Лагранжа, вводя набор дополнительных переменных λ₁, λ₂, … λ_m

F(λ_i,x_j)=ƒ(x₁, x₂, …, x_n)+ λ_i (b_i-g_i (x₁, x₂, …, x_n)).

2. Находим безусловные экстремумы функции F, которые являются решением задачи.

Приближенные методы решения ЗНЛП:

Используя градиентные методы, можно найти решение любой ЗНЛП.

Метод Франка-Вульфа: Если ƒ(x1, x2, …, xn)→max и является вогнутой функцией на выпуклом множестве ω, т.Е

При условиях ∑a_ijx_j≤b_i ; i=1;m ; x_j≥0 , то применяется следующий алгоритм:

1. Найти исходное допустимое решение задачи

2. Найти градиент функции ƒ

3. Построить функцию

; найти ее максимальное значение, т.е Z^(k)

4. По формуле ; - произвольно, или находится как наименьшее решение уравнения

5. Проверить необходимость перехода к последующему допустимому решению, приняв в качестве критерия оценки неравенство

пункт 2, где x⁽⁰⁾=х ^(к) . В противном случае решение задачи найдено.

Метод штрафных функций:

ƒ(x₁, x₂, …, x_n)→max ƒ вогнутая на Ω Ω: g_i(x₁, x₂,…, x_n)≤b_i x_j≥0, где g_i - выпуклые функции.

Алгоритм метода:

1. Найти исходное допустимое решение задачи

2. Выбрать шаг вычислений

3. Найти и

4. По формуле

Определить координаты точки определяющей новое решение задачи.

Где α_i(x₁,x₂,…,x_n)=0, если b_i-g_i(x₁,…x_n)≥0 и α_i(x₁,x₂,…,x_n)=α_{i ,}если b_i-g_i<0 и

α_i – весовые коэффициенты.

Начинают итерационный процесс при малых α_{i ,} постепенно их увеличивая.

5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу, если да, то определяют необходимость перехода к следующему допустимому решению по формуле

В случае необходимости переходят к этапу 2, в противоположном случае решение найдено.

6. Устанавливают значение весовых коэффициентов и переходят к этапу 4

Замечание: Произвольный выбор значений α_i приводит к значительным колебаниям удаленности определяемых точек от области допустимых решений. Этот недостаток устраняется при решении задачи методом Эрроу – Гурвица, согласно которому на очередном шаге числа α_i выбирают по формуле:

α_i ⁽⁰⁾ – произвольное положительное число.