Линейная оптимизация

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

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

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

Это обычная математическая задача типа: Дано / Найти / При условии, но которая имеет множество возможных решений. Таким образом, задача оптимизации - задача выбора из множества возможных вариантов наилучшего, оптимального.

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

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

Все модели линейной оптимизации имеют два общих основных свойства.

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

 Второе  - наличие  единственного параметра  эффективности, который необходимо  максимизировать или минимизировать. Например, вспомним историю о том как один генсек поставил такую задачу перед страной: «Больше товаров по меньшим ценам улучшенного качества». Эта задача нерешаема в принципе и к задачам ЛП тоже не имеет отношения.

В этом лозунге  целых 3 параметра эффективности: «количество товаров», «себестоимость продукта» и «качество продукта». Мы понимаем, что если максимизировать «количество товаров» или минимизировать «себестоимость продукта”», то падает качество исходного товара, если максимизировать «качество продукта», то повышается «себестоимость продукта» и т.д..

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

2.2 Структура линейной оптимизации

 

Для решения  задач линейной оптимизации  стоит  сначала построить математическую модель линейной оптимизации, а затем воспользоваться любым известным алгоритмом ее решения. Аналитически задачи такого плана решаются с помощью симплекс-метода, а численное решение можно получить с помощью пакета MS Excel. Математическая модель поможет вам лучше понять что делать дальше . Ограничения записываются в виде системы неравенств. (В некоторых случаях необходимо ввести ограничения в виде равенств). Зачастую требуются дополнительные ограничения на сами переменные в виде неотрицательности решения.

 Линейная  целевая функция исследуется  на максимум или к минимум.

Каждая задача оптимизации обязательно должна иметь три компоненты:

1. Неизвестные (что ищем, то есть, план);
2. Ограничение на неизвестные (область поиска);
3. Целевая функция (цель, для которой ищем экстремум).

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

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

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

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

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

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

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

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

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

 

3. . Уровни и вид системы оптимизации

 

При постановке задачи оптимизации необходимо:

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

 Рис.1. - Уровни оптимизации систем¹⁸

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

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

4. Учет ограничений.

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

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

Общая задача линейного  программирования имеет следующий  вид¹⁹:

 

 

Здесь  переменными  являются х1,…,хn, параметрами  – c_i,  a_ih,  d_ih,  s_ih,  b_i,  u_j,  v_l,  L₀,  заданные постоянными числами.

Заметим,  что  ограничения  типа  хi  qi   приводятся  к следующим ограничениям типа неравенство:  -qi  xi qi

.  Любое   решение  системы  ограничений   называется  ее допустимым  решением.  Заметим,  что  если  допустимое  решение  таково,  что  для  него  все  неравенства  системы  выполняются строго, то оно не может доставлять минимум никакой  линейной  функции  L.  Чтобы  убедиться  в  этом, достаточно лишь несколько увеличить одно из xi, если ci<0, либо  уменьшить  его,  если  ci>0.  Такие достаточно  малые изменения xi  всегда  можно осуществить,  лишь  бы  они не нарушали  неравенств  ограничений системы.  С другой стороны, эти изменения приведут к уменьшению значения L.  Поэтому,  решение экстремальной задачи  может существовать  лишь  при  условии,  когда  некоторые  из ограничений  типа  нестрогих  неравенств  выполняются  как равенства. Причем, таких условий должно быть достаточно для  однозначного  нахождения  из  полученной  системы линейных уравнений  ее решения. Имеется лишь конечное число  всевозможных  ситуаций,  при  которых  n-m  (или более,  при  вырожденности)  неравенств  рассматриваются как  уравнения.  Поэтому,  общая  задача  линейного программирования может быть решена с помощью полного перебора всех таких ситуаций. Однако при большом числе неизвестных  и  ограничений  такой  способ  требует огромного  объема  вычислений.  Для  их  сокращения предложены  различные  алгоритмы  линейного программирования,  наиболее  известным  из  которых является симплекс метод.

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

Нахождение  решения задачи линейного программирования геометрическим методом включает следующие  этапы²⁰:

1. Строят прямые, уравнения, которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости,  определяемые каждым из ограничений  задачи.

3. Находят многоугольник  решений.

4. Строят вектор.

5. Строят прямую.

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

7. Определяют  координаты точки максимума (минимума) функции и вычисляют значение  целевой функции в этой точке. 

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

Электронные таблицы Excel фирмы Microsoft имеют встроенные средства решения задач поиска экстремума, оформленные в виде так называемой надстройки.

Электронные таблицы Excel позволяют записывать в выбранную ячейку не только числа, но и математические выражения, составленные по общим правилам языков программирования с использованием символа присваивания =, знаков операций (+,-,*,/) и встроенных функций. В качестве операндов в таких выражениях могут использоваться константы или имена ячеек Excel.

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

Термин  «линейное  программирование»  не  связан  с составлением  программ  для  ЭВМ.  Корректным  переводом на русский язык английского слова programming, в варианте североамериканского диалекта,  является  «планирование»²¹.

Именно  для  задач  экономического  планирования изначально  предполагалось  применять  новые математические  метод.  Термин  «линейное программирование»  возник  отечественной  научной литературе  в  результате  недоразумения,  связанного  с неправильным переводом.

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

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

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