Дискретно-непрерывная математика (стр. 48 )

Четвертое утверждение доказывается способом от обратного. Пусть j не входит в «хвост» некоторого i, принадлежащего σk, и пусть

Σп = σk, j,…,l,…

-искомое решение, l — первый индекс из «хвоста» i.

Для σп

δij = 0, а δil = 1,

в то время как k (j)< k(l), что противоречит условию (5.57).

Докажем и пятое утверждение.

Действительно, пусть «хвост» i1 содержит j1, но не содержит j2, а «хвост» i2 не содержит j1, но содержит j2. Тогда в перестановке

σ1п= σk,…,j1,…,j2,…

т. е. при k(j1)< k(j 2),

а

иначе говоря, нарушается свойство (5.57), в перестановке же

σ2п= σk,…,j2,…,j1,…

т. е. при k(j1)> k(j2),

а

т. е. снова же нарушается свойство (5.57).

Так в нашем примере при σ2 = 1, 2 «хвост» 1 содержит j = 4, «хвост» 2 содержит j = 5. Если мы образуем перестановку

σk = 1, 2, 4, 5, ... ,

в ней δ24 = 0, a δ25 = 1. Если мы образуем перестановку

σп = 1, 2, 4, 5, ... ,

в ней δ15 = 0, а δ14 = 1.

Воспользуемся общей схемой построения порфириана, с той только разницей, что в операции «ветвления»

1) при переходе от σk к σk+1 к σk можно присоединить только j, содержащееся во всех непустых «хвостах» для i, вошедших в σk; если все «хвосты» пустые — любую j (не из σk, конечно).

2) σk, удовлетворяющее условию утверждении 5, отмечаем (крестиком) как недопустимое, дальнейшему «ветвлению» неподлежащее.

Рис. 5.30

Рис. 5.30 представляет общую схему алгоритма построения порфириана в нашем примере, табл. 5.10 - в немного своеобразной (приспособленной для записи) форме результат решения задачи.

Таблица 5.10

Обратите внимание: вместо нескольких сотен тысяч перестановок (если пользоваться методом перебора) в нашем методе оказалось достаточным построить всего 41 фрагмент σk.

5.17. Перестановочный метод

1. Решение задачи директора. Хороший директор интуитивно давно определил, в какой очередности следует принимать посетителей: прежде всего необходимо переговорить с теми, кто пришел с короткими вопросами, оставив «на потом» вопрос посложнее.

Это правило может быть строго доказано.

Предположим

σ1п = i1...,i, j.....in

- оптимальное решение. Напомним, что

(5.58)

Здесь — время начала приема i-го посетителя. Поменяем порядок приема каких-то двух посетителей, принимаемыз в σ1п один непосредственно за другим:

σ2п = i1,..., j, i,.....,in .

Можно записать, что

(5.59)

А — общая неизменная часть F(σ), так как времена ожидания в приемной посетителей, имеющих номер, отличный от i и j, не изменились в σ2п по сравнению с σ1п.

Так как σ1п — по предположению оптимальное решение, то

(5.60)

Пусть τ — момент окончания приема предыдущего посетителя для i-го в σ1п, j-го в σ2п.

Тогда для σ1п

для σ2п

Согласно (4.87) и (4.88)

А + τ + τ + Tі ≤A + τ + τ + Tj

или

Tі≤Tj. (5.61)

Последнее как раз и означает, что решение оптимально тогда, когда принята очередность согласно правилу: «предыдущая не длительней последующей». Это правило носит также название правила кратчайшей операции: первым в оптимальном решении выбирается i с наименьшей длительностью Tі .

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

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

Директор должен рассмотреть п вопросов; длительность рассмотрения i-гo вопроса равна Тi; по вопросу i к директору заходит αi посетителей; допустим, что нет посетителя, который пришел одновременно по двум вопросам.

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

σг = i1,i2,.....in ,

с функцией-критерием

(5.62)

Если считать, что αi — не только целые числа, мы получим задачу одного станка: установить очередность обработки п различных деталей, если время обработки i-й детали Тi известно заранее; по детали i за каждую минуту ожидания обработки взимается «штраф» αі.

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

Пусть

σ1п = i1,...,i, j,.....,in

- оптимальное решение, а

σ 2п = i1,..., j, i,.....,in

— вариант, который отличается перестановкой только двух каких-то соседних элементов в σ1п.

И в этом случае, так как σ1п - по предположению оптимально,

(5.63)

Обозначив через τ, как и в предыдущем пункте, получим, что неравенство (5.63) эквивалентно

или

αj Tі ≤ αі Tj

а так как все Tі > 0, то

(5.64)

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

Утверждение (решающее правило).

Перестановка

σ1п = i1,i2,.....,in

тогда есть решение задачи одного станка по критерию (5.62), когда

(5.65)

Прием исследования, который мы успешно применили и в задаче директора, и в задаче одного станка, получил название перестановочного приема.

3. Задача двух станков. Еще одно эффективное применение перестановочного приема — задача двух станков.

В этой задаче требуется за минимальное время закончить обработку п деталей. Каждая деталь i обрабатывается сначала на первом станке (первая операция), продолжительность обработки равна аі, потом на втором станке (вторая операция), продолжительность обработки bі.

Табл. 5.11 представляет исходные данные простого иллюстративного примера задачи двух станков, рис. 5.31 — временнỳю диаграмму для этого примера σ1 = (1, 2, 3, 4, 5, 6).

Таблица 5.11

Рис. 5.31

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

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

Для этого, прежде всего, надо установить, что в оптимальном решении не может быть такого, чтобы для двух каких-то деталей i, j на первом станке операции выполнялись в очередности i j ( — знак «предшествует»), а на втором станке ji. Такой случай демонстрируется несколько схематично на рис. 5.32.