Методы решения оптимизационных задач

ВОПРОСЫ К ЭКЗАМЕНУ

 

1. Понятие «решение». Классификация решений.

 

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

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

Для решения проблемы необходимо ответить на следующие вопросы:

• Что делать (какие новые потребности потребителей необходимо удовлетворять, либо на каком качественном уровне необходимо удовлетворять старые потребности)?

• Как делать (по какой технологии)?

• С какими производственными затратами делать?

• В каком количестве?

• В какие сроки?

• Где (место, производственное помещение, персонал)?

• Кому поставлять и по какой цене?

• Что это даст инвестору и обществу в целом?

Термин «управленческое решение» употребляется в двух основных значениях — как процесс и как явление. Какпроцесс УР— это выполнение восьми основных процедур: -информационная подготовка, разработка вариантов, согласование вариантов, выбор одного варианта, утверждение, реализация, контроль выполнения УР и информирование инициатора решения .

УР можно сравнить с дирижером, в ведении и под контролем которого находятся все другие решения.

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

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

Требования к управленческим решениям:

- выполнимость - своевременность - оптимальность - законность - полномочность - справедливость - непротиворечивость - простота - краткость - ясность изложения

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

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

Характеристики управленческих решений:

- временной горизонт - обратимость - эффект воздействия - периодичность - соответствие "ценностям"

Виды управленческих решении:

- по степени новизны — запрограммированные, незапрограммированные

- по подходам к принятию — интуитивные, основанные на опыте, рациональные

- по масштабам воздействия — общие, частные

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

- по прогнозируемым свойствам — с определенным результатом, с вероятным исходом

- по количеству критериев — однокритериальные, многокритериальные

- по направлениям воздействия — внутренние, внешние

- по глубине воздействия — одноуровневые, многоуровневые

- по способу принятия — индивидуальные, коллективные

 

 

2. Методы принятия решений.

 

1. Методы, применяемые на этапе диагностики проблемы и формулировки ограничений и критериев:

а) Методы ситуационного анализа:

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

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

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

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

б) Методы моделирования:

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

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

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

Имитационное моделирование – создание модели и ее экспериментальное применение для определения изменений реальной ситуации.

Экономический анализ – оценка финансово-экономического состояния предприятия. Используется в условиях доступности и достоверности бухгалтерской отчетности.

2. Методы, применяемые на этапе определения альтернатив:

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

Методы ассоциаций и аналогий – выявление новых идей.

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

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

3. Методы, применяемые на этапе оценки альтернатив:

Методы многокритериальной оценки – оценка и сравнение альтернатив по нескольким критериям.

Методы экспертной оценки – построение экспертом рациональной процедуры интуитивно-логического анализа в сочетании с количественной оценкой и обработкой результатов.

Фактографические методы – прогнозирование на основании фактической информации о прошлом и настоящем развитии объекта.

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

 

 

3. Основные понятия: модель, моделирование, экономико-математическая модель. Цель моделирования.

 

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

 

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

1) адекватность – достаточно точное отображение свойств объекта;

2) полнота – предоставление получателю всей необходимой информации

об объекте;

3) гибкость – возможность воспроизведения различных ситуаций во всем

диапазоне изменения условий и параметров;

4) трудоемкость разработки должна быть приемлемой для имеющегося

времени и программных средств.

Моделирование – это процесс построения модели объекта и исследованияего свойств путем исследования модели.

Таким образом, моделирование предполагает 2 основных этапа:

1) разработка модели;

2) исследование модели и получение выводов.

При этом на каждом из этапов решаются разные задачи и используются

отличающиеся по сути методы и средства.

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

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

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

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

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

1) модель обеспечивает корректное (адекватное) отображение свойств

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

2) модель позволяет устранить перечисленные выше проблемы, присущие

проведению исследований на реальных объектах.

 

 

4. Классификация экономико-математических моделей.

 

Экономико-математические методы (ЭММ) - обобщающее название комплекса экономических и математических научных дисциплин, введен­ное академиком В.С.Немчиновым в начале 60-х годов. Обычно в ЭММ включают следующие группы научных дисциплин:

1. Математическая статистика – дисциплина, которая изучает вопросы измерения и анализа массовых количественных данных и включает:

- дисперсионный анализ;

- корреляционный анализ;

- регрессионный анализ;

- факторный анализ.

2. Эконометрия - моделирование экономических процессов, охватывающее как абстрактные, так и статистические числовые модели:

- теория производственных функций;

- межотраслевые балансы (статические и динамические);

- анализ спроса и потребления и др.

3. Методы принятия оптимальных решений, включая исследование операций:

- оптимальное (математическое) программирование;

- линейное программирование;

- нелинейное программирование;

- дискретное (целочисленное) программирование;

- стохастическое программирование;

- сетевые методы планирования и управления;

- программно-целевые методы планирования и управления;

- теория управления запасами;

- теория массового обслуживания;

- теория игр;

- теория расписаний и др.

4. Экономико-математические методы, специфические для централизованно планируемой и рыночной экономики:

- оптимальное народно-хозяйственное, отраслевое и региональное планирование;

- теория оптимального ценообразования.

5. Экономическая кибернетика – наука об общих закономерностях процесса управления и обработки информации, включающая:

- системный анализ экономики;

- теория экономической информации;

- теория автоматизированных систем управления.

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

- методы машинной имитации;

- деловые игры;

- методы реального экономического эксперимента.

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

 

 

5. Классификация экономико-математических методов.

 

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

В зависимости от типа моделируемого объекта модели бывают макро- и микроэкономические.

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

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

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

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

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

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

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

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

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

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

Непрерывное моделирование позволяет отобразить непрерывные процессы в системах.

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

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

В зависимости от формы представления объекта можно выделить мысленное и реальное моделирование.

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

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

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

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

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

Символическое моделирование может быть языковым или знаковым. В основе языкового моделирования лежит некий тезаурус, т.е. словарь, очищенный от неоднозначности, присущей обычному словарю (например, слово "КЛЮЧ").

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

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

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

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

 

 

6. Этапы моделирования.

 

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

Рис. 4. От прототипа – к принятию решения.

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

Отправной пункт здесь - прототип (рис. 2.4). Им может быть существующий или проектируемый объект либо процесс.

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

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

I этап. Постановка задачи
Описание задачи
Цель моделирования
Анализ объекта
II этап. Разработка модели
Информационная модель
Знаковая модель
Компьютерная модель
III этап. Компьютерный эксперимент
План моделирования
Технология моделирования
IV этап. Анализ результатов моделирования
Р езультаты соответствуют цели	Результаты не соответствуют цели

Рассмотрим основные этапы моделирования подробнее.

3.2. I этап. Постановка задачи

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

Описание задачи

Задача (проблема) формулируется на обычном языке, и описание должно быть понятным. Главное здесь - определить объект моделирования и понять, что собой должен представлять результат. От того, как будет понята проблема, зависит результат моделированияи, в конечном итоге, принятие решения.

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

К первой группе можно отнести задачи, в которых требуется исследовать, как изменятся характеристики объекта при некотором воздействии на него. Такую постановку задачи принято называть «что будет, если?». Например, как изменится скорость автомобиля через 6 с, если он движется прямолинейно и равноускоренно с начальной скоростью 3 м/с и ускорением 0, 5 м/с²

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

«Один человек увидел НЛО и в течение следующих 15 минут рассказал об этом трем своим знакомым. Те в свою очередь еще через 15 минут сообщили о новости еще трем своим знакомым каждый и т. д. Проследить, каково будет количество оповещенных через 15, 30 и т. д. минут».

Вторая группа задач имеет такую обобщенную формулировку: какое надо произвести воздействие на объект, чтобы его параметры удовлетворяли некоторому заданному условию? Такая постановка задачи часто называется «как сделать, чтобы?..». Например, какого объема должен быть воздушный шар, наполненный газом гелием, чтобы он мог подняться с грузом 100 кг?

Наибольшее количество задач моделирования, как правило, являются комплексными. Например, задача изменения концентрации раствора: «Химический раствор объемом 5 частей имеет начальную концентрацию 70%. Сколько частей воды надо добавить, чтобы получить раствор заданной концентрации?». Сначала проводится расчет концентрации при добавлении 1 части воды. Затем строится таблица концентраций при добавлении 2, 8, 4... частей воды. Полученный расчет позволяет быстро пересчитывать модель с разными исходными данными. По расчетным таблицам можно дать ответ на поставленный вопрос: сколько частей воды надо добавить для получения требуемой концентрации.

Цель моделирования

Зачем человек создает модели?

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

Другая важная цель моделирования — создание объектов с заданными, свойствами. Эта цель определяется постановкойзадачи «как сделать, чтобы ...».

Цель моделирования задач типа «что будет, если...» - определение последствий воздействия на объект и принятие правильного решения. Подобное моделированиеимеет большое значение при обращении к социальным и др. проблемам.

Нередко целью моделирования бывает эффективность управления объектом (или процессом).

Анализ объекта

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

Очень часто исходный объект - это целая совокупность более мелких составляющих, находящихся в некоторой взаимосвязи. Слово «анализ» (от греч. «analysis») означает разложение, расчленение объекта с целью выявления составляющих, называемых элементарными объектами. В результате появляется совокупность более простых объектов. Они могут находиться между собой либо в равноправной связи либо во взаимном подчинении. Схемы таких связей представлены на рис. 6 и 7.

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

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

 

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

 

Большинство задач, решаемых методами исследования операций, может быть сформулировано так[3]:

максимизировать

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

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

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

Рассмотрим некоторые примеры задач линейного программирования.

Определение оптимального ассортимента. Имеютсярвидов ресурсов в количестваха₁, а₂, …, а_i, …, a_p и q видов изделий. Задана матрица , гдеa_ikхарактеризует нормы расходаi-го ресурса на единицуk-го изделия (k= 1, 2, …,q).

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

Определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности принимает наибольшее значение.

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

максимизировать (3.1.1)

при ограничении i=1, 2, …,p. (3.1.2)

Кроме ограничения по ресурсам (3.1.2), в модель могут быть введены дополнительные ограничения на планируемый выпуск продукции , условия комплектности для сборки для всехi, j, k и т. д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеютсяm видов взаимозаменяемых ресурсова₁, а₂, …, а_i, …, a_m, используемых при выполненииn различных работ в объемеb₁, b₂, …, b_n.

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

Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность была наибольшей (или суммарные затраты - наименьшими).

Данная задача называется общей распределительной задачей.

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

Математическая модель задачи такова:

минимизировать (3.1.3)

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

j=1, 2, …,n; (3.1.4)

i=1, 2, …,m. (3.1.5)

Ограничение (3.1.4) означает, что план всех работ должен быть выполнен полностью, а ограничение (3.1.5) – что ресурсы должны быть израсходованы целиком.

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

Задача о смесях. Имеется р компонентовi=1, 2, …,p, при сочетании которых в разных пропорциях получают различные смеси. В каждый компонент, а следовательно, и в смесь входитqвеществ. Количествоk-го веществаk=1, 2, …,q, входящее в состав единицыi-го компонента и в состав единицы смеси, обозначим соответственноa_ik иa_k. Полагают, чтоa_kзависит отa_ik линейно, т. е. если смесь состоит изx₁ единиц первого компонента иx₂ – единиц второго компонента и т. д., то

.

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

Необходимо определить состав смеси, при котором суммарная характеристика (цена, масса или калорийность) окажется наилучшей.

Обозначим через х₁, х₂, …, х_рвеличину компонента р-го вида, входящего в смесь.

Математическая модель имеет такой вид:

минимизировать (3.1.6)

при условии

k=1, 2, …,q. (3.1.7)

Условие (3.1.7) означает, что процентное содержание k-го вещества в единице смеси должно быть не меньше величиныb_k.

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

Задача о раскрое материалов.На раскрой поступаетmразличных материалов. Требуется изготовить из нихkразных комплектующих изделий в количествах, пропорциональныхb₁, b₂, …, b_k(условие комплектности).

Пусть каждая единица j-го материала,l=1, 2, …,m, может быть раскроенаnразличными способами, так что при использованииi-го способа раскроя,i=1, 2, …,n, получится единицk-го изделия.

Определить план раскроя, обеспечивающий максимальное количество комплектов, если известно, что объем запаса j-го материала равен a_jединиц.

Количество единиц j-го материала, раскраиваемыхi-м способом, обозначимx_ij, а количество изготавливаемых комплектов изделий –х.

Математическая модель задачи такова:

максимизировать х

при условиях

(3.1.9)

(3.1.10)

Условие (3.1.9) означает ограничение запаса j-го материала, а условие (3.1.10) – условие комплектности.

Задачу линейного программирования можно сформулировать так:

максимизировать (3.1.11)

при условиях

(3.1.12)

и

(3.1.13)

Ограничения (3.1.13) называют условиями неотрицательности.

В данном случае все условия имеют вид неравенств. Иногда они могут быть смешанными, т. е. неравенства и равенства:

(3.1.14)

Если все ограничения задачи ЛП заданы в виде строгих равенств:

(3.1.15)

то данная форма называется канонической.

В матричной форме задачу ЛП записывают следующим образом:

максимизировать с^тх (3.1.16)

при условии

Ах b;

x 0, (2.1.17)

где А – матрица ограничений размером (m n);b^{(m 1)} – вектор-столбец свободных членов;х^{(n 1)} – вектор переменных;с^т = [c₁,c₂, …,c_n] – вектор-строка коэффициентов целевой функции.

Допустимым множеством решений задачи (3.1.11)-(3.1.13) называется множеством R(x) всех векторов х, удовлетворяющих условиям (3.1.12) и (3.1.13).

Очевидно, множество R(x) представляет собой выпуклое многогранное множество или выпуклый многогранник.

Решение х₀называется оптимальным, если для него выполняется условиес^тх₀ с^тх,для всехх R(x).

Отметим, что поскольку minf(x) эквивалентенmax[-f(x)], то задачу ЛП всегда можно свести к эквивалентной задаче максимизации.

 

8. Математическое программирование. Общий вид модели линейного программирования.

 

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

Найти набор управляемых параметров

,

на котором достигается наибольшее (наименьшее) значение показателя эффективности

 (7)

при выполнении ограничений

(8)

(9)

(10)

и на некоторые переменные накладываются условия неотрицательности

(11)

Функция (7) называется целевой функцией или критерием оптимальности, или линейной формой.

Вектор управляемых параметров называется решением. Решение называется допустимым, если оно удовлетворяет ограничениям (8–11). Допустимое решение называется планом.

(12)

Решение называется оптимальным, если на нем достигается наибольшее значение критерия оптимальности :

–оптимальное решение, если

(13)

–оптимальное решение, если для любого

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

1.3. Различные формы задач линейного программирования

В зависимости от вида ограничений различают следующие формы задач:

• Каноническая
• Симметричная
• Общая.

Задача в канонической форме – задача ЛП, в которой все ограничения (8) – (10) есть равенства (p = q = 0) и все переменные неотрицательные (r = n).

Общий метод решения задачи ЛП разработан именно для задачи в каноническом виде.

Матричный вид задачи в канонической форме:

(14’)

(15’)

(16’)

( ) = ( * ) →

=

= – вектор коэффициентов критерия

=

= – матрица условий (технологических коэффициентов)

= ( )

= – вектор условий

= – вектор ограничений

Векторный вид задачи в канонической форме:

(14”)

(15”)

( ) = ( * )

+ + …+ =

(16”)

,

Для неё разработан метод решения, который называется симплексным.

Задача в симметричной форме – задача ЛП, в которой все ограничения (8) - (10) есть неравенства (p = q = m) и все переменные неотрицательные (r = n).

(17)

(18)

(19)

Матричный вид задачи в симметричной форме:

С

(14’)

(15’)

(16’)

имметричная форма допускает графическое решение (иллюстрацию).

Задача в общей (смешанной) форме – задача ЛП, в которой присутствуют все виды ограничений и не все переменные неотрицательные.

Приведение задачи линейного программирования от одной эквивалентной формы к другой

1. Сведение задачи минимизации к задаче максимизации:

Преобразование сводится к смене знака критерия.

( ) ~ ( ( ))

*

( ) = ( ( ))

1. Переход от ограничений-неравенств к уравнениям:

• (20)

Неравенство (20) заменяется на уравнение (21) и условие (22)

+ = (21)

(22)

Переменные – дополнительные или балансовые, так как обеспечивают баланс правой и левой частей.

• 

(23)

Аналогично, неравенство (23) заменяется на уравнение (24) и условие (25)

(24)

(25)

- =

1. Переход от переменных произвольного знака к неотрицательным переменным:

= -

1. Переход от переменных, ограниченных снизу, к неотрицательным:

= +

1. Переход от уравнений к неравенствам:

• Если имеется уравнение:

(26)

т

(27)

(28)

о оно заменяется на два неравенства:

• Пусть есть несколько ограничений:

(29)

А

(30)

также:

Пусть ранг (количество линейно-независимых уравнений) системы ограничений равен , тогда переменных можно выразить через остальные:

П

(31)

од решением систем уравнений (29) понимается зависимость одних переменных через другие. Эта зависимость (31) называется общим решением, независимые переменные – свободными (их можно произвольно менять), а – базисными переменными.

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

(32)

Тогда для свободных переменных получаем ограничения в виде неравенств:

Если ( ) = 2, то задача допускает иллюстрацию в пространстве двух переменных.

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

 

9. Основные теоремы линейного программирования.

 

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

14.Графический метод решения задачи ЛП.Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства. Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку. Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте. Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.

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

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

V. Построить вектор, который начинается в точке (0;0).Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI. При поиске максимума ЦФ (целев.ф-я) необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится ф-я.

15.Приемы моделирования условий задачи в ЛП.1.Запись условий с изменяющимися объемами ограничений. Условие запис. двумя линейными соотношениями: сумма(наверху n,внизу j=1)aijxj≥bi(подчеркнута внизу) и сумма(наверху n,внизу.j=1)aijxj≤bi(подчеркнута.наверху).Подобная формулировка обеспечивает изменение bi в пределах от минимально допустимого значения до максимальной границы. 2.Введение доп.переменной.Помогает установить, насколько изменится значение bi под влиянием других условий.3.Запись ограничений с использованием.коэф.пропорциональности.4.Введение вспомогат переменной с отраженной величиной. Если заранее невозможно определить потребность в производственных ресурсах или объемы пр-ва и реализации продукции.

16.Анализ результатов решения задач ЛП. Анализ предст. собой. заключит. этап. матем. моделирования маркетинговых процессов. Его необходимость вызвана след. обстоятельствами: 1.модель отображает лишь наиболее существенные черты процесса, не являясь его точным аналогом. Поэтому может возникнуть необходимость в ее уточнении с целью улучшения кач-ва решения 2.необходимость изменения исходных данных может быть вызвана случайными факторами(допущены ошибки)3.комплексное прогнозирование и планирование маркет. процессов предполагает разработку системы моделей. При их взаимной увязке выходная инф. одной модели может служить входной инф. для другой. Цели анализа:1.определение возможных последствий при изменении параметров модели 2.оценка устойчивости оптимального плана(решения) к изменению отдельных параметров задачи 3.проведение вариантных расчетов и получение новых вариантов оптимального плана без повторного решения задачи, с помощью корректировки.

17. Классификация оптимизационных моделей. В маркетинге оптимизационные модели используются в связи с множеством возможных вариантов функционирования конкретного маркетингового объекта, когда возникает ситуация выбора варианта, наилучшего по некоторому правилу, характеризуемому соответствующей функцией (максимум прибыли, минимум затрат). Оптимальное программирование -это процесс поиска оптимальных решений при заданных ограничениях на входящие в модель факторы. Обычно ищется экстремум функции, называемой целевой ф-ей. В зависимости от вида целевой функции и ограничений модели оптимальное программирование классифицируется: 1.модели линейного программирования- целевая функция и ограничения списываются только линейными зависимостями. 2.модели нелинейного программирования -при описании целевой функции и ограничений могут содержаться нелинейные зависимости 3.модели дискретного программ- ставятся условия нахождения оптимального решения только в определенных дискретных (целочисленных точках) 4.модели динамического программ -путем поэтапной оптимизации получается общий результатирующий оптимум.

18.Подходы к прогнозированию спроса на товарном рынке. Спрос определяет стратегию и тактику организации пр-ва и сбыта товаров. Маркетинг можно охарактеризовать как процесс согласования возможностей предприятия и потребителей. Результат этого процесса -предоставление благ потребителям, получение прибыли. Уровень платежеспособного спроса явл решающим фактором, определяющим необходимые объемы пр-ва готовой продукции. Сущ 2 метода: Эмпирический -основан на анализе фактически складывающихся структур потребления. Априорный- исходит из физиологических, психологич, экономич требований. При кратко и среднесрочных прогнозах применяется метод экстраполяции. При прогнозировании на длительный период -нормативный подход, при котором определяется конечный результат, достижение которого желательно в течение прогнозируемого периода.

 

10. Методы решения оптимизационных задач.

 

Методы решения оптимизационных задач

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

позволяющие найти экстремальное значение целевой функции (1.1)

при	соотношениях	между переменными,		устанавливаемых
ограничениями (1.2),		в диапазоне	изменения	переменных,
определяемом граничными условиями			(1.3).

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

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

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

9

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

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

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

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

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

Выполнение вычислений

Решение оптимизационных задач с небольшим количеством переменных х i (i = 1, 2) при знании алгоритмов методов математического программирования можно выполнить традиционными вычислениями с использованием калькулятора.

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

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

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

Появление такого мощного программного средства, как Excel 7.0, дает возможность пользователю решать практически любые

10

оптимизационные задачи, совершенно различные по своему классу и содержанию.

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

В приложениях даются некоторые рекомендации и примеры решения оптимизационных задач различного класса с помощью программного обеспечения Excel 7.0.

---

Дата добавления: 2019-01-14; просмотров: 577; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!