Транспортная задача

Имеется некий однородный груз, который нужно перевести с складов на заводов. Для каждого склада известно, сколько в нём находится груза , а для каждого завода известна его потребность в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния от -го склада до -го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются  — количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:

Целевая функция имеет вид: , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица размера . Первый игрок выбирает число от 1 до , второй — от 1 до . Затем они сверяют числа и первый игрок получает очков, а второй очков (  — число, выбранное первым игроком,  — вторым). Нужно найти оптимальную стратегию первого игрока.

Пусть в оптимальной стратегии, например, первого игрока число нужно выбирать с вероятностью . Тогда оптимальная стратегия является решением следующей задачи линейного программирования:

,

,

( ),

в которой нужно максимизировать функцию . Значение в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

Градиентные методы.

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

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

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

В общем виде градиент целевой функции характеризуется соотношением:

Данный вектор в каждой точке области определения функции цели направлен по нормали к поверхности уровня, проведенной через эту точку, и совпадает по направлению с наискорейшим изменением (возрастанием или уменьшением) целевой функции. Таким образом, движение по градиенту должно приводить к оптимальному решению (это кратчайший путь к оптимуму).

Движение по градиенту обычно является многошаговым (от исходного состояния до состояния, соответствующего оптимальному решению). Особые трудности возникают при выборе шага, так как эта процедура является произвольной. Некоторые градиентные методы основаны на изменении величины шага в процессе движения к оптимуму, так как это способствует повышенной эффективности поиска.

Метод релаксации (покоординатного спуска).

Метод релаксации основан на движении к оптимуму в направлении осей координат, вдоль которых функция цели изменяется (уменьшается или возрастает) наиболее существенно. При использовании релаксационного метода в начальной точке поиска определяют частные производные функции цели по всем независимым переменным, а затем выбирают из них производную, которая является наибольшей по модулю.

Направление убывания (возрастания) целевой функции можно определить по знаку соответствующей частной производной. Критерий оптимизации убывает в направлении соответствующей оси, если производная имеет отрицательный знак, и убывает в обратном направлении, если знак производной положительный. Критерием окончания поиска часто служит момент достижения точки, которая характерна тем, что при движении из нее по любому осевому направлению не происходит дальнейшее снижение величины критерия оптимизации.

Алгоритм движения (спуска) для каждого выбранного осевого направления имеет следующий вид:

,

где h – величина шага.

Выбор шага имеет очень важное значение: при очень малой величине шага значительно увеличивается число шагов, а чрезмерная величина шага затрудняет попадание в оптимум.

Методы случайного поиска

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

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

Среди методов случайного поиска выделяется как отдельный класс методы случайных направлений. Эти методы связаны с движением в область оптимума на основе движения в случайных направлениях с сохранением направления движения до тех пор, пока каждый следующий шаг является более удачным. При каждом неудачном шаге направление движения меняется – выбирают новое случайное направление.