Постановка и экономико-математическая модель задачи о назначениях

9. Задача производственного планирования как задача об оптимальных назначениях

Базовая модель задачи планирования производства.

Математические модели дискретного программирования

 

Классификация прикладных задач целочисленного программирования

См. вопрос №10

 

Геометрическая интерпретация задач целочисленного программирования.

См. вопрос №3

Характеристики численных методов решения дискретных задач.

Методы решения системы делятся на две группы:

1) прямые (точные методы);

2) итерационные методы (приближенные).

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

К точным методам относятся следующие:

• Метод Гаусса
• Метод Холецкого (метод квадратных корней)

К итерационным методам относятся:

· Метод Якоби (простых итераций)

· Метод Зейделя

· Метод Ричардсона

 

14. Проектирование оптимального производственного плана машиностроительного предприятия методом Гомори

 

 

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

Градиентом непрерывной однозначной функции j (обозначается gradj или Ñj) называется вектор

,

где – частная производная функции по m-му параметру xm, – единичные векторы в направлении координатных осей.

Градиент функции Ñjпредставляет собой вектор перпендикулярный к

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

Длина вектора Ñj определяется по формуле:

(2.3.1)

Движение по градиенту осуществляется в следующем порядке:

1. Вычисляются составляющие вектора в точке (основной уровень): .

2. Последовательно прибавляют составляющие к основному уровню факторов: , где h_j– шаг движения.

3. Итерационный процесс заканчивается, когда выполняется неравенство: <e

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

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

Градиентный метод оптимизации не решает вопроса о самой лучшей точке поверхности отклика при наличии нескольких экстремальных точек.

 

Рис. 2.3.1. Градиент функции Ñj в точке А.