Оптимальное одношаговое управление. Транспортная задача

Изучение организации перевозки комплектов из заготовительных в сборочный цех и обеспечения бесперебойной работы всех цехов. Построение математической модели транспортной подсистемы завода. Решение производственной задачи в условиях аварийной ситуации.
Краткое сожержание материала:

Размещено на http:///

Задание. Исходные данные

Транспортная подсистема завода обслуживает три заготовительных А_i , i=1,2,3 и три сборочных В_j , j=1,2,3 цеха, находящихся на значительном расстоянии друг от друга. Каждый заготовительный цех производит весь набор комплектующих изделий, необходимый для работы сборочных цехов. Заготовительный цех A_i производит в сутки a_i. комплектов изделий, а сборочный цех B_j реализует в сутки b_j комплектов, i, j=1,2,3. Известны стоимости S_ij перевозки одного комплекта из цеха А_i в цех В_j.

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

Как должна быть скорректирована работа транспортной подсистемы, если вышел из строя один заготовительный цех (например, А₁) и его функции взял на себя другой цех (например, А₂)?

Таблицы исходных данных

Таблица1

a1	a2	a3	a4	a5	a6
150	250	400	300	200	300

Таблица2

S11	S12	S13	S21	S22	S23	S31	S32	S33
2	1	3	1	4	3	4	1	1

Транспортная подсистема как объект управления

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



Рис.1

На входы объекта ОУ поступают материальные потоки суточные количества комплектов изделий. Их можно трактовать как управляющие воздействия. На выходе объекта имеем информацию о затратах на реализацию этих потоков общую стоимость перевозок комплектов. Ее можно трактовать как выходной параметр объекта. Задача управления объектом состоит в надлежащем выборе поступающих на объект управляющих воздействий, обеспечивающих минимизацию его выходного параметра.

Построение математической модели

заготовительный математический аварийный транспортный

На первом этапе строится математическая модель транспортной подсистемы завода соответственно возложенным на нее функциям.

Обозначим через x_ij количество перевозимых комплектов из заготовительного цеха А_i в сборочный цех В_j, а через S суммарную стоимость перевозок. В этих обозначениях транспортную подсистему можно представить в виде объекта управления ОУ с управляющими воздействиями x_ij и выходным параметром S. Внутреннее состояние объекта описывается суточными производительностями а_i и b_j заготовительных и сборочных цехов, а также стоимостями S_ij перевозок грузов из первых во вторые, i, j=1,2,3 (рис. 2).



Рис.2

Реальные условия функционирования объекта накладывают ограничения на его управляющие воздействия :

x₁₁+x₁₂+x₁₃=a₁

x₂₁+x₂₂+x₂₃=a₂

x₃₁+x₃₂+x₃₃=a₃ (1)

x₁₁+x₂₁+x₃₁=b₁

x₁₂+x₂₂+x₃₂=b₂

x₁₃+x₂₃+x₃₃=b₃

, i,j=1,2,3.(2)

Уравнения системы (1) вытекают из требования бесперебойности работы заготовительных и сборочных цехов (рис. 3). Неравенства (2) (их 9) отражают условия физической реализуемости потоков грузов.

Размещено на http:///

Выходной параметр объекта предстает в виде линейной комбинации его управляющих воздействий:

(3)

Соотношение (3) совместно с ограничениями (1) и (2) можно рассматривать как математическую модель объекта. Она дает исчерпывающую информацию для решения связанных с его функционированием задач.

Задача управления, в отличие от классических математических задач, имеет не одно, а множество решений. Применительно к рассматриваемому объекту управления любые значения его управляющих воздействий x_ij (в дальнейшем будем именовать их переменными), удовлетворяющие условиям (1) и (2), являются таким решением. Совокупность всех решений в пространстве переменных x_ij образуют n-мерный (в нашем случае n=9) многогранник, именуемый многогранником допустимых решений. В каждой из точек многогранника выходной параметр S объекта управления принимает разные значения. Этот параметр служит одновременно и показателем качества управления объектом. В тех случаях, когда ставится задача минимизации показателя качества, последний именуется целевой функцией.

В свете изложенного, математическая формулировка решаемой нами задачи выглядит так: найти переменные x_ij ,i , j=1,2,3, минимизирующие целевую функцию (3) на многограннике допустимых решений (1), (2).

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

Анализ математической модели

На втором этапе решения задачи анализируется математическая модель объекта и преобразуется к более удобному для последующих действий виду.

Бесперебойное функционирование объекта возможно лишь в том случае, если общее количество комплектов a₁+a₂+a₃ , изготовленных в сутки заготовительными цехами, равно общему количеству комплектов b₁+b₂+b₃ , используемых в сутки сборочными цехами. Коль скоро так, суммы трех первых и трех последних уравнений системы (1) дают один и тот же результат. Отсюда следует, что уравнения системы зависимы, и, значит, одно из них может быть опущено. Какое уравнение опустить, существенной роли не играет. Пусть для конкретности последующих рассуждений опущено третье уравнение.

Итак, система (1) предстает как система пяти уравнений с девятью переменными:

x₁₁+x₁₂+x₁₃=a₁

x₂₁+x₂₂+x₂₃=a₂

x₁₁+x₂₁+x₃₁=b₁ (4)

x₁₂+x₂₂+x₃₂=b₂

x₁₃+x₂₃+x₃₃=b₃

В этой системе четыре переменных (9-5=4) могут принимать любые значения в пределах ограничений (2), а остальные пять будут зависеть от них. Первые называют свободными, вторые базисными переменными.

После того как свободные переменные приняли некоторые значения, система (4) превращается в систему пяти уравнений с пятью неизвестными. Она имеет единственное решение. Решение исходной системы (4), при котором свободные переменные полагаются равными нулю, называется базисным решением. Если при этом базисные переменные оказались неотрицательными, оно именуется допустимым базисным решением.

Разбиение переменных на свободные и базисные в известной степени произвольно. Следует учитывать лишь одно условие: свободными переменными не могут быть одновременно три переменных с одинаковыми первыми или вторыми индексами.

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

Как выбрать свободные переменные, чтобы соответствующее им базисное решение было допустимым базисным? Общих рекомендаций на этот счет нет. В отдельных случаях можно воспользоваться таким правилом:

-если для какого-либо сочетания i , j и k в...