|
если Х^\ есть решение задачи Pr+h то оно принадлежит Fr4. (2.9.) Из этих двух утверждений следует, что X,*i принадлежит Fr+/, если Xг принадлежит Fr. Теперь очевидно что Хо принадлежит Fq; индукция устанавливает, что Хг принадлежит Fr для всех г < п и, следовательно, Хп принадлежит Fn. Доказательство (2.9.) очевидно. Так как множество Fn не пустое, то существует такое множество элементов х,у, принадлежащих F„ для которого линейная форма (2.7.) принимает значение, по крайней мере, не меньшее, чем Гг+/ (так как элемент из Fn всегда принадлежит Fr для всех г). Из (2.8.) тогда следует, что форма (2.7.) должна принимать значение, не меньшее, чем то, которое получается при замене х,у на Следовательно, ХТ*\ принадлежит /7+/. Для доказательства (2.8.) предположим, что Хг принадлежит Fr. Строим Хг-низ Хг путем использования машинного времени, оставшегося после выполнения г-го вида работ, на выполнение работ (гЫ)-го вида в соответствии с алгоритмом. Легко видеть, что множество X»i образует базис для задачи линейного программирования. По построению существует т+r базисных переменных, больших нуля, которые образуют цепочку, тянущуюся вправо и вниз в матрице размерности (т, г+1) с элементами (х^), начинающуюся с хн и оканчивающуюся в xwz.i. (Если Д и Tj кончаются одновременно, то мы полагаем в базисе хм,, = 0.) Пусть Pi и qj двойственные переменные, относящиеся к неравенствам (2.5.) и (2.6.) соответственно. Из соотношений двойственности следует, что a^-Pi <0 (i=l,... т). Неравенства (2.10.) и (2.11.) можно записать в виде (2.10.) (2-11.) |
(3.2.4)х,у > О, = (3.2.5) У«1 ^а,х,>Т. (У = 1,..,г). (3.2.6) 1=1 Мы покажем, что если Fn не пусто, то оно содержит Хп. Обозначим через Рг+/ адачу максимизации линейной формы » (3.2.7) /=i де элементы х/,г+, принадлежат />; другими словами, задача Pr+j состоит в гаксимизации количества выполненных работ (г+/)-го вида при условии, что довлетворены все требования, относящиеся к первым г видам работ. Мы хотим .оказать следующие два утверждения: если Xг принадлежит Fr, то Xr+i есть решение задачи Рг+ь (3.2.8) если Х„\ есть решение задачи Pr+j, то оно принадлежит Fr+j. (3.2.9) Из этих двух утверждений следует, что Хг+\ принадлежит Fr+/, если Yr принадлежит />. Теперь очевидно что Хо принадлежит Fo ; индукция сганавливает, что Хг принадлежит Fr для всех г < п и, следовательно, Y„ принадлежит Fn. Доказательство (3.2.9) очевидно. Так как множество Fn не пусто, то существует акое множество элементов х#9 принадлежащих Fr, для которого линейная форма (3.2.7) [ринимает значение, по крайней мере, не меньшее, чем 7>+/ (так как элемент из Fn сегда принадлежит Fr для всех г). Из (3.2.8) тогда следует, что форма (3.2.7) должна [ринимать значение, не меньшее, чем то, которое получается при замене на Хг+\. Следовательно, JYr+i принадлежит Для доказательства (3.2.8) предположим, что Хг принадлежит Fr. Строим Хгяиз Yr путем использования машинного времени, оставшегося после выполнения r-го вида >абот, на выполнение работ (г+1)-го вида в соответствии с алгоритмом. Легко видеть, что множество Хг+\ образует базис для задачи Рг+/ линейного [рограммирования. 61 По построению существует w+r базисных переменных, больших нуля, которые бразуют цепочку, тянущуюся вправо и вниз в матрице размерности (т, г+1) с лементами (х#), начинающуюся с хи и оканчивающуюся в хт^\. (Если М и 7} ончаются одновременно, то мы полагаем в базисе хм,/ = 0.) Пусть pi и qj двойственные переменные, относящиеся к неравенствам (3.2.5) и 3.2.6) соответственно. Из соотношений двойственности следует, что а^-р,<0 (i=l, m;j=l, ..., г) (3.2.10) ai>r^} -pi <0 (i=l,m). (3.2.11) Неравенства (3.2.10) и (3.2.11) можно записать в виде aijqi-pi<0 (i=l, ..., m;j=l, r+1) qr4=l(3.2.12) Определим qt и ph потребовав в (3.2.12) строгого равенства для базисных {временных; итак, необходимо, чтобы а,уф ~Pi= 0 при мех i>j> которым соответствует ху > 0 (3.2.13) Покажем, что (3.2.12) имеет место также и для любого из небазисных [временных, такого, как, скажем, х^9; мы покажем, что р. ! q i ^->1. (3.2.14) ak,J« Теперь можно xiJo выразить с помощью элементов подмножества базисных юременных х/(7о, х/,у,, х/2у,,..., ху4; эти элементы вместе с xVo образуют множество грайних точек замкнутой оболочки элементов матрицы (х,у). Для упрощения обозначений введем (W’V) = a/..AТогда из (13) получим (u,u-i) = —— (0Л) = ^4,. Следовательно, (н,м-1) _ qiu («,«) Дробь в (14) теперь можно переписать в виде 62 |