Задача о коммивояжере

 

      Найти:     - целевая функция;

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

      Построим  ОДР. Возьмём первое неравенство: 3x₁ + 2x₂ ³ 10– полуплоскость, границей которой является прямая 3x₁ + 2x₂ = 10. Прямая строится по двум точкам. Для нахождения координат точки, лежащей на прямой можно зафиксировать любое значение для одной их переменных, а значение другой переменной определить из уравнения прямой. Для удобства проведения вычислений возьмём x₁=0 , тогда x₂ = 5, то есть одна из лежащих на прямой точек имеет координаты (0; 5). Для определения второй точки зафиксируем значение x₂=2 , тогда x₁ =2, то есть координаты второй точки (2; 2). Через полученные 2 точки проведём прямую. Далее необходимо определить с какой стороны построенной прямой находится искомая полуплоскость. Для этого достаточно взять координаты любой точки, не лежащей на прямой, и подставить в уравнение полуплоскости. Если неравенство выполняется, значит, искомая полуплоскость лежит с той же стороны прямой, что и выбранная точка. Если неравенство не выполняется, значит, наоборот, выбранная точка не лежит в искомой полуплоскости, то есть искомая полуплоскость находится с другой стороны прямой. В нашем случае возьмём, например, точку (1; 1) и подставим в неравенство, определяющее полуплоскость: 3 * 1 + 2*1 ³ 10. Неравенство не выполняется, значит, точка (1; 1) не лежит в искомой полуплоскости, то есть искомая полуплоскость находится правее прямой 3x₁ +2 x₂ = 10. Условия неотрицательности также задают полуплоскости: x₁  ³ 0 – полуплоскость правее оси Оx₂, x₂  ³  0 - полуплоскость выше оси Оx₁.

      Также возьмём второе неравенство: 4x₁ + 6x₂ ³ 20– полуплоскость, границей которой является прямая 4x₁ + 6x₂ = 20. Возьмём x₁=2 , тогда x₂ = 2, то есть одна из лежащих на прямой точек имеет координаты (2; 2). Для определения второй точки зафиксируем значение x₂=0 , тогда x₁ =5, то есть координаты второй точки (5; 0). Через полученные 2 точки проведём прямую.

      Возьмём третье неравенство: 1x₁ + 3x₂ ³ 7– полуплоскость, границей которой является прямая 1x₁ + 7x₂ = 7. Возьмём x₁=1 , тогда x₂ = 2, то есть одна из лежащих на прямой точек имеет координаты (1;2). Для определения второй точки зафиксируем значение x₂=0 , тогда x₁ =7, то есть координаты второй точки (7; 0). Через полученные 2 точки проведём прямую.

      График  представлен на рисунке 6.

      Рисунок 6 – Графическое решение задачи 

      Пересечение всех полуплоскостей и есть искомая  ОДР, в нашем примере это область  ABКF - неограниченная область, слева и снизу ограниченная осями и прямыми, уравнения которых получены из уравнений ограничений заменой знаков неравенств на знаки равенства.

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

      Далее строим вектор-градиент целевой функции. Для этого строим            точку (3; 4). Вектор-градиент будет выходить из точки (0; 0) и заканчиваться в точке (3; 4). 

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

      

      получим координаты точки В=(2;2). Значение целевой функции в этой точке равно 3*2+4*2 = 16. Соответственно, решив систему уравнений

      

      получим координаты точки С=(3,1;1,3). Значение целевой функции в этой точке равно 3*3,1+4*1,3=14,5.

      Таким образом,  оптимальный состав  удобрения включает в себя 3,1 кг обычного удобрения и 1,3кг улучшенного удобрения. Стоимость такого рациона наименьшая и равна 14,5 рублям.

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

      Задача 2. Исследовать динамику экономического показателя на основе анализа одномерного временного ряда 

      В течении 9 последовательных недель фиксировался спрос Y(t), млн.р на кредитные ресурсы финансовой компании.

      Требуется:

1. Проверить наличие аномальных наблюдений
2. Построить линейную модель Y(t)=a₀+a₁*t, параметры которой оценить МНК(Y\t)-расчетные, смоделированные значения временного ряда
3. Оценить адекватность построенных моделей, используя свойство независимости остаточной компоненты, случайности и соответствия нормальному закону распределения(при использовании R\S- критерия взять табулированные границы 2,7-3,7)
4. Оценить точность моделей на основе использования средней относительной ошибки аппроксимации
5. По построенной модели осуществить прогноз спроса на следующие 2 недели(доверительный интервал прогноза рассчитать  при доверительной вероятности Р=70 %)
6. Фактические значения показателя, результаты моделирования и прогнозирования представить графически

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

Решение:

Расчетные данные представлены в таблице 3:

 

       
 
 
 
 
 
Задача 3. Рассчитать параметры моделей экономически выгодных размеров заказываемых партий. 

      Объем продаж магазина составляет в год 2000 упаковок супа в пакетах. Величина спроса равномерно распределена в течении года. Цена одного пакета равна 2 рубля. За доставку заказа владелец магазина должен заплатить 50 рублей. Время доставки заказа от поставщика составляет 12 рабочих дней. По оценкам специалистов издержки хранения в год составляют 4 рубля за 1 пакет. Необходимо определить сколько пакетов должен заказать владелец магазина для одной поставки, частоту заказов, точку заказа. Известно, что магазин работает 300 дней в году. Построить график общих годовых затрат.

      T=300 р.д./год;

      М=2000 пак/год

      С=2 руб/пак.;

      h= 4 руб/год;

      К= 50 руб/заказ;

      t=12  дней.

      Решение:

      Определим Количество пакетов супа в одной  поставки:

      

      Определим общие годовые затраты:

      

      Строим  график общих годовых затрат по данным представленным в таблице 7.

      Таблица 7 – Данные для построения графика  общих годовых затрат

      График  общих годовых затрат изображен  на рисунке 10.

      Рисунок 10 – График общих годовых затрат 

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

      Определим частоту заказов:

      

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

       лет, или 0,12*300=33,6 дней, или примерно 34 дня.

      Определим точку заказа:

        пакетов

      Каждый  раз, когда в магазине остается 80 пакетов супа, делается новый заказ  на поставку партии из 224 пакета.

 

       Список использованной литературы 

      

1. Дулькейт  В.И., Файзуллин Р.Т. Приближенное решение  задачи коммивояжера методом рекурсивного построения вспомогательной кривой // вычислительные методы в дискретной математике. Омск. Изд-во Омского гос.тех.ун-та. 2009. № 1 (3). С. 72-78. 
2. Ильина М.А., Копылова Н.Т., Поддубная М.Л., Кайгородова М.А. Экономико-математические методы и прикладные модели. Методические указания по выполнению лабораторной и контрольной работ (учебно-методические указания).Филиал ВЗФЭИ в г.Барнауле, 2009. -40с.
3. Экономико-математические методы и прикладные модели: Учебное пособие для вузов / Под ред. В.В. Федосеева. – М.: ЮНИТИ, 2000, 2001, 2002. – 391 с.
4. Орлова И.В. Экономико-математические методы и модели. Выполнение расчетов в среде Excel. Практикум. – М.: Финстатинформ, 2000. – 128 с.
5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004.
6. Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование. Учебное пособие. – М.: Вузовский учебник, 2007, 2008, 2009, 2010. – 365 с.
7. Прикладное программное обеспечение для решения экономических задач: лабораторный практикум. Екатеринбург: Изд-во Ур. гос.ун-та им. А.М. Горького, 2008. 30 с.
8. Задачи коммивояжера [Электронный ресурс] // URL: http://window.edu.ru/window_catalog/pdf2txt?p_id=26518&p_page=7.
9. Задача о коммивояжере [Электронный ресурс] // URL: http://mirslovarei.com/content_biz/Zadacha-O-Kommivojazhere-4474.html.
10. Надстройка Microsoft Excel «Поиск решения» [Электронный ресурс] // URL: http://office.microsoft.com/ru-ru/excel-help/HP005198443.aspx.
11. Практическое применение задачи коммивояжера [Электронный ресурс] // URL: http://lmatrix.ru/news2/news2_4.html