Автоматизированные системы управления технологическими процессами: Методические указания к лабораторным работам и домашним заданиям, страница 13


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


Система уравнений (10.5) может быть представлена в виде


или (после попарного вычитания строк)

Заметим, что всегда можно положить Δt0k(k=1,M), равными нулю (или, что то же, включить их условно в τ1k). Кроме того, работы подготовительные, регламент­ные и т. п. могут быть учтены наравне со всеми другими работами в общих соотношениях вида (10.5) — (10.7).

Зафиксировав произвольным образом все τvk, рас­смотрим эту задачу как обычную задачу линейного про­граммирования. Из выражения Tc(l) следует, что всякое допустимое базисное решение системы (10.8), содержащее в числе свободных переменные Δtv-1,1(v=2,N),ΘNk (k=2, M) будет оптимальным для сформулированной задачи. Однако подобные решения могут встретиться далеко не всегда, поэтому необходимы дополнительные исследования.

Обратимся к теореме (22): оптимальным является такое допустимое базисное решение (10.8), которое со­держит в числе свободных все Δtv-1,1  и одновременно удовлетворяет требованиям ΘvkΔtv-1,k=0, (v=2,N, k=2,M) (переменная Θvk может войти в базис только тогда, когда Δtv-1,k является свободной и наоборот).

Доказательство этой теоремы основано на по­следовательном отделении заведомо свободных перемен­ных Θvk (см. § 9.1). Чтобы найти оптимальные решения в каждом конкретном случае, достаточно использовать простое правило: если в очередной строке (10.8) сумма Δtv-1,k-1 — Θv-1,k + ωvkнеотрицательна, то в базис вводит­ся Δtv-1,k , а Θvk считается свободной (равной нулю). Если же Δtv-1,k-1 — Θv-1,k + ωvk<0, базисной переменной ста­новится Θvk, а Δtv-1,k обращается в нуль. Сформиро­ванное решение должно удовлетворять требованиям

 φvП ≥0 (vЄ SП), иначе оно окажется недопустимым.

В этих условиях можно говорить об оптимальной организации работ даже при фиксированном порядке их производства (не нарушающем ограничений а) — г)). Так, этапы работы, выполняемой первой, должны следовать друг за другом без задержек (Θ1k=0, k=2, M); этапы любой промежуточной работы идут, вообще гово­ря, со сдвигами во времени один относительно другого. Исключение составляет случай, когда все

  неотрицательны.

Полученные результаты неконструктивны (они отве­чают предположению τvk=const и не дают рекоменда­ций по выбору наилучшего плана проведения работ), однако появляется возможность отождествить произвольную перестановку столбцов матрицы ||τkv|| с некото­рым показателем, вычисляемым довольно просто, что должно облегчить применение здесь метода динамиче­ского программирования (или методов, сходных с ним по идее). Условия для этого следующие:

—  рассматривается   N-шаговый    процесс    планиро­вания;

—  содержанием очередного шага является размещение того или иного столбца на определенной позиции;

—  перед началом очередного шага возможны только Nсостояний процесса, причем параметр состояния ска­лярный (номер столбца).

Рассмотрим теперь время Tc(l) как функцию только τvk (v=1, N, k=1, M), имея в виду найденные решения. Оценка Ťc(i), получаемая при использовании рекоменда­ций приведенной выше теоремы и обозначаемая как Ťc(l), обладает рядом особенностей: в общем случае Ťc(l) представляет собой линейную комбинацию величин τvk, т. е.

N  M

 

где cvk— целочисленные коэффициенты; каждое значе­ние Ťc(l)  отвечает заданному порядку работ, который в силу условия а) определяется порядком проведения их первого этапа (т. е. принятыми τv-1, (v=1,N), следовательно, τvkесть однозначно определенная функция

τv,1, (v=1,N).

Учитывая  эти  замечания,  получаем   Ťc(l) =