Оптимизация плана производства автоматизированным способом

Содержание

Введение

1 Понятие задачи оптимизации плана производства

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

1.2 Методы решения

1.3 Генетический Алгоритм

2 Практическое решение задачи

2.1 Экономико-математическая модель задачи

2.2 Решение задачи с применением Matlab

Заключение

Список использованных источников

Приложение А

Введение

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

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

Добиться максимальной прибыли рационально распределяя материальные, финансовые и трудовые ресурсы на предприятии управленческим аппаратом

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

Целью данной работы является решение задачи оптимизации плана производства с помощью генетического алгоритма с применением пакета Matlab.

Для достижения поставленной цели необходимо решить ряд задач:

- изучить теорию по задаче оптимизации плана производства;

- изучить теорию по генетическому алгоритму;

- выбрать содержательную постановку;

- построить целевую функцию;

- ввести ограничения;

- найти оптимальное решение;

- сделать выводы.

Рассматриваемая нами задача является NP – полной, то есть для нее не существует полиномиального алгоритма, решающего её за разумное время, в этом и есть проблема. Либо мы выбираем быстрый алгоритм, но он, как известно, не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным для больших значений.

1 Понятие задачи оптимизации плана производства

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

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

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

Пусть число всех видов ресурсов равно m; обозначим их R1 R2, ..., Rm. Это могут быть: металл, электроэнергия, различные виды поставок с других предприятий. Допустим, что на нашем производстве могут выпускаться n типов товаров G1, G2, ..., Gn. Технологией производства товара Gj назовем набор чисел (аij), i = 1, 2, ..., m, показывающих, какие количества ресурсов Ri( необходимы для выпуска одной единицы товара Gj. Так, производство товара G, можно мыслить как конвейер, на всем протяжении которого подаются ресурсы в количествах а11, a21, а31, ..., am1 а на конце конвейера выходит готовая единица продукта Gi. Можно составить технологическую матрицу представленную на таблице 1.1

Таблица 1.1 - Технологическая матрица

Которая полностью описывает технологические возможности производства. Обозначим ее через А.

Пусть заданы количества bi ресурсов Ri ,i = 1, 2, ...m, которые могут быть использованы в производстве;

положим b = (b1, b2, ..., bm) (вектор ресурсов). Назовем планом производства вектор х = (х1, х2, ..., хn), показывающий, какие количества товаров G1, G2, ..., Gn будут произведены.

Будем считать технологию производства линейной, т. е. предположим, что все затраты ресурсов растут прямо пропорционально объему выпуска. Более точно, допустим, что затраты при выпуске xi единиц продукта Gj описываются вектором (a1jxj, a2jxj, .., amjxj,), причем одновременное

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

Таким образом, затраты ресурсов, необходимые для выполнения плана производства х = (x1, x2, . .., хn), описываются вектором, координаты которого имеют вид

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

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

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

Построение математической модели. Критерий оптимизации (суммарную величину прибыли) можно тогда представить так:

->max                            (1)

где:

n - количество выпускаемых продуктов;

cj - прибыль от выпуска и реализации единицы j-го продукта;

bi - количество имеющегося i-го ресурса;

xj - объем выпуска j-го продукта.

При ограничениях

где:

W-величина ресурсов.

Рассмотрим две возможные постановки оптимизационной задачи. Пусть заданы цены с = (с1, с2, ..., сn) на продукты производства G1, G2, . .., Gn. Требуется определить план производства, максимизирующий стоимость выпущенной продукции. Формальная запись этой задачи такова:

                           max<c,x>              (2)

Ах b, x.

Подобная постановка вопроса соответствует принципу планирования «по валу». Тот случай, когда планирование выпуска ведется «по номенклатуре», можно смоделировать иначе. Пусть задан вектор х = (х1 х2, ..., хn), определяющий один комплект выпуска; требуется выпустить как можно больше таких комплектов. Пусть а означает число выпускаемых комплектов. Рассмотрим задачу

max

              Ах b, x, x.              (3)

Здесь неравенство x означает, что вектор х =  (x1, х2, ..., хn) содержит не меньше а полных комплектов выпускаемой продукции.

Модели (2) и (3), хотя несомненно и отражают определенные черты реального производства, являются тем не менее сильно идеализированными. Так, в них отсутствует такое важное для производства понятие, как время. Считается также, что все необходимые ресурсы Ri,  i = 1, 2, ..., т, в нужный момент находятся под рукой. Тем самым мы абстрагировались от острых проблем динамики производства и ритмичности поставок. Кроме того, в построенных моделях не учитываются затраты живого труда и целый ряд других показателей, являющихся непременным атрибутом реального производства.

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

1.2 Методы решения

1.2.1 Симплекс-метод

Для решения данной задачи разработано много способов. Рассмотрим один из наиболее распространенных – симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом в 1947 году. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.

1.2.2 Итеративный метод

Называются методы (или алгоритмические отображения), которые при помощи заданной начальной точки x0 Î X генерируют последовательность допустимых точек x0,x1,…,xk,xk+1,… , последовательно приближающихся к оптимальному решению x* задачи . Переход от xk к xk+1 называется итерацией. Если за конечное число итераций метод (алгоритм) приводит к оптимальному решению, то он называется точным методом, в противном случае – приближенным методом. Обычно итерация строится по схеме

xk+1 = xk + αkρk, k=0,1,...

где вектор ρk ε Rn называется направлением в точке xk, а число  - длинной шага. Различные итеративные методы отличаются друг от друга способом вычисления  и .

Эффективность итеративного метода оценивается следующими факторами:

1) Универсальностью;

2) Надежностью и точностью;

3) Чувствительностью к исходным данным и параметрам;

4) Затратами на вычисление;

5) Сходимостью и скоростью сходимости;

Говорят, что итеративный метод сходится, если генерируемая им последовательность {xk} сходится к оптимальному решению.

1.2.3 Полный перебор

Полный перебор (или метод «грубой силы») — метод решения задачи оптимизации плана производства путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

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

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

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

1.3 Генетический Алгоритм

1.3.1 История

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

Сначала Чарльз Дарвин опубликовал в 1859 году свою знаменитую работу "Происхождение видов", где были провозглашены основные принципы эволюционной теории:

       Наследственность (потомки сохраняют свойства родителей)

       Изменчивость (потомки почти всегда не идентичны)

       Естественный отбор (выживают наиболее приспособленные).

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

В 1944 году Эйвери, Маклеод и Маккарти опубликовали результаты своих исследований, доказывавших, что за наследственные процессы ответственна "кислота дезоксирибозного типа". Однако о том, как работает ДНК, стало известно позднее.

В 1953 году в номере журнала "Nature" вышла статья Уотсона и Крика, которые впервые предложили модель двухцепочной спирали ДНК.

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

Первые публикация, которые можно отнести к генетическим алгоритмам, принадлежат Баричелли Н.А. Его работы "Symbiogenetic evolution processes realised by artificial methods" (1957), "Numerical testing of evolution theories" (1962) были направлены прежде всего на понимание природного феномена наследственности.

В 1966 году Л.Дж. Фогель, А.Дж. Оуэнс, М.Дж. Уолш предложили и исследовали эволюцию простых автоматов, предсказывающих символы в цифровых последовательностях.

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

В 1975 году Холланд публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems». В ней он впервые ввёл термин «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA). В дальнейшем понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.

Ученики Холланда – Кеннет Де Йонг и Дэвид Голдберг – внесли огромный вклад в развитие ГА. Наиболее известная работа Голдберга – «Genetic algorithms in search optimization and machine learning» (1989).

1.3.2 Классический ГА

Переформулируем задачу оптимизации как задачу нахождения максимума некоторой функции f(x1, x2, …, xn), называемой функцией приспособленности (fitness function).  Она должна принимать неотрицательные значения на ограниченной области определения (для того, чтобы мы могли для каждой особи считать её приспособленность, которая не может быть отрицательной), при этом совершенно не требуются непрерывность и дифференцируемость. Каждый параметр  функции приспособленности кодируется строкой битов. Особью будет называться строка, являющаяся конкатенацией строк упорядоченного набора параметров:

1010   10110   101    …    10101

|  x1  |    x2    |   x3   |  … |    xn   |

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

1.3.3 Принцип работы ГА

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

С помощью функции приспособленности среди всех особей популяции выделяют:

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

       наихудшие (плохие решения), которые удаляются из популяции и не дают потомства

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

В классическом ГА:

       начальная популяция формируется случайным образом

       размер популяции (количество особей N) фиксируется и не изменяется в течение работы всего алгоритма

       каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи длина кодировки для всех особей одинакова.

На рисунке 3 изображена схема работы любого генетического алгоритма:

Рисунок 1.1 – Схема работы ГА

Шаг алгоритма состоит из трех стадий:

1.       генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения

2.       скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения

3.       мутация нового поколения

Первые две стадии (отбор и скрещивание):

Рисунок 1.2 – Отбор и скрещивание

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

В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т.е. работает пропорциональный отбор (proportional selection).

Существует несколько способов реализации данного отбора:

       stochastic sampling. Пусть особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. N раз запуская рулетку, выбираем требуемое количество особей для записи в промежуточную популяцию.

       remainder stochastic sampling. Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная показывает её вероятность попасть туда ещё раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N, причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию. Такой способ иллюстрируется следующим рисунком:

Рисунок 3 - Remainder stochastic sampling

Особи промежуточной популяции случайным образом разбиваются на пары, потом с некоторой вероятностью скрещиваются, в результате чего получаются два потомка, которые записываются в новое поколение, или не скрещиваются, тогда в новое поколение записывается сама пара. В классическом ГА применяется одноточечный оператор кроссовера (1-point crossover): для родительских строк случайным образом выбирается точка раздела, потомки получаются путём обмена отсечёнными частями:

011010.01010001101  -> 111100.01010001101

111100.10011101001      011010.10011101001

К полученному в результате отбора и скрещивания новому поколению применяется оператор мутации, необходимый для "выбивания" популяции из локального экстремума и способствующий защите от преждевременной сходимости.Каждый бит каждой особи популяции с некоторой вероятностью инвертируется. Эта вероятность обычно очень мала, менее 1%.

1011001100101101 -> 1011001101101101

Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N. Такой процесс эволюции, вообще говоря, может продолжаться до бесконечности. Критерием останова может служить заданное количество поколений или схождение (convergence) популяции.

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

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

Генетический алгоритм производит поиск решений с помощью:

       отбора гиперплоскостей (hyperplane sampling), осуществляемого кроссовером, поскольку последний комбинирует и совмещает шаблоны родителей в их детях.

       метода hill-climbing, обеспечивающегося мутацией: особь случайным образом изменяется – неудачные варианты вымирают, полезные изменения сохраняются популяцией.

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

С точки зрения теоремы шаблонов, мутация только вредит росту количества представителей хороших шаблонов, поскольку лишний раз их разрушает. Однако мутация просто необходима для ГА с малым размером популяции, потому что для них свойственна преждевременная сходимость (premature convergence) – ситуация, когда в некоторых позициях все особи имеют один и тот же бит, не соответствующий глобальному экстремуму.

Введём понятие, использующееся для анализа ГА. Давление отбора (selection pressure) — это мера того, насколько различаются шансы лучшей и худшей особей популяции попасть в промежуточную популяцию. Для пропорционального отбора эта величина с увеличением средней приспособленности популяции уменьшается, стремясь к 1, т.е. шансы плохой и хорошей особей создать потомство уравниваются.

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

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

Необходимость сбалансированной сходимости ГА:

       быстрая сходимость может привести к схождению к неоптимальному решению

       медленная сходимость часто приводит к потере найденной наилучшей особи.

Методология управления сходимостью классического ГА до сих пор не выработана.

1.3.4 Различные модификации ГА

Кодирование.

Аргументы в пользу кодирования бинарным алфавитом:

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

      Например, при кодировании значений для бинарного алфавита количество гиперплоскостей будет , а при использовании, четырехзначного алфавита – .

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

Даже для двух строк, есть вероятность, что на каждой позиции в популяции есть и 0, и 1. Если же алфавит большей мощности, то до применения мутации большая часть пространства поиска будет недоступна с точки зрения кроссовера, после применения мутации станет недоступна другая часть.

Однако небинарные алфавиты зачастую обеспечивают более наглядное представление решений задачи.

Для большинства функций ГА будут работать лучше при кодировании параметров кодом Грея, а не прямым бинарным кодом. Это связано с тем, что расстояние Хэмминга между битовыми представлениями данных может и не отражать близость в привычном смысле – например, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск.

Пример: пусть требуется минимизировать функцию

Если в начальной популяции преобладали хорошие отрицательные решения, то скорее всего мы придём к решению −1 = 11…1.

Но достигнуть глобального минимума 00…0 будет практически невозможно, поскольку изменение любого бита будет приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает.

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

Стратегии отбора.

Ранковый отбор (rank selection): для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.

Турнирный отбор (tournament selection): из популяции случайным образом выбирается t особей, и лучшая из них помещается в промежуточную популяцию. Этот процесс повторяется N раз, пока промежуточная популяция не будет заполнена. Наиболее распространен вариант при t = 2.

Отбор усечением (truncation selection): популяция сортируется по приспособленности, затем берется заданная доля лучших, и из них случайным образом N раз выбирается особь для дальнейшего развития.

Кроссовер.

Двухточечный кроссовер: выбираются 2 точки раздела, и родители обмениваются промежутками между ними:

010.1001.1011  ->  010.1011.1011

110.1011.0100      110.1001.0100

При этом определяющая длина измеряется в кольце – для шаблона 1*****1 при двухточечном кроссовере она будет равна 1, хотя при одноточечном была 6.

Однородный кроссовер: один из детей наследует каждый бит с вероятностью p0 у первого родителя и с (1 - p0) у второго, второй ребенок получает не унаследованные первым биты. Обычно p0 = 0.5.

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

Стратегии формирования нового поколения.

Два основных типа формирования нового поколения после кроссовера и мутации: