Тема 10.1. Задача получения продукции

Пусть задано некоторое множество имён товаров (продуктов, сырья и т.п.) и имеется некоторое множество технологических процессов (производств), описывающих возможности получения одних продуктов из других. Каждый технологический процесс задаётся множеством исходных продуктов (входов) этого процесса и результирующим продуктом (выходом) , т.е. процесс позволяет из исходных продуктов получить продукт – его выход. Будем задавать технологический процесс в виде . Продукт, полученный в одном процессе, может далее использоваться в других процессах.

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

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

Пример 10.1: Пусть = {дерево, клей, гвозди, кирпич, стекло, окна, полы, стены, крыша, столы}. Множество технологических процессов задаётся соответствующими множествами входов и выходов.

: {дерево, клей, гвозди } столы

: {дерево, гвозди} полы

: {дерево, клей, стекло} окна

: {стены, полы, крыша} дача

: {кирпич, окна, дерево} стены

Рассмотрим для этой системы технологических процессов задачу получения продукта дача по исходному множеству продуктов: {дерево, клей, гвозди, стекло, кирпич, крыша}.

Нетрудно понять, что эта задача решается положительно с помощью следующей цепочки процессов: ; ; ; . Действительно, в получаются окна, которые используются в для получения стен, в производятся полы, а затем произведённые ранее стены, полы, крыша используются в для получения результата дача.

Подчеркнём, что мы абстрагируемся от количественных оценок исходных и производимых продуктов и считаем, что они всегда даются на входе и производятся в количестве, достаточном для обеспечения «сырьём» всех запускаемых процессов.

Построим формальную модель задачи о производстве с помощью булевых формул.

Будем рассматривать как множество булевых переменных. Каждому процессу с параметрами и сопоставим следующую -формул :

Например, процессу из нашего примера соответствует формула :

(кирпич & окна & дерево) стены.

Сохраним для множества -формул, соответствующих процессам, обозначение .

Справедлива следующая теорема, которая показывает, что задача о возможности получения продукции и задача о следствии из множества -формул эквивалентны.

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

Доказательство:

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

Тогда индукцией по номеру процесса в покажем, что для каждого значение соответствующей результирующей переменной . Действительно, при из применимости процесса следует, что , но тогда для любой переменной и левая часть импликации истинна на наборе . Но так как и вся формула истинна на , то и её заключение тоже истинно на , т.е. . Пусть теперь для некоторого при . Докажем, что и . Поскольку процесс применим после процессов , то . Тогда все переменные из истинны на и, следовательно, .

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

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

Шаг 0.Положим , .

Шаг 1. Положим и .

Пусть уже определены и .

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

Если или , то положим и закончим процедуру.

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

Дата добавления: 2015-10-28