Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Другие методич. материалы / МЕТОДИЧЕСКИЕ УКАЗАНИЯ для практических занятий по дисциплине «Математические методы и модели в экономике» для студентов 2 курса (специальность Экономика и бухгалтерский учет (по отраслям)
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Математика

МЕТОДИЧЕСКИЕ УКАЗАНИЯ для практических занятий по дисциплине «Математические методы и модели в экономике» для студентов 2 курса (специальность Экономика и бухгалтерский учет (по отраслям)

библиотека
материалов

Дhello_html_6ff7e003.pngЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ

«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»







М.Д. Евдокимова







методические указания

для практических занятий

по дисциплине «Математические методы и модели в экономике»

для студентов 2 курса

(специальность 080114 Экономика и бухгалтерский учет (по отраслям)





hello_html_4039a2b3.png








Семилуки , 2014

Одобрено методическим советом ГОБУ СПО ВО «СГТЭК»

Автор-составитель: Евдокимова М.Д., преподаватель ГОБУ СПО ВО «СГТЭК»


















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




















© Евдокимова М.Д., 2014

©ГОБУ СПО ВО «СГТЭК»



Оглавление


стр

Введение

4

Оценка практических работ обучающихся

6

Общая классификация ошибок

6

Раздел 1. Основные понятия и принципы моделирования

8

Практическое занятие №1 «Составление простейших математических моделей задач, возникающих в практической деятельности людей»

8

Практическое занятие №2 «Решение простейших многокритериальных задач»

13

Раздел 2. Основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей

19

Практическое занятие №3 «Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма: геометрический метод»

19

Практическое занятие №4 «Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма: симплекс метод»

25

Практическое занятие №5 «Выбор и обоснование наиболее рационального метода и алгоритма решения транспортной задачи, а также оценка сложности выбранного алгоритма: метод потенциалов»

32

Практическое занятие №6 «Решение задач о распределении средств между предприятиями»

35

Практическое занятие №7 «Нахождение кратчайшего пути в графе. Разработка алгоритма для решения различных практических задач с применением математических методов»

42

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

50

Практическое занятие №8 «Решение задачи управления запасами и задачи теории СМО, используя имитационное моделирование»

50

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

56

Практическое занятие №10 «Построение прогнозов количественными и качественными методами. Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма»

61

Литература

69


Введение


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

Перечень практических занятий соответствует рабочей программе по дисциплине «Математические методы и модели в экономике»


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

- закрепления полученных теоретических знаний по дисциплине;

- углубления теоретических знаний в соответствии с заданной темой;

- формирования умений решать практические задачи;

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

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

- подготовки к экзамену.


Содержание дисциплины ориентировано на подготовку студентов к освоению профессиональных модулей ОПОП по специальности 080114 Экономика и бухгалтерский учет (по отраслям), и овладению профессиональными компетенциями (ПК):


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


В процессе освоения дисциплины у студентов должны формироваться общие компетенции:

ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.

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

ОКЗ. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

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

ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.

ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.

ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.

ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

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


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


  • составлять простейшие математические модели задач, возникающих в практической деятельности людей;

  • выбирать наиболее рациональный метод и алгоритм решения задачи;

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


В результате освоения учебной дисциплины обучающийся должен знать:


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

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

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



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

Организация выполнения и контроля практических занятий по дисциплине «Математические методы и модели в экономике» является подготовительным этапом к сдаче дифференцированного зачета по данной дисциплине.



Нормы оценки знаний, умений и навыков обучающихся по дисциплине


Оценка практических работ обучающихся


Ответ оценивается отметкой «5», если:

  • работа выполнена полностью;

  • в логических рассуждениях и обосновании решения нет пробелов и ошибок;

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

Отметка «4» ставится в следующих случаях:

  • работа выполнена полностью, но обоснования шагов решения недостаточны (если умение обосновывать рассуждения не являлось специальным объектом проверки);

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

Отметка «3» ставится, если:

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

Отметка «2» ставится, если:

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

Отметка «1» ставится, если:

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

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



Общая классификация ошибок


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

Грубыми считаются ошибки:

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

  • незнание наименований единиц измерения;

  • неумение выделить в ответе главное;

  • неумение применять знания, алгоритмы для решения задач;

  • неумение делать выводы и обобщения;

  • неумение читать и строить графики;

  • неумение пользоваться первоисточниками, учебником и справочниками;

  • потеря корня или сохранение постороннего корня;

  • отбрасывание без объяснений одного из них;

  • равнозначные им ошибки;

  • вычислительные ошибки, если они не являются опиской;

  • логические ошибки.

К негрубым ошибкам следует отнести:

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

  • неточность графика;

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

  • нерациональные методы работы со справочной и другой литературой;

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

Недочетами являются:

  • нерациональные приемы вычислений и преобразований;

  • небрежное выполнение записей, чертежей, схем, графиков.


Раздел 1. Основные понятия и принципы моделирования


Практическое занятие №1

«Составление простейших математических моделей задач, возникающих в практической деятельности людей»


Цели занятия:

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

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


Методические указания к выполнению заданий практического занятия


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

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

  • систему ограничений в форме линейных уравнений и неравенств;

  • требование неотрицательности переменных.

Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:

найти максимальное (минимальное) значение линейной целевой функции

hello_html_m222d741d.gif

при условиях-ограничениях:

hello_html_m53d4ecad.gifhello_html_m53d4ecad.gifhello_html_m134e8d6b.gif

где aij, bi, cj – заданные постоянные величины.


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


Исходный продукт

Расход исходных продуктов на 1 кг мороженного


Запас, кг

Сливочное

Шоколадное

Молоко

0.8

0.5

400

Наполнители

0.4

0.8

365


Изучение рынка сбыта показало, что суточный спрос на сливочное мороженное превышает спрос на шоколадное мороженное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженное не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженного 16 ден.ед., шоколадного - 14 ден.ед. Определить количество мороженого каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.


Решение:

Составляем математическую модель задачи.

Вводим обозначения (переменные величины):

х 1 – суточный объем выпуска сливочного мороженного, кг;

х 2 - суточный объем выпуска шоколадного мороженного, кг

Целевая функция:

f = 16 х 1 + 14 х 2max

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

0.8 х 1 + 0.5 х 2 ≤ 400 (ограничение по молоку);

0.4 х 1 + 0.8 х 2 ≤ 365 (ограничение по наполнителям);

х 1 + х 2 ≤ 100 (рыночное ограничение по спросу);

х 2 ≤ 350 (рыночное ограничение по спросу);

х 1 ≥ 0, х 2 ≥ 0


Вариант 1


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


1. Рацион кормления коров на ферме состоит из 3х продуктов, содержащих белки, кальций и витамины. Потребность одной коровы в сутки – не менее 2000 г белков и 210 г кальция. Потребность в витаминах строго дозирована и составляет 0,087 г в сутки.


Содержание питательных веществ

Белки г/кг

Кальций г/кг

Витамины г/кг

Сено

50

10

2

Силос

70

6

3

Концентраты

180

3

1


Составить самый дешевый рацион, если цена 1 кг сена, силоса и концентратов составляет соответственно 1,5 2,0 6,0 у.е.


2. Завод производит продукцию 3х типов: П1, П2, П3. Для производства каждого изделия необходимо 3 технологические операции: О1, О2, О3. В день можно производить не более 170 единиц продукции. Найти наиболее прибыльный план производства.


Операции

Объем работ на 1 изделие (чел.-час)

Дневной фонд времени, час

П1

П2

П3

О1

2

3

2

360

О2

1

2

3

240

О3

1

1

2

180

Прибыль от 1-го изделия, $

15

22

19



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


3. Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для производства одной детали типа В - 2 чел.-ч. Производственная мощность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства детали типа А уходит 2 кг полимерного материала и 5 кг листового материала, а для производства одной детали типа В — 4 кг полимерного ма­териала и 3 кг листового металла. Еженедельные запасы каждо­го материала - по 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук. Определите, сколько деталей каждого вида следует произ­водить, чтобы обеспечить максимальный доход от продажи за неделю, если доход от продаж одной детали типа А и В состав­ляет соответственно 1,1 руб. и 1,5 руб.



Вариант 2


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


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


hello_html_m42889102.jpg


В месяц выделяется 60 000 т горючего. Потребность в рабочей силе не превышает 700 человек.

Определите количество судов I и II типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов I типа 20 млн руб., а II типа - 10 млн руб. в месяц.


2. Для сохранения здоровья и работоспособности человек должен употреблять в сутки некоторое количество белков, жиров, углеводов и витаминов. Имеются два вида пищи: I и II. Содержание питательных веществ в I кг пищи, суточная норма и стоимость одного кг пищи каждого вида даны в таблице.





Питательные вещества

Вид пищи

Суточная норма

I

II

Жиры

Белки

Углеводы

Витамины

1

4

2

0

10/3

2

2/8

1

10

12

14

1

Стоимость 1 кг

20 коп.

24 коп.

——


Как нужно организовать питание, чтобы пища содержала необходимое количество питательных веществ, а стоимость была бы минимальной?


3. Обработка деталей А и В может производиться на трех станках. Причем каждая деталь при ее изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А – 100 ден. ед., детали В – 160 ден. ед. Исходные данные приведены в таблице. Определить производственную программу, максимизирующую прибыль при условии: спрос на деталь А не менее 300 шт., на деталь В - не более 200 шт.


Станок

Норма времени на обработку одной детали, ч

Время работы станка, ч

А

В

1

0,2

0,1

100

2

0,2

0,5

180

3

0,1

0,2

100



Вариант 3


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


  1. В процессе производства два изделия А и В должны пройти обработку на станках I, II и III. Время обработки каждого изделия на каждом из этих станков задано таблицей


Станки

Изделия

I

II

III

А
В

1
1/4

4
2

1
4


Станки можно использовать соответственно в течение 45, 100 и 60 часов. Продажная цена изделия А–6 рублей, а изделия В–4 рубля. В каком соотношении следует производить изделия А и В, чтобы получить максимальную прибыль?


  1. Малое предприятие арендовало минипекарню для произ­водства чебуреков и беляшей. Мощность пекарни позволяет вы­пускать в день не более 50 кг продукции. Ежедневный спрос на чебуреки не превышает 260 штук, а на беляши — 240 штук. Суточные запасы теста и мяса и расходы на производство каж­дой единицы продукции приведены в таблице. Определить оп­тимальный план ежедневного производства чебуреков и беля­шей, обеспечивающих максимальную выручку от продажи.



Расход на производство, кг/шт.

Суточные запасы сырья, кг

чебурека

беляша

Мясо

0,35

0,6

21

Тесто

0,65

0,3

22

Цена, руб-/кг

50,0

80,0



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


Оборудование

Деталь

Полезный фонд времени, станко-ч

1

2

Технологический способ

1

2

1

2

Фрезерное

2

2

3

0

20

Токарное

3

1

1

2

37

Сварочное

0

1

1

4

30

Прибыль, ден.ед

11

6

9

6



Вариант 4


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


  1. Фирма производит и продает столы и шкафы из древеси­ны хвойных и лиственных пород. Расход каждого вида в кубо­метрах на каждое изделие задан в таблице.



Расход древесины, м3

Цена изделия, тыс. руб.

хвойные

лиственные

Стол

0,15

0,2

0,8

Шкаф

0,3

0,1

1.6

Запасы древесины, м3

80

40



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


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


Сырье

Расход сырья на производство

Поставки сырья в неделю, кг

ваза

графин

Кобальт

20

18

30

Сусальное 24-каратное золото

13

10

12

Оптовая цена, руб./шт.

700

560



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


3. Фирма производит два безалкогольных широко популяр­ных напитка «Колокольчик» и «Буратино». Для производства 1 л. «Колокольчика» требуется 0,02 ч работы оборудования, а для «Буратино» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Буратино» - 0,35 руб. Определите ежедневный план производства напитков каждо­го вида, обеспечивающий максимальный доход от их продажи.


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


  1. Что такое моделирование? Опишите цели моделирования.

  2. Что такое модель?

  3. Опишите классификацию моделей.

  4. Что такое математическое моделирование. На какие типы оно делится.

  5. Дайте определение оптимизации.

  6. Что такое исследование операции?

  7. Сформулируйте основные понятия оптимизации (РЕШЕНИЕ, ОПТИМАЛЬНОЕ РЕШЕНИЕ, ЭЛЕМЕНТЫ РЕШЕНИЯ, ПОКАЗАТЕЛЬ ЭФФЕКТИВНОСТИ).


Практическое занятие №2

«Решение простейших многокритериальных задач»


Цели занятия:

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


Методические указания к выполнению заданий практического занятия


Многокритериальные задачи


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

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


Решение простейших многокритериальных задач


В практической деятельности приходится рассматривать сложные объекты, которые невозможно целостно сопоставить. В таких случаях выделяют существенные показатели этих объектов, а затем проводят сравнение их значений. При этом первичная информация задаётся в виде таблицы значений показателей, где представлены множество сравниваемых объектов a1, a2, a3,…, ai, …,am, все наименования показателей P1, P2, P3, …, Pi, …, Pn и значение этих показателей по каждому объекту p1(ai), p2(a2), p3(a3), …, pj(ai), …, pn(am).

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

hello_html_m66d51d6e.gif

Тогда можно ввести решающее правило: aiпредпочтительнее aj, если F(ai)>F(aj).

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

hello_html_23237a1d.gif


Пример: Рассмотрим задачу выбора ноутбука на основе следующих данных:


Характеристики моделей ноутбуков

Модель

Процессор

ОЗУ

Жесткий диск

Экран

Цена

Lenovo B570

1500 МГц

2048 МБ

250 ГБ

15,6 дюйм

11500 руб

ASUS Eee PC 1225B

1650 МГц

4096 МБ

500 ГБ

11,6 дюйм

15000 руб

Toshiba SATELLITE C850-C1K

1700 МГц

2048 МБ

500 ГБ

15,6 дюйм

11600 руб

Acer ASPIRE V5-171-53314G50as

1700 МГц

4096МБ

500 ГБ

11,6 дюйм

20000 руб


Сопоставим показатели с помощью метода парных сравнений.

Результаты запишем в таблицу.



Процессор

ОЗУ

Жесткий диск

Экран

Цена

Si

Mi

Ri

Процессор

1

2

2

2

2

9

0,36

1

ОЗУ

0

1

2

2

2

7

0,28

2

Жесткий диск

0

0

1

2

0

3

0,12

4

Экран

0

0

0

1

0

1

0,04

5

Цена

0

0

2

2

1

5

0,2

3







25




После заполнения матрицы элементами сравнения находим по строкам суммы баллов по каждому показателю:

hello_html_662fa652.gif, где n- количество показателей, n=5.

Правильность заполнения матрицы определяется равенством

hello_html_cb6a9b0.gif

Затем определяем коэффициент весомости по формуле

hello_html_m5765f4f1.gif

Приоритет показателей распределяется по рангу, который пропорционален значению коэффициента весомости: чем больше его значение, тем выше ранг, причем наибольшему значению Micсоответствует Ri=1.

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


Модель

Процессор

ОЗУ

Цена

Lenovo B570

3

4

5

ASUS Eee PC 1225B

4

5

3

Toshiba SATELLITE C850-C1K

5

4

4

Acer ASPIRE V5-171-53314G50as

5

5

2

Mi

0.36

0.28

0.2


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


F (Lenovo B570) = 0,36*3+0,28*4+0,2*5= 3.2

F (ASUS Eee PC 1225B) =0,36*4+0,28*5+0,2*3= 3.44

F (Toshiba SATELLITE C850-C1K) =0,36*5+0,28*4+0,2*5=3.92

F (Acer ASPIRE V5-171-53314G50as) = 0,36*5+0,28*5+0,2*2=3.6


Так как F (Toshiba SATELLITE C850-C1K) больше остальных значений функции, то мы выбираем модель Toshiba SATELLITE C850-C1K..


Вариант 1


Задание: проведите моделирование процесса выбора товара на основе следующих данных:


Характеристики моделей микроволновой печи


Модель

Объем, л

Тип управления

Мощность гриля, Вт

Высота, см

Ширина, см


Глубина, см

BOSCH HMT 85M650

21

Тактовый

900

38

59

32

WHIRLPOOL AMW460/1

22

Электронный

750

36

56

30

LG GA-B399PQA

28

тактовый

1000

31

51

57


Вариант 2


Задание: проведите моделирование процесса выбора товара на основе следующих данных:


Характеристики моделей холодильников


Модель

Габариты: (ШxГxВ), см

Объем морозильной камеры, л

Объем холодильной камеры, л

Мощность замораживания, кг/cутки

Автономное сохранение холода, ч

цена холодильника, $

Ardo CO 2210 SHX

59.25x60x185

83

218

5

18

619

Beko CHK 36200

60x60x210

87

205

9

16

575

LG GA-B399PQA

59.5x65.1x189

86

217

6

17

461


Вариант 3


Задание: проведите моделирование процесса выбора товара на основе следующих данных:


Характеристики моделей стиральной машины


Модель

Габариты (ШxГxВ), см

Загрузка белья, кг

Тип управления

Тип загрузки

Максимальная скорость вращения, об/мин

Средняя цена, руб

BEKO WKD 23580 T

60x35x85

3.5

электронное

фронтальная

800

7975

Vestel WM-840TS

60x40x85

4.5

электронное

фронтальная

800

7740

BEKO WKD 25060 R

54x60x85

5

электронное

фронтальная

600

8250


Вариант 4


Задание: проведите моделирование процесса выбора товара на основе следующих данных:


Характеристики моделей пылесосов


Модель

Система сбора пыли

Фильтры

Управление

Мощность

Вес, кг

Средняя цена, руб

ZANUSSI ZANS710

безмешковая

Фильтр тонкой очистки — HEPA

механическое

1800

6,7

2589

SAMSUNG SC5251

Сменный пылесборник

Фильтр тонкой очистки — HEPA 11

механическое

1800

5,4

2399

DAEWOO RC-2230SA

Сменный пылесборник

микрофильтр

механическое

1500

5,4

1119


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

  1. Дайте определение многокритериальной задачи.

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

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

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




Раздел 2. Основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей



Практическое занятие №3


«Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма: геометрический метод»


Цели занятия:

  1. Научиться решать задачи геометрическим методом.

  2. Научиться записывать взаимосвязи показателей задачи в виде математической модели.



Методические указания к выполнению заданий практического занятия


Линейное программирование


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

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

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


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

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

  • систему ограничений в форме линейных уравнений и неравенств;

  • требование неотрицательности переменных.


Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:

найти максимальное (минимальное) значение линейной целевой функции

hello_html_m222d741d.gif

при условиях-ограничениях:

hello_html_m53d4ecad.gifhello_html_m53d4ecad.gifhello_html_m134e8d6b.gif

где aij, bi, cj – заданные постоянные величины.

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (2) и (4).

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (3) и (4).


Графический метод решения двумерной задачи линейного программирования (максимизация целевой функции)


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

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

Определить значение переменных x1 и x2, при которых линейная целевая функция F достигает максимума (минимума).

F = c1x1+c2x2 → max(min) при ограничениях на переменные

hello_html_m54742ba9.png

Среди ограничений могут одновременно встречаться знаки ≥, ≤ и =. Коэффициенты aij, bi, cj (i = 1..m, j = 1,2) - любые действительные числа (возможно и 0).

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

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


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


Множество планов основной задачи линейного программи­рования является выпуклым (если оно не пусто). Непустое мно­жество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной.

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


Алгоритм решения двумерной задачи линейного программирования графическим методом


Решение задачи линейного программирования графическим методом включает следующие этапы.


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

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

3. Строят многоугольник решений.

4. Строят векторN1, c2), который указывает направление возрастания целевой функции.

5. Строят начальную прямую целевой функции с1х1 + с2х2 =0 и затем передвигают ее в направлении вектора N до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов.

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


Минимальное значение линейной функции цели находится путем передвижения начальной прямой с1х1 + с2х2 = 0 в направлении, противоположном вектору N(c1,c2).


Замечание 1: В алгоритме решения пункты 4-6 можно выполнять следующим образом:

4. Найти значение целевой функции в угловых точках многогранника решений.

5. Точка, в которой функция принимает наибольшее значение и является точкой максимума.


Пример 1


На предприятии имеется сырье видов I, II, III. Из него можно изготавливать изделия типов А и В. Пусть запасы видов сырья на предприятии составляют b1, b2 , b3 ед. соответственно, изделие типа А дает прибыль c1 ден. ед., а изделие типа В c2 ден. ед. Расход сырья на изготовление одного изделия задан в условных единицах таблицей. Составить план выпуска изделий, при котором предприятие имеет наибольшую прибыль. Решить задачу графически и симплексным методом.


Изделие

Сырье

b1

b2

b3

c1

c2

I

II

III

150

260

300

6

3

А

3

4

3

В

1

3

4


Решение. Составим математическую модель задачи. Обозначим: x1 – количество выпускаемых изделий типа A, x2 - количество выпускаемых изделий типа B . Тогда с учетом расходов сырья на изготовление изделия каждого типа получим следующие ограничения на x1 и x2 , учитывающие запасы сырья каждого вида:

hello_html_52413fd5.gif(1)

По смыслу задачи

hello_html_459416e4.gif

Прибыль F предприятия при плане x1, x2 равна

hello_html_md86ea87.gif. (3)

Итак, математическая модель задачи получена: необходимо найти значения x1, x2 , удовлетворяющие неравенствам (1), (2), для которых функция (3) достигает наибольшего значения. Полученная задача – стандартная задача линейного программирования.


Решим полученную задачу графически.


Для этого введем систему координат x1Ox2 и изобразим в ней множество решений систем неравенств (1), (2) (область допустимых решений - ОДР) в виде множества точек плоскости.

Условию (2) удовлетворяют точки первой четверти. Для получения полуплоскостей, соответствующих неравенствам системы (1), построим их границы, т.е. прямые линии:


Имя прямой

Уравнение прямой

Таблица для построения прямой

(а)

hello_html_m5e12f652.gif

х1

0

50

х2

150

0

(б)

hello_html_35042e4b.gif

х1

0

65

х2

260/3

0

(в)

hello_html_m238f4daa.gif

х1

0

100

х2

75

0


hello_html_79fe052f.png


Пересечение построенных полуплоскостей с первой четвертью – искомая ОДР (многоугольник OABCD, рис.1.1.).

Ищем координаты вершин ОДР и значения целевой функции F в этих вершинах:

O(0; 0): F(O)=6*0+3*0=0$

A(0;75): F(A)=6*0+3*75=225;

hello_html_3b7cd775.gif

F(B)=6*20+3*60=300

hello_html_47d4d9c.gif

F(C)=6*38+3*36=336

D(50;0)

F(D)=6*50+3*0=300.

Отсюда

Fmax= F(C)= F(38;36)=336.

Вывод: предприятию выгодно выпустить 38 изделий типа A1=38) и 36 изделия типа B (х2=36). При этом его прибыль будет наибольшая и составит 336 ден. ед.


Задание 1


На предприятии имеется сырье видов I, II, III. Из него можно изготавливать изделия типов А и В. Пусть запасы видов сырья на предприятии составляют b1, b2, b3 ед. соответственно, изделие типа А дает прибыль с1 ден.ед., а изделие типа В - с2 ден.ед. Расход сырья на изготовление одного изделия задан в словных единицах таблицей.

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


1 вариант

Изделие

Сырье

b1

b2

b3

с1

с2

I

II

III

102

91

105

5

9

А

6

3

2

В

3

4

5

2вариант

Изделие

Сырье

b1

b2

b3

с1

с2

I

II

III

20

36

40

2

5

А

1

1

3

В

3

2

1

3 вариант

Изделие

Сырье

b1

b2

b3

с1

с2

I

II

III

40

34

46

1

2

А

2

1

3

В

2

2

1

4 вариант

Изделие

Сырье

b1

b2

b3

с1

с2

I

II

III

300

520

600

6

3

А

3

4

3

В

1

3

4


Задание 2


Фирма выпускает два вида продукции А и В. Суточные ресурсы фирмы следующие:

В1- единиц производственного оборудования;

В2 - единиц сырья;

В3- единиц электроэнергии.

Расходы каждого вида ресурсов на единицу продукции каждого типа представлены в табл. 1:

Таблица 1

Ресурсы

Тип продукции

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

А

В

Оборудование

2

4

В1

Сырьё

1

5

В2

Э/ ресурсы

3

2

В3


Цена единицы продукции первого вида равна 8 ден. ед., а второго вида – 6 ден. ед.

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


Вариант

1

2

3

4

В1

560

650

486

470

В2

490

480

360

650

В3

600

500

450

740


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


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

  2. Как определяется область допустимых решений (многоугольник решений)?

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

  4. Какие задачи линейного программирования можно решать геометрическим методом?



Практическое занятие №4

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


Цели занятия:

1. Научиться решать задачи симплекс- методом.

3. Научиться записывать взаимосвязи показателей задачи в виде математической модели.



Методические указания к выполнению заданий практического занятия


Линейное программирование


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

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

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


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

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

  • систему ограничений в форме линейных уравнений и неравенств;

  • требование неотрицательности переменных.


Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:

найти максимальное (минимальное) значение линейной целевой функции

hello_html_m222d741d.gif

при условиях-ограничениях:

hello_html_m53d4ecad.gifhello_html_m53d4ecad.gifhello_html_m134e8d6b.gif

где aij, bi, cj – заданные постоянные величины.

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (2) и (4).

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (3) и (4).


Симплекс-метод линейного программирования


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

Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канто­ровичем.


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


Алгоритм симплексного метода включает следующие этапы:


1. Составление первого опорного плана. Система ограниче­ний задачи, решаемой симплексным методом, задана в виде системы неравенств смысла «<», правые части которых bi > 0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Век­торы-столбцы при этих переменных представляют собой единич­ные векторы и образуют базис, а соответствующие им перемен­ные называются базисными:

hello_html_m622aed0.jpg

Решим эту систему относительно базисных переменных:

hello_html_2a5f3af6.jpg

а функцию цели перепишем в виде уравнения

hello_html_1d1270f2.jpg

Полагая, что основные переменные х1 =х2 = х3 =... хп =0, получим первый опорный план Х1 = (0, 0, ...,0, b1, b2, ..., bт); F(X1) = 0, который заносим в симплексную табл. Она со­стоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и за­полняется коэффициентами функции цели, взятыми с противо­положным знаком.

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

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

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

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

4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таб­лицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, т. е. вместо хi , в базис войдет переменная хj, соответ­ствующая ведущему столбцу.

Рhello_html_m9e7016f.pngазделим все элементы ведущей строки предыдущей симплек­сной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствую­щую введенной в базис переменной xj. В результате этого на месте разрешающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника:

hello_html_m7b6065dd.gifгде СТЭ - элемент старого плана, РЭ - разрешающий элемент, А и В - элементы старого плана, образующие прямоугольник с эле­ментами СТЭ и РЭ.


Далее возвращаемся ко второму этапу алгоритма — провер­ке плана на оптимальность.

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

Если в ведущем столбце все коэффициенты aij≤0, то функ­ция цели F(X) не ограничена на множестве допустимых планов, т. е. F(X) стремится к бесконечности и задача не имеет решения.


Пример:


Предприятие выпускает три вида изделий (N1, N2, N3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблице. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков. Найти решение задачи симплексным методом с представлением всех симплексных таблиц и проанализировать полученные результаты.


N1

N2

N3

З

Р1

1

3

4

42

Р2

4

2

2

54

Р3

3

2

2

80

П

2

1

3



Решение: Запишем математическую модель задачи.


Определим вектор hello_html_5c62b52c.gif, который удовлетворяет условиям

hello_html_247d0604.gif

и обеспечивает максимальное значение целевой функции

hello_html_m32c1cfea.gif


Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x4, x5, x6:


hello_html_10e633aa.gif


Полагая, что свободные переменные x1=0, x2=0, x3=0, получим первый опорный план hello_html_m4564947b.gifhello_html_m1618c96f.gif, в котором базисные переменные x4=39, x5=89, x6=59. Следовательно, изделия не производятся, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу.


План

СЗ

БП

ЗБП

Значение коэффициентов при

hello_html_24514f8e.gif

X1

X2

X3

X4

X5

X6

I

0

0

0

x4

x5

x6

42

54

80

1

4

3

3

2

2

4

2

2

1

0

0

0

1

0

0

0

1

42/4=10,5

54/2=27

80/2=40

Индексная строка

hello_html_m65b7c301.gif=0

-2

-1

-3↑

0

0

0



Первый опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: -2, -1, -3.

За ведущий столбец выберем столбец, соответствующий переменной x3, так как, сравнивая по модулю, имеем: |-3|>{|-1|,|-2|}.

Вычислим значения hello_html_677522c2.gif по строкам как частное от деления hello_html_771a536f.gif и из них выберем наименьшее:

hello_html_m6b9168d3.gif

Следовательно, ведущая строка- х4.

Разрешающий элемент равен РЭ=4 и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице.


Формируем следующую часть симплексной таблице. Вместо переменной x4 в план II войдет переменная x3. Строка, соответствующая переменной x3 в плане II, получена в результате деления всех элементов строки x4 плана I на разрешающий элемент РЭ=4. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столба x3 плана II записываем нули.

Таким образом, в новом плане II заполнены строки x3 и столбец x3. Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=4.

Значение нового элемента в плане II находится из выражения:

hello_html_7a58283a.gif

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


Построим вторую симплекс-таблицу:


План

СЗ

БП

ЗБП

Значение коэффициентов при

hello_html_24514f8e.gif

X1

X2

X3

X4

X5

X6

II

3

0

0

х3

x5

x6

10,5

33

59

0,25

3,5

0,5

0,75

0,5

0,5

1

0

0

0,25

-0,5

-0,5

0

1

0

0

0

1

42

9,43

118

Индексная строка

hello_html_m4ad7c26b.gif=3-10,5=31,5

-1,25↑

1,25

0

0,75

0

0



Второй опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: -1,25.


За ведущий столбец выберем столбец, соответствующий переменной x1.

Вычислим значения hello_html_677522c2.gif по строкам как частное от деления hello_html_m78bf7739.gif и из них выберем наименьшее:

hello_html_184b0d0d.gif

Следовательно, ведущая строка- х5.

Разрешающий элемент равен РЭ=3,5 и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице.


Формируем следующую часть симплексной таблице. Вместо переменной x5 в план III войдет переменная x1. Строка, соответствующая переменной x1 в плане III, получена в результате деления всех элементов строки x5 плана II на разрешающий элемент РЭ=3.5. На месте разрешающего элемента в плане III получаем 1. В остальных клетках столбца x1 плана III записываем нули.

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

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





Построим третью симплекс-таблицу:




План

СЗ

БП

ЗБП

Значение коэффициентов при

hello_html_24514f8e.gif

X1

X2

X3

X4

X5

X6

III

3

2

0

х3

x1

x6

8,143

9,429

35,429

1

0

0

0,714

0,143

0,143

1

0

0

0,286

-0,143

-0,143

-0,071

0,286

-0,714

0

0

1


Индексная строка

hello_html_m2eb46e7d.gif= 3*8,143+2*9,429=

=43,286

0

0,357

0

0,571

0,357

0



Получаем план III, который является оптимальным, так как все коэффициенты в индексной строке hello_html_m78774d40.gif 0.

Оптимальный план можно записать так:

hello_html_54b41103.gif


Вывод: Для получения максимального дохода 43,286 у.е. предприятию необходимо производить изделий первого вида 9,429 ед., третьего вида – 8,143 ед., изделия второго вида не производятся.

При этом ресурсы первого и второго видов расходуются полностью, ресурсы третьего остаются в количестве 35,429ед.


Задание


Предприятие выпускает три вида изделий (N1, N2, N3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблице. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков. Найти решение задачи симплексным методом с представлением всех симплексных таблиц и проанализировать полученные результаты.



Вариант 1


N1

N2

N3

З

Р1

6

7

2

57

Р2

6

6

1

97

Р3

3

7

8

63

П

5

6

8



Вариант 2


N1

N2

N3

З

Р1

7

8

3

81

Р2

4

1

6

68

Р3

5

1

7

54

П

2

5

6



Вариант 3


N1

N2

N3

З

Р1

1

2

8

65

Р2

8

3

1

35

Р3

3

4

7

46

П

3

4

2



Вариант 4


N1

N2

N3

З

Р1

2

7

1

34

Р2

4

1

1

39

Р3

8

8

8

86

П

7

2

5



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


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

  2. Каков признак оптимальности в симплексном методе?

  3. Как строится опорный план?

  4. Как определяется ведущий столбец и ведущая строка симплексной таблице?

  5. Как осуществляется перерасчет элементов симплексной таблицы?

  6. Каковы основные случаи при реализации симплексного метода?



Практическое занятие №5

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


Цели занятия:

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

  • Научиться строить опорный план транспортной задачи.

  • Научиться находить оптимальный план транспортной задачи.



Методические указания к выполнению заданий практического занятия


Постановка транспортной задачи


Однородный груз, имеющийся в m пунктах отправления (производства) А1,А2,...,Аm соответственно в количествах а1,а2,...,аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2,..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и cij (i=1,m; j=1,n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е:hello_html_109bb24d.png

а суммарные транспортные расходы минимальны.

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

Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.

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


2.Методы решения транспортных задач



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

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij ≥ 0, а в маленькие клетки – соответствующие тарифы Cij.

hello_html_m7ec9f2db.png


Затем решение задачи разбивается на два этапа:

  1. Определение опорного плана.

  2. Нахождение оптимального решения путем последовательных операций.


  1. Найдем вначале допустимое (опорное) решение транспортной задачи. Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".


Метод северо-западного угла (диагональный)


Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Хij горизонтальным и вертикальным уравнениям.


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


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


3.Метод потенциалов решения транспортных задач


Метод потенциалов:

Введем строку потенциалов ui и столбец потенциалов vj. Полагая, что u1=0, а остальные ui и vj найдем так, чтобы

а) для заполненных ячеек выполнялись равенства hello_html_6d956266.gif;

б) для незаполненных ячеек выполнялись равенства hello_html_m79798a92.gif


Критерий оптимальности

Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия hello_html_m24cdf183.gifто Х0 является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.


Цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:

  1. Одна ячейка пустая, все остальные занятые.

  2. Любые две соседние ячейки находятся в одной строке или в одном столбце.


Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой αr+βs > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:

  1. В плюсовых клетках добавляем Х.

  2. Из минусовых клеток вычитаем Х.

  3. Все остальные клетки вне цикла остаются без изменения.


Получим новую таблицу, дающую новое решение Х, такое, что F (X1) ≤ F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.


Различные виды циклов перерасчета таблицы

hello_html_1ccf1bf9.pnghello_html_m3a299f9c.png

Пример.

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

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

а1=50, а2=60, а3=90

в1=90, в2=70, в3=40 hello_html_11d96487.gif

Решение:

Эта задача является закрытой транспортной задачей, так какhello_html_m172da02d.gif

50+60+90=90+70+40. 200=200.

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

Составим первый план перевозок. В этом плане отличными от нуля перевозками hello_html_m1c954ace.gif могут быть лишь (m+n-1) значений, где m – число поставщиков, n – число потребителей. Остальные переменные заведомо равны нулю. Будем их в таблице помечать прочерком.

В нашем примере m=3, n=3.

Значит число заполненных клеток: 3+3-1=5.

Для составления плана последовательно заполняем клетки таблицы так, чтобы на каждом шаге исчерпывалась или потребность какого-либо потребителя, или возможности какого-либо поставщика. В соответствующем столбе или строке ставим в остальных пустых клетках прочерки. Если при этом одновременно исчерпывается и потребность и возможность, то вычеркивается что-то одно (столбец или строка). При таком построении плана перевозок заполненными окажутся ровно (m+n-1) клетки, а остальные прочеркиваются.

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

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



B1

B2

B3


vi

A1

1


3



3



2

50

2


-



10



40


A2



1

4


6

-1


1

60

1


60



-



-


A3



2



3

2


5

90

2


30



60



-



90

70

40

200


uj

0

1

1




Заполняем клетку (21), так как с21=1 – наименьшее, значением х21=60. При этом прочеркиваем вторую строку.

На втором шаге заполняем клетку (13), т.к. с13=2 - наименьшее, значением х13=40. При этом прочеркиваем третий столбец.

В оставшейся части таблицы наименьшее с31=2, значит, заполняем клетку (31) значением х31=30 (90-60=30). При этом прочеркиваем первый столбец.

Теперь остается наименьшее с12=3, значит, заполняем клетку (12) значением х12=10 (50-40=10). При этом прочеркиваем первая строка.

Наименьшее с32=3, значит заполняем клетку (32) значением х32=60 (70-10=60).

Число заполненных клеток равно 5.

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

hello_html_m24b34a31.gif.

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

Введем строку потенциалов uj и столбец потенциалов vi. Полагая, что u1=0, а остальные uj и vi найдем так, чтобы

а) для заполненных клеток выполнялись равенства hello_html_130adab8.gif;

б) для незаполненных клеток выполнялись равенства hello_html_745c61e7.gif.

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

Для оптимальности плана должно выполняться условие hello_html_m3c10782.gif для всех пустых клеток.

У нас hello_html_79b421fb.gif, значит, план не оптимален. Уменьшим стоимость перевозок, заполнив клетку (23).

Для этого построим цикл перерасчета таблицы:


hello_html_14802b23.png


По циклу в клетку (23) перемещаем 40 единиц из клетки (13). Получаем новый опорный план.



B1

B2

B3


vi

A1

1


3



3

0


2

50

2


-



50



-


A2



1

4


6

0


1

60

1


20



-



40


A3



2



3

3


5

90

2


70



20



-



90

70

40

200


uj

0

1

0




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

Так как среди оценок пустых клеток нет отрицательных, то построенный план оптимальный.

При этом стоимость перевозок hello_html_m53d4ecad.gifhello_html_22e40452.gif.


Вывод: Для того, чтобы транспортные расходы на перевозку продукции были минимальны и составляли 410 ден.ед., необходимо из пункта А1 перевозить 50 ед. в пункт В2, из А2 – 20 ед. в В1 и 40 ед. в В3, из А3 – 70 ед. в В1 и 20 ед. в В3.


Задание


Решить транспортную задачу.

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

  1. Составить опорный план перевозок методом северо-западного угла и вычислить стоимость перевозок.

  2. Составить опорный план перевозок методом наименьшего элемента и вычислить стоимость перевозок.

  3. Составить план перевозок всей продукции от поставщиков потребителям, при котором суммарные затраты на перевозки минимальны.


Вариант 1

а1=90, а2=40, а3=70

в1=50, в2=50, в3=100

hello_html_5c65aa97.gif



Вариант 2

а1=180, а2=80, а3=40

в1=100, в2=100, в3=200

hello_html_m3304272a.gif


Вариант 3

а1=80, а2=70, а3=50

в1=45, в2=55, в3=100

hello_html_2ff35c14.gif



Вариант 4

а1=90, а2=40, а3=70

в1=85, в2=45, в3=70

hello_html_m19df4632.gif


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

  1. Приведите пример транспортной задачи.

  2. Укажите общий алгоритм решения транспортной задачи.

  3. В чем суть метода потенциалов?

  4. Что находится изначально: опорный план перевозок или оптимальный план перевозок?



Практическое занятие№6

«Решение задач о распределении средств между предприятиями»


Цели занятия:


  1. Научиться решать задачи динамического программирования.

  2. Научиться разбивать весь процесс решения задачи на этапы.

  3. Научиться выбирать оптимальную стратегию поведения.


Методические указания к выполнению заданий практического занятия


Динамическое программирование


1. Понятие задачи динамического программирования

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

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


Задача может быть сформулирована следующим образом:

Задача динамического программирования – определить ui* (ui* не только число, а может быть вектором, функцией) на каждом шаге, i = 1, 2 …, m, и тем самым u* всей операции в целом.


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


  1. От последнего шага к первому.

  2. От первого шага к последнему или же наоборот, в зависимости от исходных данных.


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

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

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

Оптимальное распределение ресурсов


Пример:

Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)


u

Прибыль от внедрения

f4(u)

f3(u)

f2(u)

f1(u)

8

55

39

35

32

16

58

53

76

68

24

90

80

120

115

32

100

120

135

134

40

140

145

158

147


Решение:


Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.


1 этап.

Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L(i), i=8,16,24,32,40.

1 шаг: Денежные средства вкладываются в четвертый проект.

L(8)=55

L(16)=58

L(24)=90

L(32)=100

L(40)=140


2 шаг: Денежные средства вкладываются в четвертый и третий проекты.


u

Прибыль от внедрения

1 шаг

f3(u)

8

55

39

16

58

53

24

90

80

32

100

120

40

140

145


hello_html_m2ebe228c.gif

3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.


u

Прибыль от внедрения

2 шаг

f2(u)

8

55

35

16

94

76

24

108

120

32

135

135

40

175

158


hello_html_14d8f1b0.gif

4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый проекты.


u

Прибыль от внедрения

3 шаг

f1(u)

8

55

32

16

94

68

24

131

115

32

175

134

40

214

147


hello_html_4463fa9c.gif

2 этап:

На четвертом шаге выбираем максимальное из полученных значений прибыли L(40)=214.

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

Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:

1 проект – 0 млн. руб.

2 проект – 24 млн. руб.

3 проект – 8 млн. руб.

4 проект – 8 млн. руб.


Задание


Задание 1. Распределите оптимальным образом денежные средства инвестора величиной 5 у.е. между четырьмя предприятиями. Доход каждого предприятия от вложения в него и у.е.определяется функцией дохода f(u). Эти функции приведены в таблице.

u

Прибыль от внедрения по предприятиям

f4(u)

f3(u)

f2(u)

f1(u)

1

f4(1)

6

3

4

2

10

f3(2)

4

6

3

11

11

f2(3)

8

4

12

13

11

f1(4)

5

18

15

18

16


Вариант

1

2

3

4

f4(1)

9

5

6

8

f3(2)

10

10

7

7

f2(3)

7

5

8

9

f1(4)

10

9

13

15


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


  1. Какие задачи можно решать методами динамического программирования?

  2. В чем заключаются достоинства и недостатки динамического программирования?

  3. Объясните алгоритм решения задач динамического программирования.

  4. В чем заключается принцип оптимальности?

  5. Каков алгоритм распределения ресурсов?



Практическое занятие№7

«Нахождение кратчайшего пути в графе. Разработка алгоритма для решения различных практических задач с применением математических методов»


Цель занятия:

  1. Научиться определять метрические характеристики графа.

  2. Научиться определять кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.


Методические указания к выполнению заданий практического занятия


Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.


Метрические характеристики графов


В теории графов применяются:


  1. Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит (-1)  в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2.

 Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.


  1. Матрица смежности. Это матрица n*n где n – число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у и bij = 0 в противном случае.


  1. Пусть G=(X,U) - связный граф, а hello_html_fcf6c43.gif - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины hello_html_fcf6c43.gif (пути из hello_html_59204260.gif) называется расстоянием между вершинами hello_html_fcf6c43.gif и обозначается hello_html_m42455058.gif. Положим hello_html_7fdf5ab9.gif, если вершины hello_html_fcf6c43.gif не соединены маршрутом (путем). Расстояние hello_html_m42455058.gif удовлетворяет следующим аксиомам:

1) hello_html_4ec4c735.gif;

2) hello_html_m16b3c83c.gif;

3)hello_html_7f1edd10.gif тогда и только тогда, когда hello_html_m48537e5.gif;

4) hello_html_7e8fe58b.gif для симметрических графов;

5) hello_html_4a15a83d.gif


  1. Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:

hello_html_17d0e387.gif


  1. Для фиксированной вершины hello_html_mf80ebfe.gif величина hello_html_5698e6de.gifназывается эксцентриситетом (отклоненностью) вершины hello_html_mf80ebfe.gif.


  1. Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):

hello_html_117f0bb6.gif


  1. Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):

hello_html_m670000f7.gif


  1. Вершина, имеющая минимальный эксцентриситет, называется центром графа.


  1. Для вершины hello_html_780249fd.gif число hello_html_2dd4343c.gif называется передаточным числом.


  1. Вершина графа, которой соответствует минимальное передаточное число hello_html_660b7f4d.gif

называется медианой графа. Центров и медиан в графе может быть несколько.


hello_html_3d87cfe1.gif






Рис. 1



Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:

hello_html_69688356.gif


Радиус графа равен 1, диаметр равен 2. Центр графа - вершина hello_html_m14a51d2a.gif; Медиана графа - вершина hello_html_m14a51d2a.gif.


Задача о нахождении кратчайшего пути


Пусть дан граф, каждой дуге которого приписан вес. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует.

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


Данная задача может быть разбита на две:

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

  • найти кратчайшие пути между всеми парами вершин.



Алгоритм Дейкстры решения задачи


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

Пусть s - начальная вершина пути, t - конечная.

На каждой итерации алгоритма каждая вершина xi графа имеет метку l(xi), которая может быть постоянной или временной. В первом случае l(xi) является длиной кратчайшего (s, xi)-пути; во втором случае l(xi) - длина кратчайшего (s, xi)-пути, проходящего через вершину xi и вершины с постоянными метками. Таким образом временная метка l(xi), является оценкой сверху для длины кратчайшего (s, xi)-пути, и, став на некоторой итерации постоянной, она остается такой до конца работы алгоритма.

Кроме l(xi), с вершинами графа связывается еще одна метка Q(xi).На каждой итерации Q(xi) является номером вершины, предшествующей хi в кратчайшем (s, xi)-пути.

После того, как последняя вершина t получила постоянную метку, с помощью меток Q(x) легко указать последовательность вершин, составляющих кратчайший (S,t)-путь:

(s..., Qn(t)..., Q(Q(t)), Q(t),t),

Qn(t)= Q(Q(...Q(t)) (n раз).

Перед началом работы алгоритма начальная вершина s имеет постоянную метку l(s)=0, а метки всех остальных вершин равны бесконечности () и являются временными. Обозначим через p последнюю из вершин, получивших постоянную метку.


Алгоритм Дейкстры включает следующие шаги:

1. Положить l(s)=0 и считать эту метку постоянной. Положить l(xi)= для всех xi s, и считать эти метки временными. p = s.

2. Обновление пометок. Для всех вершин xi Г(p), пометки которых временные, изменить пометки в соответствии с правилом:

l(xi)=min { l(xi), l(p) +w(p, xi) }.

Если l(xi)> l(p) +w(p, xi), то Q(xi) = p.

3. Если l(xi)= для всех вершин xi, пометки которых временные, то в исходном графе отсутствуют пути из вершины s в вершины с временными метками. Останов алгоритма. В противном случае переход к шагу 4.

4. Превращение пометок в постоянные. Среди всех вершин с временными метками найти такую вершину xi* , для которой l(xi*) = minl(xi) (метка минимальная) и считать эту пометку постоянной. Положить p=xi*. Пометку Q(xi*) также считать постоянной.

5. Если p t, перейти к шагу 2, а если p = t, то l(p) - длина кратчайшего пути из s в t.

После определения длины кратчайшего пути сам кратчайший путь восстанавливается по постоянным меткам Q(xi).


Пример решения задачи

Для взвешенного орграфа найти кратчайший путь из вершины s в вершину t.

hello_html_m772c8f42.png

1. Помечаем в соответствии с алгоритмом вершины графа:

l(s) = 0 ,

l(a) = ,

l(b) = ,

l(c) = ,

l(d) = ,

l(t) = .

Вершине s приписываем постоянную пометку, т.е. p = s.

2. Из вершины s помечаем остальные вершины:

l(a) = min {, 0 + 4} = 4,

l(b) = min {, 0 + 7} = 7,

l(c) = min {, 0 + 3} = 3,

l(d) = ,

l(t) = .

У вершин a, b, с уменьшились пометки, следовательно Q(a) = s, Q(b) = s, Q(c) = s.

Вершине c приписываем постоянную пометку, т.е. p = c. Пометка Q(с)=s также становится постоянной.

3. Из вершины c помечаем остальные вершины:

l(a) = min {4, 3 + } = 4,

l(b) = min {7, 3 + } = 7,

l(d) = min {, 3 + 3} = 6,

l(t) = .

У вершины d уменьшилась пометка, следовательно Q(d) = c.

Вершине a приписываем постоянную пометку, т.е. p = a. Пометка Q(a)=s становится постоянной.

4. Из вершины а помечаем остальные вершины:

l(b) = min {7, 4 + 4} = 7,

l(d) = min {6, 4 + 3} = 6,

l(t) = .

Вершине d приписываем постоянную пометку, т.е. p = d.. Пометка Q(d)=c становится постоянной.

5. Из вершины d помечаем остальные вершины:

l(b) = min {7, 6 + } = 7,

l(t) = min {, 6 + 2} = 8,

У вершины t уменьшилась пометка, следовательно Q(t) = d.

Вершине b приписываем постоянную пометку, т.е. p=b. Пометка Q(b)=s становится постоянной.

6. Из вершины b помечаем вершину t:

l(t) = min {8, 7 + 2} = 8.

Метки l(t) и Q(t)=d становятся постоянными.

7. Восстанавливаем по меткам Q кратчайший путь из s в t:

Путь scdt длиной 8.


Вариант 1


Задание 1.Определить метрические характеристики графа.


hello_html_m485b547c.png


Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.

hello_html_m54833ed4.png


Вариант 2


Задание 1.Определить метрические характеристики графа.


hello_html_3ce8f992.png


Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.

hello_html_m69c995a9.png


Вариант 3


Задание 1.Определить метрические характеристики графа.


hello_html_721fb213.png


Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.

hello_html_6b4eaa9a.png


Вариант 4


Задание 1.Определить метрические характеристики графа.


hello_html_1204d807.png


Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.

hello_html_m1392a939.png


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


  1. Что такое граф?

  2. Приведите разновидности графов.

  3. Может ли пустой граф быть ориентированным?

  4. Нарисуйте полный граф.

  5. Каким образом понятие дерева активно используется в информатике и программировании?

  6. Перечислите метрические характеристики графов.

  7. Дайте интерпретацию задаче о кратчайших путях.




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



Практическое занятие№8

«Решение задачи управления запасами и задачи теории СМО, используя имитационное моделирование»


Цель занятия:

1.Научиться оценивать надежность простейших систем методом Монте-Карло;

2.Научиться рассчитывать СМО с отказами методом Монте-Карло.


Методические указания к выполнению заданий практического занятия


Суть имитационного моделирования


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


Как остроумно подметил Ю. Адлер, сочетание слов имитация и моделирование недопустимо и является тавтологией. Но, рассматривая исторический процесс формирования этого термина, пришли к выводу, что это словосочетание определяет в моделировании такую область, которая относится к получению экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.

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

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

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

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

Метод Монте-Карло



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

Метод Монте-Карло является методом статистического моделирования или имитационного моделирования.

Метод Монте-Карло – это численный метод решения задач при помощи моделирования случайных величин.

Датой рождения метода Монте-Карло принято считать 1948 г. Создателями метода считают математиков Дж. Неймана и С. Улама.

Теоретическая основа метода была известна давно. Однако до появления ЭВМ этот метод не мог найти широкого применения.

Само название метода происходит от названия города Монте-Карло в княжестве Монако, знаменитого своими игорными домами. Дело в том, что одним из простейших механических приборов для получения случайных величин является рулетка. Возникает вопрос: помогает ли метод Монте-Карло выигрывать в рулетку? Нет, не помогает. И даже не занимается этим.

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

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

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


Оценка надежности простейших систем методом Монте-Карло


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

а) Найти методом Монте-Карло оценку Р* надежности (вероятности безотказной работы) системы, зная вероятности безотказной работы элементов: Р (А)=0,8, Р (В)=0,85, Р (С)=0,6; б) найти абсолютную погрешность Р-Р* , где Р- надежность системы, вычисленная аналитически. Произвести 50 испытаний.


Решение. а) Выбираем из таблицы приложения (равномерно распределенные числа) три случайных числа: 0,10, 0,09 и 0,73; по правилу *) (если случайное число меньше вероятности события, то событие наступило; если случайное число больше или равно вероятности события, то событие не наступило) разыграем события А, В, С, состоящие в безотказной работе соответственно элементов А, В, С. Результаты испытания будем записывать в расчетную таблицу .

Поскольку Р (А)=0,8 и 0,10 <0,8, то событие наступило, т.е. элемент А в этом испытании работает безотказно. Так как Р (В)=0,85 и 0,09< 0,85, то событие В наступило, т.е. элемент В работает безотказно.

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


Таблица


Номер

испытания


Блок

Случайные числа,

моделирующие элементы

Заключение о работе

элементов

блоков

системы

А

В

С

А

В

С

1

Первый

Второй

0,10

0,09

0,73

+

+

-

+

-

-

2

Первый

Второй

0,25

0,33

0,76

+

+

-

+

-

-

3

Первый

Второй

0,52

0,01

0,35

+

+

+

+

+

+

4

Первый

Второй

0,86

0,34

0,67

-

+

-

+

-

-


Так как Р (С)=0,6 и 0,73< 0,6, то событие С не наступило, т.е. элемент с получает отказ; Другими словами, второй блок, а значит и вся система, получают отказ. В соответствующих клетках табл. 57 ставим минус.

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

Произведя 50 испытаний, получим, что в 28 из них система работала безотказно. В качестве оценки искомой надежности Р примем относительную частоту Р * =28/50=0,56.

б) Найдем надежность системы Р аналитически. Вероятности безотказной работы первого и второго блоков соответственно равны:

hello_html_m21ff3e20.gif

Вероятность безотказной работы системы

P=P1*P2=0,97*0,6=0,582

Искомая абсолютная погрешность Р-Р*=0,582-0,56=0,022.



Расчет СМО с отказами методом Монте-Карло


Пример: В трехканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f()=5e-5 . Длительность обслуживания каждой заявки равна 0,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=4 мин.


Решение:

Пусть Т1=0- момент поступления первой заявки. Заявка поступит в первый канал и будет им обслужена. Момент окончания обслуживания первой заявки Т1+0,5=0+0,5=0,5. В счетчик обслуженных заявок записываем единицу.

Моменты поступления последующих заявок найдем по формуле

Т= Т-1+ ,

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

Возможные = - (1/) ln ri = = (1/)(- ln ri ).

Учитывая, что, по условию, =5, получим =0,2 (- ln ri ).

Случайные числа riберем из таблицы приложения, начиная с первой строки сверху. Для нахождения времени между поступлениями первой и второй заявок возьмем случайное число r=0,10.

Тогда 2=0,2*(-ln 0,10)=0,2*2,30=0,460. Первая заявка поступила в момент T1=0.

Следовательно, вторая заявка поступила в момент T2= T1+0,4600+0,460=0,460. В этот момент первый канал еще занят обслуживанием первой заявки, поэтому вторая заявка поступит во второй и будет им обслужена. Момент окончания обслуживания второй заявки T2+05=0,460+0.5=0.960 . В счетчик обслуженных заявок добавляем единицу.

По очередному случайному числу r=0.09 разыграем время 3 между поступлениями второй и третьей заявок:

3=0,2(-ln 0,09)=0,2*2,41=0,482.

Вторая заявка поступила в момент T2= 0,460 . Поэтому третья заявка поступила в момент T3= T2+0,482=0,460+0,482=0,942. В этот момент первый канал уже свободен и третья заявка поступит в первый канал. Момент окончания обслуживания третьей заявки

T3+0,5=0,942+0,5=1,442.В счетчик обслуженных заявок добавляем единицу.

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

Заметим, что обслуживание 20-й заявки закончится в момент 4 148,>4, поэтому эта заявка получает отказ.

Испытание прекращают (в таблице записывают «стоп»), если момент поступления заявки T>4.






Таблица

номер заявки

i

Случайное числоri

-ln ri

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

i=0,2(-ln ri)

Момент поступления заявки

Ti= Ti-1+i

Момент

Ti+0,5

окончания обслуживания заявки каналом

Счетчик

1

2

3

Обслуженных заявок

отказов

1




0

0,500



1


2

0,10

2,30

0,460

0,460


0,960


1


3

0,09

2,41

0,482

0,942

1,442



1


4

0,73

0,32

0,064

1,006


1,506


1


5

0,25

1,39

0,278

1,284



1,784

1


6

0,33

1,11

0,222

1,506

2,006



1


7

0,76

0,27

0,054

1,560


2,060


1


8

0,52

0,65

0,130

1,690





1

9

0,01

4,60

0,920

2,610

3,110



1


10

0,35

1,05

0,210

2,820


3,320


1


11

0,86

0,15

0,030

2,850



3,350

1


12

0,34

1,08

0,216

3,066





1

13

0,67

0,40

0,080

3,146

3,646



1


14

0,35

1,05

0,210

3,356


3,856


1


15

0,48

0,73

0,146

3,502



4,002


1

16

0,76

0,27

0,054

3,556





1

17

0,80

0,22

0,044

3,600





1

18

0,95

0,05

0,010

3,610





1

19

0,90

00,10

0,020

3,630





1

20

0,91

0,09

0,018

3,648

4,148




1

21

0,17

1,77

0,354

4,002










(стоп)



итого

Х1=12

8

Из таблицы находим, что за 4 мин всего поступило 20 заявок; обслужено x1=12.

Выполним аналогично еще пять испытаний, получим x2=15, x3=14, x4=12, x5=13, x6=15.

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

a *=hello_html_21eb1aee.gif=(2*12+13+14+2*15)/6=13,5.


Задания


Вариант 1


  1. Система состоит из двух блоков, соединенных последовательно. Первый блок содержит три элемента: А, В, С, а второй- два элемента: D, E. Элементы каждого блока соединены параллельно.

а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,9; Р(С)=0,85; Р(D)=0,7; P(E)=0,6;

б) найти абсолютную погрешность Р-Р*, где Р- надежность системы, вычисленная аналитически. Произвести 15 испытаний.


  1. В двухканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f()=4e-4 . Длительность обслуживания каждой заявки равна 1 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=8 мин.


Вариант 2


  1. Система состоит из двух блоков, соединенных последовательно. Первый блок содержит два элемента: А, В, второй- три элемента: С, D, E. Элементы первого и второго блоков соединены параллельно.

а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,9; Р(С)=0,7; Р(D)=0,75; P(E)=0,8;

б) найти абсолютную погрешность Р-Р*, где Р - надежность системы, вычисленная аналитически. Произвести 15 испытаний.


  1. В трехканальную СМО с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f()=0,8e-0,8; время обслуживания заявок 1,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10мин.


Вариант 3


  1. Система состоит из двух блоков, соединенных последовательно. Первый блок содержит три элемента: А, В, С, а второй- два элемента: D, E. Элементы каждого блока соединены параллельно.

а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,9; Р(В)=0,5; Р(С)=0,95; Р(D)=0,8; P(E)=0,7;

б) найти абсолютную погрешность Р-Р*, где Р- надежность системы, вычисленная аналитически. Произвести 15 испытаний.


  1. В двухканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f()=5e-5 . Длительность обслуживания каждой заявки равна 1,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10 мин.


Вариант 4


  1. Система состоит из двух блоков, соединенных последовательно. Первый блок содержит два элемента: А, В, второй- три элемента: С, D, E. Элементы первого и второго блоков соединены параллельно.

а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,7; Р(С)=0,8; Р(D)=0,85; P(E)=0,6;

б) найти абсолютную погрешность Р-Р*, где Р - надежность системы, вычисленная аналитически. Произвести 15 испытаний.


  1. В трехканальную СМО с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f()=8 e-8; время обслуживания заявок 1мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=8 мин.


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


  1. В чем заключается суть имитационного моделирования?

  2. В чем заключаются достоинства и недостатки такого типа моделирования?

  3. Как применяется метод Монте-Карло?

  4. Какие способы получения случайных величин Вы знаете?



Практическое занятие№9

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


Цель занятия:

1.Научиться решать задачи в условиях полной неопределенности;

2.Научиться применять критерии Вальда, Сэвиджа, Гурвица.



Методические указания к выполнению заданий практического занятия


Основные понятия и методы теории принятия решений


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


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

ТПР, как любая научная дисциплина, оперирует определенными понятиями и определениями.

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

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

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

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

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

Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся АС.

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Фиксированные факторы, значения которых известны исследователю. Им соответствуют детерминированные задачи, характеризующиеся тем, что каждой стратегии, выбираемой ОС, отвечает единственный результат.

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

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


  1. Основные этапы решения задач ТПР


Несмотря на большое разнообразие задач ТПР, им всем присущи следующие основные этапы:

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

  2. Построение мат. модели.

  3. Нахождение метода решения.

  4. Проверка и корректировка модели.

  5. Реализация найденного решения на практике.


ПОНЯТИЕ ИГРЫ С ПРИРОДОЙ


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

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

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


ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ ПОЛНОЙ НЕОПРЕДЕЛЕННОСТИ


Неопределенность, связанную с отсутствием информации о вероятностях состоянии среды (природы), называют «безнадежной» или «дурной».

В таких случаях для определения наилучших решении ис­пользуются следующие критерии: максимакса, Вальда, Сэвиджа, Гурвица. Альтернативные подходы, в частности принципы Байеса - Лапласа, рассматриваются в разд. 6.2.1.

Применение каждого из перечисленных критериев проиллю­стрируем на примере матрицы выигрышей (3.1) или связанной с ней матрицы рисков (3.2).

Критерий максимакса. С его помощью определяется страте­гия, максимизирующая максимальные выигрыши для каждого состояния природы. Это критерий крайнего оптимизма. Наилучшим признается решение, при котором достигается максималь­ный выигрыш, равный hello_html_m72c618b2.gif.

Нетрудно увидеть, что для матрицы А наилучшим решением будет А1, при котором достигается максимальный выигрыш - 9.

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

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

Выбирается ре­шение, для которого достигается значение hello_html_m7e5fa824.gif.

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

Критерий минимаксного риска Сэвиджа. Выбор стратегии аналогичен выбору стратегии по принципу Вальда с тем отличием, что игрок руководствуется не матрицей выигрышей А (3.1), а матрицей рисков R (3.2):

hello_html_56cb6722.gif

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

hello_html_53f92c76.png

При p = 0 критерий Гурвица совпадает с максимаксным кри­ерием, а при р = 1 - с критерием Вальда.


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


Пример: Имеются четыре варианта (проекта) оснащения предприятия современным техническим оборудованием hello_html_5e7c113c.gif. Четырьмя рабочими группами hello_html_m1639d796.gif проведена экспертиза этих проектов и определена производственная эффективность hello_html_6a6262a0.gif каждого варианта. Требуется выбрать лучший проект, используя критерии Вальда, Сэвиджа, Гурвица.


Варианты оснащения

Состояние «природы»

S1

S2

S3

S4

R1

16

29

16

26

R2

15

12

22

12

R3

27

14

28

12

R4

27

30

15

26


Решение:

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

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

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


Величины риска определяются следующими выражениями:

rij = hello_html_m59c4c3b5.gifаij - аij = j - aij,

где аij – размер «выигрыша» при выборе i–й стратегии при j–м состоянии «природы»; j - максимальный «выигрыш» для j–й обстановки; rij - величина риска при выборе i–й стратегии при j–й обстановке. Составим матрицу рисков:



S1

S2

S3

S4

R1

11

1

12

0

R2

12

18

6

14

R3

0

16

0

14

R4

0

0

13

0


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


Критерий Вальда – это максиминный критерий крайнего пессимизма, или наибольшей осторожности, перестраховки. Такой подход характерен для того, кто очень боится проиграть и считает природу разумным, вредным и агрессивным конкурентом, назло мешающим нам достигнуть успеха. В этом случае оптимальной стратегией для игрока Ri будет чистая стратегия R, при которой наименьший «выигрыш» будет максимальным, т.е. при которой гарантируется выигрыш, в любом случае не меньший, чем нижняя цена игры с природой:

V = hello_html_m59c4c3b5.gifhello_html_m754cd3e.gifаij.

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

1 = 16; 2 = 12; 3 =12; 4 = 15.

Наилучший проект R1, дает максимальный (из минимальных) «выигрыш» в размере 16.


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

S = hello_html_m37d251d6.gifhello_html_2339ccfb.gifrij.

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

r1 = 12, r2 = 18, r3 = 16, r4 = 13.

Наилучший проект R1 допускает минимальный риск (из максимальных) в размере 12.


Критерий Гурвица является линейной комбинацией пессимистической и оптимистической позиций. Стратегия выбирается из условия

G = hello_html_m59c4c3b5.gif{k hello_html_m754cd3e.gifаij + (1 - k) hello_html_2339ccfb.gifаij},

где k – коэффициент «пессимизма».

Коэффициент k меняется от 0 до 1, не принимая этих граничных значений (0 < k < 1). Коэффициент k выбирается на основании опыта или из субъективных соображений. Чем опаснее ситуация, тем менее мы склонны к риску, тем больше мы хотим подстраховаться, а значит, тем ближе к единице выбирается k. При k = 1 критерий Гурвица превращается в критерий Вальда, а при k = 0 – в критерий «крайнего оптимизма».


По условию k =α= 0,45, тогда

0,45 16 + 0,55 12 = 23,05

0,45 12 + 0,55 18 =22,35

0,45 12 + 0,55 16 =21,25

0,45 15+ 0,55 13 =22,6

Наилучший проект R4 дает «выигрыш» в размере 22,6.


Вывод: По большинству критериев наилучшим проектом является R4.



Задания


Вариант 1

Решить задачу.

Имеются четыре варианта (проекта) оснащения предприятия современным техническим оборудованием hello_html_5e7c113c.gif. Четырьмя рабочими группами hello_html_m1639d796.gif проведена экспертиза этих проектов и определена производственная эффективность hello_html_6a6262a0.gif каждого варианта. Требуется выбрать лучший проект, используя критерии Вальда, Сэвиджа, Гурвица.


Варианты оснащения

Состояние «природы»

S1

S2

S3

S4

R1

17

18

16

24

R2

23

14

25

15

R3

11

14

20

18

R4

20

22

10

10


Вариант 2

Решить задачу.

Имеются четыре варианта (проекта) оснащения предприятия современным техническим оборудованием hello_html_5e7c113c.gif. Четырьмя рабочими группами hello_html_m1639d796.gif проведена экспертиза этих проектов и определена производственная эффективность hello_html_6a6262a0.gif каждого варианта. Требуется выбрать лучший проект, используя критерии Вальда, Сэвиджа, Гурвица.


Варианты оснащения

Состояние «природы»

S1


S1


R1

22

R1

22

R1

R2

21

R2

21

R2

R3

13

R3

13

R3

R4

27

R4

27

R4



Вариант 3

Решить задачу.

Имеются четыре варианта (проекта) оснащения предприятия современным техническим оборудованием hello_html_5e7c113c.gif. Четырьмя рабочими группами hello_html_m1639d796.gif проведена экспертиза этих проектов и определена производственная эффективность hello_html_6a6262a0.gif каждого варианта. Требуется выбрать лучший проект, используя критерии Вальда, Сэвиджа, Гурвица.


Варианты оснащения

Состояние «природы»

S1

S2

S3

S4

R1

14

17

29

22

R2

28

16

19

23

R3

11

23

24

22

R4

15

25

27

13



Вариант 4

Решить задачу.

Имеются четыре варианта (проекта) оснащения предприятия современным техническим оборудованием hello_html_5e7c113c.gif. Четырьмя рабочими группами hello_html_m1639d796.gif проведена экспертиза этих проектов и определена производственная эффективность hello_html_6a6262a0.gif каждого варианта. Требуется выбрать лучший проект, используя критерии Вальда, Сэвиджа, Гурвица.


Варианты оснащения

Состояние «природы»

S1

S2

S3

S4

R1

22

21

18

28

R2

26

19

13

26

R3

21

19

22

15

R4

11

24

24

27


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


  1. Дайте определение ТПР.

  2. Опишите типы задач ТПР

  3. Опишите основные этапы решения задач ТПР с пояснением всех этапов.

  4. Дайте определение «игры с природой»

  5. Какими метолами решаются задачи в условиях неопределенности?

  6. Опишите критерии Вальда, Сэвиджа, Гурвица.



Практическое занятие№10

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


Цель занятия:

  1. Научиться применять МНК для линейного сглаживания данные.

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


Методические указания к выполнению заданий практического занятия


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

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


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

1. Если hello_html_278687bc.gif - линейная функция, т.е. hello_html_m6a2639f3.gif, то hello_html_2de7beea.gif, неизвестные параметры hello_html_447dedc1.gifопределяются из системы

hello_html_3f62caa2.gif(1)

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


Система (1) называется системой нормальных уравнений.


2. Если hello_html_278687bc.gif - квадратичная функция, т.е. hello_html_65d0ccfd.gif, то hello_html_m65b8036d.gif, неизвестные параметры hello_html_1df38be4.gifопределяются из системы нормальных уравнений:

hello_html_2864e214.gif(2)


Пример 1.

С помощью МНК подобрать параметры a и b линейной функции hello_html_m6a2639f3.gif, приближенно описывающей следующие опытные данные.

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


hello_html_m758c9fab.gif

0

1

1,5

2,1

3

hello_html_575c2e83.gif

2,9

6,3

7,9

10

13,2


Решение:

Параметры hello_html_m770c8044.gif и hello_html_m46559856.gif искомой функции найдем из системы нормальных уравнений. Для этого перепишем ее в следующем виде:

hello_html_3f62caa2.gif

Для решения задачи составим таблицу.



hello_html_m44b4eb0.gif

hello_html_m303da3ac.gif

hello_html_m5277f90c.gif

hello_html_m31819a07.gif

1

0

2,9

0

0

2

1,0

6,3

1

6,3

3

1,5

7,9

2,25

11,85

4

2,1

10,0

4,41

21

5

3,0

13,2

9,0

39,6

7,6

40,3

16,66

78,75


Тогда система нормальных уравнений примет вид:

hello_html_m64e037f8.gif.

Решим систему.

Для этого выразим hello_html_m46559856.gif из второго уравнения:

hello_html_3d3c8fc.gif

hello_html_5ddb64ba.gif

Подставим в первое уравнение:

hello_html_m7865fdd2.gif

hello_html_4ddf7c7.gif

hello_html_m5ef91a44.gif

hello_html_m19aae105.gif.

Отсюда hello_html_4acd3a39.gif.

Итак, hello_html_m19aae105.gif, hello_html_m2e24301a.gif, и, следовательно, искомая функция имеет вид:

hello_html_2e7314b.gif.


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


hello_html_m4aff4b72.png

Вывод:


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




Задание


Задание 1. С помощью МНК подобрать параметры a и b линейной функции hello_html_m6a2639f3.gif, приближенно описывающей следующие опытные данные. Построить полученную прямую и исходные точки в одной системе координат.


вариант


1

hello_html_m750b9a99.gif

1

3

4

5

6

8

hello_html_48b0f9d1.gif

6

4

4

2

3

2

2

hello_html_m750b9a99.gif

2

3

4

5

7

8

hello_html_48b0f9d1.gif

1

3

4

6

6

9

3

hello_html_m750b9a99.gif

1

2

4

6

7

8

hello_html_48b0f9d1.gif

7

6

4

5

3

3

4

hello_html_m750b9a99.gif

2

3

4

5

7

8

hello_html_48b0f9d1.gif

2

6

6

7

8

10



Задание 2. С помощью МНК подобрать параметры a и b квадратичной функции hello_html_57142c3e.gif, приближенно описывающей следующие опытные данные. Построить полученную линию и исходные точки в одной системе координат.


вариант


1

hello_html_m750b9a99.gif

2

2,5

3

3,5

4

4,5

hello_html_48b0f9d1.gif

4,2

2,5

6,2

7,5

2,6

1

2

hello_html_m750b9a99.gif

1

1,5

2

2,6

2,9

3,1

hello_html_48b0f9d1.gif

2,6

5,6

4,3

1,6

2,6

3,4

3

hello_html_m750b9a99.gif

2

3

3,6

3,8

4,2

4,6

hello_html_48b0f9d1.gif

0

2,3

2,5

2,9

1

4,5

4

hello_html_m750b9a99.gif

5

5,5

6

6,5

7

7,5

hello_html_48b0f9d1.gif

4,5

4,6

8,5

2,6

4,5

6,7



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

  1. Какова общая постановка задачи нахождения эмпирических формул?

  2. Каким образом можно оценивать качество приближения?

  3. Каким образом графически можно интерпретировать постановку задачи нахождения эмпирических формул?

  4. В чем сходство и различие постановки задачи метода наименьших квадратов и задачи интерполяции?

  5. Какие виды приближающих функций обычно применяются?

  6. В чем суть метода приближения таблично заданной функции по методу наименьших квадратов линейной функцией?

  7. Как сводится задача построения различных эмпирических формул к задаче нахождения линейной функции?



Литература


Основные источники


  1. Партыка Т.Л., Попов И.И. Математические методы. – М.: ФОРУМ : ИНФРА-М, 2012.

  2. Агальцов В.П., Волдайская И.В.. Математические методы в программировании: Учебник.- М.: ФОРУМ: ИНФРА-М, 2008.


Дополнительные источники


  1. Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2008.

  2. Попов А.М. Экономико-математические методы и модели :учебник.-М.: Юрайт, 2012


Интернет-ресурсы


  1. Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru

  2. Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru

  3. Информационно-справочная система. Форма доступа: http://dit.isuct.ru.

  4. Информационно-справочная система. Форма доступа: http://www.resolventa.ru




32



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


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Краткое описание документа:

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

Организация выполнения и контроля практических занятий по дисциплине «Математические методы и модели в экономике» является подготовительным этапом к сдаче дифференцированного зачета по данной дисциплине.

 

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

Автор
Дата добавления 28.01.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров870
Номер материала 346071
Получить свидетельство о публикации
Похожие материалы

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