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

где

Назовем наименьшее в нашем случае φ(σп) рекордом на Р, а соответствующее σп — рекордным. Если рекорд φ(σп) не больше всех b(σk) на Р, то, как легко видеть, соответствующее рекордное σп представляет оптимальное решение задачи бродячего торговца.

Если это не так, ветвлению подлежит σk с минимальным b(σk), а если таких σk несколько, то крайнее левое из них в построенной части порфириана.

Рис. 5.41 иллюстрирует решение задачи бродячего торговца, представленной табл. 5.15, по схеме ветвей и границ.

Рис. 5.41. Решение задачи бродячего торговца методом «ветвей и

границ».

3. Обобщенная задача о рюкзаке. Мы будем называть обобщенной задачей о рюкзаке следующую постановку.

Максимизировать

при условиях

∑аijхі≤Аj, j=1, ..., т, (5.84)

хi =0 или 1. (5.85)

Отличие ее от «обычной» задачи о рюкзаке в том, что решение должно удовлетворять больше чем одному ограничению (не одному, а т — (5.84)). Как и обычная задача о рюкзаке, обобщенная также может быть интерпретирована как задача теории расписаний (см. п. 2).

Построение порфириана в этой задаче выполняется, как и в задаче о рюкзаке. Весь вопрос применения схемы «ветвей и границ» — в вычислении «обещаний» на каждом фрагменте решения σk.

Заметим, что если, как и в задаче о рюкзаке (п. 2), отказаться от дискретности хi, т. е. считать, что «грузы сыпучие», 0 ≤ хi≤1, то мы придем к формулировке вспомогательной задачи как задачи линейного программирования, которую можно решить стандартными методами. Однако можно еще больше упростить решение. Вспомните рекомендации из формулированию вспомогательной задачи (п. 1). Самое грубое «естественное» упрощение — это отбросить т—1 неравенство и свести задачу к обычной задаче о рюкзаке. Но какое неравенство оставить? Первое? А если второе? А что будет, если мы решим т задач о рюкзаке, по одной для каждого неравенства? Наверное, мы получим т «обещаний» по числу ограничений (5.84), каждое из которых как бы отражает значение «своего» неравенства при построении решения.

Рассмотрим пример. Максимизировать

∑сiхі

при условиях

∑аiхі≤А, ∑biхі≤B, хi =0 или 1.

Значение сi, ai, bi, А, B представлены табл. 5.20.

Таблица 5.20

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

Максимизировать

С1 (х) = ∑ сіхi

при условиях

∑аiхі≤А, 0≤хі≤1.

С помощью табл. 5.20 легко найти это решение: х1 = х2 = х3 = 1,

х4 = 3/5, х5 = 0, С1 (x) = 48.

Сформулируем другу вспомогательную задачу, выбрав второе ограничение:

Максимизировать

С2 (х) = ∑ сіхi

при условиях

∑biхі≤B, 0≤хі≤1.

Легко получить, что С2(х) = 46, х1=0, х2 = 3/4, х3 = х4 = х5 = 1.

Рис. 5.42. Решение обобщенной задачи о рюкзаке по схеме «ветвей и границ» (крестиком отмечен недопустимый ограничениями вариант).

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

F(σп) ≤C1(x) и F(σп) ≤C2(x).

Рис. 5.42 иллюстрирует ход решения в рассмотренном примере по схеме «ветвей и границ». Возле каждой вершины выписан символ вида

х у =z(z(σk)), где х — обещание по первому ограничению, у — по второму, z (или z(σk)) — наименьшее из х и у. Ветвлению подвергается σk с наибольшим z(σk).

5.20. Задача трех станков

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

Задача трех станков формулируется аналогично залаче двух станков (п. 5.17, п. 3). Дано п деталей, каждая из которых обрабатывается последовательно на трех станках. Продолжительность первой операции на первом станке для i-й детали обозначим через аi, второй операции на втором станке bi, третьей на третьем станке сi. Как и прежде, предполагаем, что операция не может начаться, пока не закончилась предыдущая.

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

Таким образом, каждое расписание на трех станках может быть представлено как п-перестановка

σп = i1, i2,…,ik,…,in...

Обозначим через A(σk) время окончания обработки k первых операций в σп на первом станке, через В(σk) - время окончания обработки первых k операций в σп на втором станке, через C(σk) - время окончания обработки первых k операций в σп на третьем станке.

Тогда по условиям задачи (считая, что в момент t = 0 все станка готовые к выполнению работ)

A(σ1) = ,

B(σ1) = + = A( σ1) + , (5.86)

С (σ1) = + + = В (σ1) + ,

и, дальше,

A (σk) = A (σk -1) + ,

В (σk) = max (A (σk), B(σk -1)) + , (5.87)

C(σk t) = max(B(σk), С(σk -1)) + .

Утверждение 1 (правила доминирования). Фрагменты решений σk 1 и σk 2 сравнимые, если, как и в (п. 5.18, п. 1),

М(σk 1) = М(σk 2).

Вариант σk 1 лучше варианта σk 2, если одновременно

В(σk 1)≤В(σk 2), C(σk 1)≤C(σk 2). (5.88)

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

В частности, если

ai = 4, bi=1, c1 = 3, aj = 3, bj=2, сj = 1,

это в σ2 1= i, j

В(σ 2) = 9, С(σ 2) = 10,

а в σ2 2= j, i

В(σ 2) = 8, С(σ 2) = 11.

Заметим, что относительно пары (i, j) не очень-это просто ответить на вопрос, i передует j в оптимальном решении, или j передует i, даже если

В(σ2 1)≤ В(σ2 2), С(σ2 1)≤ С(σ2 2)

— довольно нетривиальная здесь зависимость от В(σk) и С(σk); довольно внимательно следует проводить изложение, если воспользоваться перестановочним приемом.

В некоторых простых случаях ответ на эти вопросы удается получить довольно очевидным образом.

Так, пусть детали перенумерованы таким образом, что оказалось

а1≤а2≤ ... ≤ап,

b1≤b2≤ ... ≤bп, (5.89)

с1≤с2≤ ... ≤сп,

и, кроме того,

аi≤ bi ≤сi для всех 1 ≤i ≤п. (5.90)

Утверждение 2. При условиях (5.89) и (5.90)

σn =1, 2, ..., п

есть оптимальная очередность обработки деталей.

Доказательство этого утверждения очевидно: во-первых, согласно (5.89) и (п. 5.17, п. 3) обработка деталей на двух станках — втором и третьем — оптимальна, и, кроме того, В (σ0) = аі для такой очередности минимальна (a1) из всех возможных.

Рассмотрим другой случай.

Пусть

. (5.91)

Тогда, применяя перестановочный прием, несложно показать, что i предшествует j в оптимальном решении как только

min (aі + bі, bj + сj) ≤ min (aj + bj, bі + cі). (5.92)