Презентация на тему "Математические задачи"

Содержание

• 
  Слайд 1
  

  Задачи: _______________________________________ Коммивояжёра О ранце *Гамильтонов цикл – маршрут, включающий ровно единожды каждую вершину графа.

• 
  Слайд 2
  

  ЗАЧЕМ???

• 
  Слайд 3
  
• 
  Слайд 4
  

  Задача про рюкзак Математическая модель Ценность МАХ Объем ваших вещей

• 
  Слайд 5
  

  Жадный алгоритм ______________________________________________________________________________________________ i=− тип i-того предмета pi–ценность каждого xi wi – объем каждого xi   //удельная ценность xi План: упорядочить предметы по класть в рюкзак от большего к меньшему; Условие:  

• 
  Слайд 6
  

  Имеем задачу ЛП; 65 2) Решаем ее при помощи симплекс-метода; Z=3*018.75 3)!Если ∉ задачу 1 на две подзадачи 1(1) и 1(2): для 1(1) : для 1(2): 3.75 => 3 3.75 =>   ШАГ №1

• 
  Слайд 7
  

  ШАГ №2 Имеем новую ЗЛП 1(1): 65   Имеем новую ЗЛП 1(2): 65   2) Решаем каждую из них при помощи симплекс-метода 1(1): =0 Z=17.4 ! исп. ВЕТВЛЕНИЕ для (повтор ШАГ №2)   3) В результате имеем: уравнение 1(2) не имеет решений 3) В результате имеем:

• 
  Слайд 8
  

  Повторять ШАГ №2 до получения целочисленной функции для ∉Z   Z=max Ответ – для max(Zg)   Для данного примера: Zmax=14  

• 
  Слайд 9
  

  Задача коммивояжёра Математическая модель Длина МІN Для каждого рядка и столбца ‘Х’ ОДИН ui порядковый номер города

• 
  Слайд 10
  

  Метод ветвей и границ* Имеем целочисленную ЗЛП, заданную матрицей расстояний: 1) Найти – Вычесть 2)В редуцированной матрице: Найти – Вычесть 3)Получим полностью редуцированную матрицу  

• 
  Слайд 11
  

  Метод ветвей и границ* Полная редуцированная матрица: H0 – нижняя граница начальной матрицы  

• 
  Слайд 12
  

  Метод ветвей и границ* ШАГ №1 Начальная матрица Замена нулевых эл-тов на   Поиск ребра приведения )   Для ребра (1,4)   Элемент (1,4) заменяем на  

• 
  Слайд 13
  

  Метод ветвей и границ* ШАГ №1 2) Делим полученное множество решений на два подмножества (1,4) и (1*,4*): (1*,4*) H* =2+7=9   (1,4) ! Вычеркиваем столбец и рядок, на пересечении которых стоял (1,4) ! Элемент (4,1) заменяем на   H1 =2+7=99   Hn  

• 
  Слайд 14
  

  Метод ветвей и границ* №2 №3 ОТВЕТ: (1,4),(4,2),(2,3),(3,5),(5,1)

• 
  Слайд 15
  

  (1,4) (4,2) (2,3) (3,5) (5,1)

• 
  Слайд 16
  

  ЗАДАЧА 4 3   О ранце Коммивояжера

• 
  Слайд 17
  

  Автор: студент группыИК-61 Корзун Илья Михайлович