Доказательство - оптимальность
Cтраница 2
 |
Карты Вейча и комбинационная схема из примера 3 в § 3 - 7. [16] |
Далее находят все простые импликанты всех возможных совокупностей функций первой системы. Из найденных простых импликант и конституент второй системы составляют импликантную матрицу для системы функций, с помощью которой формируют МДНФ оптимально доопределенных функций заданной системы. Так же, как и для одной функции, доказательство оптимальности данного метода очевидно и основано на том, что наиболее короткие простые импликанты будут у первой системы, а наименьшее число импликант, необходимое для ДНФ функций, будет содержать вторая система. [17]
Функция р задается на непустых подмножествах индексов заданий и используется для введения упорядочения на множестве наборов заданий. Мы введем также понятия начального множества и р-максимального множества индексов заданий, р-максимальные множества играют важную роль, поскольку, как показано в следующем параграфе, индексы в таком множестве должны появляться в виде непрерывной последовательности во всех оптимальных перестановках. Наконец, мл дадим двойственную формулировку в терминах конечных множеств и р-минимальных множеств, которая используется при доказательстве оптимальности алгоритмов составления расписаний. [18]
Эти две ФКВ корректно определены в силу компактности S. Проверим, что они оптимальны по Парето. Если Ае доминиру-ется вектором v е S, то можно считать, что vАе, а поскольку S исчерпывающее множество, значит, можно найти ASA и А е е 5, противоречие. Доказательство оптимальности по Парето р ( S) на множестве 5 аналогично. Тем самым мы только что доказали, что дилемма равенство - эффективность для S не возникает. [19]
В этом случае оптимальное решение состоит в следующем: надо разбить множество деталей на две группы. К первой отнесем все детали, для которых время обработки на первом станке меньше времени обработки на втором станке, ко второй группе - все остальные. Расписание составим так: на первый станок сначала запустим все детали первой группы в порядке возрастания времени их обработки на первом станке, а затем детали второй группы в порядке убывания времени их обработки на втором станке. В книге 172 ], в которой вопросы планирования работы производственного участка рассмотрены более подробно, приведено доказательство оптимальности этого расписания. [20]
Страницы: 1 2