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

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

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

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

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

    При использовании метода наискорейшего спуска на каждой итерации величина шага а_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

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

    x_ij 0, i 1, …, m; j 1, …, n.

    Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.

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

     , i 1, …, m.

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

    Задачи транспортного типа широко распространены в практике. Кроме того, к ним сводятся многие другие задачи линейного программирования – задачи о назначениях, сетевые, календарного планирования.

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

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

      Имеются следующие исходные данные.

      Наличие однородной продукции в филиалах производственного объединения.

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

      Расстояния  между филиалами и пунктами доставки. 

      На  пересечении столбца конкретного  пункта доставки со строкой филиала находится информация о расстояниях между этими пунктом доставки и филиалом. Например, расстояние между 3 пунктом и филиалом №3 равно 4 километра.

      Для решения задачи подготовим необходимые  таблицы.

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

      После выбора данной команды появится диалоговое окно.

      Поскольку в качестве критерия оптимизации  нами выбрана минимизация грузооборота, в поле Установить целевую ячейку введите ссылку на ячейку, содержащую формулу расчета общего объема грузооборота продукции. В нашем случае это ячейка $H$8. Чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение минимальному значению;

      В поле Изменяя ячейки введите ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($В$4:$F$7). Это означает, что для достижения минимального грузооборота перевозок будут меняться значения в ячейках с B5 по F8, то есть будут изменяться количество груза, перевезенного по конкретному маршруту.

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

      В группе полей Ограничения нажмите кнопку Добавить. Появится диалог Добавление ограничения. 

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

      Для изменения и удаления ограничений  в списке Ограничения диалогового окна Поиск решения укажите ограничение, которое требуется изменить или удалить. Выберите команду Изменить и внесите изменения либо нажмите кнопку Удалить.

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

      После нахождения решения появляется диалог Результаты поиска решения/

      Нажав кнопку ОК, вы занесете вариант решения на рабочий лист.