Оптимальное комплектование машин в условиях полной определенности

Постановка задачи и выбор критерия оптимизации. Пусть задан не­который технологический процесс, включающий, а операций. Каждая опе­рация может быть выполнена различными типами и типоразмерами машин. Известны приведенные затраты на выполнение каждой операции каждой машиной. Исходная информация, необходимая для формирования опти­мального комплекса машин, представлена в табл. 3.1

 

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

Выявление основных особенностей, взаимосвязей и количествен­ных закономерностей. Изобразим графически все возможные комплексы машин в виде сетевого графа. Каждая операция в сетевом графе (рис. 3.1) представляется в виде стрелки с указанием над ней приведенных затрат на выполнения i-й операции к-й машиной после выполнения у'-й машиной (i -/)-й операции.

Стрелка означает также возможные связи одной машины с другими. Кружочек означает завершение одной операции одним типом машин и на­чало выполнения другой операции другим типом машин.

Число, стоящее в кружочке, означает номер (тип, типоразмер) машины, используемой на предшествующей операции. Число над кружочком означа­ет сквозную нумерацию машин, определяющих допустимое множество машин, для выполнения, данного технологического процесса. Начальный и конечный кружочки сетевого графа означают, соответственно, начало вы­полнения технологического процесса и его завершение, а номера над ними (0 и 11 — номера фиктивных машин). Таким образом, в нашей задаче для формирования оптимального комплекса машин принято 10 машин. Из них по три типа, (типоразмера) на 1-й и 2-й операциях и по два На 3-й и 4-й опе­рациях.

Приведенные затраты C(iJ,k) на выполнение (-ой операции А-ой маши­ной после выполнения у'- ой машиной (i -1)-ой операции даны в табл. 3.1.

Если при выполнении какой-то операции, например транспортировки продукции, габариты и грузоподъемность транспортного средства не соот­ветствуют параметрам погрузочного оборудования, то в этих условиях дан­ное погрузочное оборудование не может быть использовано с данным по­грузочным средством. В этом случае на графе возможных комплексов ма­шин должна отсутствовать связь (стрелка) между этими машинами. Мно­жество такого рода ограничений часто упрощает решение задачи при ис­пользовании специальных методов решения.

Представление всех возможных комплексов машин в виде графа обес­печивает наглядность и простоту формирования допустимого множества.

Данная задача относится к классу комбинаторных, в которых число воз­можных комплексов N = З^шЗ*2*2 = 36.

При увеличении операций и машин на каждой операции резко возрас­тает число возможных комплексов.

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

Метод динамического программирования дает возможность заменить перебор всех вариантов определенной системой действий, при которых отыскание экстремума многих переменных заменяется многократным оты­сканием экстремума функции одиой переменной. Оптимизируемый процесс разделяется на ряд последовательных этапов (шагов). Затем проводится последовательная оптимизация на каждом шаге. В качестве математиче­ской модели может быть использовано функциональное уравнение Беллма­на, которое дает ключ для решения задачи:

где y(i, j) —- минимальные приведенные затраты для комплекса машин, вы­полняющего технологический процесс, начиная с i-й операции и с_/-й машины;

y(i+l,k) — то же,¹ начиная с (i+I)-& операции и с 4-й машины.

Исследование математической модели. Алгоритм оптимизации вы­бора оптимального комплекса машин методом динамического программи­рования состоит из двух основных этапов..

На первом этапе производят расчет критерия оптимизации, для частич­ных комплексов машин начиная с машин, выполняющих последнюю опе­рацию. Постепенно переходя к началу технологического процесса и ис­пользуя функциональное (рекуррентное) уравнение Беллмана, определяют минимальные приведенные затраты.

На первом шаге полагают

 

 

Минимальные значения критерия оптимизации для частичных ком­плексов машин y(i,j) представлены рядом с кружочками.