|
Алгоритм. Предлагается следующий алгоритм выбора оборудования для выполнения работ. Сначала назначаем машины самого мощного типа на самые трудоемкие работы. Если все необходимые работы данного вида могут быть выполнены с помощью имеющихся машин данного типа, то оставшиеся неиспользованными машины этого типа направляются на выполнение следующего по трудоемкости вида работ. Так продолжаем до тех пор, пока не исчерпаем запас машин наиболее мощного типа; затем то же самое проделываем с машинами второго по мощности типа. Процесс оканчивается в одном из следующих двух случаев: либо все машины, которые способны выполнять работы данного вида, уже использованы, но не все работы еще окончены, и в этом случае программа работ неосуществима; либо имеющихся машин окажется достаточно для назначения на все виды работ, и в этом случае программа работ осуществима. Второе утверждение очевидно; трудности вызывает доказательство критерия неосуществимости, так как с первого взгляда может показаться, что назначение машин на работы, отличное от назначения самых мощных машин на самые трудоемкие работы, приведет к тому, что программа будет осуществима, в то время как предлагаемый выше алгоритм утверждает обратное. В действительности же как мы это увидим далее такая возможность исключена. Более того, будет показано, как с помощью этого алгоритма решить эквивалентную задачу линейного программирования. Представляем математическую формулировку формирования и решения данной задачи. Обозначим через а у количество работы у'-го вида, которое приходится при выполнении этой работы машинами /-го типа на единицу мощности этих машин. Тогда упорядочение машин по мощности, а работ по трудоемкости можно выразить следующим образом: есливу> 0 и i’ < i, то а^> 0; еслиау> 0 и j’ |
энного вида могут быть выполнены с помощью имеющихся машин данного типа, то ставшиеся неиспользованными машины этого типа направляются на выполнение ледующего по трудоемкости вида работ. Так продолжаем до тех пор, пока не счерпаем запас машин наиболее мощного типа; затем то же самое проделываем с (ашинами второго по мощности типа. Процесс оканчивается в одном из следующих вух случаев: либо все машины, которые способны выполнять работы данного вида, же использованы, но не все работы еще окончены, и в этом случае программа работ еосуществима; либо имеющихся машин окажется достаточно для назначения на все иды работ, и в этом случае программа работ осуществима. Второе утверждение очевидно; трудности вызывает доказательство критерия ^осуществимости, так как с первого взгляда может показаться, что назначение машин :а работы, отличное от назначения самых мощных машин на самые трудоемкие •аботы, приведет к тому, что программа будет осуществима, в то время, как ’редлагаемый выше алгоритм утверждает обратное. В действительности же как мы то увидим далее такая возможность исключена. Более того, будет показано, как с юмощью этого алгоритма решить эквивалентную задачу линейного фограммирования. Математическая формулировка. Обозначим через а,у количество работы у-го вида, :оторое приходится при выполнении этой работы машинами Z-го типа на единицу ющности этих машин. Тогда упорядочение машин по мощности, а работ по рудоемкости можно выразить следующим образом: если a,j> 0 и i’ (3.2.2) Предположим далее, что если / Это означает, что если использовать машины /-го типа ia у-ых видах работ, то выход работ на единицу мощности будет меньше, чем при ^значении на работы у’-го вида машин /-го типа и применением на них также машин -го типа в необходимом количестве. По определению полагаем, что если для выполнения некоторого количества работ у-го вида требуется одна единица мощности Под машинами мы понимаем установки по переработке нефте-газо-сырья, а под работами реализацию >азличных этапов технологических процессов изготовления продукции. 59 |