Главная

Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Среда IBM ILOG CPLEX studio. Назначение, возможности, задачи моделирования, разрешимые и неразрешимые в этой среде.


IBM ILOG CPLEX OptimizationStudio - комплект инструментов с поддержкой аналитических решений, предназначенный для быстрой разработки и развертывания моделей оптимизации с помощью математического программирования, и программирования в ограничениях. Он состоит из интегрированной среды разработки (IDE), мощного языка программирования для оптимизаций (OPL) и высокопроизводительных модулей решения ILOG CPLEX для оптимизаторов.

Возможности:

· Оптимизация бизнес-решений за счет высокопроизводительных модулей оптимизации.

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

· Создание приложений, которые найдут применение в реальной жизни и смогут значительно улучшить бизнес-результаты.

Для решения задач оптимизации разработчиками предусмотрены два инструмента CPLEX (движок для решения проблем, описываемых при помощи математических моделей) и CP Optimizer (библиотека инструментов для решения задач с помощью программирования на ограничительных языках).

Задачи, разрещимые в этой среде:

5. Задачи линейного программирования (планирования производства)

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

6. Задачи целочисленного программирования (задачи о ранце)

Целочисленное программирование выражает оптимизацию линейной функции с учетом множества линейных ограничений на целочисленных переменных.

7. Задачи частично-целочисленного линейного программирования

В частично-целочисленных линейных программах используются и целочисленные и вещественные переменные. В OPL для этих задач применяется в целом тот же подход, что и для целочисленных программ.

8. Задачи об управлении запасами

Задачи, неразрешимые в этой среде:

Некоторые ЗТР (задачи теории расписаний) с числом целых переменных не более ста являются фактически неразрешимыми для данного ПО (монография, стр. 16, внизу).


Проекты IBM ILOG CPLEX studio, состав, назначение компонент. Основные элементы языка OPL.

IBM ILOG CPLEX OptimizationStudio – продукт, позволяющий создавать математические модели для решения различныхоптимизационных задач, как линейного, так и нелинейного и интегрированного характера. Любой проект содержит собственно математическую модель, вводимые данные и опции по выполнению процесса оптимизации. Рабочая область модели и данных заполняется кодом на языке OPL (OptimizationProgrammingLanguage).

OPL относится к моделирующим языкам, созданным для решения некоторых задач математического программирования. При помощи таких языков можно описать задачи математического программирования так, что они будут восприниматься и решаться при помощи программного обеспечения.

В CPLEX Studio в состав проекта составления расписаний входят файлы моделей,файлы данных и файлы параметров.

Файлы моделей

Файлы моделей (расширение .mod) содержат все операторы OPL. Файл модели, как правило, содержит следующие компоненты:

Объявления данных

Объявления данных позволяют присвоить данным имена, упростив тем самым их использование в модели. Например, если таблица содержит стоимость доставки единицы материалов из расположения i в расположение j, то элемент данных можно назвать costij, где i=1,...,n, j=1,...,n и n - это число расположений в модели. Объявление этих данных модели в OPL выглядит следующим образом:

int n = ... ;

float cost[1..n][1..n] = ... ;

Многоточие (…) означает, что физические значения таблицы расположены в файле данных, который должен быть указан в текущем проекте.

Объявления переменных решений

Объявления переменных описывают имя и тип каждой переменной в модели. Например, количество материалов, доставленных из расположения i в расположение j, можно указать в переменной с именем shipij:

dvarint+ ship[1..n][1..n];

Ключевое слово dvar позволяет объявить переменную решения. Поскольку тип int+ разрешает только положительные целые значения, оператор объявляет массив положительных целых переменных.

Объявление службы

Модель составления расписаний начинается с объявления службы, которое выглядит следующим образом: using CP;

Это объявление указывает, что для решения задачи следует использовать службу CP. Кроме того, оно разрешает применение ограничений, относящихся к программированию в ограничениях и составлению расписанию.

  • Функция цели

Функция цели - это выражение, которое требуется оптимизировать. Она должна содержать переменные и данные, объявленные ранее в файле модели. Функция цели объявляется с помощью ключевого слова minimize или maximize. Пример: minimize endOf(tasks["moving"]);

Этот оператор указывает, что требуется максимально сократить конец переменной интервала tasks["moving"].

  • Ограничения

Ограничения описывают условия, необходимые для осуществимого решения модели. Ограничения объявляются в блоке subject to. Пример:

subject to {

forall(t in Tasks)

forall(s in successors[t])

endBeforeStart(tasks[t], tasks[s]);

}

Этот оператор объявляет набор ограничений очередности.

· Операторы сценариев

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

· оператор main для сценария управления потоком

· оператор execute для сценариев предварительной и заключительной обработки.

minimizeendOf(tasks["moving"]);

subject to {

...

}

execute DISPLAY {

writeln("end=", tasks["moving"].end);

}

Файлы данных

Для более эффективной организации больших задач можно разделить модель и данные экземпляра. В этом случае данные экземпляра хранятся в файлах данных (расширение .dat). Файлы данных содержат фактические значения применяемых в модели данных. Файл данных будет выглядеть следующим образом:

n = 3;

c = [[0.0 1.5 2.3]

[1.5 0.0 3.7]

[2.3 3.7 0.0]];

В каждом файле данных можно указать одно или несколько соединений с источниками данных, такими как реляционная база данных или электронная таблица, для чтения и записи данных. В IDE внешние и внутренние данные можно экспортировать в файл .dat, который затем можно использовать в качестве входных данных. В файлы данных экспортируются только данные, которые фактически применяются в модели.

Файлы параметров

При изменении значений параметров по умолчанию новые значения параметров сохраняются в файле параметров проекта.

В файлах параметров (.ops) сохраняются пользовательские значения параметров при изменении значений параметров по умолчанию языка OPL, программирования в ограничениях (CP Optimizer) и математического программирования (CPLEX).

Параметры применяются только к модели в конфигурации выполнения, они не применяются к загружаемым и решаемым подмоделям.

 


Задача №1.

Методом ДП с отсевом вариантов найти приближение к оптимальному по быстродействию расписанию параллельной системы с задержками.

Номер заявки (j) Время обслуживания на станке Задержка

Положим K=2, следовательно S=4.

1) Если у нас на некотором этапе два варианта с одинаковыми временами, то берем любой вариант на наше усмотрение.

2) Мы начинаем отбрасывать половину из вариантов на том этапе, когда количество вариантов будет больше S, которое по условию у нас будет равно 4.

3) Мы рассчитываем задержку исходя из разности задержки рассматриваемого этапа и суммы предыдущих задержек (фактических, а не данных по условия) и времени обработки конкретного станка. Это можно подсчитать в уме.

Для тех, кто не хочет считать в уме (для этого надо перебирать варианты как делала я, т.е. берем оптимальный вариант, найденный на предыдущем шаге и пишем его два раза а справа дописываем сначала: 1 0, потом 0 1): смотрим на столбец предыдущего этапа, где есть Мах(…,…)=… соответствующего оптимального варианта. Заполняем f для следующего после него варианта который оканчивается на 1 0. Первое число в Мах – это сумма всех фактических задержек и времен обработки предыдущих шагов для этого варианта. Сравниваем его с задержкой, рассматриваемого этапа и если задержка больше данного числа, то разницу между ними прибавляем к времени обработки данного варианта. В противном случае ничего не прибавляем, а пишем только время обработки. Далее переходим к варианту, который оканчивается на 0 1. Ему соответствует второе число Max. Производим с ним аналогичную операцию, как и с предыдущим вариантом.

Результаты первого этапа (Хij, где i–номер станка, j–номер заявки)

Этап 1 Х11 Х21 Fi,1
Заявка 1 (3,0) Max(3,0)=3
(0,4) Max(0,4)=4

Прибавляем задержку, если станки ранее не использовались.

Результаты 2-ого этапа

Этап 2 Х11 Х21 Х12 Х22 Fi,2
Заявка 1 + Заявка 2 (2,0) Max(5,0)=5
(0,3+2) Max(3,5)=5
(2+2,0) Max(4,4)=4
(0,3) Max(0,7)=7

На следующем этапе у нас больше 4 вариантов, значит будем половину вариантов отметать. Помним, если у нас есть промежуток между задержкой и временем обработки предыдущих заявок, то добавляем данный промежуток как задержку.

 

Результаты третьего этапа и отсев вариантов. Выделила то, что берем на следующий этап.

Этап 3 Х11 Х21 Х12 Х22 Х13 Х23 Fi,3
Заявка 1 + Заявка 2 + Заявка 3 (3,0) Max(8,0)=8
(0,2+4) Max(5,6)=6
(3+1,0) Max(7,5)=7
(0,2) Max(3,7)=7
(3,0) Max(7,4)=7
(0,2) Max(4,6)=6
(3+4,0) Max(7,7)=7
(0,2) Max(0,9)=9

Результаты четвертого этапа и отсев вариантов

Этап 4 Х11 Х21 Х12 Х22 Х13 Х23 Х14 Х24 Fi,4
Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4 (4+1,0) Max(10,6)=10
(0,4) Max(5,10)=10
(4,0) Max(11,5)=11
(0,4+1) Max(7,10)=10
(4,0) Max(11,4)=11
(0,4+2) Max(7,10)=10
(4+2,0) Max(10,6)=10
(0,4) Max(4,10)=10

Результаты пятого этапа и отсев вариантов

Этап 5 Х11 Х21 Х12 Х22 Х13 Х23 Х14 Х24 Х15 Х25 Fi,5
Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4 + Заявка 5 (2+3,0) Max(10,10)=10
(0,4) Max(5,14)=14
(2+1,0) Max(10,10)=10
(0,4) Max(7,14)=14
(2+1,0) Max(10,10)=10
(0,4) Max(7,14)=14
(2,0) Max(12,6)=12
(0,4+2) Max(10,12)=12

Результаты шестого этапа и отсев вариантов

Этап 6 Х11 Х21 Х12 Х22 Х13 Х23 Х14 Х24 Х15 Х25 Х16 Х26 Fi,6
Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4 + Заявка 5 + Заявка 6 (4,0) Max(14,10)=14
(0,3) Max(10,13)=13
(4,0) Max(14,10)=14
(0,3) Max(10,13)=13
(4,0) Max(14,10)=14
(0,3) Max(10,13)=13
(4,0) Max(16,6)=16
(0,3+4) Max(16,13)=16

 

 


Результаты последнего этапа и выбор наилучших вариантов

Этап 7 Х11 Х21 Х12 Х22 Х13 Х23 Х14 Х24 Х15 Х25 Х16 Х26 Х17 Х27 Fi,7
Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4 + Заявка 5 + Заявка 6 + Заявка 7 (3,0) Max(17,10)=17
(0,4+2) Max(14,16)=16
(3+2,0) Max(15,13)=15
(0,4) Max(10,17)=17
(3+2,0) Max(15,13)=15
(0,4) Max(10,17)=17
(3+2,0) Max(15,13)=15
(0,4) Max(10,17)=17

 

Наилучшее расписание 1

Номер заявки (j) Время обслуживания на станке Задержка

Наилучшее расписание 2

Номер заявки (j) Время обслуживания на станке Задержка

Наилучшее расписание 3

Номер заявки (j) Время обслуживания на станке Задержка

 


Задача №2. Job Shop

Найти оптимальное по быстродействию расписание последовательной системы (JSP)

Матрица маршрутов   Матрица времени обслуживания

 

Обозначим тройкой (i,j,q) операцию обслуживания детали i станком j в q-й по очереди раз. Построим дизъюнктивную сетевую модель обслуживающей системы в представлении «узел-операция» (рисунок 1). Дуги (стрелки) обозначают последовательность выполнения операций, ребра (прямые линии) — конфликты за станок.

н
к

Рисунок 1 — Дизъюнктивная сеть

Экономико-математическая модель задачи в общем виде представлена формулами 1–6.

(1)

(2)

(3)

(4)

Формула 4 по-другому может быть записана в виде формул 5 и 6.

время начала выполнения операции i (5)

(6)

Булевы переменные =1, если операцию i решено выполнять раньше операции j, и =0 в противном случае.

B>0 — некоторое большое число, превышающее величиной длительность самой трудоемкой операции в системе. Примем его равным 100.

— время выполнения операции i

Для рассматриваемой задачи экономико-математическая модель представлена формулами 7–28.

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

Для решения данной задачи будем использовать алгоритм ветвей и границ.

Ранжируем все ребра смешанной сети по убыванию конфликтности, которая определяется количеством конкурирующих относительно одного и того же агрегата требований в каждый интервал времени. Получаем следующее упорядоченное множество из десяти элементов:

V = { , ,

}

Точно не знаю, как ранжировать ребра. Я использовала матрицу маршрутов и матрицу времени обслуживания.

Убрала конфликты и нарисовала диаграмму Ганта обработки партий деталей. Партии подписаны слева, на отрезках написаны номера станков. Если идти от 0 направо, видны однозначные конфликты (когда интервалы, требующие одинаковые станки, заходят друг на друга). Это , Далее конфликтность я определяла в зависимости от расстояния между интервалами, требующими один станок. Опять идем от 0 направо. Между операциями 111 и 211 интервал 1 час, так же как между операциями 211 и 112, 211 и 312. Ранжируем . Между операциями 311 и 211 интервал 3 часа. Между операциями 111 и 312 интервал 4 часа. Между операциями 311 и 112 интервал 6 часов.

Для оценки нижней границы задачи уберем все конфликты (ребра) и посчитаем критическое время как для обычного сетевого графика (рисунок 2).

н
к

Рисунок 2

Получили, что минимально возможное время обработки трех партий деталей — 11 часов, то есть, нижняя граница решения — 11 часов.

Выбирать ребра будем по принципу максимального приоритета (для чего и ранжировали). При этом будем проверять сеть на отсутствие циклов.


Шаг 1. Выбираем ребро

Подзадача 1.1

(111, затем 311)

н
к

 

 

Подзадача 1.2

(311, затем 111)

н
к

 

Критическое время 12 минимальное. Оставляем подзадачу 1.2, выбираем следующее ребро.


Шаг 2. Выбираем ребро

Подзадача 1.2.1

н
к

 

 

Подзадача 1.2.2

н
к

 

Минимальным остается критическое время 12.


Шаг 3. Выбираем ребро

Подзадача 1.2.1.1

н



Последнее изменение этой страницы: 2016-06-09

headinsider.info. Все права принадлежат авторам данных материалов.