Если хц = А/,, ТО Х[] =0 для j >1 и Х21 = min(A/2, Т, "31 Г Если хи = —,то х/1 = 0 для i>l и "и X2I = min(M, ,—) "ll ".2 ит.д. Исходя из результатов работы, можно сделать следующий вывод. Если некоторый процесс назначения удовлетворяет заданной программе работ с данным количеством машин, то вышеприведенный алгоритм приводит к этому же результату и, кроме того, максимизирует количество выполненных работ последнего вида, удовлетворяя и всем другим ограничениям. Доказательство. Проведем доказательство по индукции. Пусть Fr множество х,у, удовлетворяющих условиям (ограничениям) •S * 0, (2-4.) У=1 (2.5.) т i=\ (2-6.) Мы покажем, что если Fn не пусто, то оно содержит Х„. Обозначим через Ли задачу максимизации линейной формы , (2.7.) /•! где элементы х,(Г+/ принадлежат Fr; другими словами, задача Рг+/ состоит в максимизации количества выполненных работ fr+7/го вида при условии, что удовлетворены все требования, относящиеся к первым г видам работ. Мы хотим доказать следующие два утверждения: если Xг принадлежит Fn то X„i есть решение задачи Pr+J, (2.8.) |
1ашин /-го типа, то для выполнения этого же количества работ требуется ау/ац единиц ющности машин i -го типа; следовательно, наше предположение можно выразить так: если i < i\ j au (3.2.3) т.к. no (1) из arj> 0 следует oy> 0. Введем следующие обозначения: Mi число единиц мощности машин /-го типа (7=7, 2, т)\ Tj число единиц работыу-го вида, которые необходимо выполнить (/=1, 2, ху число единиц мощности машин /-го типа, предназначенное для гспользования нау-ом виде работ; (ху)г Хг множество тех ху, определенных в соответствии с алгоритмом, сложенным ранее, которые относятся к первым г видам работ. Таким образом, Г хп = ). *п Если xj 1 = Л/,, то х\у = 0 для у >7 и Х21 =min(M2,r, --1—■).. *21 Г Если хп = —, то хп = 0 для / >7 и *п — Т Т хг\ min(A/,-----) *11 *12 и т.д. Мы установим следующий результат. Если некоторый процесс назначения удовлетворяет заданной программе работ с данным количеством машин, то вышеприведенный алгоритм приводит к этому же результату и, кроме того, максимизирует количество выполненных работ последнего шда, удовлетворяя и всем другим ограничениям. Доказательство. Проведем доказательство ио индукции. Пусть Fr множество х,у, удовлетворяющих условиям (ограничениям) 60 |