Файл: Математическое программирование и производственные задачи..pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.10.2024

Просмотров: 63

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

§ 3. ЗАДАЧА ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ТЕХНОЛОГИИ

ИЗГОТОВЛЕНИЯ ДЕТАЛЕЙ

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

Для составления экономико-математической модели ука­

занной задачи введем следующие обозначения:

 

Ь/,{к = \,

2............К)

объем запаса k-ro

производствен­

ного

фактора;

 

 

 

 

 

 

d[(l==\, 2, . . ., L)

запланированное

количество изго­

товления деталей /-го вида;

 

 

 

Q;x,(/=1,

.2,

. . ., т- у=1, 2,

. . ., /г;

/=1, 2 ............L;

k — \,

2, . . .,

К )

норма

расхода

к -го производственного'

фактора при реализации у-го варианта /-он технологической операции изготовления /-го вида деталей*.

Сщ (/=1,

2, . .

ш\ j —1, 2, . .

 

п; 1=1, 2 ,. .

-

норма расхода

минимизируемого

фактора

при

реализации

/-ой технологической операции

изготовления

деталей /-ого

вида по у-ому варианту;

 

 

 

 

 

 

 

 

 

 

(/=1,

2, . .

т; /=1,

2, . . .,

п-

1 = 1,

2............L)

-переменная

величина, определяемая

условиями

 

 

* Если при изготовлении деталей /-ого

вида

либо

ая

операция

не

участвует (для k-

1, 2 ............К и j -

1,

2,

•

• ., л),

либо

ее

невозможно

реализовать /-ым

вариантом

(для

к

=1,

2, . .

.,

К),

то

нормативы а кщ

при решении практических

задач

принимаются

произвольно большими.

 

59

1, если t-ая технологическая операция изготовления деталей /-го вида осуществляется по у'-ому варианту;

О, в противном случае.

Задача определения оптимальной технологии математи­ чески формулируется следующим образом.

Минимизировать линейную функцию

L

т

п

Сц1 d t Xiji

/ = 1

I

I

i- i

;~i

у-

1

при условиях

п

у .*ijl = 1, /= 1, 2, . . ., т; 1 = 1, 2, • • „ Ц /'-1

L

/ т

п

a tл

Xiji

^ d [< b k,

k = \,

2,

 

 

^

(У

У

• .

К ,

1

 

1

 

 

 

 

/ 1 V “ |i

 

 

 

 

 

 

Хщ > 0 ,

/=1 , 2,

. .

., т ; j = l ,

2, .

. ., п\

1= 1,2, .

(3.1)

(3.2)

(3.3)

г

 

 

 

(3.4)

Xijl— целые числа, /= 1, 2, . .

., /га;

/ =1, 2,

■ ■ ., П\

/=1,

2, . .

., L.

(3.5)

Целевая функция (3.1) представляет собой суммарный расход выбранного (дефицитного) производственного факто­ ра.

Условия (3.2), (3.4) и (3.5) означают, что каждая техно­ логическая операция изготовления деталей каждого вида может осуществляться только одним из возможных вариан­ тов.

Условие (3.3) означает, что суммарные расходы каждого производственного фактора при выполнении плана не должны превосходить имеющегося в наличии объема ресурсов этого фактора.

При каждом фиксированном

/

прямоугольная матрица

|Xiji |тл„ ,

элементы

которой

удовлетворяют

условиям

(3.2) (3.5),

определяет

некоторую

технологию

изготовле­

ния деталей /-го

вида.

 

 

 

 

Задача

(3.1)

— (3.5)

является

 

задачей целочисленного

линейного программирования с булевыми переменными. Для ее решения можно применять один из известных методов це­

60

лочисленного линейного программирования. Однако решение задачи (3.1) — (3.5) указанными методами связано с опреде­ ленными трудностями. Специфический характер поставлен­

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

щие обозначения:

 

 

 

 

 

 

 

 

/.

/ т

W

\

 

2, . . ., K,

(3.6)

'к -

V

( V min a?

k= \ ,

!' i

V- 11 i:„

/

 

 

 

 

 

к

min a f7 , i= \ ,

2, .

. ., m ; 7 = 1 ,

2, . .

n\

ill

1 j

n

 

 

L-

 

2............К.

 

 

/= 1,

2, .

.

А=1,

 

 

 

 

 

 

 

 

(3.7)

Ясно, что для разрешимости

 

задачи (3.1)- (3.5) необ­

ходимо выполнение условий Д^Д-О,

k = \ ,

2, . .

., К.

Вели­

чины Д* будем называть резервами соответствующих произ­

водственных факторов, а величины

-

приращениями

расходов этих факторов при замене

варианта с минималь­

ными нормативами на у'-ый вариант

реализации технологи­

ческой операции. При помощи величин 3fy7

и А*, можно из

дальнейшего рассмотрения исключить

все

варианты реали­

зации технологических операций,

которые

 

заведомо нару­

шают разрешимость поставленной

задачи.

 

Действительно,

если

 

 

 

 

 

 

 

 

(3-8)

то при у-ом варианте реализации г-ой технологической опе­

рации изготовления деталей

I-го вида расходы k-ro факто­

ра производства

превышают

наличные

ресурсы.

Поэтому,

если для

заданных индексов

г, J,

I \\ k

выполняется усло­

вие

(3.8),

то для всех k= \ ,

2,

К числа ц*7 заменяют­

ся

произвольно

большими величинами

(т. е. принимается,

Что l -ую технологическую операцию изготовления

деталей

^-го вида

невозможно реализовать

у'-ым

вариантом). Ука­

занная процедура исключения вариантов за конечное число Шагов приведет либо к неразрешимости задачи (3.1)—(3.5), либо к матрицам, позволяющим из дальнейшего рассмотре­ ния исключить определенные столбцы (соответствующие ва-

61

риангы нереализуемы) или строки (соответствующие техно­ логические операции реализуются единственным вариантом)

Отметим, что при L ~ \ и ^

= 1 получаем задачу опреде­

ления оптимальной технологии

изготовления единственной

детали, которая совпадает с задачей определения оптималь­ ной технологии очистки засоренных твердыми почвами земель­ ных площадей [11].

В указанной работе приведена процедура возможного уменьшения размеров матриц нормативов производственных факторов для L— 1, которая может применяться и для Z)> 1.

Кроме того, дан алгоритм решения задачи при L=\ \\йх= 1.

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

зависящей от векторного параметра при достаточно простых

условиях.

 

 

 

 

 

Здесь вместо

задачи

(3.1) — (3.5)

рассматривается сле­

дующая

задача.

 

 

 

 

Для

каждого

вектора Х>О Q^RK) построить функцию

 

 

L

п т .

К

 

/:'(A)=min/1==min 2

 

+

‘

 

 

Z - 1 Z ~ 1 p i

к - 1

где минимум берется на множестве, определяемом условиями

(3.2), (3.4) и

(3.5).

 

Цель этой

задачи заключается

в нахождении точки л0,

при которой выполняются условия

(3.2) — (3.5).

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

Непосредственной проверкой можно убедиться, что в точке /.=0 функция F(\) порождается базисом, соответству­ ющим опорному плану с элементами

* Из экономического смысла задачи ясно, что F(k)5zO при Х.;5Ю,

поэтому случай неограниченности невозможен.

62

Смотрите также файлы