Мурманского государственного "МУРМАНСКИЙ технического университета
ГОСУДАРСТВЕННЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ"
Кафедра информационных систем и прикладной математики Методические указания рассмотрены и одобрены кафедрой информационных систем и прикладной математики апреля 2013 г., протокол № Математические методы и компьютерное Рецензент – Шиманский Сергей моделирование в торговом деле Александрович, доцент кафедры информационных систем и прикладной математики Мурманского государственного технического Методические указания и контрольные университета задания для студентов заочной формы обучения по направлению 100700. Электронное издание подготовлено в «Торговое дело»
авторской редакции Мурманский государственный технический университет 183010, Мурманск, ул. Спортивная д. тел. (8152) 25-40- Уч.-изд. л. _ Заказ Мурманский Мурманск государственный 2014 технический университет,
ОГЛАВЛЕНИЕ
ОБЩИЕ ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ УКАЗАНИЯ
ТЕМАТИЧЕСКИЙ ПЛАН
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
СОДЕРЖАНИЕ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ИЗУЧЕНИЮ ТЕМ
ДИСЦИПЛИНЫ
СПРАВОЧНЫЙ МАТЕРИАЛ
ВОПРОСЫ К ЭКЗАМЕНУ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ И ОФОРМЛЕНИЮ
КОНТРОЛЬНОЙ РАБОТЫ
КОНТРОЛЬНАЯ РАБОТА
ОБЩИЕ ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ УКАЗАНИЯ
Настоящие методические указания составлены на основе ФГОС ВПО по направлению 100700.62 «Торговое дело», утвержденного Министерством образования и науки 22 декабря 2009 г., приказ № 787 и рабочего учебного плана данного направления.
Целью дисциплины «Математические методы и компьютерное моделирование в торговом деле» является ознакомление с классификацией математических моделей и методов, применяемых в экономике для оптимизации процессов и принятия управленческих решений, обоснованно выбрать математический метод для решения поставленной задачи.
Задачи изложения и изучения дисциплины – дать необходимые знания по основам математики и теории вероятностей для решения задач в профессиональной деятельности.
Процесс изучения дисциплины «Математические методы и компьютерное моделирование в торговом деле» направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО по специальности 100700.62 «Торговое дело»:
а) общекультурных (ОК):
– осознанием сущности и значением информации в развитии современного общества; владением основными методами и средствами получения, хранения, переработки информации; навыками работы с компьютером как средством управления информацией (ОКб) профессиональных (ПК):
– способностью применять основные законы социальных, гуманитарных, экономических и естественно-научных наук в профессиональной деятельности, а также методы математического анализа и моделирования, теоретического и экспериментального исследования; владением математическим аппаратом при решении профессиональных проблем (ПК-1);
– готовностью анализировать, оценивать и разрабатывать стратегии организации (ПК-14);
– способностью разрабатывать проекты профессиональной деятельности (торговотехнологические, и/или маркетинговые, и/или рекламные, и/или логистические процессы) с использованием информационных технологий (ПК-18);
– готовностью участвовать в реализации проектов в области профессиональной деятельности (коммерческой, или маркетинговой, или рекламной, или логистической, или товароведной) (ПК-19).
В результате изучения дисциплины студент должен:
– классификацию математических моделей, применяемых в экономике для оптимизации процессов и принятия управленческих решений;
принципы оптимальности в экономике, ситуации принятия управленческих решений – обоснованно выбрать математический метод для решения поставленной задачи;
строить линейные модели многоотраслевой экономики, торговли – методами математического анализа и моделирования, математическим аппаратом при решении профессиональных проблем.
Общая трудоемкость дисциплины составляет _4зачетных единиц, 144 часов.
№ Содержание разделов (модулей), тем Количество часов, Компетенции программирование.
математических методов в торговом деле. Классификация задач. Системы линейных неравенств. Линейные задачи оптимизации.
Построение математических моделей прямой и двойственной задач Графический метод решения.
Симплексный метод. Теория двойственности, теоремы двойственности. Экономическая интерпретация двойственных переменных. Экономический анализ решения задачи линейного программирования.
Сбалансированность транспортной задачи. Построение начального допустимого плана. Метод наименьшего и наибольшего элемента. Метод потенциалов. Задачи, сводящиеся к транспортной.
программирование.
программирования. Метод ветвей и границ. Задача построения оптимального целого ассортимента решение. Игры с природой. Критерии Байеса, Лапласа, Вальда, Сэвиджа, Модуль 4. Динамическое программирование.
Принцип оптимальности Беллмана.
Задача распределения капитала на 1 и года. Задачи управления запасами.
программирование.
Аналитический и геометрический методы решения задач нелинейного программирования. Метод множителей Лагранжа.
операций : учеб. пособие 2 Исследование операций в под ред. Н. Ш. Кремера М.: Market DS экономике : учеб. пособие экономистов: учебное пособие для вузов математические методы и прикладные модели методические указания и
СОДЕРЖАНИЕ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ИЗУЧЕНИЮ ТЕМ
ДИСЦИПЛИНЫ
Содержание темы: Основные определения и задачи линейного программирования. Построение математических моделей прямой и двойственной задач. Графический метод решения.
Симплексный метод. Теория двойственности, теоремы двойственности. Экономическая интерпретация двойственных переменных. Экономический анализ решения задачи линейного программирования.
Цели изучения темы: освоить основные понятия линейного программирования. Научиться составлять математические модели. Научиться решать задачи графическим методом, симплекс-методом.
Методические рекомендации по изучению темы: при выполнении заданий обратить внимание на частные случаи решений.
Рекомендуемая литература: основная: [1-4].
Вопросы для самопроверки 3. Математическая модель прямой задачи 4. Математическая модель двойственной задачи 5. Математическая модель прямой задачи в стандартном виде 6. Графический способ решения 7. Симплекс-метод решения задач линейного программирования 9. Теоремы двойственности Содержание темы: Сбалансированность транспортной задачи. Построение начального допустимого плана. Метод наименьшего и наибольшего элемента. Метод потенциалов.
Задачи, сводящиеся к транспортной.
Цели изучения темы: освоить основные методы решения транспортной задачи. научиться решать транспортные задачи методом потенциалов, учитывая формулировку цели.
Методические рекомендации по изучению темы: прочитать рекомендуемую литературу. При выполнении заданий обратить внимание цель задачи и дополнительные условия.
Рекомендуемая литература: основная: [1-4].
Вопросы для самопроверки 1. Проверка задачи на сбалансированность 2. Проверка начального плана на вырожденность 3. Составление математических моделей 4. Метод наименьшего элемента Содержание темы: Задачи целочисленного программирования. Метод ветвей и границ.
Задача построения оптимального целого ассортимента изделий Цели изучения темы: освоить основные понятия целочисленного программирования. Научиться решать задачи графическим методом, методом ветвей и границ Методические рекомендации по изучению темы: при выполнении заданий обратить внимание на ограничения Рекомендуемая литература: основная: [1-4].
Вопросы для самопроверки 1. Составление математической модели 2. Требования к системе ограничений 3. Графический способ решения Содержание темы: Матричные игры. кооперативные игры. Цена игры. Решение антагонистических игр в чистых и смешанных стратегиях. Графическое решение. Аналитическое решение. Игры с природой. Критерии Байеса, Лапласа, Вальда, Сэвиджа, Гурвица.
Цели изучения темы: освоить основные понятия теории игр. Научиться решать задачи графически, аналитически.
Методические рекомендации по изучению темы: при выполнении заданий обратить внимание на особенности решения игр с природой.
Рекомендуемая литература: основная: [1-4].
Вопросы для самопроверки 1. Нахождение нижней и верхней цены игры 2. Определение игры в чистых и смешанных стратегиях 3. Составление математической модели 4. Алгоритм решения задачи теории игр графически.
5. Особенности решения задачи теории игр при помощи критериев.
Содержание темы: экономическая модель задачи динамического программирования. Метод рекуррентных соотношений. Принцип оптимальности Беллмана. Задача распределения капитала на 1 и 2 года. Задачи управления запасами.
Цели изучения темы: освоить основные понятия динамического программирования.
Научиться решать задачи, используя принцип Беллмана.
Методические рекомендации по изучению темы: при выполнении заданий обратить внимание на особенности применения принципа Беллмана.
Рекомендуемая литература: основная: [1-4].
Вопросы для самопроверки 1. Составление математической модели 3. Алгоритм решения задачи распределения капитала на 1 и 2 года.
4. Алгоритм решения задачи управления запасами.
Содержание темы: задача о замене оборудования.
Цели изучения темы: освоить решение экономической задачи о замене оборудования. Научиться решать задачу о замене оборудования Методические рекомендации по изучению темы: при решении задачи использовать принцип Беллмана Рекомендуемая литература: основная: [1-4].
Вопросы для самопроверки 1. Составление математической модели 2. Схема принципа Беллмана 3. Алгоритм решения задачи о замене оборудования Содержание темы: Общая постановка задачи. Аналитический и геометрический методы.
Метод множителей Лагранжа.
Цели изучения темы: освоить основные понятия нелинейного программирования. Научиться решать задачи аналитическим, графическим методами, методом множителей Лагранжа.
Методические рекомендации по изучению темы: для изучения данной темы необходимо повторить нахождение частных производных и экстремумов функций нескольких переменных Рекомендуемая литература: основная: [1-4].
Вопросы для самопроверки 1. Геометрический метод решения 2. Аналитический метод решения 3. Алгоритм решения методом множителей Лагранжа.
СПРАВОЧНЫЙ МАТЕРИАЛ
Линейное программирование — наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
Определение Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.
В общем виде математическая модель задачи линейного программирования (ЛП) записывается как Z(x)=C1X1+C2X2 + …+СJXJ +...+СnXn max(min) при ограничениях:
где Xi — неизвестные; aij, bj, Ci — заданные постоянные величины.
Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.
Математическая модель в более краткой записи имеет вид Z(x) = Ci Xi max(min) при ограничениях:
Определение Допустимым решением (планом) задачи линейного программирования называется вектор X = (х1, х2,,...хn, ), удовлетворяющий системе ограничений.
Множество допустимых решений образует область допустимых решений (ОДР).
Определение Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования и обозначается Хопт.
Базисное допустимое решение Является опорным решением, где r - ранг системы ограничений.
Виды математических моделей ЛП Математическая модель задачи ЛП может быть канонической и неканонической.
Определение Если все ограничения системы заданы уравнениями и переменные Xj неотрицательные, то такая модель задачи называется канонической.
Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную хn+i.
Если знак неравенства, то — минус. В целевую функцию балансовые переменные не вводятся.
Чтобы составить математическую модель задачи ЛП, необходимо:
— вести обозначения переменных;
— сходя из цели экономических исследований, составить целевую функцию;
— считывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений.
Каждая задача линейного программирования, называемая прямой или исходной, тесно связана с другой задачей, ее называют двойственной.
Математические модели этих задач имеют следующий вид.
Эти задачи экономически могут быть сформулированы следующим образом.
Прямая задача: сколько и какой продукции хi(i-1, 2, …, n) надо произвести, чтобы при заданных стоимостях единицы продукции Сi, объемом имеющихся ресурсов bj (j=1,2,…, m) и нормах расхода ресурсов аij максимизировать выпуск продукции в стоимостном виде.
Двойственная задача: какова должна быть оценка единицы каждого ресурса yj (j=1, 2,…, m), чтобы при заданных bj, ci и аij минимизировать общую оценку затрат на все ресурсы.
Правила построения двойственной задачи по имеемой прямой задаче:
1) Если прямая задача решается на максимум, то двойственная задача решается на минимум; если прямая задача решается на минимум то двойственная на максимум;
2) В задаче на максимум ограничения неравенства имеют вид –, а в задаче на минимум 3) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, в другой модели ограничению двойственной задачи соответствует переменная 4) Матрица системы ограничений двойственной задачей получается из матрицы из матрицы систем ограничений прямой задачи транспонированием;
5) Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи и наоборот;
6) Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничениенеравенство, в противном случае – как ограничение равенство;
7) Если какое либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не Пример:
В этой задаче y1, y2, y3 – предельные оценки стоимости единицы каждого ресурса, целевая функция – оценка стоимости всех ресурсов, а каждое ограничение есть условие, что оценка ресурсов, идущих на производство продукции x1, x2, x3, не менее чем цена единицы продукции.
Взаимосвязь решений прямой и двойственной задач находится из трех теорем двойственности.
Первая теорема двойственности:
Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций совпадают Z(X)=Z'(Y). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание первой теоремы двойственности: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения и оценок ресурсов, при этом полная стоимость продукта, полученного в результате реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадения, значений целевых функций для соответствующих решений пары двойственных задач достаточно для того, чтобы эти решения были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными только тогда, когда полная стоимость произведенной продукции и суммарная оценка ресурсов совпадает.
Оценки выступают как инструмент сбалансирования затрат и результатов.
Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, т.е. равенство общей стоимости продукции и ресурсов обуславливает убыточность всякого другого плана отличающегося от оптимального. Двойственные оценки позволяют сопоставлять и сбалансировать затраты и результаты производства.
Вторая теорема двойственности:
Для того чтобы план Х* и Y* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:
Эти условия называются условиями дополняющей нежесткости. Из них следует, что если какое-либо неравенство системы ограничений в одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующий элемент оптимального плана двойственной задачи должен равняться нулю. Если какой-либо элемент оптимального плана одной из задач положителен, то соответствующее ограничение в двойственной задаче её оптимальным планом должно обращаться в строгое равенство, т.е.
Аналогично, Экономически это означает, что если по некоторому оптимальному плану X*= x1, x2,..., xn производства расход j-го ресурса меньше его запаса bj, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод:
двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е.
полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.
Третья теорема двойственности:
Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи линейного программирования, т.е.
В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:
если b j 1, тогда Z ( x* ) y *, Экономическое содержание третьей теоремы двойственности: двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки yj часто называются скрытыми теневыми или маргинальными оценками ресурсов.
Решение задач линейного программирования графическим методом При решении задач линейного программирования геометрическим способом необходимо помнить, что визуализация решения достигается только при рассмотрении задачи с двумя переменными и небольшим количеством ограничений. Также желательно выбрать масштаб осей так, чтобы график был компактным, но было четко видно все точки пересечения ограничений.
С геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на которой достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста.
Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор grad Z на плоскости Х2ОХ2.
Этот вектор показывает направление наискорейшего изменения целевой функции.
Координатами вектора grad Z являются коэффициенты целевой функции Z(x).
Алгоритм геометрического метода решения задач ЛП.
Решение задач ЛП геометрическим методом осуществляется по следующему алгоритму:
1. Строим координатные оси Х1ОХ2 и с учетом коэффициентов математической модели выбираем масштаб.
2. Находим область допустимых решений (ОДР) системы ограничений математической модели.
3. Строим прямую целевой функции и показываем направление наискорейшего ее изменения (нормаль-grad L).
4. Линию целевой функции (линия уровня) перемещаем по направлению нормали для задач на максимум целевой функции и в противоположном направлении - для Перемещение линии уровня через ОДР производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений. Эта точка будет точкой экстремума, и будет определять единственное решение задачи ЛП.
Если окажется, что линия уровня совпадает с одной из сторон ОДР, то задача ЛП будет иметь бесчисленное множество решений.
Если ОДР представляет неограниченную область, то целевая функция – Задача ЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми.
«