Оптимизация трикотажного производства

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

Метод наискорейшего спуска 

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

    Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода. 

    При использовании метода наискорейшего спуска на каждой итерации величина шага а_k выбирается из условия минимума функции f(x) в направлении спуска, т. е. f(x[k] –a_kf’(x[k])) = f(x[k] – af'(x[k])).

    Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])) . 

    Алгоритм метода наискорейшего спуска состоит в следующем.

    1. Задаются координаты начальной точки х[0].

    2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k]).

    3. Определяется величина шага a_k, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).

    4. Определяются координаты точки х[k+1]:

    х_i[k+1] = x_i[k] – а_kf’_i(х[k]), i = 1 ,..., п. 

    5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

    В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 1). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_k выбирается путем минимизации по а функции ?(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = -f’(x[k+1]f’(x[k]) = 0.

Рис. 1. Геометрическая интерпретация метода наискорейшего спуска 
 

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

 

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l_i, i =1, …, n, матрицы являются корни характеристического уравнения 

 

    Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 2. Овражная функция 

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

 

    Задание №2.

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

    - аналитические методы;

    - методы математического программирования. 

    Определение оптимума функциональной зависимости  длины нити в петле, мм от диаметра бобины, см F(x)=-0,002x²+0,0363x+3,9292 на локальном участке изменения x[5,5;18] аналитическим методом.

      
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    В соответствии с методом классического  мат.анализа непрерывно дифференцируемых моделей на отрезке [a,b] существуют локальные экстремумы, если соблюдаются условия:

• если на всем участке [a,b] функция имеет производную, то она является непрерывной;
• если вторая производная больше нуля, то функция F(X) имеет экстремум в виде минимума в точке, где первая производная равна нулю F'(X)=0;
• если вторая производная меньше нуля, то функция F(X) имеет экстремум в виде максимума в точке, где первая производная равна нулю F'(X)=0.

 

    Проверяем 1-е условие наличия экстремума F'(X)= -0,004x + 0,0363.

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

    Определяем  знак экстремума F''(X) = -0,004 < 0.

    Определение оптимума: -0,004x + 0,0363=0; x=9,75;

    y=-0,002*(9,75)²+0,0363*(9,75)+3,9292; y=4,093;

    Функция имеет экстремум в виде минимума в точке (9,75; 4,093). 

      
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      

 

    Задние  №3. Нахождение корней уравнения F(x) методом Дихотомии 

    Метод дихотомии (половинного деления) 

    Метод дихотомии используется для нахождения безусловного минимума унимодальных функций f(x).

    Функция f(x) называется унимодальной на отрезке [a,b], если

1. имеет единственную точку минимума x* на этом отрезке
2. f(x) монотонно убывает на [a,x*], возрастает на [x*,b].

    Свойства унимодальных функций.

    Пусть f(x) унимодальна на [a,b], x,z принадлежат отрезку, x<z, тогда:

    1) если f(x)<f(z), то x* принадлежит [a,z];

    2) если f(x)>f(z), то x* принадлежит [x,b]; 

    Метод дихотомии (метод деления отрезка пополам) основан на известной теореме Больцано-Коши:

      Если непрерывная на отрезке [a,b] функция f(x) на концах его имеет противоположные знаки, т.е. f(a)*f(b)<0, то на интервале (a,b) она хотя бы раз обращается в нуль.

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

    А вот если функция на отрезке является строго монотонной, то тогда можно утверждать

    Если непрерывная и строго монотонная на отрезке [a,b] функция f(x) на концах его имеет противоположные знаки, т.е. f(a)*f(c)<0, то на интервале (a, b) имеется один и только один корень.

    Метод дихотомии основан на последовательном делении отрезка локализации корня пополам.

    Для этого выбирается начальное приближение к отрезку [a,b], такое, что f(a)*f(b)<0, затем определяется знак функции в точке c=(a+b)/2 - середине отрезка [a,b]. Если он противоположен знаку функции в точке a, то корень локализован на отрезке [a,c], если же нет – то на отрезке [c,b].

    Алгоритм можно записать так

    1. представить решаемое уравнение в виде f(x)=0

    2. выбрать такие a, b, что

    3. вычислить c=(a+b)/2

    4. если f(a)*f(c)<0, то b = с, иначе a = c

    5. если критерий сходимости не выполнен, то перейти к п. 3

    6. напечатать корень из переменной с

 

     Для нашего примера  
 
 
 

    решение принимает вид:

      
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

    Задание №4. Решить оптимизационную задачу симплекс методом и средствами Excel 

    Транспортная задача линейного программирования

    Транспортная  задача является классической задачей  исследования операций. Множество задач  распределения ресурсов сводится именно к этой задаче.

    Постановка задачи

    Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта.A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.

    Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

    Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что

     , i 1, …, m.

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

     , j 1, …, n

    Объемы перевозок – неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены: