Алгоритм симплексного метода

Рис.4.6.4.1. Алгоритм симплексного метода.

 

Качественно суть симплексного метода заключается в том, что очередной план берется соответствующей той или иной вершине ОДР и после этого план проверяется на оптимальность. Если результат положительный, т.е. план - оптимален, то значение координат этой вершины является искомым решением, если нет — то осуществляется переход к следующему плану, т.е. к следующей вершине. Причем переход от одного допустимого плана к другому осуществляется так, что ЦФ последовательно уменьшается.

1 этап. Выбор начального плана:

1) Произвольно выбираются свободные переменные СП k: X₁, X₂, …,X_k, и тогда X_k+1…X_n – базисные переменные.

2) Выражается целевая функция W=f₁₁(X₁…X_k) через свободные переменные.

3) Выражаются базисные переменные через свободные переменные БП=f₂₁(СП₁) или БП=f₂₁(Х₁…Х_k).

4) Полагаются: СП₁=0 (X₁=0,…X_k=0).

5) Поскольку определена зависимость БП=f₂₁(СП₁) и W=f₁₁(СП₁), то определяются конкретные значения W₁ и БП₁ для начального плана.

2 этап. Оценка оптимального плана осуществляется на основе выражения:

+св.член или +const                   (1)

Для оценки плана на оптимальность необходимо проанализировать знаки всех коэффициентов уравнения (1), и если все знаки положительны, то этот план является оптимальным.

3 этап. Выбор очередного плана

1) Выбирается новый i-ый набор свободных и базисных переменных, который не совпадает с предыдущими наборами (планами)(путем замены 1-ой СП на соответственно 1 БП)

2) Выражается W_i=f_1i(СП_i).

3) Выражаются БП_i=f_2i(СП_i).

4) Полагаются СП_i=0.

5) Определяются конкретные значения базисных переменных и краевой функции для i-ого плана БП_i и W_i.

6) Осуществляется переход на блок 2.

Рассмотрим реализацию симплекс-метода на примере.

4.6.5 Пример поиска оптимального плана

 

Исходная постановка задачи линейного программирования.

Дано:

1. ;

2. ;

3. ;

n=6, m=4, k=2.

Формулировка задачи:

 Необходимо найти такие положительные значения X₃,…,X₆, которые удовлетворяют системе ограничений (2) и обращают в минимум критерий эффективности.

Первый план

Выбираем тогда X _3, X ₄, X ₅,X₆ ® БП выбрав СП, БП, выразим критерий эффективности и ограничения, (W и БП) через СП:

1. W₍₁₎= –7X₁–5X₂=0.

2. .

3. Х₁≥0,…,Х₆≥0.

Полагаем выбранные СП равными 0 и определяем БП и W:

X₁=X₂=0, X₃=19, X₄=13, X₅=15, X₆=18, W₍₁₎=0.

Поскольку в уравнении W₍₁₎=f(СП) есть отрицательные знаки коэффициентов, то первый план не оптимален. Следовательно, переходим к новому набору СП. Если проанализировать вид целевой функции, то убедимся в том, что, увеличивая X₁ и X₂ можно достичь меньших значений критерий эффективности. Если, например, увеличивать одну из свободных переменных, например, X₂, то, анализируя уравнения для базисных переменных БП=f(СП) (2), можно убедиться в том, что X₂ можно увеличивать до определенного предела, а именно до тех пор, пока хотя бы одна из БП не станет отрицательной. В данном случае наиболее быстро приближается к опасной зоне, т.е. к зоне отрицательных значений, при возрастании Х_2, базисная переменная БП Х₅, следовательно, производим замену: из БП убираем Х₂ и на её место включаем Х₅.

 

Второй план:

Х₁, Х₅ → СП; Х₂, Х₃, Х₄, Х₆→БП, выражаем W и БП через СП.

1) W₍₂₎= –25–7 X₁+ X₅.

2) .

3) Х₁≥0,…,Х₆≥0.

Полагаем Х₁=0, Х₅=0, и определяем W₍₂₎ и БП₂, и получаем для 2-го плана:

X₁=X₅=0, X₃=4, X₄=8, X₂=5, x₆=18,         W₍₂₎= -25.

Значения W₍₂₎ стало меньше, по сравнению с 1-ым планом, но второй план также не оптимален, т.к. один из коэффициентов в уравнении W₍₂₎=f(СП) отрицателен.

Третий план.

Проводим анализ- какая БП быстрее приближается к опасной зоне при увеличении Х₁ так как знак при Х₁ отрицательный. Наиболее быстро приближается к зоне отрицательного значения БП Х₃.

Поэтому исключаем из СП Х₁, а вводим в состав СП – Х₃.

Х₃, Х₅ → СП; Х_1, Х₂, Х₄, Х₅ → БП, выражаем W и БП через СП:

1) W₍₃₎= –39+ Х₁- Х₅.

2) .

Полагаем Х₃=Х₅=0, и находим Х₁=2, Х₂=5, Х₄=4, Х₆=12; W₍₃₎= -39; значения W₍₃₎ меньше чем W₍₂₎, но план 3 также не оптимален, т.к. в уравнении (1) W₍₃₎= -39+(7/2)Х₃ - (11/6)Х₅

есть отрицательные коэффициенты.

Четвёртый план. Т.к отрицательный коэффициент в ЦФ W₍₃₎ при Х₅ то ее выводим из состава СП, а взамен вводим Х₄, как переменную, наиболее быстро приближающуюся к 0, при увеличении Х₅.

Х₃, Х₄→СП; Х₁, Х₂, Х₅, Х₆→БП.

1. W₍₃₎= 50 + Х₃+ ₄.

2. .

Х₃=Х₄=0, Х₁=5, Х₂=3, Х₅=6, Х₆=3;           W₍₄₎= –50; т.к. в уравнении (1) все коэффициенты положительны, то W₍₄₎=W_min.

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

 

4.7 Алгоритм календарного планирования и оперативное управление в АИУС

4.7.1 Дискретное производство и планирование производственных процессов

 

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

1) сам труд,

2) средства труда (орудия труда),

3) предметы труда.

Все технологические процессы производства делятся на основные и вспомогательные.

Те процессы, с помощью которых предметы труда превращаются в готовую продукцию, называются основными.

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

Продукция основного производства, в зависимости от степени готовности к использованию подразделяется на:

· изделия,

· узлы,

· детали и т.д.

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

Одним из показателей уровней организации производства является время нахождения производимых изделий в производстве (длительность производственного цикла). Чем меньше это время для изделия заданной номенклатуры, тем меньше временные затраты предприятия на производство единицы продукции. (Следовательно, можно выпустить больше продукции за единицу времени)

Длительность производственного цикла можно сократить за счёт:

1. Совершенствования техники и технологий.

2. Создание рациональной производственной структуры предприятия.

3. Повышение уровня организации производства путём рационализации планирования производства.

Рассмотрим более детально вопросы планирования, в том числе и оперативного т.к. оно может совершенствоваться с использованием возможностей АИУС.

Планирование производства — это разработка комплекса мероприятий, обеспечивающих выполнение задач производственно-хозяйственной деятельности предприятия (технико-экономические расчеты; разработка различных нормативов; разработка плановых показателей).

 Чем меньше это время для изделий заданной номенклатурной группы, тем меньше временные затраты предприятия на производство единицы продукции. Следовательно, на оборудовании предприятия можно изготовить еще изделий, и получить дополнительную прибыль.

 

Общая схема планирования предприятия имеет вид:

 

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

В задачи ОПП входит обеспечение ритмичной работы производственного объекта по заранее заданному графику или программе.

По характеру задач и по организационным формам их выполнения весь комплекс задач ОПП можно разделить на задачи оперативно-календарного планирования (КП) и задачи диспетчеризации (Д).

В рамках оперативного календарного планирования осуществляется следующее:

1) Разрабатываются календарно-плановые нормативы.

2) Рассчитывается загрузка оборудования.

3) Составляется для каждого объекта месячные, декадные и другие производственные программы и план–графики.

4) Уточняются производственные программы и планы–графики в процессе их выполнения.

Диспетчеризация (оперативное управление) объединяет следующие задачи:

1) Планирование частичных процессов на более короткие отрезки времени (сутки, смены).

2) Разработка почасовых графиков обработки изделий.

3) Систематический учет и анализ хода выполнения плановых заданий.

4) Ликвидация выявленных в результате контроля и анализа неувязок (отклонений) путем регулирования (оперативного руководства).

Задачи календарного планирования и оперативного управления целесообразно решать в АИУС цеха, АИУС участка, АИУС производства с использованием математического моделирования, методов оптимизации и возможностей ЦСОИ.

4.7.2 Математическое моделирование и методы планирования дискретного производства

 

Основным аппаратом в решении задач в управлении и планирования дискретного производства в условиях АИУС является математическое моделирование.

В этих математических моделях должно:

1) Отражаться реальное протекание производственных процессов.

2) Отражаться схема выработки управляющих воздействий.

3) Прогнозироваться и моделироваться влияние этих управляющих воздействий на дальнейшее протекание производственного процесса.

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

1. Производственные функции.

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

Например: Р_ээ=K·N; где Р_ээ— расход электроэнергии, N — количество продукции, выпускаемой цехом.

2. Балансовые модели.

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

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

4.7.3 Математическая постановка задачи оперативного календарного планирования