Software & Systems

При проектировании сложных технических и экономических систем, при обосновании их характеристик и параметров, как правило, возникает необходимость в решении различного рода экстремальных и параметрических задач [1-5]. При автоматизации проектирования технических систем с особой остротой встает проблема использования количественных методов для обоснования проектных решений [6,7]. Дополнительные трудности, связанные с широким участием человека и необходимостью учета такого участия, возникают при проектировании экономических систем организационного типа [8,9]. Современные методы исследования операций [10], особенно методы математического программирования [11], находят при этом широкое применение. Не последняя роль принадлежит теории и методам линейного программирования (ЛП), которые к настоящему времени достаточно хорошо отработаны [12,13] и не порождают новых проблем. Тем не менее, в ЛП ещё имеется одна область, которая не вполне обеспечена достаточно эффективным аппаратом количественного анализа – это область параметрического линейного программирования (ПЛП). В связи с этим основной целью данной работы будет являться изложение нового подхода и его применения для эффективного анализа задач ПЛП.

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

Задача ЛП (ЗЛП)

                         (1)

Dx                    (2)

(Dx – область допустимых решений) путем введения дополнительных неотрицательных переменных ei () сводится к каноническому виду:

                          (3)

Dx     (4)

Переменная ei – разность (невязка) между большей и меньшей частью i-го неравенства (2).

Для дальнейшего решения ЗЛП (3), (4) записывается в виде симплексной таблицы Т1 (с-табл. T1):

                                     Свободные пер.

Базисные пер.

Удобство записи ограничений в виде (4) и Т1 состоит в том, что для соблюдения условий (2) теперь достаточно обеспечить неотрицательность переменных ei , значения которых для базисного решения записаны в правом столбце с-табл. Т1: ei = bi " i. Если для " i : bi ³ 0, то получен опорный план (вершина или грань области Dx). На следующем этапе решения (поиск оптимального плана) нужно добиться неотрицательности значений всех коэффициентов сj при свободных (независимых) переменных в целевой функции (нижняя строка с-табл. Т1).

Поиск опорного плана и оптимального решения осуществляется путем последовательных преобразований с-табл. относительно разрешающего элемента (р-элемента) ars. В результате преобразования базисная переменная er, записанная в разрешающей (i=r) строке (р-строке), меняется местом со свободной переменной xs, расположенной в разрешающем столбце (р-столбце) j=s (er « xs). Такая замена производится в ходе шага обыкновенных жордановых исключений (ОЖИ) по формулам пересчета всехэлементов с-таблицы [13,14]:

ars¢= 1/ars       – р-элемент (i=r, j=s);

ars¢= - arj / ars        – элементы р-строки (i=r, j¹s);     (5)

ais¢= ajs / ars    – элементы р-столбца ( j=s, i¹ r);

aij¢= aij - arj ais/ars – остальные элементы (i¹r, j¹s).

Блок-схема алгоритма определяет условия выбора р-элемента при поиске опорного плана (5о,6о), при минимизации целевой функции (10о,11о), а также условия неограниченности решения (3о,8о) и несовместности (4о) системы неравенств.

Примечание

Если среди ограничений (2) имеются равенства, то каждое из них заменяется двумя неравенствами (³,£) или представляется в виде . “Нулевые” переменные Oi перед началом работы алгоритма должны быть обращены в нуль, путем вывода их из базиса (Oi « xj см. (5)).

Классическая задача ПЛП состоит в количественном анализе влияния параметров ЗЛП ïïbiïï, (cj), ïïaijïï на оптимальное решение, в выявлении области изменения параметров, при которых структура оптимального решения (множество значащих переменных) не меняется. Существующий подход к решению состоит в том, что для исследования влияния некоторого параметра bi (2) вначале находится оптимальное решение исходной ЗЛП. Далее для параметра bi в общем виде вводится приращение Dbi. Затем путем ОЖИ получается тот же базис, что и при оптимальном решении. На конечном этапе определяется область изменения приращения Dbi, не приводящая к изменению структуры оптимального решения (базиса) [14].

Предлагаемый подход к решению задачи ПЛП состоит в том, что до решения ЗЛП всем параметрам bi () даются соответствующие приращения Dbi. Эти приращения наравне с xj ()вводятся как независимые (свободные) переменные, могущие, однако, принимать и отрицательные значения. Решение сформулированной расширенной ЗЛП позволяет определить влияние параметров Dbi на оптимальное решение и провести анализ чувствительности. Рассмотрим реализацию указанного подхода на числовом примере, заимствованном из [14, c.25], что позволит сравнить оба метода.

Пример состоит в определении оптимального плана выпуска продукции X0, максимизирующего общую выручку L(X)

          (6)

при ограничениях на ресурсы:

2,5x1+ 2,5x2 + 2x3 + 1,5x4 £ 100 +D b1,

4x2 + 10x2 + 4x3 + 6x4£ 260 +D b2 , "xj³0 . (7);

8x1 + 7x2 + 4x3 + 10x4 £ 370 +D b3 ,

К исходным ресурсам bi () в (7) добавлены приращения D bi как дополнительные свободные переменные.

Примечание

Если считать, что исходные ресурсы не могут быть отрицательными, то переменные D bi следует ограничить снизу: D b1 ³ -100, D b2 ³ -260, D b3 ³ -370.

Таким образом, задача ПЛП теперь сведена к обычной ЗЛП, и в форме с-табл., с учетом (3), (4) она примет вид:

 (8)

После двух шагов ОЖИ (e1 « x3 , e2 « x4) в соответствии с приведенным алгоритмом получаем конечную с-табл. Т3:

 X0=(0;0;35;20), L(X0)=-L¢ =5100.                      (9)

Одной этой с-табл. достаточно для анализа чувствительности по каждому параметру D bi и по их изменениям в совокупности. Область изменения параметров D bi определяется из условий сохранения базиса по с-табл. Т3:

x3=D b1 -(1/4)D b2+ 35 > 0,

x4= -(2/3)D b1 +(1/3)D b2+ 20 > 0,                          (10)

e3=(8/3)D b1 -(7/3)D b2+D b3+ 30 ³ 0.

Примечание

В первых двух неравенствах исключены случаи x3=0 и x4=0 т.к., строго говоря, это уже меняет структуру оптимального решения.

Из (10) можно установить, что область изменения каждого параметра в отдельности соответственно равна:

- 35 < D b1 < 30 ,

- 60 < D b2 £ 90/7,                                             (11)

- 30 £ D b3 < ¥.

С учетом примечания, области (11) совпадают с областями, полученными в [14, с.66, 67], однако здесь они получены после однократного решения ЗЛП (6), (7).

Коэффициенты в столбцах D bi, записанные в нижней строке с-табл. Т3 как переменные двойственной ЗЛП (-yj0), характеризуют чувствительность ЗЛП к единичным изменениям ресурсов [14, c. 57]., то есть , " i.

Анализ коэффициентов cj (6) как другой группы параметров ЗЛП также может быть проведен после однократного решения двойственной к (6), (7) ЗЛП:

2,5y1 + 4y2 + 8y3 ³ 40 + D c1,

2,5y1 + 10y2 + 7y3 ³ 50 + D c2,

2y1 + 4y2 + 4y3 ³ 100 + D c1,                " i: yi ³ 0.

1,5y1 + 6y2 + 10y3 ³ 80 + D c4,                                (12)

L

После записи ЗЛП (12) в форме с-табл. № 1 (здесь она опускается) и двух шагов ОЖИ (w3«y1,w4«y2,w i - дополнительные неотрицательные переменные) получено оптимальное решение (с-табл. № 3):

(13)

Y0 = (140/3, 5/3, 0, 0), L(Y0) = 5100.

Из анализа условий (с-табл. № 3):

w1 = -Dc1    +    (3/2)Dc3 -(1/3)Dc4 + (250/3) ³ 0,

w2 =      -Dc2                   + (5/3)Dc4 + (250/3) ³ 0, (14)

y1 =                          Dc3 - (2/3)Dc4 + (140/3) > 0,

y2 = - (1/4)Dc3 +(1/3)Dc4 + 5/3 > 0,

получаем области изменения параметров Dcj:

-40 £ Dc1 £ 250/3, -140/3 < Dc3 < 20/3,

-50 £ Dc2 £ 250/3, -5 < Dc4 < 70, (15)

где учтено также условие неотрицательности коэффициентов Dcj , откуда следует Dc1 ³ - 40, Dc2 ³ - 50 и т.д. (см. (12)). Добавив к границам областей изменения Dcj (15) исходные значения cj (12), можно получить и области изменения параметров cj:

0 £ c1 £ 370/3,             160/3 < c3 < 320/3,

0 £ c2 £ 400/3,             75 < c4 < 150.              (16)

Аналогичные результаты были получены в [14 с.63, 65], при этом отклонения в верхней границе для c2 и c4 следует объяснить опечатками в [14], где c2 £ 385/3 и c4 £ 330.

Таким образом, рассмотренный подход к параметрическому анализу ЗЛП существенно упрощает процедуру анализа, сокращает его трудоемкость, но может быть и далее упрощен.

Действительно, сравнивая элементы в столбцах для w3, w4, и Dc3, Dc4 с-табл. №3, видим, что элементы в них соответствено одинаковы. Это обусловлено тем, что дополнительные переменные w j вводятся в равенства (12) так же, как были введены приращения Dcj, а потому можно принять Dcj = w j. Тогда в исходную с-табл. можно и не вводить Dcj," j и решать не расширенную, а обычную исходную ЗЛП. При составлении неравенств (14) вместо невязок w j, выведенных из базиса (с-табл. №3, w3, w4 ), записывать соответствующие им параметры Dc3, Dc4. Те переменные Dcj, которые соответствуют невязкамw j, не выведенным из базиса (w 1, w 2), учитываются в соответствующих неравенствах (14) с коэффициентом -1 (это видно из (13)).

Аналогичную ситуацию имеем при анализе коэффициентов Dbi (с-табл.Т3). Коэффициенты в столбцах e1, e2 и Db1, Db2 отличаются только знаками. Это обусловлено тем, что в неравенства (7) параметры Dbi по сравнению с ei введены с противоположными знаками, что, впрочем, легко учесть (Dbi = -ei ) при составлении системы неравенств (10).

Дальнейшее упрощение параметрического анализа может состоять в том, чтобы решать только один раз и только одну из двойственных задач, т.к. все необходимые данные по обеим взаимодвойственным задачам будут содержаться в конечной с-таблице. Это можно наглядно показать, если с-табл. №3 представить в транспонированном виде и сравнить с с-табл. Т3(9):

Выше и слева от с-табл. N3T записаны соответствующие переменные двойственной к двойственной ЗЛП (т.е. исходной ЗЛП). Противоположность знаков при коэффициентах ai j в с-табл.Т3 и N3T объясняется двойственностью задач и не представляет трудностей для их учета в ходе анализа.

Таким образом, решив исходную ЗЛП, по конечной с-табл. можно провести весь указанный параметрический анализ относительно параметров и .

Рассмотренный подход предоставляет возможности для формулировки и анализа некоторых других задач ПЛП, имеющих немаловажное значение в экономике, при проектировании систем и в других областях.

Первую задачу ПЛП можно назвать задачей об оптимальной стратегии закупки ресурсов (в отличие от задачи об оптимальной стратегии выпуска продукции (6), (7)). Из решения задачи (Т3) следует, что при оптимальном плане выпуска получена прибыль L(X0)= 5100 ед. при остатке ресурсов e3 = 30 ед. (9). Возникает вопрос: сколько и каких ресурсов следовало бы реализовать по существующим на них рыночным ценам, чтобы затем докупить недостающие с целью получения наибольшей дополнительной прибыли?

Полагая стоимости 1 ед. ресурсов i-го вида известными (Si), задачу ПЛП можно сформулировать как задачу определения оптимального (в смысле общей прибыли) вектора параметров b0 = êêbi 0 êê при ограничении на его компоненты

                                  (17)

Общий бюджет Q при этом равен затратам на закупленные ранее ресурсы:

               (18)

где принято ST=(Si)=(1;2;3).

С учетом (6) и (7) задача ПЛП сводится к расширенной ЗЛП:

                    (19)

                     (20)

Примечание

Продукция j=1-го и 2-го видов исключена из рассмотрения как явно невыгодная по сравнению с другими видами. Например, удвоив коэффициенты при x2 в (6), (7), увидим, что при равной прибыли (2c2 = c3) расход ресурсов каждого вида будет больше, чем для 1 ед. продукции j=3. То же имеем и для продукции вида j=1.

Вводя дополнительные неотрицательные переменные  и приводя ЗЛП к виду (3), (4), в форме с-табл. получим:

После 4-х шагов ОЖИ получим конечную с-табл.:

                                                            (21)

Реализовав 370-315=55 ед. ресурсов вида j=3 (см. (7), (21)) и докупив на полученную выручку (DQ » 3 × 55 = 165 ед.) соответственно 57 и 55 ед. ресурсов 1-го и 2-го видов (см.(7)), получим общую прибыль L(X0,b0)=7865 ед.

Таким образом, оптимальная стратегия закупки ресурсов позволила дополнительно увеличить прибыль на 7865-5100=2765 ед. (т.е. на 54%). Интересно отметить, что теневые (скрытые) [14] цены ресурсов yi0 (Т5) оказались пропорциональными рыночным ценам Si:

.                      (22)

Анализ решения показывает, что при оптимальной стратегии закупки ресурсов оптимальная стратегия производства состоит в выпуске только наиболее рентабельной продукции. Действительно, вычислив полные затраты Sj и рентабельность Rj 1 ед. каждого вида продукции по формулам

 (23) получим:

       (24)

Примечание

Из дальнейшего анализа следует, что основной результат, полученный из решения задачи (19), (20), может быть вычислен проще: достаточно весь бюджет Q=1730 ед. потратить на закупку ресурсов для производства только наиболее рентабельной продукции (R3=4,55, j=r=3). При ее себестоимости S3=22 ед. будем иметь:

xr0 = x30 =Q/S3 = 1730/22 » 78.7,

" i: bi0 = air xr0 Þ b0 » (157;315;315),                    (25)

L(X0,b0) = c3x30 » 7865.

Для получения оценок ресурсов (скрытых цен yi0) воспользуемся основной теоремой двойственности ЗЛП [14], согласно которой для рассматриваемых условий имеем:

                                                    (26)

Подставив bi0 из (25) в (26) и поделив равенство на xr0, получим:

                                                        (27)

Учитывая, что при оптимальной стратегии закупки ресурсов теневые цены пропорциональны рыночным (, см. (22)), после подстановки yi0 в (27) будем иметь:

            (28)

Таким образом, коэффициент пропорциональности - ни что иное, как рентабельность наиболее рентабельной (j=r=3) продукции и, следовательно,

 S=(1;2;3)                        (29)

что совпадает с (22).

Вторую задачу ПЛП сформулируем как задачу минимизации затрат на закупку ресурсов для обеспечения заданного уровня выручки Lзад при данных рыночных ценах на ресурсы (), нормах их расхода на 1 ед. продукции ïïaijïï и выручке от реализации 1 ед. продукции j-го вида (cj).

Используя те же числовые данные: что и в задаче (6), (7) и приняв Lзад=5100 ед., задачу минимизации затрат запишем в форме следующей ЗЛП:

                       (30)

2,5x1+2,5x2+2x3+1,5x4 £ b1 ,

4x1+10x2+4x3+6x4 £ b2 ,   "xj,bi ³ 0.               (31)

8x1+7x2+4x3+10x4 £ b3 ,

(L(X)= 40x1+50x2+100x3+80x4) ³ 5100,

Вводя дополнительную неотрицательную переменную L5100=L(X)-5100,                                          (32)

и учитывая (4), задачу запишем в табличном виде:

        (33)

где переменные x1 и x2 по указанной ранее причине исключены из рассмотрения.

Обращая в нуль переменную L5100 путем ее вывода из базиса (это обеспечивает фиксацию L(X) на заданном уровне Lзад), после еще трех шагов ОЖИ (e1 « b1, e2 « b2, e3 « b3) получим конечную с-табл. t5 и оптимальное решение X0, b0:

                                     (y10) (y20) (y30)

X0 = (0;0;51;0), Y0 T =(1;2;3).

b0 T = (102;204;204),                                        (34)

Qmin = Q(X0,b0) = 1122,

Таким образом, оптимальная стратегия закупки ресурсов позволила снизить затраты на них с 1760 до 1122 ед., то есть неоптимальная закупка ресурсов в (6), (7) привела к излишним затратам на 57%. Как видно из (34), оценки используемых (air ¹ 0) ресурсов совпали с их рыночными ценами ("i: yi0 = Si).

Примечание

На основе опыта решения предыдущей задачи решение (34) можно также получить более простым путем.

Так как минимум затрат возможен только при выпуске наиболее рентабельной продукции, то согласно (24) определяется наиболее рентабельная продукция (j=r=3). 1 ед. этой продукции обеспечивает выручку cr=c3=100 ед., следовательно, для достижения заданного уровня потребуется выпустить 51 ед. продукции:

xr0 = x30 = Lзад /cr = 5100/100 = 51.

Требуемые ресурсы и общие затраты определяются по формулам:

" i: bi0 = airxr0, Qmin = Srxr0 ,                                                       (35)

что приведет к (34).

При проектировании систем может возникнуть необходимость знать возможный диапазон изменения тех или иных ее параметров при некоторых условиях. Пусть, например, дополнительные условия отражают требования по стоимости и эффективности проектируемой системы:

L(X0,b0)³ Lзад= 5000,

Q(X0,b0)£ Qдоп= 1200,                                            (36)

Требуется найти возможную область изменения параметра b1 при этих условиях.

Наиболее короткий путь решения данной задачи ПЛП состоит в том, что ограничения (36) вводятся в конечную с-табл. t5. Полученная ЗЛП далее решается на max и на min, причем целевой функцией является параметр b1. Найденные значения b1min и b1max определят собой область его изменения.

Ограничение по стоимости вводится как дополнительная неотрицательная переменная DQ=1200-Q, где Q бертся из нижней строки в t5. Тогда

что и записывается вместо нижней строки в с-табл. t5.

Ограничение по эффективности вводится путем замены свободной переменной L5100 на L5000:

L5100=(L-5000)-100= L5000-100,

при этом элементы правого столбца в с-табл. t5 пересчитываются по формуле:

После введения обоих ограничений с-табл. t5 примет вид:

  (37)

После замены DQ«x4 параметр b1 принимает минимальное значение, при этом

b1min=99,8,      X0»(0; 0; 48.3; 2.16),

L(X0,b)=5000, Q(X0,b)=1200 DQ=1200, "ei=0.

Решение ЗЛП (37) на max() приводит к следующему результату:

b1max=156, X0=(0; 0; 50; 0), e1=56,

однако при этом 56 ед. ресурсов b1 остались неиспользованными.

Рассмотренный подход может быть применен и для анализа параметров  в (2). Пусть для коэффициентов строки i=k (2) введен общий параметр (множитель) tk>0. Тогда, поделив на tk>0 k-ое неравенство, приведем его к виду:

.                                                         (38)

Задача сведена к анализу параметра bk’=bi / tk (при tk<0 изменится только смысл неравенства (38)).

При введении параметра ml для всех элементов ail j=l-го столбца, система (2) примет вид:

                 (39)

Трансформируя ограничения (2) в условия двойственной задачи, для l-го неравенства получим:

                                   (40)

Поделив ограничение (40) на ml>0, приходим к рассмотренной ранее задаче анализа параметра cl’=cl /ml.

Для анализа отдельных параметров aij рассмотренный подход применен быть не может.

Для проектирования экономических систем. Л.В. Канторовичем совместно с группой ученых ГДР разработан комплексный метод управления экономикой [15]. В его основе лежит линейная комплексная модель с дополнительной (параметрической) оптимизацией. Комплексная модель путем многошаговой оптимизации, как отмечается в [15, с. 104], позволяет найти “оптимальные изменения вектора ресурсов, коэффициентов матрицы ограничений и коэффициентов целевой функции”.

Применение изложенного подхода позволит существенно снизить трудоемкость упомянутого комплексного метода.

Список литературы

1. Кудрявцев Е.М. Основы автоматизации проектирования машин.- М.: Машиностроение, 1993.-334 с.

2. Вермишев Ю.Х. Основы автоматизации проектирования.-М.: Радио и связь, 1988.-280 с.

3. Автоматизация проектирования технологических процессов и оснастки: Сб.научн.тр.-Минск: ИТК,1991.-165 с.

4. Кристофер Дж.Дж. Методы проектирования (пер. с англ.).-М.: Мир, 1986.-326 с.

5. Корячко В.П. и др. Теоретические основы САПР: Учебн. пособие.-М.: Энергоатомиздат, 1987.-398 с.

6. Выбор и принятие решений в САПР: Межвуз.СНТ.-Воронеж, 1989.-158 с.

7. Вязгин В.А., Федоров В.В. Математические методы автоматизированного проектирования: -М.:Высшая школа, 1989.-183 с.

8. Автоматизация и проектирование в промышленных системах: Межвуз.СНТ.-Тверь: ТГТУ,1994.-141 с.

9. Егоров В.А. Автоматизация проектирования предприятий.- Л.: Машиностроение, 1983.-327 с.

10. Исследование операций. Методологические основы и методы. /Под ред. Дж. Моудера, С. Элмаграби.-М.: Мир,1981.-707 с.

11. Карманов В.Г. Математическое программирование.-М.: Наука,1986.-285 с.

12. Муртаф Б. Современное линейное программирование.-М.: Мир,1971.-230 с.

13. Банди Б. Основы линейного программирования.-М.: Радио и связь, 1989.-175 с.

14. Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие.-М.:Высшая школа,1984.-256 с.

15. Канторович Л.В. и др. Экономика и оптимизация.-М.:ИзЭМИ АН СССР, Наука, 1990.-248 с.