close

Вход

Забыли?

вход по аккаунту

?

113.Реализация задачи динамического линейного программирования при оптимальном планировании судостроительного производства

код для вставкиСкачать
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
3. Булавский В. А. О решении задач оптимального раскроя линейных материалов на ЭВМ /
В. А. Булавский, М. А. Яковлева // Математические методы в технико-экономических расчетах:
материалы науч. совещ. — М.: АН СССР, 1961. — Т. IV.
4. Информационные технологии в транспортной логистике: сб. материалов / сост. А. К. Труханов. — М.: КИА центр, 2000. — 81 с.
5. Мухачева Э. А. Методы условной оптимизации в задаче рационального раскроя листового
проката / Э. А. Мухачева // Оптимизация: сб. науч. тр. СО АН СССР. — 1978. — Вып. 22.
6. Мухачева Э. А. Рациональный раскрой промышленных материалов. Применение в АСУ /
Э. А. Мухачева. — М.: Машиностроение, 1984. — 176 с.
7. Мухачева Э. А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки / Э. А. Мухачева // Сб. науч. тр. СО АН СССР. — 1966. — Вып. 6.
8. Мухачева А. С. Задачи двумерной упаковки: развитие генетических алгоритмов на базе
смешанных процедур локального поиска оптимального решения / Э. А. Мухачева [и др.] // Прил. к
журн. «Информационные технологии». — 2001. — № 9. — 24 с.
9. Мухачева Э. А. Метод перестройки для решения задач прямоугольной упаковки / Э. А. Мухачева, А. С. Мухачева // Информационные технологии. — 2000. — № 4.
УДК 681.322
В. Д. Чертовской,
д-р техн. наук, профессор,
СПГУВК
РЕАЛИЗАЦИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ ПРИ ОПТИМАЛЬНОМ ПЛАНИРОВАНИИ
СУДОСТРОИТЕЛЬНОГО ПРОИЗВОДСТВА
REALIZATION OF DYNAMIC LINEAR PROGRAMMING TASKBY OPTIMAL
MANUFACTURING PLANNING
Выпуск 3
Показана необходимость рассмотрения процедур перехода от задачи динамического линейного программирования к статическому линейному программированию и возможности ускорения расчетов адаптивных автоматизированных систем управления производством. Излагаются теоретические основы реализации и прикладное выполнение задач с использованием СУБД.
Necessity to consider procedures of transition from dynamic linear programming task to static linear programming task and computations accelerate convenience of adaptive automatized control of manufacturing are
shown. Theoretical basis of realization and applied execution of tasks with application of Databases Control Systems are set.
78
Ключевые слова: адаптивные автоматизированные системы, реализация, задача динамического линейного программирования.
Key words: adaptive automatized system, realization, dynamic linear programming task.
Введение. В современных организационных системах, например в судостроительных производствах, для процесса планирования все чаще [1, с. 123–128; 2] используют
задачу динамического линейного программирования.
Постановка задачи. Задача ДЛП имеет
следующий математический вид:
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
задачу ДЛП к задаче статического линейного
программирования
z(t) = Az(t1) + Bp1(t), z(0) = z0, (1)
p(t) = Cz(t), (2)
G(p) = FP Æ max, (6)
Dp1(t) ≤ b(t1), p(t) ≥ 0, (3)
N
b* ≤ Dp ≤ b*, (7)
R(T) ≤ Σp(t) ≤ R (T), (4)
+
d* ≤ p ≤ d*, (8)
t=1
N
G = FΣp(t) Æ min, (5)
где d*, d* — нижнее и верхнее ограничения
плана.
В то же время в работе [2] показано, что
задача (1)–(5) сводится к задаче
t=1
где R(T), R+(T) — нижнее и верхнее значения
спроса; z, p — векторы планового незавершенного производства и ежедневного плана,
p1 — вектор запуска комплектов материалов
в производство, D — матрица норм расходов,
b — вектор наличного количества ресурсов;
F — прибыль от выпуска единицы продукции, A, B, C — матрицы соответствующей
размерности, отражающие динамику процесса планирования; τ, T (T = Nτ, N — целое
число) — минимальный интервал времени и
время моделирования.
Трудность решения задачи ДЛП заключается в специфическом учете динамики выражениями (1) и (2). Для успешного решения
задачи следует первоначально привести [2]
b*(t 1) ≤ Dp(t) ≤ b*(t 1), (9)
d*(t) ≤ p(t) ≤ d*(t), (10)
N
R(T) ≤ Σp(t) ≤ R+(T), (11)
t=1
N
G = –FΣp(t) Æ min, (12)
t=1
Ограничения (9), (10) — локальные, ограничение (11) — глобальное. Нетрудно заметить, что задача (9)–(12) обладает значительно
большей размерностью, чем задача (1)–(5).
r
r
p
Выпуск 3
79
Рис. 1. Схема связей БД
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Delphi [2] в квазирежиме клиент-сервер. В то
же время при значительных размерах задачи
необходим полный режим клиент-сервер.
Решение задачи ДЛП предполагает следующие этапы: реализация системы таблиц,
включая триггеры; формирование интерфейса пользователя; построение алгоритма приложения.
Первые два этапа стандартны и не требуют детального освещения. На третьем этапе
следует выделить переход от задачи ДЛП (1)–
(5) к задаче СЛП (6)–(8) и реализацию задачи
СЛП в полном режиме клиент-сервер. Задача
(1)–(5) реализуется по схеме, приведенной на
рис. 1
При решении задачи (9)–(12) может быть
использована БД со схемой, представленной
на рис. 2.
Выпуск 3
В реализации задачи (9)–(12) возникают,
таким образом, два затруднения: повышенная
размерность и наличие глобального ограничения (11).
Решение задачи. Решение этой задачи
возможно с применением стандартных пакетов (например, Excel, MatLab с программой
Linprog). Повышенная размерность задачи
требует ускорения ее решения. Это возможно
сделать двумя путями: формированием более
быстродействующих методов решения и приведением глобальной задачи (9)–(12) к системе
локальных задач.
Использование
быстродействующих
методов. Более быстродействующим методом
является адаптивный метод Р. Габасова [3]. Он
программно реализован на языке программирования Pascal [3] и СУБД InterBase в среде
80
Рис. 2. Схема для задачи ДЛП
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Выпуск 3
81
Рис. 3. БД для задачи ДЛП
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
База данных для этой задачи представлена на рис. 3.
Преобразованная задача может быть
представлена выражениями
J1(p1) = F(A KB)U Æ max, (13)
F* ≤ U ≤ F , (14)
*
R1 ≤ WU ≤ R+1, (15)
Выпуск 3
CAT z0; R+1 = R+
CAT z0;
где R1 = R
K
T
W = C(A B) — матрица; F* = (b*(0) …
b*(N 1)); F*T = (b*(0) … b*(N 1)); K = (N v 1; v =
0, N 1; UT = (p1(0), p1(1), …, p1(N 1,)); (A KB) =
(A N 1B A(N 2B … AB B).
82
Рассмотрим детальнее задачу перехода, спецификой которой является необходимость вычисления матриц At B. Это вычисление значительно сложнее получения
результата произведения двух матриц AB,
которое осуществляется применением функции агрегации Sum и не представляет труда.
Однако получение в одном запросе последующих степеней матрицы A затруднено,
поскольку приходится искать результат для
Sum(A{Sum(At B)}) и т. д. Такую операцию
СУБД выполнить не может и приходится
искать другие пути решения. Чтобы их оперативно апробировать, используем первоначально СУБД Access.
Возможны следующие случаи постановки задачи.
1. Размерность задачи неизменна, меняются лишь числовые данные:
а) система таблиц строится в первый
раз;
б) система таблиц имеется, необходимо
изменить числовые данные.
2. Размерность задачи меняется.
В силу сложности задачи обсудим первоначально ручной вариант ее решения.
Полагаем, что имеются две заполненные
таблицы: МатрА (с полями а, б, A1) и МатрБ
(а, б, Б1).
Начнем с рассмотрения случая 1, а. Схема его реализации (способ 1) представлена на
рис. 3.
Сначала построим запрос А1Б
SELECT МатрА.а, МатрБ.б, Sum([А1]*[Б1])
AS А1Б
FROM МатрА INNER JOIN МатрБ ON
МатрА.б = Мтр_Б.а
GROUP BY МатрА.а, МатрБ.б;
Далее запрос А1Б трансформируем в
таблицу МатрА1Б
SELECT МатрА.а, МатрБ.б, Sum([А1]*[Б1])
AS В1 INTO МатрА1Б
FROM МатрА INNER JOIN Мтр_Б ON
МатрА.б = МатрБ.а
GROUP BY МатрА.а, МатрБ.б.
Аналогичным образом формируется
запрос А2Б и таблица МатрА2Б. Процедура
продолжается, пока не будет построена таблица МатрАnБ.
В случаях 1, б; 2 первоначально корректируются числовые данные таблиц МатрА и
МатрБ, а затем с точки S (рис. 4) возможно
применить макрос.
Недостатком способа 1 является наличие значительного количества запросов и
таблиц (объектов), особенно при большой размерности задачи.
Способ 2 (рис. 5) позволяет сократить
число объектов за счет использования цикла, который можно организовать с помощью
макроса. Используются те же команды, что
и в способе 1. Копия таблицы АrБ необходима как промежуточное запоминающее устройство, поскольку при формировании последующей таблицы А(r + 1)Б предыдущая
таблица должна быть уничтожена, а без нее
не будет существовать соответствующий запрос.
Способ 3, а (рис. 6) предполагает начальное получение таблицы АБ с последующим умножением на таблицу А и записью
результата в специальную таблицу АnБ. Возможно (способ 3, б) и поэтапное получение
значений Аr с последующим умножением на
МатрБ и записью результата в специальную
таблицу АnБ.
Пример реализации способа 3, а приведен в разделе «Моделирование и его результаты». Другие способы также успешно апробированы.
Ж У Р Н А Л
Приведение глобальной задачи к системе локальных задач. Задачу (6)–(9) возможно
решить двумя способами.
1. «В лоб» как единую задачу. Однако
потребуется найти решение для всех p(t), что
связано с решением высокоразмерной задачи.
2. Если бы глобальное ограничение (8)
удалось «разделить» на отдельные интервалы времени, то глобальная задача могла бы
решаться как система локальных задач (отдельно для каждого интервала времени) значительно меньшей размерности. Глобальная
задача в целом решалась бы быстрее.
Будем искать возможности преобразования глобальной задачи без потери оптимальности.
Выделим задачу, которую назовем задачей А, включим выражения (6), (7), (9) и будем
иметь оптимальное решение pА(t). Обозначим
оптимальное решение задачи (6)–(9) через pБ(t).
университета
в о д н ы х
коммуникаций
Рис. 5. Схема преобразования таблиц ДЛП в СЛП
(способ 2)
Рис. 6. Схема преобразования таблиц ДЛП в СЛП
(способ 3)
S
Введем обозначение
N
H(p(t)) = Σp(t), H(pА(t)) = R0.
t=1
При нахождении pБ(t) через pА(t) возможны 4 случая, которые иллюстрируем числовым примером c R А = (0 15 3 0 15 3)T. R0 =
(0 30 6)T
1. H(pА(t)) ≤ R(T) ≤ R0. Программа решения задачи в MatLab имеет вид
Рис. 4. Схема преобразования таблиц ДЛП в СЛП
(способ 1)
Optimization terminated.
Выпуск 3
function x= nlp1m(f,A,b,lb);
f=[-5; -4; -6; -5; -4; -6];
A=[1 1 1 0 0 0; 3 2 4 0 0 0; 3 2
0 0 0 0; 0 0 0 1 1 1; 0 0 0 3 2 4; 0 0
0 3 2 0; 0 -1 0 0 -1 0; 0 0 -1 0 0 -1;
0 1 0 0 1 0; 0 0 1 0 0 1];
b=[20; 42; 30; 20; 42; 30; -27; 5; 30; 6];
lb=zeros(6,1);
[x]=linprog(f,A,b,[],[],lb);
83
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
ans =
0.0000
15.0000
3.0000
0.0000
15.0000
3.0000
Иначе говоря, pБ(t) = pА(t).
2. H(pА(t)) ≤ R(T) > R0.
function x= nlp1m(f,A,b,lb);
f=[-5; -4; -6; -5; -4; -6];
A=[1 1 1 0 0 0; 3 2 4 0 0 0; 3 2
0 0 0 0; 0 0 0 1 1 1; 0 0 0 3 2 4; 0 0
0 3 2 0; 0 -1 0 0 -1 0; 0 0 -1 0 0 -1;
0 1 0 0 1 0; 0 0 1 0 0 1];
b=[20; 42; 30; 20; 42; 30; -31; 7; 32; 8];
lb=zeros(6,1);
[x]=linprog(f,A,b,[],[],lb);
Exiting: One or more of the residuals, duality
gap, or total relative error
has stalled:
the primal appears to be infeasible (and the
dual unbounded).
(The dual residual < TolFun=1.00e-008.)
ans =
0.0000
15.0878
3.9718
0.0000
16.2057
3.4224
Выпуск 3
Задача несовместна.
3. H(pА(t)) ≤ R+(T) ≤ R0.
84
function x= nlp1m(f,A,b,lb);
f=[-5; -4; -6; -5; -4; -6];
A=[1 1 1 0 0 0; 3 2 4 0 0 0; 3 2
0 0 0 0; 0 0 0 1 1 1; 0 0 0 3 2 4; 0 0
0 3 2 0; 0 -1 0 0 -1 0; 0 0 -1 0 0 -1;
0 1 0 0 1 0; 0 0 1 0 0 1];
b=[20; 42; 30; 20; 42; 30; -27; 4; 28; 5];
lb=zeros(6,1);
[x]=linprog(f,A,b,[],[],lb);
Optimization terminated.
ans =
0.6667
14.0000
2.5000
0.6667
14.0000
2.5000
Иначе говоря, pБ(t) < pА(t).
4. H(pА(t)) ≤ R+(T) > R0.
function x= nlp1m(f,A,b,lb);
f=[-5; -4; -6; -5; -4; -6];
A=[1 1 1 0 0 0; 3 2 4 0 0 0; 3 2
0 0 0 0; 0 0 0 1 1 1; 0 0 0 3 2 4; 0 0
0 3 2 0; 0 -1 0 0 -1 0; 0 0 -1 0 0 -1;
0 1 0 0 1 0; 0 0 1 0 0 1];
b=[20; 42; 30; 20; 42; 30; -27; 4; 31; 7];
lb=zeros(6,1);
[x]=linprog(f,A,b,[],[],lb);
Optimization terminated.
ans =
0.0000
15.0000
3.0000
0.0000
15.0000
3.0000
Иначе говоря, pБ(t) = pА(t).
Таким образом, может быть предложен
следующий алгоритм решения задачи (6)–(9).
1. Решается N задач А. Находятся их решения pА(t), определяется вектор R0.
2. Для случаев 1 и 4 решение найдено.
3. В случае 2 система несовместна и требуется определить условия совместности
4. В случае 3 следует решать задачу
целиком. Правда, в [4] предложен другой вариант. Задача А трансформируется в двойственную. Добавляется условие (8) и решается двойственная задача. Однако здесь не-
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
обходим алгоритм двойственного симплексметода.
Моделирование и его результаты.
Проверим справедливость сказанного на числовых примерах в СУБД Access и InterBase.
СУБД Access. Для примера опишем более подробно реализацию способа 3 (рис. 6)
в СУБД Access. Создаются таблицы A(i, j,
val) = B(i, j, val). Для проверки работоспособности алгоритма принята матрица
A=
1
2
3
4
Запрос zapAB
SELECT B.i, B.j, B.val INTO AB FROM B;
на создание таблицы формирует копию таблицы A.
Запрос zapAB на создание таблицы AB
имеет вид
SELECT A.i AS i, AB.j, Sum([A].[val]*[AB].[val
]) AS val INTO proizved
FROM A INNER JOIN AB ON A.j = AB.i
GROUP BY A.i, AB.j;
Рис. 6. Реализация способа 3
Матрица AnB, n порядок матрицы A,
формируется запросом proizv на создание таблицы proizved
SELECT A.i, B.j, Sum([A].[val]*[B].[val]) AS val
INTO AB
FROM T_A INNER JOIN B ON T_A.j = B.i
GROUP BY T_A.i, B.j;
Запрос zapobr на создание таблицы AB
сформирован так
SELECT proizved.i, proizved.j, proizved.val
INTO AB
FROM proizved;
Выпуск 3
85
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Предпочтительным является первый
случай.
Пусть имеются таблицы
Create table A
(i integer,
j integer,
val integer);
Create table B
(i integer,
j integer,
B integer);
Create table AB
(i integer,
j integer,
B integer);
Формирование выходных таблиц осуществляется системой видов типа
CREATE VIEW PREOBRAZ2 ( I, J, S)
AS
select A.i, preobraz1.j, SUM(val*M)
from A, preobraz1
where A.j=preobraz1.i
GROUP BY A.i, preobraz1.j;
Пример результата показан на рис 7.
Недостатком данной реализации является необходимость формирования таблиц и
видов с избыточным, порой не используемым
количеством полей.
Выпуск 3
Для упрощения интерфейса созданы
два макроса. Макрос zapAB активизирует запрос zapAB.
Макрос multiple состоит из нескольких
макросов: макросы proizv и zapobr запускают
одноименные запросы.
Тогда получение выражения An проводится в два этапа. Сначала запускается один
раз макрос zapAB, а затем (n раз макрос multiple. Результат получается в таблице AB.
При изменении размерности необходимо следить за согласованием размерностей
матриц A и B вручную или предусмотреть
программное слежение.
Если бы в запросах proizv и zapobr можно было бы на каждом шаге менять название
AB на AnB, то получилась бы таблица со всеми
полями AnB. Эту таблицу можно было бы использовать для решения (по Р. Габасову) задачи
СЛП, выполняя таким образом задачу ДЛП.
В то же время недостатками использования Access являются ручное формирование промежуточных таблиц и невозможность
реализации полного режима клиент-сервер.
Эти недостатки отсутствуют при применении
СУБД InterBase, в работе с которыми используем опыт, накопленный в экспериментах с
СУБД Access.
СУБД InterBase. Воспользуемся способом 2. В его реализации возможно выделить
два случая: а) запрос и таблица с добавлением полей результирующей таблицы; б) вид с
дополнением полей и преобразованием в таблицу.
86
Рис. 7. Преобразованные матрицы
университета
в о д н ы х
коммуникаций
Рис. 8. Результаты решения
Ж У Р Н А Л
Выпуск 3
87
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Этот недостаток отсутствует при реализации в рамках JavaScript. Отсутствие базы
данных компенсируется возможностью создания таблиц (рис. 8), доступ к которым при
большом их количестве и размерности обеспечивается введением прокрутки.
Отметим универсальность задачи ДЛП.
Она может быть использована не только для
процесса планирования, как рассмотрено ранее, но и для процесса управления. В этом
случае выражения (13)–(15), как показано в
[2], трансформируются к виду
J1(u) = {F(A KB)U C2U} Æ max, (16)
F* ≤ U ≤ F*, (17)
R1 ≤ WU ≤ R+1, (18)
CAT z0; R+1 = R+
CAT z0;
где R1 = R
K
T
W = C(A B) — матрица; F* = (b*(0) …
b*(N 1)); F*T = (b*(0) … b*(N 1)); K = (N v 1;
v = 0, N 1; UT = (u(0), u(1), …, u(N 1,)); (A KB)
= (A N 1B A(N 2B … AB B).
Выражения (13)–(18) определяют суть
однородного метода интегрированного математического описания процессов планирования и управления в адаптивной автоматизированной системе управления производством.
Решенные автором задачи приводят к
появлению новой, требующей решения задачи моделирования процесса планирования на
уровне h = 2 (технологической линии). Линия
представляет собой последовательное соединение подразделений (цехов). Необходимо,
следовательно, построить последовательную
схему решения задач линейного программирования. Для решения задачи можно взять за
основу программу генерации задач линейного
программирования Р. Габасова [3].
Вместе с тем программу следует модернизировать с учетом особенностей процесса
планирования.
Во-первых, элементы всех матриц и векторов должны быть неотрицательны.
Во-вторых, следует провести изменения
в таких направлениях.
1. Задан выход (план), необходимо определить элементы матриц, входа (ресурсов) и
целевой функции.
2. Задан вход (ресурсы), необходимо определить элементы матриц, выхода (плана) и
целевой функции.
3. В направлениях 1, 2 сформировать
коэффициенты целевых функций так, чтобы
задачи соседних связанных подразделений
были не согласованы. Это создает предпосылки для проверки алгоритма горизонтального
согласования [1, с. 123–128].
Заключение. В работе представлен
вариант повышения быстродействия при решении задачи ДЛП, показаны возможности
преобразования задачи ДЛП в задачу СЛП,
глобальной задачи СЛП в систему локальных
задач, что позволяет повысить скорость решения глобальной задачи.
Выпуск 3
Список литературы
88
1. Чертовской В. Д. Информационные технологии в исследовании процесса управления производством / В. Д. Чертовской // Журнал университета водных коммуникаций. — 2010. — Вып. 1.
2. Чертовской В. Д. Интеллектуализация автоматизированного управления производством /
В. Д. Чертовской. — СПб.: Изд-во С.-Петерб. ун-та, 2007. — 164 с.
3. Альсевич В. В. Оптимизация линейных экономических моделей. Статические задачи /
В. В. Альсевич, Р. Габасов, В. С. Глушенков. — Минск: БГУ, 2000. — 210 с.
4. Ашманов С. А. Линейное программирование / С. А. Ашманов. — М.: Наука, 1981. —
340 с.
1/--страниц
Пожаловаться на содержимое документа