Решение экономических задач методами дискретной математики

Таблица 3РаботаНормальный режим работыМаксимальный режим работыПродолжительность,днейЗатраты,тыс. руб.Продолжительность,днейЗатраты,тыс. руб.1212019262263021373115107431602464541653378651904410074680428581651010926502257Требуется:Составить график проведения работ, определить критический путь и стоимость работ по переоборудованию цеха при нормальном режиме работ.2. Провести «сжатие» работ. Составим график проведения работРис.2 На проведения переоборудования необходимо 269 днейГрафик можно улучшить, если выполнять некоторые работы одновременно.Введем обозначения для работ(0,1) – подготовка и выпуск технического задания на переоборудование цеха;(1,2) – разработка мероприятий по технике безопасности;(1,4) – подбор кадров;(1,5) – заказ и поставка необходимого оборудования; (2,3) – заказ и поставку электрооборудования;(3,6) – установка оборудования;(5,6) – установку электрооборудования;(4,6) – обучение персонала;(6,7) – испытание и сдачу в эксплуатацию линии.Рис.3Критический путь: (0,1)(1,5)(5,6)(6,7). Продолжительность критического пути: 134. График улучшится на 269-134 = 135 дней. Пример. 3Транспортная сеть состоит из определённого количества узлов, часть из которых соединена магистралями.Стоимость перевозки груза между отдельными пунктами указана на схеме. Двигаться по возможным маршрутам можно только слева направо. Найдите оптимальный маршрут перевозки груза из первого пункта в конечный пункт.Рис.4Разобьём транспортную сеть на n = 5 поясов (рис. 5), считая, что конкретный пункт принадлежит k-му поясу (k = 1, 2, 3, 4, 5), если попасть в него из начального пункта можно ровно за (k – 1) шаг.Обозначим m = 12 – число пунктов транспортировки;i – пункт, из которого осуществляются перевозки, то есть i = 1,..,11;j – пункт, в который доставляется груз, то есть j = 2,…,12;cij – стоимость перевозки груза из пункта i в пункт j;Fk(i) – минимальные затраты на перевозку груза на k-ом шаге из i-го пункта до конечного.Рис.5Переменной состояния в данной задаче на k-ом шаге является номер i пункта, принадлежащего k-му поясу. Находясь в этом пункте, мы принимаем решение о перемещении груза в один из пунктов (k+1)-го пояса, номер j которого является переменной управления на k-ом шаге.Функция Беллмана для данной задачи имеет вид:при k = n, ,при k =n–1,…,1 .Условная оптимизация.Первый шаг. k = 5. Из рисунка видно, что переменная состояния может принимать значения i5 = 10, 11,12. Составим вспомогательную таблицу 4, используя функцию Беллмана:Таблица 4i5j5F5(i5)13ci 13101010131112121312161513Второй шаг. k = 4. Из рисунка видно, что переменная состояния может принимать значения i4 =  8, 9.Составим вспомогательную таблицу 5, учитывая, что .Таблица 5i4j4F4(i4)101112ci 10 + F5(10)ci 11 + F5(11)ci 12 + F5(12)818 + 10 =28––2810914+10 =2415+12=2710+16=262410Третий шаг. k = 3. Из рисунка видно, что переменная состояния может принимать значения i3 = 5, 6,7. Составим вспомогательную таблицу 6, учитывая, что .Таблица 6i3j3F3(i3)89ci 8 + F4(8)ci 9 + F4(9)513+28 = 41–41865+28 =3313+24 =373387–11+24 =35359Четвёртый шаг. k = 2. Из рисунка 5 видно, что переменная состояния может принимать значения i2 = 2, 3, 4.Таблица 7i2j2F2(i2)567ci 5 + F3(5)ci 6 + F3(6)ci 7 + F3(7)25+41=468+33 = 41–41638+41=497+33 = 406+35 = 414064––15+35=50507Пятый шаг. k = 1. Из рисунка видно, что переменная состояния может принимать значения i1 = 1.Составим вспомогательную таблицу, учитывая, что .Таблица 5i1j1F1(i1)234ci 2 + F2(2)ci 3 + F2(3)ci 4 + F2(4)19+41=5011+40=513+50=53502Безусловная оптимизация.Определим компоненты оптимальной стратегии.Первый шаг. k = 1. По таблице 5 минимальные затраты на перевозку из первого пункта в конечный составляютF1(1) = 50.Этот результат достигается при движении из первого во второй пункт, то есть = 2.Второй шаг. k = 2. По таблице 4 минимальные затраты на перевозку из второго пункта в конечный составляютF2(2) = 41.Этот результат достигается при движении из второго в шестой пункт, то есть = 6.Третий шаг. k = 3. По таблице 3 минимальные затраты на перевозку из третьего пункта в конечный составляютF3(6) = 33.Этот результат достигается при движении из шестого в восьмой пункт, то есть = 8.Четвёртый шаг. k = 4. По таблице 2 минимальные затраты на перевозку из четвёртого пункта в конечный составляютF4(8) = 20.Этот результат достигается при движении из восьмого в десятый пункт, то есть = 10.Пятый шаг. k = 5. По таблице 83 минимальные затраты на перевозку из пятого пункта в конечный составляютF5(10) = 17.Этот результат достигается при движении из десятого в двенадцатый пункт, то есть = 12.Таким образом, получен оптимальный маршрут (рис. 6) доставки груза:12681013.с минимальными затратами в размере:F* = c1,2 + c2,6 + c6,8 + c8,10 + c10,13 = 9 + 8 + 5 + 18 + 10 = 50.Рис. 6ВыводыВ реферате были рассмотрены некоторые примеры применения дискретной математики как математическая логика и теория графов. Было рассмотрено на конкретных примерах, как алгоритмы дискретной математики применяются в сфере экономики.В первой части реферата сделан обзор литературных источников по данной тематике. Во второй части приведено описание конкретных экономических методов, успешно применяемых в решении экономических задач. В третьей части на реальных примерах рассмотрено практическое применение теории графов в экономике. Составлены математические модели данных алгоритмов. Приведенные выше примеры показывают, что для экономистов большое значение имеет знание классической логики в будущей профессиональной деятельности. На основе знаний законов логики основываются принципы алгоритмизации, лежащие в основе программирования. Таким образом, дискретная математика играет важную роль в современном мире, так как имеет широкий спектр приложений в различных областях жизнедеятельности человека. Обучение дискретной математике для будущих специалистов экономической деятельности является многофункциональным, многоцелевым, многоуровневым процессом, который состоит в воздействии на элементы системы обучения, а также их связи. Список использованной литературыАндерсон Дж. Дискретная математика и комбинаторика – М. Вильямс, 2003.Гончарова Г.А., Мочалин А.А. Элементы дискретной математики – М., Форум – Инфра-М, 2003.Дискретная математика / М.С. Спирина, П.А. Спирин. – М.: Издательский центр «Академия», 2006. – 368с.Ерусалимский Я.М. Дискретная математика: Теория, задачи, приложения. – М.: Вузовская книга, 2005. – 268сКолмогоров А.Н., Драгалин А.Г. Математическая логика. – М. УРСС 2004.Коннова Д.А., Леликова Е.И., Мелешко С.В. Взаимодействие математики с экономикой // Современные наукоемкие технологии. – 2014. – № 5-2. – С. 159-161.Крон Р.В., Попова С.В., Долгих Е.В., Смирнова Н.Б. Линейная алгебра: учебное пособие // Международный журнал экспериментального образования. – 2014. – № 11-1. – С. 115.Крон Р.В., Попова С.В., Долгих Е.В., Смирнова Н.Б. Математика: учебное пособие // Международный журнал экспериментального образования. – 2014. – № 11-1. – С. 114-115.Кудрявцев В.Б. Конечная математика//БСЭ Ланина Н. Р. Дискретная математика: учебное пособие. В 2 ч. Ч.1 / Н.Р. Ланина. – Мурманск: Изд-во МГТУ, 1998. – 123 с.Мамаев И.И., Шибаев В.П. Активизация познавательной деятельности студентов при изучении математических дисциплин / Теоретические и прикладные проблемы современной педагогики. – 2012. – С. 62-67.Математическая логика. Типовые расчеты: методические указания и контрольные задания / сост.: Гулай Т.А., Мелешко С.В., Невидомская И.А. – Ставрополь: 2013. – 28 с.Мельников О.И. Обучение дискретной математике. – М.: Издательство ЛКИ, 2008. – 224с.Морозова О.В., Долгополова А.Ф., Попова С.В., Крон Р.В., Смирнова Н.Б., Долгих Е.В., Тынянко Н.Н. Комплект рабочих тетрадей по курсу высшей математики для экономических специальностей // Международный журнал экспериментального образования. – 2009. – № S4. – С. 22.Нефёдов В. Н., Осипова В. А.: "Курс дискретной математики", 1992 г.Нечепуренко М. И.: "Алгоритмы и программы решения задач на графах и сетях", 1990 г.Новиков Ф.А. Дискретная математика для программистов: учебник для вузов. 2-е изд. – СПб.: Питер, 2007.Осипова В.А. Основы дискретной математики. – М.: ФОРУМ: ИНФРА-М, 2006. – 160с.Соболева Т.С. Дискретная математика: учебник для студ. Вузов / Т. С. Соболева, А.В.Современный толковый словарь изд. «Большая Советская Энциклопедия» http://www.classes.ru/all-russian/russian-dictionary-encycl-term-27389.htm.Хаггарти Р. Дискретная математика для программистов – М. Техносфера, 2003.