Общее представление о задачах оптимальног ОКП. Обзор методов реш-я задач оптим. ОКП

Среди моделей оптим. план-я работы пром. пред-я особенно важны модели, используемые для реш-я задач упр-я технологич-ми производств. процессами. Они позволяют установить наилучший режим д-ти внутризаводских подразделений во времени. Для составления оптим-х календ-ых планов-гр-ков работы отдельных участков пред-я примен. большой арсенал мат. м-дов объединенных под общим названием м-дов КП. Рассмотрим общую постановку задачи КП применительно к машиностр-му пр-ву. Предположим, что в цехе имеется обор-е m разл. видов. Оно применяется при изгот-и деталей n видов, потребность в деталях в план. периоде Т опред-ся планом выпуска готовых изд-й пред-я. Причем план выпуска изд-й задается с разбивкой на одпериоды план. периода Т (по декадам).

Известно: - нормы з-т времени на обработку разл. деталей на станка каждого типа; - длит-ть переналадок обор-я при переходе от обработки одних деталей к другим; - технологические маршруты движ-я деталей в процессе обработки. Требуется опред-ть такой режим работы обор-я, при кот. план-гр-к выпуска гот. изд-й будет полностью обеспечен необходимым кол-вом деталей. Критерий оптимальности – min сум. з-ты в план. периоде Т.

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

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

2. Для отд. наимен-я дет-ей, потребность в кот. неравномерна во времени. Треб-ся опред-ть оптим. режим пр-ва и хранения. Крит. оптим-ти – min з-т обусловленных как неравномер-ю гр-ка пр-ва д-ей, так и содержанием их запасов.

3. В зад.2 рассматр. Отдельное наимен-е д-ей и не учит-ются др., кот-е д.б. сделаны в план. периоде Т. Возникает более сложная зад. оптим. план-я пр-ва и хран-я разл. видов д-ей. Целью решаемой зад. явл-ся опред-е для каждого наимен-я д-ей оптим. величины партии обработки или оптим. периодичности запуска данных изд-й в пр-во.

4. При наличии в цехе взаимозаменяемого обор-я разл. производ-ти треб-ся опред-ть оптим. план загрузки обор-я. Крит. оптим. – min ден.з-ты на обработку всех деталей.

М-ды реш-я задач ОКП.

1. М-ды лин. программ-я, в частности м-ды целочисл-го лин. программ-я.

2. М-ды теории массового обслуж-я. Отд. раб. место, отд. станок рассм-ся как обслуживающая с/с, для кот. поток требований образует ожидающие обработки д-ли. Весь цех рассм-ся как сеть с/с массового обслуж-я. Треб-ся отыскать правила приоритета, в соотв- с кот. нужно установить очередность обработки на станке ожидающих в очереди д-ей.

3. М. исп-ть м-ды сетевого план-я.

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

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

11. Построение начального опорного плана для стандартной задачи.

F(X)=C1X1+C2X2+…+CnXnà max (1)

A11X1+A12X2+…A1nXn<B1

A21*X1+A22*X2+…A2n*Xn<B2 (2)

……………………………………………

Am1*X1+Am2*X2+…Amn*Xn<Bm

X1>0;X2>0;…Xn>0 (3)

Приведем задачу 1,2,3 к каноническому виду. Для этого в каждом ограничении системы (2) введем дополнительную неотрицательную переменную, в целевую ф-ю эти переменные запишем с нулевыми коэф-ми.

F(X)=C1*X1+C2*X2+…+Cn*Xn+0*Xn+1+0*Xn+2+…+0*Xn+màmax (4)

A11*X1+A12*X2+…A1n*Xn+X(n+1)=B1

A21*X1+A22*X2+…A2n*Xn+X(n+2)=B2 (5)

……………………………………………

Am1*X1+Am2*X2+…Amn*Xn+X(n+m)=Bm

X1>0;X2>0;…Xn>0;X(n+1)>0;X(n+2)>0;…X(n+m)>0 (6)

Задача 4,5,6 имеет базисный вид (базисные переменные это X(n+1),X(n+2),…X(n+m)). Можно применять алгоритм симплексного метода: строим первые опорные решения:

Х1=Х2=Хn=0

X(n+1)=B1

X(n+2)=B2

Х(n+m)=Bm

F(X)=0 Теперь решаем ее.