Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

РТА

РЕФЕРАТ

предмет: Основы системного анализа

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

2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

Совершенствование процесса производства и оптимизации присутствуют в самых различных его этапах: поставка; выпуск; управление запасами; распределение ресурсов; планирование; функционирование.

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

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

СИСТЕМНЫЙ АНАЛИЗ В УПРАВЛЕНИИ ПРЕДПРИЯТИЕМ

1.1 Системный анализ в управлении предприятием

Менеджмент – это наука об управлении предприятием. Это одна из самых молодых наук, которая окончательно сформировалась в конце ХХ века, хотя история возникновения менеджмента изобилует примерами организаций, существовавших в глубокой древности и дошедших, и даже процветающих и в наши дни. В качестве примера такой линейной структуры можно привести католическую церковь в Риме, в которой существует четкая иерархия подчинения³.

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

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

Положил начало менеджменту как науке Ф. Тейлор, написав труд «Принципы научного управления», в котором наглядно продемонстрировал значение системного анализа в управлении предприятием для его успешности.

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

Третий этап – «неоклассический», когда происходит апробация социологической концепции принятия групповых решений. Здесь к вышеуказанным ученым присоединяется Э. Мейо – основатель школы «человеческих отношений»⁴.

1.2 Понятие системного анализа в системе наук

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

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

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

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

Начало изучения было связано с военно-промышленным комплексом, и, как и многие серьезные разработки, обязано стремление крупных держав мира получить конкурентные преимущества. Впервые термин системный анализ был применен в работах корпорации RAND в 50-х годах прошлого века. В 1952 году разработка проекта сверхзвукового бомбардировщика В-52 строилась на представлении бомбардировщика как системы⁸.

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

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

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

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

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

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

К задачам управления относятся целеполагание, стабилизация, выполнение программы, слежение и оптимизация.

Задача целеполагания – определение поведения системы.

Задача стабилизации – удержание системы в существующем состоянии в условиях возмущающих воздействий.

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

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

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

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

1.3 Этапы становления методологии системного анализа

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

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

Первый этап становления системного анализа относится к первой половине 20 века и является периодом появления и формирования основных идей системного мышления. Рассмотрим основные исторические источники современного системного мышления. «Учение о биосфере и ее постепенном переходе в ноосферу» В.И. Вернадского (1893-1918); «Всеобщая организационная наука, или тектология» А.А. Богданова (1913-1929); «Общая теория систем» Л. фон Берталанфи (1934-1949); «Кибернетика или управление и связь в животном и машине» Н. Винера (1948); «Праксеология» Т. Котарбинского (1930–1940).

Второй этап становления системного анализа формировался в период чрезвычайных условий нарастающей военной угрозы 30-х годов и почти глобального театра боевых действий второй мировой войны в 40-е годы 20 века. Тогда во многих странах появилась реальная необходимость оперативного решения сложнейших междисциплинарных задач обороноспособности. Этот этап характеризуется качественно новыми свойствами решаемых задач и принципиально важными особенностями условий, в которых осуществлялось их решение. К их числу относятся: концептуальная неопределенность, неструктурируемость, NP-сложность и стратегическая важность реальных задач; высокая цена ошибочного или недостаточно обоснованного решения, которая соответствует катастрофическим последствиям стратегического уровня; наличие неустранимого, априорно неизвестного порогового ограничения времени на цикл формирования и реализацию стратегических решений, нарушение которого может иметь катастрофические последствия государственного масштаба.

Третий этап становления и развития системного анализа формировался в послевоенных условиях с середины 40-х до конца 70-х годов 20 века. Этот период принципиально отличается от предыдущих периодов качественно новыми задачами, принципиальными социально-политическими изменениями в мире после окончания Второй мировой войны, уникальными научно-техническими достижениями.

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

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

К важнейшим свойствам, которыми должна обладать общая методология системного анализа, следует отнести¹³:

1) целостность методологии с позиции достижения заданных целей исследования;

2) системность учета факторов, присущих реальным исходным условиям функционирования объекта - неполнота, неопределенность, неточность исходной информации, противоречивость и неоднозначность целей;

3) возможность объяснения, обоснования и реализации осуществления рационального компромисса при решении системной задачи с позиции получения наилучших результатов достижения целей и снижения рисков;

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

2. ЛИТЕЙНАЯ ОПТИМИЗАЦИЯ

2.1 Понятие линейного программирования (оптимизации)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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, в варианте североамериканского диалекта, является «планирование»²¹.

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

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

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

Линейная оптимизация 📙 Реферат → 🆔 137196