Учебник. Кафедра Математических методов принятия решений

• Название: Кафедра Математических методов принятия решений
• Анкор: wqeeqwq
• Дата: 25.04.2023
• Размер: 1.84 Mb.
• Имя файла: Учебник.pdf
• Тип: Решение; #1088275
• страница: 1 из 5

Кафедра Математических методов принятия решений
Харитонов С.В.
© Харитонов С.В., 2012
© Московский финансово-промышленный университет «Синергия», 2012
Содержание
Аннотация по дисциплине
Тема 1. Классификация методов принятия управленческих решений. Задачи линейного программирования
Вопрос 1. Классификация методов принятия управленческих решений.
Вопрос 2. Постановка задачи линейного программирования и свойства ее решений.
Вопрос 3. Решение ЗЛП с помощью MS EXCEL.
Литература.
Тема 2. Математические методы принятия решений в условиях определенности, неопределенности и риска
Вопрос 1. Проблема планирования деятельности фирмы.
Вопрос 2. Методы решения задач планирования в условиях полной определенности.
Вопрос 3. Принятие решений в условиях неопределенности.
Вопрос 4. Методы планирования в условиях риска.
Литература.
Вопросы для самопроверки:
Тема 3. Теория игр
Интернет-курс по дисциплине
«Методы принятия управленческих решений»

Вопрос 1. Решение матричных игр в чистых стратегиях.
Вопрос 2. Смешанные стратегии в матричных играх
Вопрос 3. Принятие решений в условиях неопределенности
Литература.
Вопросы для самопроверки:

Аннотация по дисциплине
Предметом изучения является система принятия управленческих решений компании.
Объектом изучения выступают количественные и иные методы принятия управленческих решений.
Место дисциплины в учебном процессе Университета
Настоящая дисциплина включена в учебные планы Университета по всем программам подготовки специалистов по специальности «Менеджмент». Дисциплина «Методы принятия управленческих решений» является необходимым элементом профессиональной подготовки менеджеров всех направлений специализации.
Для успешного освоения настоящего курса необходимо предварительно завершить изучение следующих дисциплин:
·
Макроэкономика;
·
Микроэкономика;
·
Управленческие решения;
·
Теория менеджмента.
Цель и задачи дисциплины.
Цельюизучения дисциплины является формирование у студентов теоретических знаний,
практических навыков по вопросам, касающимся принятия управленческих решений с использованием экономико-математических методов; применению математических методов в процессе подготовки и принятия управленческих решений в организационно-экономических и производственных системах, т.е. тех инструментов, с помощью которых в современных условиях формируются и анализируются варианты управленческих решений.
Прикладной задачейявляется изучение студентом следующих базовых вопросов:
·
обучение теории и практике принятия решений в современных условиях хозяйствования с использованием экономико-математических методов;
·
рассмотрение широкого круга задач, возникающих в практике менеджмента и связанных с принятием решений, относящихся ко всем областям и уровням управления;
·
обучение будущих специалистов теории и практике применения математических, т.е.
количественных методов для обоснования решений во всех областях целенаправленной деятельности.
В результате изучения курса студенты должны:
Знать:
·
основные математические методы и модели принятия решений;
·
области применения математических методов принятия решений;
·
содержательную сторону задач, возникающих в практике менеджмента и маркетинга,
т.е. уметь идентифицировать проблему.
Уметь:
·
пользоваться математическими методами принятия решений, с помощью которых в современных условиях формируются и анализируются варианты управленческих решений:
·
уточнять совместно с ЛПР постановку задачи,
·
собирать необходимую информацию,
·
строить математическую модель задачи,
·
интерпретировать полученные результаты и представлять их ЛПР,

·
выбирать метод принятия решений.
Иметь навык:
·
использования математических методов при решении специфических задач возникающих в процессе принятия решений;
·
применения информационных технологий в процессе моделирования и оптимизации управленческих решений.
Тема 1. Классификация методов принятия управленческих решений. Задачи линейного
программирования
Цели и задачи:
Цель изученияданной темы – получение общетеоретических знаний о методах принятия
УР.
Задачи изученияданной темы:
·
изучение классификации эвристических методов принятия решений;
·
изучение классификации количественных и качественных методов принятия решений.
·
изучение оптимизационных методов (ЗЛП)
Вопросы темы:
1.
Классификация методов принятия управленческих решений.
2.
Постановка задачи линейного программирования и свойства ее решений.
3.
Решение ЗЛП с помощью MS EXCEL.
Вопрос 1. Классификация методов принятия управленческих решений.
На сегодняшний момент существует очень большое количество методов принятия управленческих решений. Их можно разделить на три категории:
1.
Эвристические методы.
2.
Качественные методы.
3.
Формализованные методы.
Рассмотрим каждую категорию более подробно в разрезе базовых составляющих методов.
Эвристические методы принятия управленческих решений.
В литературе под эвристическими методами понимаются различные процедуры,
направленные на сокращение перебора вариантов. Эвристические методы увеличивают вероятность получения работоспособного, но не всегда оптимального решения той или иной задачи.
Ассоциативные методы.
Эти методы основываются на применение в творческом процессе семантических свойств понятий путем использования аналогии их вторичных смысловых оттенков. Основными источниками для генерирования новых идей служат ассоциации, метафоры и случайно выбранные понятия.
К ассоциативным методам относятся:
·
Метод каталога;
·
Метод фокальных объектов;
·
Метод гирлянд случайностей и ассоциаций.

Для разработки большего количества идей решения проблемы прибегают к метафорам.
Метафоры служат подсказкой для генерации идеи. Для расширения идей и повышения их оригинальности прибегают к гирляндам ассоциаций.
Если на объект исследования перенести свойства других объектов, резко возрастает число неожиданных альтернатив решений. Эта идея стала основой метода каталога, и усовершенствованного метода фокальных объектов. Дальнейшим развитием метода фокальных объектов стал метод гирлянд ассоциаций. Он помогает найти больше количество подсказок для новых идей путем образования ассоциаций.
Метод мозгового штурма.
Метод мозгового штурма (мозговой штурм, мозговая атака) — оперативный метод решения проблемы на основе стимулирования творческой активности, при котором участникам обсуждения предлагают высказывать как можно большее количество вариантов решения, в том числе самых фантастичных. Затем из общего числа высказанных идей отбирают наиболее удачные, которые могут быть использованы на практике.
Этапы и правила мозгового штурма.
Правильно организованный мозговой штурм включает три обязательных этапа. Этапы отличаются организацией и правилами их проведения:
·
Постановка проблемы. Предварительный этап. В начале этого этапа проблема должна быть четко сформулирована. Происходит отбор участников штурма, определение ведущего и распределение прочих ролей участников в зависимости от поставленной проблемы и выбранного способа проведения штурма.
·
Генерация идей. Основной этап, от которого во многом зависит успех всего мозгового штурма. Поэтому очень важно соблюдать правила для этого этапа:
1.
Главное — количество идей
. Не делайте никаких ограничений.
2.
Полный запрет на критику и любую (в том числе положительную) оценку высказываемых идей, так как оценка отвлекает от основной задачи и сбивает творческий настрой.
3.
Необычные и даже абсурдные идеи приветствуются. Комбинируйте и улучшайте любые идеи.
·
Группировка, отбор и оценка идей. Этот этап часто забывают, но именно он позволяет выделить наиболее ценные идеи и дать окончательный результат мозгового штурма. На этом этапе, в отличие от второго, оценка не ограничивается, а наоборот, приветствуется. Методы анализа и оценки идей могут быть очень разными. Успешность этого этапа напрямую зависит от того, насколько «одинаково» участники понимают критерии отбора и оценки идей.
Мозговые атаки.
Для проведения мозговой атаки обычно создают две группы:
·
участники, предлагающие новые варианты решения задачи;
·
члены комиссии, обрабатывающие предложенные решения.
Различают индивидуальные и коллективные мозговые атаки.
В мозговом штурме участвует коллектив из нескольких специалистов и ведущий
. Перед самим сеансом мозгового штурма ведущий производит четкую постановку задачи, подлежащей решению. В ходе мозгового штурма участники высказывают свои идеи, направленные на решение поставленной задачи, причём как логичные, так и абсурдные
. Если в мозговом штурме принимают участие люди различных чинов или рангов, то рекомендуется заслушивать идеи в

порядке возрастания ранжира, что позволяет исключить психологический фактор «соглашения с начальством».
В процессе мозгового штурма, как правило, вначале решения не отличаются высокой оригинальностью
, но по прошествии некоторого времени типовые, шаблонные решения исчерпываются, и у участников начинают возникать необычные идеи. Ведущий записывает или как-то иначе регистрирует все идеи, возникшие в ходе мозгового штурма.
Затем, когда все идеи высказаны, производится их анализ
, развитие и отбор
. В итоге находится максимально эффективное и часто нетривиальное решение задачи.
Успех мозгового штурма сильно зависит от психологической атмосферы и активности обсуждения, поэтому роль ведущего в мозговом штурме очень важна. Именно он может
«вывести из тупика» и вдохнуть свежие силы в процесс.
Изобретателем метода мозгового штурма считается
Алекс Осборн
, сотрудник рекламного агентства
BBD&O
. Одним из продолжений метода мозгового штурма является метод синектики
Метод синектики.
Синектика — методика психологической активизации творчества, предложенная В. Дж.
Гордоном. Является развитием и усовершенствованием метода мозгового штурма
. Д. Гордон разработал этот метод решения проблем, когда руководил группой исследования изобретений для Артура Д. Литтла. При синектическом штурме допустима критика, которая позволяет развивать и видоизменять высказанные идеи. Этот штурм ведет постоянная группа. Её члены постепенно привыкают к совместной работе, перестают бояться критики, не обижаются, когда кто-то отвергает их предложения.
В методе применены четыре вида аналогий — прямая, символическая, фантастическая,
личная.
Виды аналогий:
1.
При прямой аналогии рассматриваемый объект сравнивается с более или менее похожим аналогичным объектом в природе или технике. Например, для усовершенствования процесса окраски мебели применение прямой аналогии состоит в том, чтобы рассмотреть, как окрашены минералы, цветы, птицы и т. п. или как окрашивают бумагу, киноплёнки и т. п.
2.
Символическая аналогия требует в парадоксальной форме сформулировать фразу,
буквально в двух словах отражающую суть явления. Например, при решении задачи, связанной с мрамором, найдено словосочетание «радужное постоянство», так как отшлифованный мрамор
(кроме белого) — весь в ярких узорах, напоминающих радугу, но все эти узоры постоянны.
3.
При фантастической аналогии необходимо представить фантастические средства или персонажи, выполняющие то, что требуется по условиям задачи. Например, хотелось бы, чтобы дорога существовала там, где её касаются колёса автомобиля.
4.
Личная аналогия (эмпатия) позволяет представить себя тем предметом или частью предмета, о котором идёт речь в задаче. В примере с окраской мебели можно вообразить себя белой вороной, которая хочет окраситься. Или, если совершенствуется зубчатая передача, то представить себя шестерней, которая крутится вокруг своей оси, подставляя бока соседней шестерне. Нужно в буквальном смысле входить «в образ» этой шестерни, чтобы на себе почувствовать всё, что достаётся ей, и какие она испытывает неудобства или перегрузки. Что даёт такое перевоплощение? Оно значительно уменьшает инерцию мышления и позволяет рассматривать задачу с новой точки зрения.
Формализованные методы принятия решений.
Параметрический метод.
Метод заключается в выявлении и устранении физических противоречий, действующих в системе. Под физическим противоречием следует понимать – взаимоисключающие требования,
предъявляемые к элементу системы, причем один из характеризующих его параметров должен

иметь два альтернативных значения. При этом состояние элемента (движение) называется узловым параметром, а характеризуемый им элемент – узловым элементом.
Морфологический метод.
Суть морфологического метода заключается в следующем:
·
сначала мы определяем пространство поиска, которое обязательно должно включать в себя искомое решение (схему устройства);
·
затем сужаем это пространство, осуществляя поиск этого решения.
В процессе морфологического синтеза мы ищем структуру синтезируемого устройства,
проводя поиск на морфологическом множестве.
Балансовые методы.
Балансовые методы – совокупность приемов, позволяющих исследовать и прогнозировать развитие объектов путем сопоставления прихода и расхода вещества, энергии и других потоков.
В основе балансовых методов лежит баланс, оценивающий количественно движение потока в пределах анализируемого объекта.
Балансовый метод, сопоставление взаимосвязанных показателей хозяйственной деятельности с целью выяснения и измерения их взаимного влияния, а также подсчета резервов повышения эффективности производства.
Диаграмма Ганта.
Диаграмма Ганта представляет собой отрезки
(графические плашки), размещенные на горизонтальной шкале времени. Каждый отрезок соответствует отдельной задаче или подзадаче.
Задачи и подзадачи, составляющие план, размещаются по вертикали. Начало, конец и длина отрезка на шкале времени соответствуют началу, концу и длительности задачи. На некоторых диаграммах Ганта также показывается зависимость между задачами. Диаграмма может использоваться для представления текущего состояния выполнения работ: часть прямоугольника, отвечающего задаче, заштриховывается, отмечая процент выполнения задачи;
показывается вертикальная линия, отвечающая моменту «сегодня».
Иначе говоря, это популярный тип столбчатых диаграмм
, который используется для иллюстрации плана, графика работ по какому-либо проекту
Управление проектом – профессиональная деятельность по руководству ресурсами
(человеческими и материальными) путем применения методов, средств и управления для успешного достижения заранее поставленных целей в результате выполнения комплекса взаимосвязанных мероприятий при определенных требованиях к срокам, бюджету и характеристикам ожидаемых результатов проектов.
Метод анализа иерархии (МАИ).
МАИ – математический инструмент системного подхода к сложным проблемам принятия решений. МАИ не предписывает лицу, принимающему решение (ЛПР), какого-либо
«правильного» решения, а позволяет ему в интерактивном режиме найти такой вариант
(альтернативу), который наилучшим образом согласуется с его пониманием сути проблемы и требованиями к ее решению. МАИ позволяет понятным и рациональным образом структурировать сложную проблему принятия решений в виде иерархии, сравнить и выполнить количественную оценку альтернативных вариантов решения. Метод Анализа Иерархий используется во всем мире для принятия решений в разнообразных ситуациях: от управления на межгосударственном уровне до решения отраслевых и частных проблем в бизнесе,
промышленности, здравоохранении и образовании. Для компьютерной поддержки МАИ
существуют программные продукты, разработанные различными компаниями. Анализ

проблемы принятия решений в МАИ начинается с построения иерархической структуры,
которая включает цель, критерии, альтернативы и другие рассматриваемые факторы, влияющие на выбор. Эта структура отражает понимание проблемы лицом, принимающим решение.
Каждый элемент иерархии может представлять различные аспекты решаемой задачи, причем во внимание могут быть приняты как материальные, так и нематериальные факторы, измеряемые количественные параметры и качественные характеристики, объективные данные и субъективные экспертные оценки. Иными словами, анализ ситуации выбора решения в МАИ
напоминает процедуры и методы аргументации, которые используются на интуитивном уровне.
Следующим этапом анализа является определение приоритетов, представляющих относительную важность или предпочтительность элементов построенной иерархической структуры, с помощью процедуры парных сравнений. Безразмерные приоритеты позволяют обоснованно сравнивать разнородные факторы, что является отличительной особенностью
МАИ. На заключительном этапе анализа выполняется синтез (линейная свертка) приоритетов на иерархии, в результате которой вычисляются приоритеты альтернативных решений относительно главной цели. Лучшей считается альтернатива с максимальным значением приоритета.
Оптимизационные методы.
По типу математического аппарата различают условную и безусловную оптимизацию.
Условная оптимизация – это задачи линейного программирования (ЗЛП).
Линейное программирование – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума)
линейной функции многих переменных при наличии линейных ограничений, т.е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования приводится широкий круг вопросов планирования экономических и технико- экономических процессов, где ставится задача поиска наилучшего (оптимального) решения;
само возникновение и развитие линейного программирования непосредственно связано с экономической проблематикой.
Качественные методы.
Метод «Дельфи».
Суть этого метода в том, чтобы с помощью серии последовательных действий – опросов,
интервью, мозговых штурмов – добиться максимального консенсуса при определении правильного решения. Анализ с помощью дельфийского метода проводится в несколько этапов,
результаты обрабатываются статистическими методами.
Базовым принципом метода является то, что некоторое количество независимых экспертов лучше оценивает и предсказывает результат, чем структурированная группа личностей.
Позволяет избежать открытых столкновений между носителями противоположенных позиций т.к. исключает непосредственный контакт экспертов между собой и, следовательно, групповое влияние, возникающее при совместной работе и состоящее в приспособлении к мнению большинства. Даёт возможность проводить опрос экстерриториально, не собирая экспертов в одном месте (например, посредством электронной почты).
Метод «Дерева решений».
Дерево решений — это графическое изображение процесса принятия решений, в котором отражены альтернативные решения, альтернативные состояния среды, соответствующие вероятности и выигрыши для любых комбинаций альтернатив и состояний среды.
Метод «сценариев».

Метод сценариев получил очень большое распространение в современном мире.
Используется во всех отраслях экономики, как для открытия новых компаний, так и для синтеза действующих компаний. Наиболее часто можно увидеть применение данного метода при составлении различных прогнозов для финансово-хозяйствующего субъекта ( к примеру, при прогнозировании продаж ).
Как правило, данный метод подразумевает составление трех сценариев:
1.
Пессимистического.
2.
Реального.
3.
Оптимистического.
Вопрос 2. Постановка задачи линейного программирования и свойства ее решений.
Линейное программирование
— раздел математического программирования,
применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП).
Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.
Формы записи задачи линейного программирования:
Общей задачей линейного программирования называют задачу
(1)
при ограничениях
(2)
(3)
(4)
(5)
– произвольные
(6)
где
– заданные действительные числа; (1) – целевая функция; (1) – (6) –
ограничения;
– план задачи.
Пусть ЗЛП представлена в следующей записи:
(7)
(8)
(9)

Чтобы задача (7) – (8) имела решение, системе её ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай вообще невозможен. При система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть
. В
этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более
.
Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные переменных будут
свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов
. Этому базису соответствуют базисные переменные
, а свободными будут переменные
Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным
решением (планом).
Теорема. Если система векторов содержит m линейно независимых векторов
, то допустимый план
(10)
является крайней точкой многогранника планов.
Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.
Графический способ решения ЗЛП.
Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства ОЗЛП,
приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации.
Пусть дана задача
(11)
(12)
(13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений
(12), (13) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством.
Отсюда следует, что область допустимых решений задачи (11) — (13) есть выпуклое множество.
Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник
Рис. 1
Выберем произвольное значение целевой функции
. Получим
. Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение
. Считая в равенстве (11) параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).
Найдём частные производные целевой функции по и :
, (14)
. (15)
Частная производная (14) (так же как и (15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и
— скорости возрастания соответственно вдоль осей и
. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:
Вектор указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.
Вектор перпендикулярен к прямым семейства
Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.
1.
С учетом системы ограничений строим область допустимых решений .
2.
Строим вектор наискорейшего возрастания целевой функции — вектор градиентного направления.
3.
Проводим произвольную линию уровня
.

4.
При решении задачи на максимум перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении
(крайней точке). В случае решения задачи на минимум линию уровня перемещают в антиградиентном направлении.
5.
Определяем оптимальный план и экстремальное значение целевой функции
Симплексный метод решение ЗЛП.
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:
1)
умение находить начальный опорный план;
2)
наличие признака оптимальности опорного плана;
3)
умение переходить к нехудшему опорному плану.
Пусть ЗЛП представлена системой ограничений в каноническом виде:
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства – с коэффициентом,
равным нулю.
Пусть система ограничений имеет вид
Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные
. Получим систему, эквивалентную исходной:
,
которая имеет предпочтительный вид
В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю
Пусть далее система ограничений имеет вид

Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему
Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть (при
) с коэффициентами, равными
–1. Поэтому, вообще говоря, базисный план не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом – М для задачи на максимум, где М – большое положительное число. Полученная задача называется М-задачей, соответствующей исходной.
Она всегда имеет предпочтительный вид.
Пусть исходная ЗЛП имеет вид
, (16)
, (17)
, (18)
причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:
(19)
(20)
(21)
Задача (19) – (21) имеет предпочтительный план. Её начальный опорный план имеет вид
Если некоторые из уравнений (17) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.
Теорема. Если в оптимальном плане
(22)

М-задачи (19) – (21) все искусственные переменные
, то план является оптимальным планом исходной задачи (16) – (18).
Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида,
вводят искусственный базис и решают расширенную М – задачу, которая имеет начальный опорный план
Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом.
Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные
, то его первые n
компоненты дают оптимальный план исходной задачи.
Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
Признаки оптимальности.
Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален.
Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки не положительны, то такой план оптимален.
Рассмотрим классические примеры ЗЛП.
Задача о смесях.
В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д. Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы.
Пример. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов.
Содержание в 1 кг. каждого вида комбикорма жиров, белков и углеводов (граммы) приведено в таблице 1:
Таблица 1.
Содержание жиров, белков и углеводов (граммы) в 1 кг. каждого вида комбикорма
Содержание в 1 кг.
Комбикорм
А
В
С
Жиры
320 240 300
Белки
170 130 110

Углеводы
380 440 450
Стоимость 1 кг
31 23 20
Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость?
Математическая модель задачи есть:
– количество комбикорма А, В и С. Стоимость смеси есть:
Ограничения на количество ингредиентов:
Задача о раскрое материалов.
Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.
Рассматривается простейшая модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.
Задача о назначениях.
Речь идет о задаче распределения заказа (загрузки взаимозаменяемых групп оборудования) между предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа (загрузки оборудования), при котором с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности достигал экстремального значения.
Пример. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке (табл. 2).
Таблица 2.
Процент брака каждого рабочего на каждом станке
Рабочие
Станки
С1
С2
С3
С4
Р1 2,3 1,9 2,2 2,7
Р2 1,8 2,2 2,0 1,8
Р3 2,5 2,0 2,2 3,0
Р4 2,0 2,4 2,4 2,8
Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака
(который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот

процент?
Обозначим за
– переменные, которые принимают значения 1,
если i-й рабочий работает на j-м станке. Если данное условие не выполняется,
. Целевая функция есть:
Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть
Кроме того, каждый станок обслуживает только один рабочий:
Кроме того, все переменные должны быть целыми и неотрицательными:
Транспортная задача.
Математическая модель задачи.
Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m
складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j
получает единицу продукции (по прямой дороге) со склада i, то возникают издержки С
ij
Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы
Далее, предполагается, что где есть количество продукции, находящееся на складе i, и
– потребность потребителя
. Такая транспортная задача называется закрытой. Однако, если данное равенство не выполняется, то получаем открытую транспортную задачу, которая сводится к закрытой по следующим правилам:
1.
Если сумма запасов в пунктах отправления превышает сумму поданных заявок то количество продукции, равное остается на складах. В этом случае мы введем «фиктивного» потребителя с потребностью и положим транспортные расходы равными 0 для всех i.

2.
Если сумма поданных заявок превышает наличные запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m+1 с запасом и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.
Математическая модель транспортной задачи имеет вид:
где количество продукции, поставляемое со склада i потребителю j, а издержки
(стоимость перевозок со склада i потребителю j).
Рассмотрим пример:
Пример. Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и
600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона, дали заказ на поставку соответственно 300, 600, 650 и 750 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:
Таблица 3.
Карьер
Строительный объект
1
2
3
4
1
8 4
1 7
2
3 6
7 3
3
6 5
11 8
Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.
Данная транспортная задача является закрытой, так как запасы поставщиков равны спросу потребителей
. Математическая модель ЗЛП в данном случае имеет вид:
– количество щебенки, перевозимой с i–го карьера на j–й объект.
Тогда целевая функция равна
Ограничения имеют вид

Вопрос 3. Решение ЗЛП с помощью MS EXCEL.
Для решения задач оптимизации в MS Excel используют надстройку Поиск решения,
которая вызывается из пункта главного меню «Сервис»(рис. 2).
Рис. 2
Если в версии Excel, установленной на Вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения» (рис. 3).

Рис. 3.
Рассмотрим на примере использование данной надстройки. Решим с её помощью задачу.
Математическая модель задачи имеет вид:
(целевая функция)
при
Составим шаблон в редакторе Excel, как показано на рис. 4.
Рис. 4. Шаблон оформления задачи
Теперь занесём данную в задаче числовую информацию (рис. 5).

Рис. 5. Исходные данные задачи
В выделенные пустые ячейки (значения целевой функции и левых частей неравенств)
необходимо занести формулы, отображающие связи и отношения между числами на рабочем листе.
Ячейки B4 – С4 называются в Excel изменяемыми (в нашей модели это неизвестные переменные), т.е., изменяя их Поиск решения будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).
Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных.
Действительно, выражение можно рассматривать как произведение вектора (3,2) на вектор (Х
1
,Х
2
).
В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку Е4 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это В5:С5) и ячеек, в которые в результате решения будут помещены значения и
(ячейки В4:С4) (рис. 6).

Рис. 6. Вызов функции СУММПРОИЗВ
Каждая левая часть ограничения тоже представляет собой произведение двух векторов:
соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение
(для первого ограничения
) будем рассматривать как произведение вектора коэффициентов (1,2) и вектора переменных (
).
В ячейке, отведенной для формулы левой части первого ограничения (D9), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов В9:С9 и адрес значений переменных В4:С4 (рис. 7).
Рис. 7
В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы,
используя соответствующую строку матрицы затрат. Фрагмент экрана с введёнными формулами показан на рис. 8.
Рис. 8

Важно! К моменту вызова сервиса «Поиск решения» на рабочем листе с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой
функции.
В меню Сервис выбираем Поиск решения. В появившемся окне задаём следующую информацию:
1)
в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции
Е4;
2)
«флажок» устанавливаем на вариант «максимальному значению», т.к. в данном случае,
целевая функция дохода подлежит максимизации;
3)
в качестве изменяемых ячеек заносится адрес строки значений переменных В4:С4;
4)
справа от окна, предназначенного для занесения ограничений, нажимаем кнопку
«Добавить», появится форма для занесения ограничения (рис. 9)
Рис. 9. Форма для занесения одного ограничения ЗЛП
1)
в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения D9, выбирается требуемый знак неравенства (в нашем случае,
), в поле
«Ограничение» заносится ссылка на правую часть ограничения F9 (рис. 10).
Рис. 10. Занесение первого ограничения задачи
2)
аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».
Таким образом, окно «Поиск решения» с занесенной информацией выглядит следующим образом (рис. 11):

Рис. 11
Далее необходимо нажать кнопку Параметры, установить «флажки» «Линейная
модель» и «Неотрицательные значения», поскольку в данном случае задача является ЗЛП, а ограничение 6) требует неотрицательности значений (рис. 12).
Рис. 12. Установка параметров
Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения (рис. 13).
Рис. 13. Окно результата решения
Если в результате всех действий получено окно с сообщением «Решение найдено», то Вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение,
нажав «ОК». В результате получено решение задачи из примера 1. (рис. 14).

Рис. 14. Результат применения «Поиска решения»
Если в результате решения задачи выдано окно с сообщением о невозможности нахождения решения (рис. 15), это означает, что при оформлении задачи была допущена ошибка
(не заполнены формулы для ограничений, неправильно установлен «флажок» максимизации/
минимизации и т.д.).
Рис. 15. Сообщение об ошибке
В данном разделе рассмотрен общий формат решения задач оптимизации в Excel. В
зависимости от экономических моделей, выполняют его соответствующие модификации.
Литература.
Основная литература:
1.
Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в
Волшебных странах: Учебник. – М.: Логос, 2008. – 392 с.
2.
Литвак Б.Г. Управленческие решения. – М.: Дело, 2008. – 254 с.
3.
Смирнов Э.А. Разработка управленческих решений. – М.: ИНФРА-М, 2008. – 272 с.
4.
Фатхутдинов Р.А. Разработка управленческого решения: Учеб. пособ. – М.: Бизнес- школа, Интел-Синтез, 2007. – 272 с.
Дополнительная литература:
1.
Андрейчиков А.В., Андрейчикова О.Н. Анализ, синтез, принятие решений в экономике
– М.: Финансы и статистика, 2007. – 368с.
2.
Трахтенгерц Э.А. Компьютерная поддержка принятия решений: Научно-практическое издание. – М.: СИНТЕГ, 1998. – 376 с.
3.
Варфоломеев В.И., Воробьев С.Н. Принятие управленческих решений: Учеб пособие для вузов. – М.: КУДИЦ-ОБРАЗ, 2007. – 288 с.

4.
Плис А.И., Сливина Н.А. Mathcad 2000. Математический практикум для экономистов и инженеров: Учеб. пособие. – М.: Финансы и статистика, 2007. – 656 с.
5.
Ашихмин А.А. Разработка и принятие управленческих решений: формальные модели и методы выбора. – М.: МГТУ, 2005.
6.
Вентцель Е.С. Исследование операция. – М.: Советское радио, 1972.
7.
Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985.
8.
Горелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. – М.: Радио и связь, 1982/
9.
Давыдов Э.Г. Исследование операций. – М.: Высшая школа, 1990.
10.
Лапшин К.А., Светлов Н.М. Прогграммный комплекс «Линейная оптимизация» –
методические указания для студентов экономического факультета. – М.: МСХА, 1994.
11.
Лесик, А. И., Чистяков, Ю. Е. Теоретико-игровые модели взаимодействия экономических субъектов производственной системы. – М. : ВЦ РАН, 1994.
12.
Мулен Э. Теория игр с примерами из математической экономики. – М.: Мир, 1985.
13.
Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.: Высшая школа, 1998.
14.
Платов В.Я. Деловые игры: разработка, организация, проведение. – М.: Профиздат,
1991.
15.
Сысоев, В. В. Теоретико-игровые модели принятия решений многоцелевого управления в задачах выбора и распределения ресурсов / Воронеж : Воронеж. гос. технол. акад.,
2000.
16.
Giblons R. Game theory for applied economists. Princeton University press, Princeton, New
Gersey, 1992.