Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Исследование операций. Курс лекций с примерами решения задач - файл 1.doc


Лекции - Исследование операций. Курс лекций с примерами решения задач
скачать (1662 kb.)

Доступные файлы (1):

1.doc1662kb.23.11.2011 02:48скачать

содержание
Загрузка...

1.doc

  1   2   3   4   5   6   7   8
Реклама MarketGid:
Загрузка...






ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ«МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

ИНСТИТУТ ДИСТАНЦИОННОГО ОБУЧЕНИЯ

Яретенко Н. И.

Математика (Исследование операций)
Курс лекций

для направления подготовки (специальности)

230105.65 «Прикладная информатика (Программное обеспечение ВТ и АС)»,

080801.65«Прикладная информатика (в экономике)»,080507.65 «Менеджмент организации»,080105.65 «Финансы и кредит», 080109.65 «Бухгалтерский учет, анализ и аудит».


(C применением элементов дистанционного обучения )

Мурманск

2010 г.
Автор - Н.И. Яретенко,

к. воен. наук, доцент

кафедры Информационных систем и

прикладной математики МГТУ.
Курс лекций

рассмотрен

и одобрен кафедрой ИС и ПМ

«__» _______ 2010 г.

Рецензенты:

В.В. Ковальчук,

д.т.н., профессор, зав.кафедрой

ИС и ПМ МГТУ.

Н. Н. Морозов зав. кафедрой

Физики МГТУ.


ОГЛАВЛЕНИЕ


  1. Лекция. Основы теории принятия решений




    1. Общие положения………………………………………………………….6

    2. Основные понятия системного анализа…………………………………..8

    3. Основные понятия исследования операций…………………………….12

    4. Постановка задач принятия оптимальных решений……………………13

    5. Методология и методы принятия решений………………………………15

Контрольные вопросы………………………………………………...17
2. Лекция. Экономико – математическое моделирование

2.1.Основные понятия.............................................................................18

2.2.Классификация моделей....................................................................19

2.3.Классификация решаемых экономических задач...............................21

Контрольные вопросы....................................................................22

3.Лекция. Линейное программирование

3.1.Общая постановка задачи..................................................................23

3.2. Двойственность в задачах линейного программирования……………25

3.3.Теоремы двойственности...................................................................26

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

методом................................................................................................28

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

Контрольные вопросы..................................................................39

4.Лекция .Транспортная задача

4.1.Постановка задачи..............................................................................41

4.2.Алгоритм решения транспортных задач………………………….………42

4.3.Метод наименьшего элемента..............................................................43

4.5.Метод потенциалов.............................................................................44

4.6.Примеры решения транспортных задач................................................45

Контрольные вопросы..................................................................55
5 .Лекция .Целочисленное программирование

5.1.Постановка задачи целочисленного программирования........................57

5.2.Графический метод решения задач целочисленного программирования.....................................................................................58

5.3.Пример решения задачи целочисленного программирования…………..59

5.4.Задача о коммивояжере……………………………………………………..61

5.5.Пример решения задачи о коммивояжере…………………………………62

Контрольные вопросы...................................................... .....64
6. Лекция. Динамическое программирование

6.1. Постановка задачи............................................................................65

6.2.Принцип оптимальности Беллмана....................................................66

6.3.Задача распределения средств на 1 год…………………………………67

6.4. Задача распределения средств на 2 года............................... ……….72

Контрольные вопросы........................................................72
7. Лекция. Управление производством

7.1.Задача о замене оборудования …………………………………………73

7.2 Управление запасами. Складская задача ……………………………….79

Контрольные вопросы ..........................................................81

8. Лекция. Теория игр

8.1.Основные понятия………………………………………………………..82

8.2.Антагонистические игры ………………………………………………..83

8.3.Игры с «природой»...........................................................................85

Контрольные вопросы………………………………………….93

9.Лекция. Системы массового облуживания

9.1.Формулировка задачи и характеристики СМО………………………..94

9.2.СМО с отказами…………………………………………………………..96

9.3.СМО с неограниченным ожиданием.................................................96

9.4. СМО с ожиданием и с ограниченной длиной очереди……………….97

9.5. Примеры решения задач...................................................................98

Контрольные вопросы……………………………………….…..101
10. Лекция . Сетевое планирование

10.1. Основные понятия метода сетевого планирования.........................101

10.2. Расчет сетевых графиков................................................................105

Контрольные вопросы………………………………………...…109
11. Лекция. Нелинейное программирование

11.1. Основные понятия……………………………………………………..109

11.2. Безусловный экстремум …………………………………..………….109

11.3. Условный экстремум …………………………………………………111

Контрольные вопросы................................................................112
Перечень задач для решения при усвоении материала………………….112

Литература...............................................................................128
Вопросы для самопроверки………………………………….………….129
Приложение: Греческий алфавит……………………………….…131

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

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

Одним из первых исследований является работа Л. В. Канторовича ,, Математические методы организации и планирования производства ,, , вышедшая в 1939 г., а в зарубежной литературе – вышедшая в 1947 г. работа Дж. Данцинга , посвященная решению экстремальных линейных задач. В 1975 г. Л. В. Канторович стал лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике.

50-е и последующие годы были отмечены широким применением в практику полученных фундаментальных теоретических исследований и связанных с этим переосмыслением потенциальных возможностей теории исследования операций. Важный вклад в развитие новой науки также внесли такие видные ученные, как Дж. Фон. Нейман, Д. Гейл, К. Эрроу, Р. Беллман, Р. Гомори, Е. С. Вентцель, М. К. Гавурин и др .ученные.

Курс лекций разработан на основании рабочих программ для направления подготовки (специальности) 230105.65 «Прикладная информатика (Программное обеспечение ВТ и АС)»,080801.65«Прикладная информатика (в экономике)»,080507.65 «Менеджмент о рганизации»,080105.65 «Финансы и кредит», 080109.65 «Бухгалтерский учет, анализ и аудит».

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

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


1 Лекция. Основы теории принятия решений.
1.1. Общие положения

1.2. Основные понятия системного анализа

1.3. Основные понятия исследования операций

1.4. Постановка задач принятия оптимальных решений

1.5. Методология и методы принятия решений.


    1. Общие положения


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

В XVIII веке началом науки "Теория принятия решений" следует считать работу Жозефа Луи Лагранжа, смысл которой заключался в следующем:

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

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

Научно-техническими предпосылками становления "Теории принятия решений" являются:

  • удорожание "цены ошибки". Чем сложнее, дороже, масштабнее планируемое мероприятие, тем менее допустимы в нем "волевые" решения и тем важнее становятся научные методы, позволяющие заранее оценить последствия каждого решения, заранее исключить недопустимые варианты и рекомендовать наиболее удачные;

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

  • развитие ЭВМ. Размерность и сложность реальных инженерных задач не позволяло использовать аналитические метода.


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



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

  • кибернетика, которая рассматривается как наука об управлении и преобразовании информации.


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

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

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


  • постановку задачи для принятия решения;

  • описание множества альтернатив;

  • исследование многокритериальных задач;

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

  • обработку экспертных оценок;

  • работу с макромоделями системы.





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

  • методологию;

  • аппаратную реализацию;

  • практические приложения.

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

  • связями, которые позволяют посредством переходов по ним от элемента к элементу соединить два любых элемента совокупности;

  • свойством, отличным от свойств отдельных элементов совокупности.

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

В качестве примера можно привести мост с пролетами и опорами.

.

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

  • в виде технических средств;

  • в виде действия человека.

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

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

Указанное расчленение может иметь материальную, функциональную, алгоритмическую или другую основу.

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

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

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

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

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


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


  • принцип конечной цели: абсолютный приоритет конечной цели;

  • принцип единства: совместное рассмотрение системы как целого и как совокупности элементов;

  • принцип связности: рассмотрение любой части совместно с ее связями с окружением;

  • принцип модульного построения: полезно выделение модулей в системе и рассмотрение ее как совокупности модулей;

  • принцип иерархии: полезно введение иерархии элементов и(или) их ранжирование;

  • принцип функциональности: совместное рассмотрение структуры и функции с приоритетом функции над структурой;

  • принцип развития: учет изменяемости системы, ее способности к развитию, расширению, замене частей, накапливанию информации;

  • принцип децентрализации: сочетание в принимаемых решениях и управлении централизации и децентрализации;

  • принцип неопределенности: учет неопределенностей и случайностей в системе.



^ Аппаратная реализация включает стандартные приемы моделирования принятия решения в сложной системе и общие способы работы с этими моделями. Модель строится в виде связных множеств отдельных процедур.
Системный анализ исследует как организацию таких множеств, так и вид отдельных процедур, которые максимально приспосабливают для принятия согласующихся и управленческих решений в сложной системе.
Модель принятия решения чаще всего изображается в виде схемы с ячейками, связями между ячейками и логическими переходами. Ячейки содержат конкретные действия - процедуры. Совместное изучение процедур и их организации вытекает из того, что без учета содержания и особенностей ячеек создание схем оказывается невозможным. Эти схемы определяют стратегию принятия решения в сложной системе.
Именно с проработки связанного множества основных процедур принято начинать решение конкретной прикладной задачи.
Отдельные же процедуры (операции) принято классифицировать на формализуемые и неформализуемые.
В отличие от большинства научных дисциплин, стремящихся к формализации, системный анализ допускает, что в определенных ситуациях неформализуемые решения, принимаемые человеком, являются более предпочтительными.
Системный анализ рассматривает в совокупности формализуемые и неформализуемые процедуры и одной из его задач является определение их оптимального соотношения.
Формализуемые стороны отдельных операций лежат в области прикладной математики и использования ЭВМ.
В ряде случаев математическими методами исследуется связное множество процедур и производится само моделирование принятие решения
. В этом и состоит математическая основа системного анализа.
Такие области прикладной математики, как исследование операций и системное программирование, наиболее близки к системной постановке вопросов.

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


^ 1.3. Основные понятия исследования операций


Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.
^ Цель исследования операций - предварительное количественное обоснование оптимальных решений.
Решение- Всякий определенный выбор зависящих от нас параметров.
Оптимальным называется решение, по тем или другим признакам предпочтительнее перед другими.
^ Элементы решения- параметры, совокупность которых образует решение.
Множеством допустимых решений называются заданные условия, которые фиксированы и не могут быть нарушены.
^ Показатель эффективности - количественная мера, позволяющая сравнивать по эффективности разные решения.
Все решения принимаются всегда на основе информации, которой располагает лицо принимающее решение (ЛПР).
Каждая задача в своей постановке должна отражать структуру и динамику знаний ЛПР о множестве допустимых решений и о показателе эффективности.
^ Задача называется статической, если принятие решения происходит в наперед известном и не изменяющемся информационном состоянии.
Задача называется динамической - если информационные состояния в ходе принятия решения сменяют друг.
^ Информационные состояния ЛПР могут по-разному характеризовать его физическое состояние:

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

  • Если информационное состояние содержит несколько физических состояний и ЛПР кроме их множества знает еще и вероятности каждого из этих физических состояний, то задача называется стохастической (частично неопределенной).

  • Если информационное состояние содержит несколько физических состояний, но ЛПР кроме их множества ничего не знает о вероятности каждого из этих физических состояний, то задача называется неопределенной.


^ 1.4. Постановка задач для принятия

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

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

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

  • Обычно выбираются показатели экономического (издержки, прибыль и т.д.) или технологического (производительность, энергоемкость, материалоемкость и т.д.) характера. "Наилучшему" варианту всегда соответствует экстремальное значение показателя эффективности функционирования системы;

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

  • построение модели, которая описывает взаимосвязи между переменными задачи и отражает влияние независимых переменных на значение показателя эффективности.

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

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

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



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


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


Все оптимизационные задачи имеют общую структуру. Их можно классифицировать как задачи минимизации(максимизации) M-векторного векторного показателя эффективности Wm(x), m=1,2,...,M, N-мерного векторного аргумента x=(x1,x2,...,xN), компоненты которого удовлетворяют системе ограничений-равенств hk(x)=0, k=1,2...K, ограничений-неравенств gj(x)>0, j=1,2,...J, областным ограничениям xli<xi<xui, i=1,2...N.


Все задачи принятия оптимальных решений можно классифицировать в соответствии с видом функций и размерностью Wm(x), hk(x), gj(x) и размерностью и содержанием вектора x:

  • одноцелевое принятие решений - Wm(x) - скаляр;

  • многоцелевое принятие решений - Wm(x) - вектор;

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

  • принятие решений в условиях неопределенности - исходные данные - случайные.

Наиболее разработан и широко используется на практике аппарат одноцелевого принятия решений в условиях определенности, который получил название математического программирования.
Более подробно будут рассмотрены задачи линейного программирования (W(x), hk(x), gj(x) - линейны), нелинейного программирования (W(x), hk(x), gj(x) - нелинейны), целочисленного программирования (x - целочисленны), динамического программирования (x - зависят от временного фактора),математический аппарат одноцелевого принятия решений в условиях неопределенности, , т. е. стохастическое программирование (известны законы распределения случайных величин), теорию игр и статистических решений (закон распределения случайных величин неизвестен).


^

1.5 Методология и методы

принятия решений.


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

Метод - способ, прием выполнения тех или иных действий.

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

 - неформальные (эвристические);

 - коллективные;

 - количественные.

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

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

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

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

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

Решения принимаются руководителем на основе экспертных оценок с помощью одного из следующих принципов:

 - принципа большинства голосов;

 - принципа диктатора - за основу берется мнение одного лица группы;

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

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

 - линейное моделирование (используются линейные зависимости);

 - динамическое программирование (позволяет вводить дополнительные переменные в процессе решения задач);

 - вероятностные и статистические модели (реализуются в методах теории массового обслуживания);

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

 - имитационные модели (позволяют экспериментально проверить реализацию решений, изменить исходные предпосылки
Контрольные вопросы.

  1. Что означает понятие «системный анализ»?

  2. Определения системного анализа ?

  3. Сформулируйте принципы системного подхода.

  4. Раскройте основные понятия исследования операций.

  5. Какая последовательность действий процесса постановки задачи ?

6. Какие методы принятия решений вы знаете ?


^ 2.Лекция. Экономико - математическое моделирование
2.1 Основные понятия.

Слово «модель» (от латинского слова «modulus») означает меру, мерильный образец, норму. Под моделью понимается либо некий образ объекта, интересующего нас, либо прообраз некоторого объекта или системы объектов.

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

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

Применяемые в разных областях человеческой деятельности модели можно классифицировать по разным признакам:

-по характеру моделируемых объектов

-по сферам приложения

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

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

ОПРЕДЕЛЕНИЯ
Операция – всякое мероприятие (система действий), объединенное единым замыслом и направленное на достижение определенной цели.

^ Решение – определенный выбор зависящих от нас параметров.

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

^ Оптимальные решения – решение, которое по тем или иным признаком предпочтительнее других.

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


^ 2. 2 Классификация моделей

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

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

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

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

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

^ Равновесные модели описывают такие состояния экономики , когда результирующая всей воздействий на нее равна нулю. Как правило, равновесные модели являются описательными.

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

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

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

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

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

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

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

Предназначение модели состоит в том, что она является инструментом обработки информации.
^ 2. 3 Классификация решаемых экономических задач.

По уровню информации о ситуации:

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

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

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

По виду информации о ситуации :

1.Статический вид – информация о ситуации не меняется во времени и известна заранее.

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

По виду критерия оптимальности :

1.Однокритериальные задачи

2.Монокритериальные задачи
По типу критерия оптимальности:

  1. Линейные задачи

  2. Нелинейные задачи



По типу области ограничения:

  1. Выпуклая область

  2. Целочисленная область

  3. Булева область

Контрольные вопросы.

  1. Что означает понятие «экономическая модель»?

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

  3. Классификация решаемых экономических задач.

  4. Какое решение является оптимальным?

  5. Дать определение показателя эффективности.


^ 3.Лекция . Линейное программирование.
3.1 Общая постановка задачи

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

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

Математическое выражение целевой функ­ции и ее ограничений называется математической моделью экономической задачи.

В общем виде математическая модель задачи линейного программирования (ЛП) записывается как
Z(x)=C1X1+C2X2 + . . . JXJ + . . . nXn _ max(min)

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

где Xi — неизвестные;a ij , bj , Ci — заданные постоянные вели­чины.
Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.

Математическая модель в более краткой записи имеет вид



Z(x) = ∑Ci Xi max(min)

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

Определение Допустимым решением (планом) зада­чи линейного программирования называется вектор X = (х1, х2, ,...хn , ) , удовлетворяющий системе ограничений.
Множество допустимых решений образует область допус­тимых решений (ОДР).
Определение Допустимое решение, при котором целевая функция достигает своего экстремального значения, называ­ется оптимальным решением задачи линейного программиро­вания и обозначается Хопт.

Базисное допустимое решение

Является опорным решением, где r— ранг системы ограничений.


^ Виды математических моделей ЛП
Математическая модель задачи ЛП может быть каноничес­кой и неканонической.
Определение . Если все ограничения системы заданы урав­нениями и переменные Xj неотрицательные, то такая модель задачи называется канонической.

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

неравенство ввести балансовую переменную хn+i .
Если знак неравенства < , то балансовая переменная вводится со знаком плюс, если знак неравенства >, то — минус. В целевую функ­цию балансовые переменные не вводятся.
Чтобы составить математическую модель задачи ЛП, не­обходимо:

— ввести обозначения переменных;

— исходя из цели экономических исследований, составить целевую функцию;

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

^ 3. 2 Двойственность в задачах линейного программирования
Каждая задача линейного программирования, называемая прямой или исходной, тесно связана с другой задачей, ее называют двойственной.

Математические модели этих задач имеют следующий вид.


прямая задача:



двойственная задача:





Эти задачи экономически могут быть сформулированы следующим образом.
^ Прямая задача: сколько и какой продукции хi(i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции Сi, объемом имеющихся ресурсов bj (j=1,2,…, m) и нормах расхода ресурсов аij максимизировать выпуск продукции в стоимостном виде.

Двойственная задача: какова должна быть оценка единицы каждого ресурса yj (j=1, 2,…, m), чтобы при заданных bj, ci и аij минимизировать общую оценку затрат на все ресурсы.

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

  1. Если прямая задача решается на максимум, то двойственная задача решается на минимум; если прямая задача решается на минимум то двойственная на максимум;

  2. В задаче на максимум ограничения неравенства имеют вид – ≤, а в задаче на минимум – ;

  3. Каждому ограничению прямой задачи соответствует переменная двойственной задачи, в другой модели ограничению двойственной задачи соответствует переменная прямой задачи;

  4. Матрица системы ограничений двойственной задачей получается из матрицы из матрицы систем ограничений прямой задачи транспонированием;

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

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

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



Пример:

Прямая задача:



Двойственная задача:



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

Взаимосвязь решений прямой и двойственной задач находится из трех теорем двойственности.

^ 3. 3 Теоремы двойственности.
Первая теорема двойственности:
Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций совпадают Z(X)=Z'(Y). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание первой теоремы двойственности: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения и оценок ресурсов, при этом полная стоимость продукта, полученного в результате реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадения, значений целевых функций для соответствующих решений пары двойственных задач достаточно для того, чтобы эти решения были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными только тогда, когда полная стоимость произведенной продукции и суммарная оценка ресурсов совпадает.


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

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

если  0, то .

Аналогично,

если

если 0 то
Экономически это означает, что если по некоторому оптимальному плану X*= производства расход j-го ресурса меньше его запаса bj, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е. полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.


^ Третья теорема двойственности:

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


В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:

,

если , тогда , Экономическое содержание третьей теоремы двойственности: двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки yj часто называются скрытыми теневыми или маргинальными оценками ресурсов.
3.4 Решение задач линейного программирования

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

Этот вектор показывает направление наискорейшего изменения целевой функции. Координатами вектора grandZ являются коэффициенты целевой функции Z(x).


^ Алгоритм геометрического метода решения задач ЛП.
Решение задач ЛП геометрическим методом осуществляется по следующему алгоритму:
1.Строим координатные оси Х1ОХ2 и с учетом коэффициентов математической модели выбираем масштаб.
2.Находим область допустимых решений (ОДР) системы ограничений математической модели.
3.Строим прямую целевой функции и показываем направление наискорейшего ее изменения (нормаль-gradL).
4.Линию целевой функции (линия уровня) перемещаем по направлению нормали для задач на максимум целевой функции и в противоположном направлении - для задач на минимум ЦФ.
Перемещение линии уровня через ОДР производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений. Эта точка будет точкой экстремума, и будет определять единственное решение задачи ЛП.
Если окажется, что линия уровня совпадает с одной из сторон ОДР , то задача ЛП будет иметь бесчисленное множество решений.
Если ОДР представляет неограниченную область, то целевая функция – неограниченна.
Задача ЛП может быть неразрешима ,когда определяющие ее ограничения окажутся противоречивыми.

5.Находим координаты точки экстремума и значение ЦФ в ней.

^ Рассмотрим задачу.

Торговая фирма для продажи товара трех видов использует ресурсы: время и площадь торговых залов. Затраты ресурсов на продажу одной партии товаров каждого вида даны в таблице. Прибыль получаемая от реализации одной парии товаров 1 вида – 5 у.е. 2 вида – 8 у.е.



Ресурсы

Вид товара

Объем ресурсов

1

2

Время

0,5

0,7

370

Площадь

0,1

0,3

90



Определить оптимальную структуру товарооборота, обеспечивающую фирме максимальную прибыль.

Решение задачи.
Математическая модель прямой задачи

Max Z= 5x1+8x2

0,5 x1+0,7x2  370

0,1 x1+0,3x2  90

x1,2  0
Математическая модель двойственной задачи

Min Z’= 370y1+90y2

0,5y1+0,1y2  5

0,7у1+0,3у2  8

y1,2  0
Разберем экономический смысл переменных, входящих в модели и ограничений, составленных на основе условия задачи.

x1 – количество товара первого вида, которое необходимо продавать согласно оптимальному плану.

х2 – количество товара второго вида, которое необходимо продавать согласно оптимальному плану.

0,5 x1+0,7x2 – это условие показывает, сколько времени всего будет потрачено на продажу товаров первого и второго вида.

0,1 x1+0,3x2 – это условие показывает, сколько площади будет потрачено на продажу товаров первого и второго вида.

5x1+8x2 – выручка, полученная при продаже оптимального количества товаров первого и второго вида.

у1 – цена одной единицы первого ресурса (1 часа работы продавца)

у2 – цена одной единицы второго ресурса (1 м2 площади торгового зала).

0,5y1+0,1y2 – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого вида.

0,7у1+0,3у2 это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий второго вида.

370y1+90y2 – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого и второго вида.
Непосредственное решение состоит из построения нескольких прямых на плоскости XOY. Построение неравенств на плоскости состоит из построения соответствующих прямых и выбора нужной полуплоскости. Для выбора полуплоскости необходимо подставить какую-нибудь точку плоскости (чаще всего точку (0,0)) в соответствующее неравенство и о выполнении или невыполнении этого неравенства сделать вывод о том, какая именно полуплоскость соответствует неравенству.


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



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



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



Решая эту систему, получаем, что для получения максимальной прибыли необходимо продавать 600 единиц товара первого вида и 100 товара второго вида. При этом максимальная выручка от продажи составит 600*5+100*8=3800 ден. ед.
^ Анализ решения данной задачи.
Так как оба ограничения этой задачи активно, то товары обоих видов необходимо продавать. По второй теореме двойственности это означает, что остатков ресурсов не будет, и ограничения-неравенства двойственной модели превратятся в ограничения-равенства.

Решая соответствующую модель, находим стоимости ресурсов.



у1 = 8,75 ден. ед., у2 = 6,25 ден. ед.

Проверим выполнение первой теоремы двойственности.
Min Z’= 370*8,75+90*6,25=3800 ден. ед.
Это означает, что выручка от продажи товаров будет равна суммарным расходам на продажу товаров первого и второго вида.

Аналогично можно проверить выполнение рентабельность продаж изделий.

Для товара первого вида: 0,5*8,75+0,1*6,25=5 – следовательно, продавать товары первого вида рентабельно.

Для товара первого вида: 0,7*8,75+0,3*6,25=8 – следовательно, продавать товары второго вида рентабельно.

Этот же вывод можно сделать исходя из второй теоремы двойственности.
Построим матрицу взаимозаменяемости ресурсов.





у1

у2

у1

1

6,25/8,75=0,71

у2

1,4

1


Это означает, что одну единицу второго ресурса можно заменить 1,4 единицами первого ресурса.

Рассмотрим необходимость покупки двух единиц первого ресурса по цене 50 ден. ед. за партию и трех единиц второго ресурса по цене 15 ден. ед. за партию.

Так как одну единицу первого ресурса предлагают по цене 50/2=25 и это больше, чем 8,75 , то покупка первого ресурса по таким ценам невыгодна, одну единицу второго ресурса предлагают по цене 15/3=5 и это меньше, чем 6,25, поэтому покупка второго ресурса по таким ценам выгодна.

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

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

В данном случае это будет матрица

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

=0,00625

=0,0625

=0,0125

=0,014583

Таким образом,

,

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

=2,33

=1

=5

=1

Таким образом, ,

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

Например, если предлагается на продажу товар третьего вида по цене 10 ден. ед., который требует времени продавца в объеме 1,5 ед., и занимает площадь 0,5 ед., то затраты на его продажу составят 1,5*8,75+0,5*6,25=16,25 ден. ед. Это явно больше 10 ден. ед. прибыли, которой товар третьего типа мог бы принести , и его продажа на данных условиях не выгодна.
^ 3. 5 Симплексный метод решения задач ЛП
Общая постановка задачи
Симплексный метод – метод последовательного улучшения плана.

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

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

Алгоритм симплексного метода
1.Математическую модель задачи привести к каноническому (стандартному) виду.
2. Построить начальную симплекс-таблицу исходя из стандартного вида.
3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.
4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).

5.Построить новую симплекс-таблицу-второй шаг.

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



  • Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент.

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


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

  • Написать математическую модель двойственной задачи в стандартном виде

  • Решить двойственную модель симплекс - методом

  • Записать ответ.



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

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


Х1


x2



xn

S1

S2



Sm

S1


S2



Sm

y1

y2



ym


Задача

На предприятии имеется возможность выпускать n видов продукции (1,2,…n). При ее изготовлении используются ресурсы Р1, Р2, Р3. Размеры прямых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход i –го ресурса на единицу продукции j-того вида составляют aij. Цена единицы продукции j-того вида равна cj ден. ед. Сформулировать прямую и двойственную задачу и раскрывать экономический смысл всех переменных.
Требуется:

Найти оптимальный план симплекс-методом.

Найти решение двойственной задачи

Указать дефицитность ресурсов

Обосновать эффективность плана производства

Оценить целесообразность приобретения ресурса

Оценить целесообразность выпуска новой продукции

Данные :

b1 = 25, b2 = 30, b3 = 42

a11= 2, a12= 3, a13= 2, a14= 1

a21= 4, a22= 1, a23= 3, a24= 2

a31= 3, a32= 5, a33= 2,a34= 2

c1= 6, c2= 5, c3= 4, c4= 3


^ Математическая модель прямой задачи
max (Z= 6x1+5x2+4x3+3x4)

2x1+3x2+2x3+x4< 25

4x1+x2+3x3+2x4< 30

3x1+5x2+2x3+2x4< 42

x1, x2, x3, x4 > 0
Математическая модель двойственной задачи
min (Z*= 25y1+30y2+42y3)

2y1+4y2+3y3> 6

3y1+y2+5y3> 5

2y1+3y2+2y3> 4

y1+2y2+2y3> 3

y1, y2, y3, y4 > 0
Стандартный вид
min (Z= -6x1-5x2-4x3-3x4)

2x1+3x2+2x3+x4+S1=25

4x1+x2+3x3+2x4+S2=30

3x1+5x2+2x3+2x4+S3=42

x1, x2, x3, x4, S1, S2, S3 > 0
Экономический смысл переменных
Xi – количество произведенной продукции

Yj – цена ресурса

Si – количество оставшегося ресурса


базис

значение

x1

x2

x3

x4

S1

S2

S3

отношение

Z


0

-6

-5

-4

-3

0

0

0




S1


25

2

3

2

1

1

0

0

12,5

S2


30

4

1

3

2

0

1

0

7,5

S3


42

3

5

2

2

0

0

1

14

Таблица 2

базис

значение

x1

x2

x3

x4

S1

S2

S3

отношение

Z


45

0

-3,5

0,5

0

0

1,5

0




S1



10

0

2,5

0,5

0

1

-0,5

0

4

x1


7,5

1

0,25

0,75

0,5

0

0,25

0

30

S3

19,5

0

4,25

-0,3

0,5

0

-0,8

1

4,59



Таблица 3



базис

значение

x1

x2

x3

x4

S1

S2

S3

отношение

Z


59

0

0

1,2

0

1,4

0,8

0




x2


4

0

1

0,2

0

0,4

-0,2

0




x1


6,5

1

0

0,7

0,5

-0,1

0,3

0




S3


2,5

0

0

-1,1

0,5

-1,7

0,1

1





^ Анализ решения
Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц.
Ресурс 1 типа стоит 1,4 ден. ед., 2 типа – 0,8 ден. ед. Третий тип ресурса у нас остался в количестве 2,5 ед., поэтому его покупать не нужно.
Ресурсы 1 и 2 типа дефицитны, 3 типа избыточен.
Эффективность производства
Z = 6*6.5+5*4+4*0+3*0=59 Z*=25*1.4+30*0.8+42*0=59 Производство в целом эффективно
2*1,4+4*0,8+3*0< 6 6=6 Производство 1 вида продукции эффективно

3*1,4+1*0,8+5*0< 5 5=5 Производство 2 вида продукции эффективно

2*1,4+3*0,8+2*0< 4 5,2> 4 Производство 3 вида продукции не эффективно

1*1,4+2*0,8+2*0< 3 3=3 Т.к. x4 не входит в базис, то оптимальный план не единственен.
Оценить целесообразность покупки 5 ед. второго ресурса по цене 10 ден. ед, т.е. единица ресурса обойдется нам в 2 ден. ед. Мы же готовы покупать только по 0,8 ден. ед. за 1 единицу ресурса.

а1 = 2, а2 = 2, а3 = 4. Цена новой продукции равна 4.

2*1,4+2*0,8+2*0< 4 4,4> 4 Производство 5 вида продукции не эффективно.

Контрольные вопросы.

1.Определение математической модели экономической задачи.

2.Виды математических моделей ЛП.

3.Составление математической модели.

4.Экономическая формулировка математической модели прямой и двойственной задач.

5.Понятие двойственности в задачах линейного программирования.

6.Правило построения математической модели двойственной задачи.

7. Первая теорема двойственности.

8. Вторая теорема двойственности.

9. Третья теорема двойственности.

10.Алгоритм геометрического метода решения задач ЛП.

11.Симплексный метод решения задач ЛП и его применение.

12.Алгоритмм симплексного метода.

13.Анализ решения задачи по симплекс – таблице, отвечающей критерию оптимальности.

^ 4.Лекция . Транспортная задача

4. 1 Постановка задачи. Математическая модель

транспортной задачи.

Постановка задачи:
Однородный груз сосредоточен у m поставщиков в объемах а1, а2, …, аm.

Данный груз необходимо доставить n потребителям в объемах, b1, b2, … , bn.

Известен Сij (i= 1, 2, … , m; j=1, 2 ,…, n) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю.

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

Исходные данные транспортной задачи записываются в таблице вида:

bj

аi

b1

b2



bn

А1

С11

С12



С1n

А2

С21

С22



С2n











аm

Cm1

Cm2

...

Cmn
  1   2   3   4   5   6   7   8



Скачать файл (1662 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации