Полная версия

Главная arrow Информатика arrow Интегрированные автоматизированные системы управления химическими производствами и предприятиями

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Определение оптимальной стратегии переналадки технологического оборудования

Постановка задачи (задача коммивояжера)

Пусть на некотором технологическом аппарате необходимо выпускать множество п различных продуктов (рис. 7.1).

Схематическое изображение многопродуктового технологического аппарата

Рис. 7.7. Схематическое изображение многопродуктового технологического аппарата

В каждый момент времени на технологическом аппарате обрабатывается только один продукт, и этот процесс происходит без прерывания, т. е. можно приступить к обработке следующего продукта только после окончания обработки предыдущего. Для переналадки данного технологического аппарата с выпуска i-ro продукта на выпуск; -го продукта требуется время 0г;-. Пусть п = {i1} i2, ..., iq, ..., in} — последовательность выпуска продуктов. Здесь iq означает номер продукта, который производится q-м по порядку.

В этом случае задача определения оптимальной стратегии переналадки технологического оборудования сводится к выбору оптимальной очередности выпуска продуктов п ={i{ ,i2,...,i„} так, чтобы суммарные затраты времени на переналадку технологического аппарата при выпуске заданного множества продуктов, были минимальны.

Математическое описание задачи имеет следующий вид:

где F(n) — суммарные затраты времени на переналадку, критерий оптимизации, который имеет вид

где — время переналадки с выпуска продукта, выпускаемого

q-ым в последовательности, на продукт q+1.

В ряде случаев требуется учитывать время подготовки аппарата к выпуску первого (i-ro) продукта 0O;j1 и время приведения аппарата к исходному положению 0; 0, если ;-й продукт последний.

Математическое описание задачи будет иметь вид:

где F(n) — критерий оптимизации, имеющий вид:

Эта задача является известной задачей коммивояжера, имеющей простую геометрическую интерпретацию: есть множество городов {О, 1, 2,..., п} и 0j , — расстояние между i-ым и;-ым городами. Коммивояжер должен выехать из города 0, объехать все остальные города ровно по одному разу и вернуться в исходный город, Необходимо указать такую последовательность объезда городов, при которой коммивояжер проедет наименьшее суммарное расстояние.

Пример 7.1

В некотором химическом реакторе выпускаются 3 продукта Рь Р2, Р3. Время промывания реактора 0!; при переходе с выпуска i-ro продукта к выпуску j-ro продукта с учетом фиктивного продукта Р0, характеризующего первоначальное состояние реактора, представлено в виде следующей матрицы:

Необходимо определить оптимальную последовательность выпуска этих трех продуктов.

Очевидно, существует 3! = 6 вариантов выпуска продуктов. Для каждого варианта вычислим значение критерия F(n) по формуле (7.3):

Оптимальной последовательностью выпуска продуктов л* будет та, суммарное время выпуска всех продуктов F(n) которой минимально, л5 = л* =3, Рг, Р2}, так какР(л5) = min(Р(я;)}, где i = 1,6.

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

Рассчитаем число вариантов решений для некоторых значений п:

п - 3, V - 3 - 6,

п = 8, V = 8! = 40 320,

п = 50 V = 50! = 3,041‘Ю64,

п = 6,

V - 6 - 720,

п = 10,

7= 10! = 3 628 800,

п = 100

7= 100! = 9,333-10157.

Предположим, что на каждый вариант для вычисления F(n) по формуле (1.2) затрачено 0,1 с, тогда измеренное время перебора вариантов решений т составит:

  • п=3, т =0,6 с;
  • п = 6, т = 72 с;
  • п = 8, т =4042 с или 1,02 ч;
  • п = 10, т = 362 880 с или 100,8 ч;
  • — п=50, т = 3,041-1063 с или 8,45-1059 ч

Таким образом, для решения задачи выпуска 10 продуктов общее машинное время составляет более 4 дней, а когда число продуктов равно 50, что реально для современных многопродуктовых химических производств, общее машинное время составляет 3,5-1058 дней, что делает невозможным применение метода полного перебора.

Используя формулу Стирлинга п! = у](2? л-п) •пп •е(_п), можно легко доказать, что п > ап при любом наперед заданном а, начиная с некоторого п. Это означает, что исследуемая нами задача (7.1) или (7.2) принадлежит к классу NP (недетерминистски полиномиальная) — труднорешаемых задач, для которых число вычислений экспоненциально растет с ростом размерности задачи.

Рассмотрим формулировку задачи (7.1) или (7.3) в терминах линейного целочисленного программирования.

Линейно-целочисленная форма представления задачи

Рассмотрим целочисленную переменную х^:

Ху должна удовлетворять следующим соотношениям:

п п

Нужно найти такую матрицу [Xу], чтобы сумма ? ? 0у • Ху была

i=0j=0

минимальна. В такой постановке задача аналогична задаче оптимального назначения. Но для задачи коммивояжера существует дополнительное ограничение, состоящее в том, что его маршрут должен завершиться в исходной точке после однократного посещения всех п городов. Это означает, что матрицы [Ху] типа:

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

Это несущественное на первый взгляд ограничение приводит к тому, что одна из наиболее простых задач математического программирования превращается в одну из наиболее трудных.

Существует несколько способов формализации условия связности.

Введем п дополнительных переменных Z>0 (i = l,n), означающих порядковый «номер» вершины i при обходе контура, содержащего вершину 0. Условие связанности может быть записано в виде:

Таким образом, задачу коммивояжера можно сформулировать в виде задачи смешанно-целочисленного программирования:

Для решения задачи (7.7) можно применить стандартные пакеты программ.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>