Воротницкий Ю.И. Исследование операций. 2.Сетевые и транспортные модели. Целочисленное программирование. - презентация

1 Воротницкий Ю.И. Исследование операций

2 2. Сетевые и транспортные модели. Целочисленное программирование.

3 2. Сетевые модели Основные определения Сеть состоит из множества узлов (вершин), связанных дугами или ребрами. Сеть описывается парой множеств (N,A), где N – множество узлов, а А – множество ребер

4 2. Сетевые модели Основные определения Показанная на рисунке сеть описывается следующим образом: N={1,2,3,4,5} A={(1,3), (1,2), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)} 12345

5 2. Сетевые модели Основные определения С каждым типом сети связан определенный тип потоков. В общем случае потоки в сети ограничены пропускной способностью ее ребер C ij, которая в общем случае может быть как конечной, так и бесконечной (максимальный ток в цепи электропитания, пропускная способность телекоммуникационных каналов и т.д.) (C 13,C 31 )

6 2. Сетевые модели Основные определения Ребро называется направленным (ориентированным), если в одном направлении возможен только положительный поток, а в противоположном – только нулевой В этом случае ребро называют дугой (C 13,>0,C 31 =0)

7 2. Сетевые модели Основные определения В ориентированной сети все ребра ориентированы: N={1,2,3,4,5} A={(1,3), (2,1), (2,3), (2,4), (2,5), (4,3), (3,5), (4,5)} 12345

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

9 2. Сетевые модели Основные определения Связная сеть – такая сеть, у которой любые два узла связаны по крайней мере одним путем. Это – связная сеть: N={1,2,3,4,5} A={(1,3), (1,2), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)} 12345

10 2. Сетевые модели Основные определения Связная сеть – такая сеть, у которой любые два узла связаны по крайней мере одним путем. Это – тоже связная сеть: N={1,2,3,4,5} A={(1,2), (2,3), (2,5), (4,5)} 12345

11 2. Сетевые модели Основные определения Связная сеть – такая сеть, у которой любые два узла связаны по крайней мере одним путем. А эта сеть связной не является: N={1,2,3,4,5} A={(1,2), (3,4), (3,5), (4,5)} 12345

12 2. Сетевые модели Основные определения Деревом называется связная сеть, содержащая подмножество узлов исходной сети и не имеющая циклов. Пример дерева: N={1,2,4,5} A={(1,2), (2,5), (4,5)} 1245

13 2. Сетевые модели Основные определения Остовное дерево – дерево, содержащее все узлы сети. Пример остовного дерева: N={1,2,3,4,5} A={(1,3), (1,2), (2,4), (2,5)} 12345

14 2. Сетевые модели Представление сетей Сеть G=(N,A) может быть полностью определена простым перечислением множеств N и A. N={1,2,3,4,5} A={(1,3), (1,2), (2,4), (2,5)} Такой способ не позволяет легко анализировать свойства сетей 12345

15 2. Сетевые модели Представление сетей Матрица смежности. Любая сеть G=(N,A) с m узлами (вершинами) может быть представлена матрицей A(G)=[a ij ] размера m x m. Для этого узлы должны быть перенумерованы (или помечены метками порядкового типа v 1, v 2, …, v m ). a ij =1, если v i смежен с v j, в противном случае a ij =0. Для неориентированной сети G A(G) всегда будет симметричной матрицей (0,1) с нулями на диагонали. Для ориентированной матрицы G только один из элементов a ij, a ji может отличаться от нуля. При необходимости значения 0 и 1 в матрице можно заменить пропускными способностями или стоимостями путей.

16 2. Сетевые модели Представление сетей Матрица смежности

17

18 2. Сетевые модели Представление сетей Матрица инцидентности. Любая сеть G=(N,A) с m узлами и n ребрами может быть представлена матрицей I(G)=[b ij ] размера m x n. Для этого узлы должны быть перенумерованы (или помечены метками порядкового типа v 1, v 2, …, v m ), а ребра также перенумерованы (или помечены метками порядкового типа e 1, e 2, …, e n ),. b ij =1, если v i инцидентен e j, в противном случае b ij =0. Каждый j-й столбец матрицы I(G), соответствующий j-му ребру, всегда содержит ровно две единицы. Никакие два столбца не могут быть идентичны. Матрица инцидентности полезна для решения сетевых задач, касающихся анализа циклов.

19 2. Сетевые модели Представление сетей Матрица инцидентности

20 2. Сетевые модели Представление сетей Векторы смежности. Любая сеть G=(N,A) с m узлами может быть представлена матрицей С(G)=[с ij ] размера m x m-1. Для этого узлы должны быть перенумерованы (или помечены метками порядкового типа v 1, v 2, …, v m ). Каждая i-я строка матрицы соответствует i-му узлу. Значения элементов i-й строки c ij – номера узлов, смежных с v i. Каждая i-я строка представляет собой вектор смежности для i-го узла сети. Порядок элементов в векторе смежности в общем случае произволен. Векторы смежности целесообразно использовать, когда задача решается за небольшое число просмотров каждого ребра в G.

21 2. Сетевые модели Представление сетей Вектор смежности

22 2. Сетевые модели Представление сетей Списки смежности. Списки смежности – один из наиболее эффективных способов представления сети G=(N,A), где N – m вершин, А – n ребер. В этом случае сеть представляется с помощью m списков, каждый из которых может иметь от 0 до m-1 элемента. Информационное поле каждого элемента i-го списка содержит номер вершины, смежной с i-й Удобно использовать одномерный массив из m элементов, причем каждый элемент массива представляет собой линейный список, представляющий ненулевые компоненты вектора смежности для соответствующей вершины

23 2. Сетевые модели Представление сетей Списки смежности

24 2. Сетевые модели Постановки задач и базовые алгоритмы Основные классы задач: Проектирование сети минимальной длины (минимальной стоимости), соединяющей заданное множество узлов некоторой сети. Алгоритм нахождения минимального остовного дерева

25 2. Сетевые модели Постановки задач и базовые алгоритмы Основные классы задач: Нахождение кратчайшего маршрута (маршрута наименьшей стоимости) между двумя узлами существующей сети Алгоритм нахождения кратчайшего пути.

26 2. Сетевые модели Постановки задач и базовые алгоритмы Основные классы задач: Определение максимальной пропускной способности сети между заданными узлами (задача о максимальном потоке) Алгоритм определения максимального потока

27 2. Сетевые модели Постановки задач и базовые алгоритмы Основные классы задач: Нахождение потока наименьшей стоимости между заданными узлами при заданной максимальной пропускной способности путей Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью

28 2. Сетевые модели Постановки задач и базовые алгоритмы Основные классы задач: Задачи сетевого планирования Алгоритм нахождения критического пути

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

30 2. Сетевые модели Алгоритм построения минимального остовного дерева Заданы N={1,2,…m} – множество узлов сети. Заданы длины (стоимости) возможных дуг s ij, которые можно провести между узлами i и j. Необходимо соединить все узлы сети с помощью путей (дуг) наименьшей суммарной длины. Очевидно, что для этого необходимо построить дерево, связывающее все узлы с помощью дуг наименьшей общей длины (стоимости). Обозначим C k – множество узлов, соединенных алгоритмом после выполнения k-й итерации, D k – множество узлов сети, не соединенных с узлами множества C k после выполнения k- й итерации алгоритма.

31 2. Сетевые модели Алгоритм построения минимального остовного дерева Шаг 0. Положить С 0 = (пустое множество), D 0 =N. Шаг 1. Выбрать любой узел i из множества D 0 и определить С 1 ={i}, D 1 =N-{i}. Положить k=2. Шаг 2. Пока множество D 0 не является пустым, выполнить: Шаг 2.1. В множестве D k-1 выбрать узел j, который соединен самой короткой дугой с каким-либо узлом из С k-1. Шаг 2.2. C k =C k-1 +{j}, D k =D k-1 -{j}. Шаг 2.3. k=k+1. Шаг 3. Завершить работу.

32 2. Сетевые модели Алгоритм построения минимального остовного дерева. Задача построения опорной телекоммуникационной сети Банк имеет в городе 6 крупных отделений. С целью создания корпоративной информационной системы необходимо связать их с помощью опорной оптоволоконной сети минимальной стоимости, полагая, что она определяется общей длиной коммуникаций. Расстояния между офисами известны. Разумеется, такая постановка задачи в значительной степени идеализирована: не учитываются параметры и стоимость коммуникационного оборудования в узлах сети, а также пропускная способность каналов; не учитывается, что прокладка по существующим телефонным канализациям дешевле, однако при этом могут существенно увеличиваться длины кабелей; не рассматривается необходимость резервирования каналов связи.

33 2. Сетевые модели Алгоритм построения минимального остовного дерева. Задача построения опорной телекоммуникационной сети

34 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Банк имеет в городе 6 крупных отделений, соединенных оптоволоконными линиями передачи. Необходимо организовать видеоконференцсвязь между центральным офисом (узел 1) и отделениями. Для этого необходимо предложить схему статической маршрутизации пакетов, минимизирующую времена задержек от узла 1 до каждого из остальных узлов. Средние времена задержек при передаче от узла к узлу в условиях нормальной загрузки сети известны. Разумеется, эта задача тоже идеализирована. В частности: не учитывается влияние изменения самого трафика видеоконференций на средние времена задержек; не учитываются другие параметры, влияющие на качество видеоконференцсвязи (вариации задержек, вероятность потери пакетов).

35 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры

36 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Алгоритм Дейкстры. При переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через u i кратчайшее расстояние от исходного узла 1 до узла i, через d ij – длину ребра ( i,j ). Тогда для узла j определим метку [ u j, i ] следующим образом: [ u j, i ] = [ u i + d ij, i ]. Метки могут быть двух типов: временные и постоянные. Временная метка может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Статус временной метки заменяется на постоянный, когда станет очевидным, что не существует более короткого пути от исходного узла к данному.

37 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Алгоритм Дейкстры. Шаг 0. Исходному узлу (узел 1) присваивается метка [0,-]. Положить i =1. Шаг i. Вычислить временные метки [ u i + d ij, i ] для всех узлов j, которые можно достичь из узла i и которые не имеют постоянных меток. Если узел j уже имеет временную метку, полученную от другого узла k и если u i + d ij < u j, то заменить метку [ u j, k ] на [ u i + d ij, i ]. Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбрать метку [ u r, s ] с наименьшим значением расстояния среди всех временных меток (если их несколько – выбор произволен). Изменить статус этой метки на постоянную. Положить i=r и повторить шаг i.

38 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]временная 3[0+80,1] = [80,1]временная

39 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]временная 3[0+80,1] = [80,1]постоянная

40 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]временная 3[0+80,1] = [80,1]постоянная 4 5 6[80+450] = [530,3]временная

41 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]временная 5[ ,2]=[500,2]временная 6[80+450] = [530,3]временная

42 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]временная 5[ ,2]=[500,2]временная 6[80+450] = [530,3]временная

43 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]постоянная [500,2] <= [360+90,4] = [450,4]временная [530,3]<=[ ,4] =[480,4]временная

44 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]постоянная 5[360+90,4] = [450,4]временная 6[ ,4] =[480,4]временная

45 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]постоянная 5[360+90,4] = [450,4]постоянная 6[ ,4] =[480,4]постоянная

46 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]постоянная 5[360+90,4] = [450,4]постоянная 6[ ,4] =[480,4]постоянная

47 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]постоянная 5[360+90,4] = [450,4]постоянная 6[ ,4] =[480,4]постоянная Кратчайший путь между узлом 1 и любым узлом определяется начиная с узла назначения путем прохождения в обратном направлении с помощью информации, представленной в постоянных метках.

48 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры. Узел МеткаСтатус 1[0,-]постоянная 2[0+200,1] = [200,1]постоянная 3[0+80,1] = [80,1]постоянная 4[ ,2] = [360,2]постоянная 5[360+90,4] = [450,4]постоянная 6[ ,4] =[480,4]постоянная

49 2. Сетевые модели Нахождение кратчайшего пути. Принцип построения алгоритма Флойда. Алгоритм Флойда более общий: он приводит к нахождению кратчайших путей между любыми двумя узлами сети. Сеть с n узлами представляется в виде квадратной матрицы с n строками и n столбцами. Элемент ( i,j ) равен расстоянию d ij от узла i до узла j, которое имеет конечное значение, если узлы связаны дугой и равно бесконечности в противном случае. Основная идея метода. Пусть есть три узла i,j,k и заданы расстояния между ними. Если d ij + d jk k путем i -> j -> k. Такая замена (ее еще называют треугольный оператор) выполняется систематически в процессе выполнения алгоритма. j ik

50 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации потерь пакетов в корпоративной сети. Банк имеет в городе 6 крупных отделений, соединенных оптоволоконными линиями передачи. Необходимо организовать видеоконференцсвязь между центральным офисом (узел 1) и отделениями. Для этого необходимо предложить схему статической маршрутизации пакетов, минимизирующую потери пакетов на маршрутах от узла 1 до каждого из остальных узлов. Усредненные значения вероятностей доставки пакетов UDP от узла к узлу в условиях нормальной загрузки сети известны. Разумеется, эта задача тоже идеализирована. В частности: не учитывается влияние изменения самого трафика видеоконференций на вероятности доставки пакетов; не учитываются другие параметры, влияющие на качество видеоконференцсвязи.

51 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации задержек пакетов в корпоративной сети. Алгоритм Дейкстры p 12 p 24 p 13 p 36 p 25 p 46 p 45

52 2. Сетевые модели Нахождение кратчайшего пути. Задача минимизации потерь пакетов в корпоративной сети. Мы имеем дело с задачей нахождения не кратчайшего, а наиболее длиного пути. Проблема: вероятности не складываются, а умножаются. Эта проблема преодолевается, если заменить вероятности их логарифмами: d ij = log p ij. Теперь можно воспользоваться алгоритмом Дейкстры или алгоритмом Флойда.

53 2. Сетевые модели Нахождение кратчайшего пути. Задача о замене оборудования (Х. Таха) Компания по прокату автомобилей разрабатывает план обновления парка своих машин на 5 лет ( гг.). Каждый автомобиль должен прослужить не менее одного и не более трех лет. Стоимость замены автомобиля в зависимости от года покупки и срока эксплуатации приведена в таблице. Год покупки Стоимость замены в зависимости от срока эксплуатации 1 год 2 года 3 года

54 2. Сетевые модели Нахождение кратчайшего пути. Задача о замене оборудования (Х. Таха)

55 2. Сетевые модели Нахождение кратчайшего пути. Задача о рюкзаке Путешественник, собираясь в путь, пытается поместить в свой рюкзак, объемом 5 кубических футов, наиболее необходимые в путешествии вещи. Имеются три вещи объемом соответственно 2, 3 и 4 кубических фута, необходимость которых оценивается (по 100-балльной шкале) в 30, 50 и 70 баллов. Сформулируем эту задачу как сетевую, где необходимо найти самый длинный путь. Узлу в этой сети можно сопоставить пару чисел (i,v), где i – номер выбираемой вещи, а v – свободный объем рюкзака, оставшийся после выбора i-й вещи

56 2. Сетевые модели Нахождение кратчайшего пути. Задача о рюкзаке (3,x) 30 (2,x)(0,5)(1,x)

57 2. Сетевые модели Нахождение кратчайшего пути. Задача о рюкзаке Конечно, задача о рюкзаке может быть сформулирована как классическая задача линейного программирования (причем – целочисленного). Если объем рюкзака равен V, объем i -й вещи – v i, ее полезность – с i, а варьируемые переменные xi могут принимать значение 1 (вещь положили) или 0 (не положили) то имеем задачу: Впрочем, на самом деле, задача о рациональнной загрузке – классическая задача динамического программирования. Эта задача отнсится к классу задач, называемому задачи распредления ресурсов.

58 2. Сетевые модели Задача о максимальном потоке. Постановка задачи. Рассмотрим сеть трубопроводов для транспортировки сырой нефти от буровых скважин до нефтеперерабатывающих заводов. Каждый сегмент трубопровода имеет свою пропускную способность. Сегменты могут быть как однонаправленные, так и двунаправленные. Требуется определить максимальный поток между скважинами и заводами. i C ij C ji j Источник Сток Скважины Насосные станции Заводы

59 2. Сетевые модели Задача о максимальном потоке. Перебор разрезов. Разрез определяет множество ребер, при удалении которых из сети полностью прекращается поток от источника к стоку. Пропускная способность разреза равна сумме пропускных способностей разрезанных ребер Разрез с минимальной пропускной способностью определяет максимальный поток в сети Разрез 1Разрез 2Разрез 3 Это не все разрезы !

60 2. Сетевые модели Задача о максимальном потоке. Перебор разрезов Разрез 1Разрез 2Разрез 3 Разрез Разрезанные ребра Пропускная способность 1(1,2), (1,3), (1,4) = 60 2(1,3), (1,4), (2,3), (2,5) = 110 3(2,5), (3,5), (4,5) = 70

61 2. Сетевые модели Задача о максимальном потоке. Идея алгоритма. Перебор всех разрезов – непростая задача. Идея алгоритма нахождения максимального потока состоит в нахождении сквозных путей с положительными потоками от источника к стоку. Нахождение очередного сквозного пути предполагает задействование части пропусной спосообности ребер. Поэтому следующий сквозной путь ищется на остаточной сети. Максимальный поток вычисляется как сумма потоков в сквозных путях. Более общей является задача с нижними положительными границами пропускных способностей. При этом сеть может вообще не иметь допустимого потока. В этом случае интерес представляет нахождение как максимального, так и минимального потоков в сети.

62 2. Сетевые модели Задача о максимальном потоке. Оптимизация производственного плана. Четыре фабрики имеют заказ на производство четырех видов игрушек. Возможности фабрик по производству игрушек показаны в таблице. Фабрика Типы игрушек Ежедневная производственная мощность (игрушек) 11,2, , , ,4100 Ежедневный спрос на игрушки каждого из четырех типов составляет 200, 150, 350 и 100 штук. Необходимо разработать производственный план, максимально удовлетворяющий спрос на игрушки

63 2. Сетевые модели Задача о максимальном потоке. Оптимизация производственного плана Фабрики Потребители Игрушки 0

64 2. Сетевые модели Задача о максимальном потоке. Оптимизация производственного плана. Конечно, задача оптимизации производственного плана может быть сформулирована как классическая задача линейного программирования (причем – целочисленного). Если количество выпускаемых i -й фабрикой игрушек l -го о типа – x il max (x 11 +x 12 +x 13 +x 22 +x 23 +x 31 +x 34 +x 43 +x 44 ); x 11 + x ; x 12 + x ; x 13 + x ; x 34 + x ; x 11 + x 12 + x ; x 22 + x ; x 31 + x ; x 43 + x ;

65 2. Сетевые модели Нахождение потока наименьшей стоимости. Постановка задачи. Задачу нахождения потока наименьшей стоимости в сети с ограниченной пропускной сппособностью можно рассматривать как обобщение задачи определения максимального потока: Все ребра допускают только одностороннее направление потока, т.е. являются (ориентированными) дугами. Каждой дуге поставлена в соответствие (неотрицательная) стоимость прохождения единицы потока по данной дуге. Дуги могут иметь положительную нижнюю границу пропускной способности. Любой узел сети может выступать в качестве источника и стока. В рассматриваемой задаче необходимо найти потоки по дугам, минимизирующие стоимость прохождения потока по сети. При этом должны удовлетворяться ограничения на пропускные способности дуг и на величины предложений и спроса отдельных (или всех) узлов. Эта задача решается с помощью специального симплексного алгоритма.

66 2. Сетевые модели Нахождение потока наименьшей стоимости. Постановка задачи. Рассмотрим сеть G=(N,A) с ограниченной пропускной способностью, где N – множество узлов, A – множество дуг. Обозначим: x i j – велиичина потока, протекающего от узла i к узлу j, u ij – верхняя пропускная способность дуги (i,j), lij – нижняя пропускная способность дуги (i,j), с ij – стоимость прохождения потока по дуге (i,j), f i – величина результирующего потока, протекающего через узел j. i с ij j fifi fjfj x ji (l ij,u ij )

67 2. Сетевые модели Нахождение потока наименьшей стоимости. Пример (Х.Таха). Компания Зернышко снабжает зерном из трех зернохранилищ три птицеводческие фермы. Предложение зернохранилищ составляет 100, 200 и 50 тонн зерна в месяц. Компания может транспортировать зерно по железной дороге, за исключением трех маршрутов, где используется автомобильный транспорт (20,120) $5 (20,80) $10 (10,120) $20 $30 $10 $15 $25 $20 Пропускная способность железных дорог не ограничена. Пропускная способность автотранспорта огранничена снизу и сверху.

68 2. Сетевые модели Нахождение потока наименьшей стоимости. Сетевая модель как задача линейного программирования Используя данные выше определения, можно записать задачу ЛП для сети с ограниченной пропускной способностью следующим образом: Условие сбалансированности сети:f i =0. Сбалансированность сети не гарантирует существования допустимого решения: этому может помешать ограниченность пропускных способностей дуг.

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

70 3. Транспортные модели Определение транспортной модели. Транспортные модели в классической постановке описывают перемещение (перевозку) какого-либо продукта из пунктов отправления в пункты назначения. Цель транспортной задачи – определение объемов перевозки из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения на объемы грузов в пунктах отправления (предложения) и в пунктах назначения (спрос). Предполагается, что стоимость перевозки по какому-либо маршруту прямо пропорциональна объему товара. Транспортная модель применяется для описания ситуаций, связанных с управлением запасами, составлением расписаний, управлением движением капиталов, назначением персонала и др. Транспортная модель может рассматриваться как упрощенная задача нахождения потока минмальной стоимости в сети.

71 3. Транспортные модели Определение транспортной модели. Представление транспортной задачи в виде сети. 1 2 m n c 11 x 11 c mn x mn a1a1 a2a2 amam Объемы предложений b1b1 b2b2 bnbn Спрос

72 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи. Минский тракторный завод построил три завода в Лос- Анджелесе, Детройте и Новом Орлеане и два дистрибьюторских центра в Денвере и Майами. Объемы производства заводов в следующем квартале соответственно составляют 1000, 1500 и 1200 тракторов. Ежеквартальнная потребность дистрибьюторских центров составляет 2300 и 1400 автомобилей Даны расстояния (в милях) между заводами и дистрибьюторскими центрами. Транспортная компания оценивает свои услуги в 8 центов за перевозку одного трактора на одну милю. Требуется минимизировать транспортные расходы.

73 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи. Таблица расстояний Денвер Майами Лос-Анджелес Детройт Новый Орлеан Таблица стоимостей (долларов США) Денвер Майами Лос-Анджелес Детройт Новый Орлеан 10268

74 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи. Основываясь на таблице стоимости, сформулируем следующую задачу линейного программирования min F=80x x x x x x 32 ; x 11 + x 12 = 1000; (производство в Лос-Анджелесе) x 21 + x 22 = 1500; (производство в Детройте) x 31 + x 32 = 1200; (производство в Новом Орлеане) x 11 + x 21 + x 31 = 2300; (спрос в Денвере) x 12 + x 22 + x 32 = 1400; (спрос в Майами) x ij 0, i=1,2,3, j=1,2.

75 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи. Данная задача решается с помощью транспортной таблицы Денвер Майами Лос-Анджелес 80 x x 12 Детройт 100 x x 22 Новый Орлеан 102 x x 32 Спрос Объем производства

76 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи Объемы предложений 2300 Спрос

77 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи (Решение) Объемы предложений 2300 Спрос

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

79 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи. Например, пусть завод в Детройте уменьшил выпуск продукции до 1300 тракторов вместо Денвер Майами Лос-Анджелес Детройт Новый Орлеан Фиктивный завод Спрос Объем производства

80 3. Транспортные модели Определение транспортной модели. Пример постановки транспортной задачи. Предположим теперь, что наоборот, при прежнем объеме производства спрос в Денвере уменьшился до 1900 тракторов. Денвер МайамиФиктивный центр Лос-Анджелес Детройт Новый Орлеан Спрос Объем производства

81 3. Транспортные модели Нетрадиционные транспортные модели. Управление запасами Фабрика производит купальные костюмы. В течение года спрос на эту продукцию есть только в мае-августе. Фабрика оценивает спрос в эти месяцы соответственно в 1000, 2000, 1800 и 3000 единиц изделия. В зависимости от числа задействованных рабочих и производственного оборудования в течение этих месяцев можно выпустить 500, 1800, 2800 и 2700 костюмов соответственно. Производство и спрос в различные месяцы не совпадают, спрос в текущем месяце можно удовлетворить следующими способами: производством изделий в текущем месяце (себестоимость - 40 долларов); избытком произведенных в прошлом месяце изделий (стоимость хранения – 0,5 доллара в месяц); избытком произведенных в следующм месяце изделий в счет невыполненных заказов (штраф - 2 доллара за месяц просрочки)

82 3. Транспортные модели Нетрадиционные транспортные модели. Управление запасами Транспортная модель Модель управления запасами Пункт отправления i Период производства i Пункт назначения j Период потребления j Предложение в пункте отправления i Объем производства за период i Спрос в пункте назначения j Объем реализации продукции за период j Стоимость перевозки из пункта i в пункт j Стоимость единицы продукции (производство+хранение+штрафы) за период от i до j

83 3. Транспортные модели Нетрадиционные транспортные модели. Управление запасами майиюньиюльавгуст май 4040,54141,5 июнь ,541 июль ,5 август Спрос Объем пр-ва

84 3. Транспортные модели Нетрадиционные транспортные модели. Управление запасами майиюньиюльавгуст май , ,5 0 июнь , июль ,5 300 август Спрос Объем пр-ва

85 3. Транспортные модели Нетрадиционные транспортные модели. Управление запасами Объемы производства 1000 Спрос

86 3. Транспортные модели Нетрадиционные транспортные модели. Управление оборудованием Лесопильный завод обрабатывает различную древесину по утвержденному недельному производственному плану. Согласно этому плану в зависимости от типа древесины в разные дни недели требуется различное число полотен для пил: 1- Пн.2-Вт.3-Ср.4-Чт.5-Пт.6-Сб.7-Вс Завод может удовлетворить потребность в полотнах следующим образом: Купить новые по $12 за штуку Применить ночную заточку стоимостью $6 за полотно Сдать полотно на 2-дневную заточку за $3 за полотно. Требуется минимизировать затраты в течение недели на обеспечение производства полотнами для пил.

87 3. Транспортные модели Нетрадиционные транспортные модели. Управление оборудованием Пн ВтСр ЧтПт СбВс Оста- ток Кол-во использо- ванных полотен Новые$12 24 $12 2 $12 $ ПнМ$6 10 $6 8 $3 6 $3 $0$0 24 ВтММ$6 6 $6$3 6 $3 $0$0 12 СрМММ$6 14 $6$3 $0$0 14 ЧтММММ$6 12 $6$3 8 $0$0 20 ПтМММММ$6 14 $6$04$0418 СбММММММ$6 14 $0$0 ВсМММММММ$0 22 Необх.кол. полотен (спрос) Здесь Остаток – к-во незаточенных полотен в конце каждого дня – фиктивный пункт назначения

88 3. Транспортные модели Принципы построения алгоритма решения Последовательность шагов алгоритма решения транспортной задачи: 1. Определить начальное базисное допустимое решение 2. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определить вводимую в базис. Если все небазисные переменнные удовлетворяют условию оптимальности, завершить вычисления. 3. С помощью условия допустимости симплекс-метода среди текущх базисных переменных определить исключаемую. 4. Найти новое базисное решение и перейти к шагу 2. Данная последовательность шагов в точности повторяет аналогичную последовательность симплексного алгоритма.

89 3. Транспортные модели Принципы построения алгоритма решения Определение начального решения Общая траснспортная модель с m пунктами отправления и n пунктами назначения имеет m+n ограничений. В силу сбалансированности транспортной модели одно из этих равенств избыточно. Таким образом, транспортаня модель имеет m+n-1 независимых ограничений, откуда следует, что начальное базисное решение состоит также из m+n-1 переменных. Специальная структура транспортной задачи позволяет использовать для построения начального решения следующие методы: Метод северо-западного угла Метод наименьшей стоимости Метод Фогеля.

90 3. Транспортные модели Принципы построения алгоритма решения Итерационный алгоритм решения транспортной задачи Далее реализуются известнные шаги симплекс-метода: 1. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определить вводимую в базис. Если все небазисные переменнные удовлетворяют условию оптимальности, завершить вычисления. 2. С помощью условия допустимости симплекс-метода среди текущх базисных переменных определить исключаемую. 3. Найти новое базисное решение и перейти к шагу 2. Однако, при изменении базиса в данном случае используется более простой способ, основанный на анализе транспортной таблицы (вычислении коэффициентов F- строки, соответствующих небазисным переменным с помощью метода потенциалов).

91 3. Транспортные модели Задача о назначениях Постановка задачи Необходимо назначить работников на опредленные работы. Каждый работник может выполнять любую работу, хотя и с различной степенью мастерства. Если на некоторую рработу назначается работник именно той квалификации, которая необходима для ее выполнения, стоимость выполнения работы будет ниже, чем при назначении работника неподходящей квалификации. Цель – найти оптимальное (минимальной стоимости) распределение работников по всем заявленным работам.

92 3. Транспортные модели Задача о назначениях Постановка задачи c 11 c 12 …c 1n c 21 c 22 …c 2n ………… c n1 c n2 …c nn … n Работы 12…n12…n Работники

93 3. Транспортные модели Задача о назначениях Венгерский метод 1. В исходной матрице стоимостей определить в каждой строке минимальную стоимость и отнять ее от всех элементов строки. 2. В полученной матрице найти в каждом столбце минимальную стоимость и отнять ее от всех элементов столбца. 3. Если допустимое решение получено, то 1. Оптимальные назначения соответствуют нулевым элементам. Завершить работу. 4. Иначе: 1. В последней матрице провести минимальное число горизонтальных и вертикальных прямых, чтобы вычеркнуть все нулевые элементы. 2. Найти наименьший невычеркнутый элемент и вычесть его из всех невычеркнутых элементов и прибавить к элементам, стоящим на пересечении проведенных прямых. 3. Если допустимое решение получено, то оптимальные назначения соответствуют нулевым элементам. Завершить работу. Иначе перейти к 2.

94 3. Транспортные модели Задача о назначениях Венгерский метод $1$4$6$3 $9$7$10$9 $4$5$11$7 $8$7$8$ Работы Работники Исходная задача о назначении работников на работы

95 3. Транспортные модели Задача о назначениях Венгерский метод $1$4$6$3 $9$7$10$9 $4$5$11$7 $8$7$8$ Работы Работники Находим в каждой строке минимальную стоимость

96 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$3$3$5$5$2$2 $2$2$0$0$3$3$2$2 $0$0$1$1$7$7$3$3 $3$3$2$2$3$3$0$ Работы Работники Отняли ее от всех элементов строк

97 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$3$3$5$5$2$2 $2$2$0$0$3$3$2$2 $0$0$1$1$7$7$3$3 $3$3$2$2$3$3$0$ Работы Работники Находим в каждом столбце минимальную стоимость

98 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$3$3$2$2$2$2 $2$2$0$0$0$0$2$2 $0$0$1$1$4$4$3$3 $3$3$2$2$0$0$0$ Работы Работники Вычитаем из всех элементов соответствующих столбцов (реально – только из третьего). Допустимое решение не получено. Назначив 1-го работника на работу 1 мы лишаем возможности получить работу 3-го работника

99 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$3$3$2$2$2$2 $2$2$0$0$0$0$2$2 $0$0$1$1$4$4$3$3 $3$3$2$2$0$0$0$ Работы Работники Вычеркиваем все нулевые элементы с помощью наименьшего числа горизонтальных и вертикальных линий

100 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$3$3$2$2$2$2 $2$2$0$0$0$0$2$2 $0$0$1$1$4$4$3$3 $3$3$2$2$0$0$0$ Работы Работники Находим наименьший невычеркнутый элемент

101 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$2$2$1$1$1$1 $2$2$0$0$0$0$2$2 $0$0$0$0$3$3$2$2 $3$3$2$2$0$0$0$ Работы Работники Вычитаем его из всех невычеркнутых элементов

102 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$2$2$1$1$1$1 $3$3$0$0$0$0$2$2 $0$0$0$0$3$3$2$2 $4$4$2$2$0$0$0$ Работы Работники Прибавляем его ($1) к элементам на пересечении линий

103 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$2$2$1$1$1$1 $3$3$0$0$0$0$2$2 $0$0$0$0$3$3$2$2 $4$4$2$2$0$0$0$ Работы Работники Получаем допустимое решение: сначала безальтернативные назначения

104 3. Транспортные модели Задача о назначениях Венгерский метод $0$0$2$2$1$1$1$1 $3$3$0$0$0$0$2$2 $0$0$0$0$3$3$2$2 $4$4$2$2$0$0$0$ Работы Работники Полученное допустимое решение

105 4. Целочисленное линейное программирование Постановка задач. Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные должны принимать целочисленные (дискретные) значения. В настоящее время надежных вычислительных алгоритмов решения таких задач не существует. В качестве примеров вспомним две задачи, рассмотренные нами во введении. Первая задача – выбор оптимального способа подключения к сетям мобильной связи.

106 0. Введение Задача выбора операторов мобильной связи и тарифных планов. Предположим, что нам необходимо выбрать операторов мобильной связи и тарифные планы для организации персональной системы мобильной связи. Известны: среднемесячный объем разговоров с абонентами мобильных сетей Velcom, МТС, Belcel, республиканской телефонной сети, тарифные планы операторов, стоимость приемлемого мобильного телефона требуемый срок окупаемости его приобретения, максимальное количество телефонов, предельная сумма разовых вложений в приобретение телефонов.

107 0. Введение Задача выбора операторов мобильной связи и тарифных планов. Варьируемые параметры и целевая функция Варьируемые параметры: массив бинарных переменных x i, i=1,...,n. x i ={1,0}. Количество элементов массива n равно количеству существующих тарифных планов у всех операторов. Значение 1 означает приобретение телефона и подключение к соответствующему тарифному плану соответствующего оператора. Функция, описывающая критерий оптимальности (целевая функция) – суммарные затраты в месяц здесь A i – затраты в месяц на подключение по i -му тарифному плану

108 0. Введение Задача выбора операторов мобильной связи и тарифных планов. Структура месячных затрат (Velcom и МТС) Затраты в месяц по i -му тарифному плану для операторов Velcom и МТС определяются следующим образом: здесь T ij =v j t ij – стоимость j -го типа трафика объема vj, если он направлен на подключение по i -му тарифному плану (трафик направляется, если существует подключение по этому плану, т.е. x i =1, и тариф t ij по этому плану наименьший из тарифов существующих подключений); B i – ежемесячная абонентская плата по i -му плану; P i = S i /d – ежемесячные отчисления за стоимость телефона S i для i -го подключения из расчета окупаемости за d месяцев.

109 0. Введение Задача выбора операторов мобильной связи и тарифных планов. Структура месячных затрат (Belcel) Затраты в месяц по i -му тарифному плану для оператора Belcel определяются следующим образом: здесь M i – ежемесячная оплата за разговоры определяется как T ij - стоимость j -го трафика, если он направлен на подключение по i - му тарифному плану; B i – ежемесячная предоплата по i -му плану; P i = S i /d – ежемесячные отчисления за стоимость телефона S i для i -го подключения из расчета окупаемости за d месяцев.

110 0. Введение Задача выбора операторов мобильной связи и тарифных планов. Ограничения Ограничения в нашем случае принимают следующий вид: где X – максимально приемлемое число телефонов здесь c i – стоимость приемлемого телефона для i -го подключения, C – предельная сумма разовых вложений в стоимость телефонов.

111 0. Введение Задача выбора операторов мобильной связи и тарифных планов. Математическая модель задачи Окончательно математическая модель задачи оптимального выбора операторов мобильной связи и тарифных планов выглядит следующим образом:

112 0. Введение Задача выбора операторов мобильной связи и тарифных планов. Алгоритм и программная реализация Учитывая ограниченное число возможных вариантов оптимальное решение данной задачи может быть найдено путем полного перебора всех возможных вариантов Программная реализация метода была выполнена в среде пакета Microsoft Excel. Исходные данные заносятся в электронную таблицу, в ней же выполняется расчет целевой функции и функций, задающих ограничения. Перебор параметров выполняется с помощью небольшой программы, написанной на встроенном языке Microsoft Visual Basic. Ссылка на соответствующую книгу Excel размещена здесь.здесь

113 1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг Телекоммуникационная компания Spam Networks оказывает два основных вида услуг: подключение пользователей по коммутируемым каналам по безлимитному плану в Internet и хостинг веб-сайтов. Для организации доступа в Internet компания покупает асимметричный трафик: исходящий у оператора Fool Communications по цене 6 долларов за 1 Кбит/с, пропускная способность выделенной линии – до 2 Мбит/с входящий трафик через собственную приемную спутниковую тарелку по цене 0,8 доллара за 1 Кбит/с, максимальный объем – 2 Мбит/с Для предоставления услуги хостинга одного сайта необходимо зарезервировать 2 Кбит/с на передачу и 1 Кбит/с на прием. Месячный доход от услуги составляет 8 долларов. Для предоставления услуги доступа в Internet необходимо зарезервировать 4 Кбит/с на прием и 1 Кбит/с на передачу. Месячный доход от услуги составляет 6 долларов.

114 1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг: формализация исходной проблемы Множество возможных альтернатив – различное число сопровождаемых веб-сайтов и количество подключаемых пользователей Internet Варьируемые параметры – число сопровождаемых сайтов x 1 и число пользователей Internet x 2. Хотя параметры являются целочисленными, эту задачу можно попытаться решить в вещественных числах и затем округлить решение до ближайших целых. Цель – получение максимального дохода: F(x 1, x 2 )=8x 1 +6x 2 Ограничения: общий объем входящего трафика меньше или равен предельно возможному, общий объем исходящего трафика меньше или равен пропускной способности канала, число подключаемых пользователей меньше или равно емкости портов х – средний коэффициент использования. Число сопровождаемых сайтов и число пользователей неотрицательны.

115 1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг: математическая модель max F(x 1, x 2 ); F(x 1, x 2 ) = 8x 1 +6x 2 ; x 1 +4 x ; 2x 1 + x ; x 2 480; x 1 0; x 2 0. Данная модель – классическая модель линейного программирования. Замечание: хотя мы и назвали задачу: «оптимизация структуры услуг…», это – типичная задача параметрической оптимизации. Рассмотрим графическое решение этой модели (модель решается в электронной таблице Excel: см. соответствующую книгу).книгу

116 4. Целочисленное линейное программирование Классические методы решения. Классические методы решения задач линейного программирования основаны на использовании вычислительных возможностей методов решения непрерывных задач ЛП. Обычно алгоритмы целочисленного ЛП можно представить в виде трех основных шагов: «Ослабление» пространства допустимых значений путем отбрасывания требований целочисленности (для двоичных переменных – замена на непрерывные с ограничениями 0x i1 ); Решение задачи ЛП Имея полученное непрерывное оптимальное решение, добавляем специальные ограничения, которые итерационным путем изменяют пространство допустимых решений задачи ЛП таким образом, чтобы получилось оптимальное решение, удовлетворяющее условиям целочисленности.

117 4. Целочисленное линейное программирование Классические методы решения. Метод ветвей и границ. Рассмотрим следующую задачу ЛП: max F=5x 1 +4x 2 при ограничениях x 1 +x 2 5, 10x 1 +6x 2 45, x 1 и x 2 – целые Оптимальное решение: x 1 =3,75 x 2 =1,25 F=23,75

118 4. Целочисленное линейное программирование Классические методы решения. Метод ветвей и границ. Рассмотрим две новые задачи: max F=5x 1 +4x 2 1. при ограничениях x 1 +x 2 5, 10x 1 +6x 2 45, x 13, 2. при ограничениях x 1 +x 2 5, 10x 1 +6x 2 45, x 14, x 1 и x 2 – целые Оптимальное решение: x 1 =3 x 2 =2 F=23

119 4. Целочисленное линейное программирование Классические методы решения. Метод ветвей и границ. ЛП0: x 1 =3,75, x 2 =1,25, F=23,75 ЛП1: x 1 =3, x 2 =2, F=23ЛП2: x 1 =4, x 2 =0,83 F=23,33 x13x13x14x14 ЛП3: x 1 =4,5, x 2 =0 F=22,5ЛП4: Нет решения x20x20 x 2 1 ЛП5: x 1 =4,5, x 2 =0 F=22,5ЛП6: Нет решения x 14x 15

120 4. Целочисленное линейное программирование Классические методы решения. Метод ветвей и границ. Алгоритм максимизации Положить нижнюю границу оптимального значения -. Положить i=1 Шаг 1. (Зондирование и определение границы). Выбираем i-ю подзадачу ЛПi для исследования. Решаем ЛПi и зондируем ее: Оптимальное значение целевой ф-ии задачи ЛПi не может улучшить текущей нижней границы. ЛПi приводит к лучшему допустимому целочисленному решению, чем текущая нижняя граница. ЛПi не имеет допустимых решений. Возможны два случая: Если задача ЛПi прозондирована: Если все подзадачи прозондированы, положить в качестве оптимального решение, соответствующее текущей нижней границе. Иначе, положить i=i+1 и повторить шаг 1 Если задача ЛПi не прозондирована, перейти к шагу 2. Шаг 2 (Ветвление) Выбираем одну из целочисленных переменных, оптимальное значение которой в решении задачи ЛПi не является целым. Исключаем из пространства допустимых решений область, лежащую между двумя ближайшими к оптимальному значению целыми числами путем формирования двух новых подзадач ЛП с дополнительными оограничениями на данную переменную. Положить i=i+1. Перейти к шагу 1.

121 4. Целочисленное линейное программирование Генетические алгоритмы. Представим себе искусственный мир, населенный множеством существ (особей), причем каждое существо это некоторое решение нашей задачи. Будем считать особь тем более приспособленной, чем лучше соответствующее решение (чем большее значение целевой функции оно дает). Тогда задача максимизации целевой функции сводится к поиску наиболее приспособленного существа. Будем рассматривать много поколений, сменяющих друг друга. Если ввести в действие естественный отбор и генетическое наследование то полученный мир будет подчиняться законам эволюции. В соответствии с нашим определением приспособленности, целью этой искусственной эволюции будет как раз создание наилучших решений. Принудительно остановив этот процесс через достаточно долгое время после его начала и выбрав наиболее приспособленную особь в текущем поколении, мы получим не абсолютно точный, но близкий к оптимальному ответ. Для того чтобы говорить о генетическом наследовании, нужно снабдить наши существа хромосомами. В генетическом алгоритме хромосома это некоторый числовой вектор, соответствующий изменяемым параметрам задачи, а набор хромосом данной особи определяет решение задачи. Какие именно векторы следует рассматривать в конкретной задаче, решает пользователь. Каждая из позиций вектора хромосомы называется геном.

122 4. Целочисленное линейное программирование Генетические алгоритмы. Определим теперь понятия, соответствующие мутации и кроссинговеру в генетическом алгоритме: Мутация это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций случайное изменение только одного из генов хромосомы. Кроссовер (cross-over, в литературе по генетическим алгоритмам также употребляется название кроссинговер или скрещивание) это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае кроссовер в генетическом алгоритме реализуется так же, как и в биологии. При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2, 3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).

123 4. Целочисленное линейное программирование Генетические алгоритмы. Общая схема 1. Генерируется начальная популяция особей (индивидуумов), т. е. некоторый набор решений задачи. Как правило, это делается случайным образом. 2. Моделируется размножение внутри этой популяции: рассчитываются вероятности участия индивидуумов в скрещивании: чем приспособленнее индивидуум, то есть чем больше (меньше) соответствующее ему значение целевой функции, тем с большей вероятностью он будет участвовать в скрещивании, с учетом рассчитанных вероятностей случайно составляется несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, полученные новые хромосомы помещаются в популяцию нового поколения. 3. Моделируются мутации в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. 4. Старая популяция частично или полностью уничтожается и переходим к рассмотрению следующего поколения – к шагу 2.

124 4. Целочисленное линейное программирование Генетические алгоритмы. Общая схема

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

126 4. Целочисленное линейное программирование Генетические алгоритмы. Пример Рассмотрим диофантово (только целые решения) уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d). Сведем ее к задаче ИО (самостоятельно). Выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Вообще говоря, мы можем использовать меньшее ограничение для b,c,d, но для упрощения пусть будет 30. Хромосома (a,b,c,d) 1 (1,28,15,3) 2 (14,9,2,4) 3 (13,5,7,3) 4 (23,8,16,19) 5 (9,13,5,2)

127 4. Целочисленное линейное программирование Генетические алгоритмы. Пример Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением. Хромосома Коэффициент выживаемости 1 |114-30|=84 2 |54-30|=24 3 |56-30|=26 4 |163-30|=133 5 |58-30|=28 Так как меньшие значения ближе к 30, то они более желательны. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) может быть выбрана каждая. Например, можно вычислить сумму обратных значений коэффициентов, и исходя из этого вычислять вероятности Хромосома Подходящесть 1 (1/84)/ = 8.80% 2 (1/24)/ = 30.8% 3 (1/26)/ = 28.4% 4 (1/133)/ = 5.56% 5 (1/28)/ = 26.4%

128 4. Целочисленное линейное программирование Генетические алгоритмы. Пример Далее симулируется выбор родителей. Хромосома отца Хромосома матери Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать одноточечный кроссовер. Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кросс-оверов (| = разделительная линия): Хромосома-отец Хромосома-мать Хромосома-потомок a1 | b1,c1,d1 a2 | b2,c2,d2 a1,b2,c2,d2 or a2,b1,c1,d1 a1,b1 | c1,d1 a2,b2 | c2,d2 a1,b1,c2,d2 or a2,b2,c1,d1 a1,b1,c1 | d1 a2,b2,c2 | d2 a1,b1,c1,d2 or a2,b2,c2,d1

129 4. Целочисленное линейное программирование Генетические алгоритмы. Пример Попробуем проделать это с нашими потомками Хромосома-отец Хромосома-мать Хромосома-потомок (13 | 5,7,3) (1 | 28,15,3) (13,28,15,3) (9,13 | 5,2) (14,9 | 2,4) (9,13,2,4) (13,5,7 | 3) (9,13,5 | 2) (13,5,7,2) (14 | 9,2,4) (9 | 13,5,2) (14,13,5,2) (13,5 | 7, 3) (9,13 | 5, 2) (13,5,5,2) Теперь мы можем вычислить коэффициенты выживаемости (fitness) потомков. Хромосома-потомок Коэффициент выживаемости (13,28,15,3) |126-30|=96 (9,13,2,4) |57-30|=27 (13,5,7,2) |57-30|=22 (14,13,5,2) |63-30|=33 (13,5,5,2) |46-30|=16 Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30.