«В.П. Белокуров С.В. Белокуров Г.А. Денисов Н.И. Злобина Э.Н. Бусарин ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ В ТЕХНОЛОГИИ ТРАНСПОРТНЫХ ПРОЦЕССОВ Учебное пособие Воронеж 2013 1 Министерство образования и науки Российской Федерации ...»

Таким образом, возникающие на практике задачи принятия решений достаточно часто представляют собой задачи СТП. Как же решать такие задачи?

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

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

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

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

При Р - постановке задача формулируется несколько иначе. Прежде всех должно быть дополнительно задано предельно допустимое наихудшее значение целевой функции. При максимизации задается минимально допустимое значение Fmin и требуется выполнение условия F Fmin. При минимизации задается максимально допустимое значение Fmaх и нужно выполнить условие F Fmax. Суть Р - постановки заключается в том, что необходимо найти такие значения xj, при которых максимизируется вероятность того, что целевая функция будет не хуже предельно допустимого значения.

Целевая функция в Р - постановке будет иметь вид:

при максимизации при минимизации Из (6.2) и (6.3) следует, что целевая функция F в обоих случаях стремится к max. Однако при минимизации, как и при максимизации, надо стремиться к максимизации вероятности. Но при максимизации целевой функции наименьшее допустимое значение задается как Fmin, а при минимизации целевой функции как Fmax. И поэтому, чтобы при максимизации увеличивать значение целевой функции, надо увеличивать значение Fmin в (6.2). Аналогично при минимизации надо уменьшать значение Fmax в постановке (6.3).

Из приведенного видно, что М - и Р - постановки принципиально различаются.

Посмотрим теперь, как учитывается фактор неопределенности при записи ограничений. В ограничения входят величины аij и bi. Учесть, что эти величины являются случайными, можно так же, как и для целевой функции, в двух вариантах. В первом варианте случайные величины определяются их математическими ожиданиями и ограничения записываются в виде где aij и bi – математические ожидания случайных величин aij и bi. В этом случае стохастический характер задачи, по сути, никак не учитывается.

Во втором варианте каждое i-e ограничение должно быть записано так:

Эта запись означает, что вероятность выполнения каждого заданного ограничения должна быть не менее назначенной величины i. Задачу, включающую условия (6.4), называют задачей с вероятностными ограничениями. Объединив целевую функцию и ограничения, запишем задачу СТП в двух постановках.

При М - постановке задача СТП имеет вид:

При Р - постановке задачи СТП максимизация и минимизация будут различаться.

При максимизации с учетом целевой функции (6.2) Р - постановка будет иметь вид:

При минимизации с учетом целевой функции (6.3) Р - постановка записывается так:

Задачи (6.5) – (6.7), как в М-, так и в Р - постановке, непосредственно решены быть не могут. Возможным методом решения этих задач является переход к их детерминированным эквивалентам.

В основе этого перехода лежит использование закона распределения случайных величин.

В дальнейшем принимаем, что случайные величины aij, bi, cj подчиняются нормальному закону распределения. В этом случае детерминированный эквивалент целевой функции в Р - постановке можно записать следующим образом:

при максимизации целевой функции при минимизации целевой функции где c j, j – математическое ожидание и дисперсия случайной величины c j.

Приведенные зависимости достаточно сложны для вычислений, широкого распространения на практике не имеют, поэтому в дальнейшем Р - постановку задачи СТП мы рассматривать не будем. Что же касается детерминированного эквивалента для М - постановки задачи СТП (6.5), он будет иметь вид где c j – математическое ожидание случайной величины c j ; ij, 2ij – соответственно математические ожидания и дисперсии случайных величин ij, bi ; ti – значение t в нормальном законе распределения, соответствующее заданному уровню вероятности соблюдения ограничений i.

Эта система является основой нашего дальнейшего рассмотрения принятия оптимальных решений в условиях неопределенности, поэтому остановимся на ней подробнее.

В модель (6.7 а) переменные хj входят во второй степени, а из их суммы извлекается квадратный корень. Значит, ограничения этой модели являются нелинейными.

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

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

Из сравнения этой системы с задачей линейного программирования (3.13) для терминированных величин видно, что детерминированный эквивалент задачи СТП отличается от задачи линейного программирования следующим: вопервых, выполнен переход от значений детерминированных величин aij, bi, cj к математическим ожиданиям случайных величин ij, bi, c j ; во-вторых, во всех ограничениях располагаемый ресурс bi уменьшился на величину i. Значит, и это очень важно, учет того, что величины aij, bi являются случайными, приводит фактически к уменьшению располагаемого ресурса. За принятие решений в условиях неопределенности необходимо иметь дополнительный ресурс i. Однако этот дополнительный ресурс может остаться неиспользованным, но для гарантированного выполнения плана иметь его необходимо. В этом и проявляется неопределенность.

Значит, для гарантированного выпуска продукции без изменения ее объема в условиях неопределенности располагаемый ресурс надо увеличить на веn к уменьшению выпуска продукции. Итак, имеется возможность выпускать тот же объем продукции при большем ресурсе или при том же ресурсе изготовлять меньше продукции. Хотя, дополнительный ресурс может оказаться неиспользованным. Вот, какова плата за принятие решений в условиях неопределенности. И размер этой платы определяется величиной i. От чего же зависит размер этой платы?

Как видно из (6.8), на i влияют все вероятностные характеристики задачи: ti – заданная вероятность соблюдения i-гo ограничения; 2ij – дисперсия значений норм расхода ij ; i2 – дисперсии ресурсов bi. Увеличение заданного уровня вероятности ij, которое приводит, в свою очередь, к возрастанию tij (см. рис. 6.2), а также к 2ij и i2, вызывает увеличение i. Следовательно, при этом растет плата за неопределенность. Поскольку чем продолжительнее плановый период Т, тем больше неопределенность, то можно сказать, что с увеличением Т возрастет и плата за неопределенность i. Эти рассуждения являются качественной оценкой влияния неопределенности. Для точного же анализа ее влияния полезно выполнить количественную оценку. С этой целью введем коэффициенты:

относительное ухудшение целевой функции относительное увеличение ресурса, т. е. относительная плата за неопределенность, где F0 и F – соответственно значения целевой функции при i = 0 и в задаче СТП.

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

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

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

где величины aij, bi, cj являются случайными.

На основании (6.5) при М - постановке задачи запишем:

где 1, 2 – заданные уровни вероятности соблюдения каждого ограничения.

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

Исходные данные, необходимые для решения этой задачи, сведены в табл. 6.1 и 6.2.

Если задать уровни вероятности 1, 2 = 0,6, для которых t = 0,25, то после подстановки исходных данных получим детерминированный эквивалент в виде:

Результаты решения задачи для детерминированного случая ( i = 0 ) и при i = 0,6 приведены в табл. 6.3.

Анализируя результаты решения задачи (6.11), можно сделать следующие выводы: для обеспечения гарантированного (с вероятностью = 0,6 ), выполнения плана необходимо иметь дополнительно примерно 5 % каждого вида ресурса; при отсутствии дополнительного ресурса целевая функция может уменьшиться на величину = 4 % вследствие возможного сокращения выпуска продукции х2 от 5,3 до 5,04.

Этот пример подтверждает тот факт, что в реальных условиях для гарантированного выполнения плана необходимы дополнительные ресурсы в размере i.

В противном случае возможно уменьшение выпуска продукции.

Рассмотрим, как влияют на результат решения задачи величины, определяющие ее вероятностный характер. К таким величинам относят заданный уровень вероятности i и дисперсий 2 ij и i2. Начнем с величины i. На основании данных, приведенных в табл. 6.4, построены кривые на рис. 6.3. При этом можно сделать следующие выводы.

Величина В целях повышения заданного уровня вероятности выполнения плана i требуется увеличить дополнительные ресурсы i.Так, для выполнения плана с вероятностью, близкой к единице ( = 0.987 ), необходим дополнительный ресурс в размере = 26 33 % от используемого без учета вероятностных характеристик.

Рис. 6.3. Графические зависимости по табл. 6. 2. Отсутствие такого увеличения ресурсов может привести к ухудшению целевой функции на величину = 33,6 %.

3. Возрастание отражается на номенклатуре выпускаемой продукции.

При этом в интервале = 0,5 0,77 значение х1 сохраняется неизменным, а х уменьшается. При дальнейшем увеличении = 0,89 0,987 значение х2 остается неизменным, в то время как х1 сначала скачком возрастает, а затем постепенно уменьшается. Несмотря на то, что при = 0,89 значения х1 и х2 изменяются резко, целевая функция F во всем интервале изменения уменьшается плавно.

Таково влияние заданного уровня вероятности соблюдения ограничений на результат решения задачи распределения ресурсов.

Влияние дисперсии на результат задачи рассмотрим на примере i2. Для удобства рассмотрения используем коэффициент вариабельности i-го ресурса Результаты решения задачи при заданной вероятности 1, 2 = 0,6 для различных значений 1.2 приведены в табл. 6.5 и на рис. 6.4, из рассмотрения которых видно, что увеличение коэффициента вариабельности, а, следовательно, и дисперсии располагаемых ресурсов для обеспечения гарантированного выполнения плана обусловливает необходимость в дополнительных ресурсах, которые, впрочем, могут остаться неиспользованными.

Величина Ведь мы решаем задачу в условиях неопределенности! В нашем примере дополнительные ресурсы равны = 13 15,8 % от используемых без неопределенности. При отсутствии такого увеличения ресурсов целевая функция может уменьшиться примерно на 10 %.

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

Рис. 6.4. Графические зависимости по табл. 6. Для получения надежных выполнимых планов работу надо вести в два этапа. Первый этап – это планирование с учетом неопределенности, что мы рассмотрели достаточно подробно. На этом этапе случайные величины оцениваются их законами распределения. Второй этап – это периодическое уточнение (а не корректировка) планов на основе реализаций, т. е. фактически полученных значений случайных величин. Чем чаще уточняются элементы математической модели по фактическим значениям, тем более реальными и выполнимыми будут планы.

ОПТИМИЗАЦИОННОГО УПРАВЛЕНИЯ

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

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

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

При оперативном управлении решается достаточно широкий и важный круг вопросов, которые возникают при ежедневном обеспечении производственного процесса. Мы будем рассматривать лишь те вопросы оперативного управления, которые могут быть решены с помощью моделей, уже составленных при планировании. «Что будет, если…?», «что надо, чтобы…?» – вот вопросы, ответы на которые составляют зерно оперативного управления. Посмотрим, как находить ответы на эти вопросы, на конкретном примере.

Ресурсы Прибыль с единицы продукции П2, П3, П4, используя для этого три вида ресурсов. Располагаемые ресурсы, нормы расхода ресурсов и прибыль приведены в табл. 7.1. Мы уже знаем, что модель этой задачи имеет вид:

В результате решения задачи получен следующий оптимальный план: x1* = 10; x2 = 0; x3 = 6; x4 = 0;, при этом прибыль F = 1320.

При выпуске данной продукции могут возникнуть, например, такие вопросы: 1) что будет, если пять человек из числа трудовых ресурсов привлечь на другие работы? 2) что будет, если сырья поставят на 20 % меньше? 3) какую продукцию следует выпускать, если мощность оборудования увеличить на 10 %, и т. д.

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

Однако для принятия оптимальных решений необходимо иметь хотя бы элементарное представление о некоторых довольно сложных теоретических вопросах.

7.2. Симплекс – метод в решении оптимизационных задач В гл. 4 мы показали, что задачи линейного программирования можно решать графически. При этом на плоскости, т. е. в двухмерном пространстве, мы решали такие задачи, в которых число искомых переменных равно двум, т. е.

мерности пространства: k = n, где k – мерность пространства; n – число переменных.

Как мы видели, при k – 2, т. е. на плоскости, ОДР представляет собой многоугольник. В этом многоугольнике координаты каждой его вершины являются допустимым решением. Координаты той вершины, в которой целевая функция имеет максимальное (или минимальное) значение, являются оптимальным решением задачи. Идея решения заключается в последовательном переборе вершин. Правила перехода от одной вершины к другой обеспечивают такую последовательность перебора вершин, при которой значение целевой функции все время улучшается, т. е. увеличивается при максимизации или уменьшается при минимизации.

Все сказанное применительно к двухмерному пространству можно распространить и на трехмерное. Аналогично плоскости для трехмерного пространства ОДР представляет собой многогранник. Координаты каждой его вершины – это допустимые решения. Координаты той вершины, в которой целевая функция имеет максимальное (или минимальное) значение, являются оптимальным решением задачи. Для трехмерного пространства это нетрудно себе представить. Однако трехмерное пространство описывает задачи, в которых число переменных равно трем. В практических задачах число переменных может исчисляться не только десятками или сотнями, но и тысячами. В этом случае никакое пространственное воображение не поможет. Что же делать? А выход один – решать задачу аналитически. Аналитическое решение задачи линейного программирования – дело весьма сложное, поэтому подробно описывать его не будем, а изложим лишь некоторые идеи такого решения, которые реализованы в симплекс-методе.

Пусть в результате составления математической модели была получена система неравенств:

Переменные x1, х2,...,хn будем называть основными.

От системы неравенств (7.2) перейдем к системе уравнений. Для этого в каждое неравенство добавим по одной дополнительной переменной: yi 0; i = 1, m. Тогда получим систему уравнений:

В системе (7.3) общее число переменных N = n + m, где n – число основных переменных; m – число дополнительных переменных. Все переменные можно подразделить, с одной стороны, на основные и дополнительные, а с другой – на базисные и свободные. Свободными переменными будем называть такие, которые равны нулю. Из теории известно, что n переменных в допустимом решении должны быть равны нулю, т. е. столько же переменных, сколько и основных. Однако из этого ни в коей мере не следует, что нулю равны все основные переменные. Поясним это на таком примере.

Пусть учебная группа состоит из n юношей и m девушек. На группу выделено n билетов в театр и m билетов в кино. Как распределить эти билеты? Тот факт, что число билетов в театр равно числу юношей, а число билетов в кино – числу девушек, далеко не означает, что все юноши пойдут в театр, а девушки – в кино.

Точно так же и в нашем случае: совершенно не обязательно, чтобы свободными переменными (т. е. равными нулю) были только основные переменные. Если, из общего числа переменных n + m будут свободными п переменных, то очевидно, что т переменных будут базисными, т. е. не равными нулю.

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

В ограничения системы (7.1) введем дополнительные переменные у1, у2, у3 и запишем ограничения в виде уравнений:

Затем перепишем систему (7.4) в следующем виде:

Систему (7.5) можно представить в виде табл. 7.2, которую составляют следующим образом: целевую функцию и базисные переменные, которые находятся в уравнениях слева, записывают в первый столбец таблицы.

Реализация решения задачи симплекс-методом Базисные переменные:

Свободные переменные, заключенные в скобки, выносят в верхнюю строку таблицы. В остальные столбцы записывают свободные члены и коэффициенты перед свободными переменными. Эта так называемая симплекс-таблица служит основой для решения задач линейного программирования. В этой таблице переменные, являющиеся свободными, в данном случае x1, x2, x3, x4, по условию равны нулю. Поскольку свободные переменные равны нулю, то из системы (7.5) видно, что базисные переменные у1, у2, у3, а также целевая функция F равны свободным членам. Значит, у1 = 16, у2 = 110, у3 = 130, F = 0.

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

Целевая функция имеет минимальное значение, если, во-первых, решение является допустимым, т. е. свободные члены будут неотрицательными, а вовторых, все элементы в строке целевой функции (свободный член не рассматривается) будут неположительными. При этом целевая функция равна свободному члену. Таким образом, можно сделать вывод, что в табл. 7.2 получено оптимальное решение нашей задачи для случая минимизации целевой функции.

Если мы вернемся к системе (7.1), то увидим, что в задаче требовалось максимизировать целевую функцию – прибыль. А решение, полученное в табл. 7.2, соответствует минимизации прибыли. Действительно, если x1 = x2 = x3 = x4 = 0 значит, мы никакой продукции не выпускаем, при этом прибыль F = 0. Дополнительные переменные у1, у2, у3, показывающие объем неиспользованного ресурса, равны соответственно 16, 110, 100, т. е. тому ресурсу, который имеется в наличии. В самом деле, если мы ничего не выпускаем, то и не расходуем ресурсы. В этом случае неиспользованные ресурсы оказываются равными их первоначальным значениям. Следовательно, данные в табл. 7.2 соответствуют такой вершине ОДР, в которой целевая функция приобретает минимальное значение.

Но вернемся к задаче (7.1). В ней требовалось найти такие значения x j, которые максимизировали бы прибыль. Признак максимизации целевой функции формулируется следующим образом: целевая функция имеет максимальное значение, если, во-первых, решение является допустимым, а во-вторых, все элементы в строке целевой функции (свободный член не рассматривается) будут неотрицательными.

Поскольку табл. 7.2 не удовлетворяет данному признаку, то необходимо перейти к другой вершине. Переход от одной вершины к другой производится по достаточно сложному алгоритму симплекс-метода, который заключается в обмене переменных. Каждый переход от одной вершины к другой, который называется итерацией, состоит в том, что одна базисная переменная приравнивается к нулю, т. е. переходит в свободную, а одна свободная переменная переводится в базисную. На каждой итерации проверяют удовлетворение признаков допустимого и оптимального решений. Такая процедура продолжается до тех пор, пока не будут удовлетворены оба признака. Применительно к нашей задаче, последняя симплекс-таблица, полученная после второй итерации, будет иметь вид табл. 7.3.

Из этой таблицы видно, что в столбце свободных членов все элементы положительные. Значит, решение является допустимым. В строке целевой функции все элементы также положительные. Следовательно, это решение оптимальное и максимизирует целевую функцию. При этом оптимальным планом будут следующие величины: x1* = 10, x3 = 6 (значит, они базисные); x2 = x4 = (так как они свободные). При этом целевая функция F = 1320. Вот результат решения задачи. Однако с помощью симплекс-таблицы можно не только найти ответ, но и узнать еще очень много полезных сведений, которые могут быть использованы для анализа. Так, из табл. 7.3 мы видим, что свободные переменные у1 =у3=0, а базисная переменная у2 = 26. А это значит, что в оптимальном плане резервы трудовых ресурсов и оборудования равны нулю. Иными словами, и эти ресурсы используются полностью. Вместе с тем резерв ресурсов сырья у2 = 26, что свидетельствует об его излишках.

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

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

Для того чтобы записать двойственную задачу, необходимо знать следующее:

1. Каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи, которую будем называть двойственной переменной и обозначим z i. В системе (7.6) ограничению ( а ) соответствует переменная z i, ограничению (б) – переменная z2.

2. Каждой переменной исходной задачи соответствует ограничение двойственной задачи. В системе (7.6) три переменных: x1, x2, x3. Значит, двойственная задача должна иметь три ограничения.

3. Матрица коэффициентов при двойственных переменных в ограничениях двойственной задачи является транспортированной матрицей коэффициентов при переменных в ограничениях исходной задачи (7.6) Следовательно, транспонированная матрица 4. Если в исходной задаче ограничения имеют знаки неравенств « », то в двойственной они будут « ».

5. Правые части ограничений в двойственной задаче равны коэффициентам при переменных в исходной задаче.

6. Коэффициенты при двойственных переменных в целевой функции двойственной задачи равны правым частям ограничений исходной задачи.

7. Максимизация целевой функции исходной задачи заменяется минимизацией целевой функции двойственной задачи.

Таким образом. Для исходной задачи (7.6) можно записать двойственную задачу:

В общем виде исходной задаче соответствует двойственная Важное свойство двойственной задачи заключается в том, что max F = min Fд. При этом Если последнюю формулу записать то, видно, что двойственная переменная zi является коэффициентом при bi и, следовательно, показывает зависимость целевой функции от изменения ресурсов bi на единицу. Таким образом, двойственная переменная оценивает влияние изменения каждого вида ресурса на целевую функцию. В связи с этим двойственные переменные часто называют двойственными оценками.

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

Очень существенно, что для нахождения двойственных оценок не требуется решать двойственную задачу. Их значения уже получены в симплекстаблице оптимального решения исходной задачи (табл. 7.3). Узнать значение двойственных оценок можно следующим образом. Если некоторый i-й ресурс используется не полностью, т. е. имеется резерв, значит, дополнительная переменная в ограничении для данного ресурса будет больше нуля. В нашем примере таким ресурсом является сырье, поскольку b2 =110 и его резерв у2 = 26. Совершенно очевидно, что при наличии сырья не 110, а 1 1 1 резерв стал бы равен не 26, а 27. При этом увеличения целевой функции не произошло бы. Следовательно, для второго ограничения z 2 = 0. Напомним, что переменная, отличная от нуля, называется базисной. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет базисной, а двойственная оценка такой переменной равна нулю.

В рассматриваемом примере трудовые ресурсы и оборудование использовались полностью, поэтому их дополнительные переменные равны нулю. В табл. 7.3 y1 и у3 являются свободными переменными, значит y1 = y2 = 0. Если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции и в конечном счете на целевую функцию. Как мы уже знаем, целевая функция увеличится или уменьшится на размер двойственной оценки. А значение двойственной оценки находится по симплекс-таблице (табл. 7.3) на пересечении строки целевой функции со столбцом данного дополнительного переменного. Так, для трудовых ресурсов при y1 = 0 двойственная оценка z1 = 20, а для оборудования при у3 = 0 двойственная оценка z3 = 10.

Для наглядности выпишем значения дополнительных переменных и двойственных оценок из табл. 7.3 и внесем их в табл. 7.4, из которой видно, что при увеличении трудовых ресурсов на единицу целевая функция возрастет на 20 единиц и будет равна F = 1320 + 20 = 1340, а при уменьшении трудовых ресурсов F = 1320 – 20 = 1300. Аналогично для оборудования при увеличении ресурса на единицу целевая функция возрастет на 10: F = 1320 + 10 = 1330. При уменьшении же ресурса на единицу целевая функция F = 1320 - 10 = 1310.

7.3. Принятие решений в случае отклонения ресурсов от первоначально запланированных Один из важнейших вопросов из числа тех, которые приходится решать в ходе оперативного управления, – это принятие решений в случае отклонения ресурсов от первоначально запланированных. Как же решать этот вопрос на основе математической модели? Рассмотрим это на примере модели (7.1).

Прежде всего, надо включить появившееся отклонение в модель. Начнем с отклонений для сырья. Допустим, отклонение в поставке сырья равно b2. Тогда в математической модели (7.1) ограничение для сырья запишем так Это ограничение в системе (7.5) будет иметь вид а в симплекс-таблице (см. табл. 7.2) соответственно произойдет изменение, показанное в табл. 7.5. После нахождения решения с учетом b2 получим симплекс-таблицу, отличие которой от аналогичной ей табл. 7.3 указано в табл. 7.6.

Согласно табл. 7.6 в оптимальном решении b2 вошло только в свободный член для y2 = 26 + b2.

Мы помним, что оптимальное решение, прежде всего, должно быть допустимым, т. е. в симплекс-таблице все свободные члены должны быть неотрицательными. Таким образом, можно сделать вывод, что решение будет оптимальным при условии y 2 = 26 + b2 0, но это условие будет соблюдаться, когда b2 26.

Следовательно, уменьшение сырья на 26, т. е. на 23,6 % от первоначального объема, не скажется на выполнении плана. Вот мы и получили ответ на вопрос:

«что будет, если...?».

При решении аналогичного вопроса о влиянии отклонения трудовых ресурсов b1 первое ограничение в модели (7.1) надо будет записать так:

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

Что же касается последней симплекс-таблицы, то она будет иметь вид табл. 7.7. В ней значения в столбце y1 те же, что и для основной задачи в табл.

7.3, а свободные члены равны свободным членам в табл. 7.3, к которым прибавлены элементы столбца y1, умноженные на b1.

Какие выводы можно сделать из рассмотрения табл. 7.7?

Для обеспечения требования, о сохранении допустимого решения должны быть выполнены условия неотрицательности свободных членов:

5 / 3( b1 ) 10 ; b1 10 : 5 / 3; b1 6. Аналогично из второго неравенства Перейдя от приращений ресурсов к их предельным значениям, найдем:

Найденные пределы показывают, в каких границах может колебаться трудовой ресурс, чтобы структура оптимального плана, т. е. номенклатура выпускаемой продукции, оставалась без изменений. А это означает, что при изменении трудовых ресурсов в найденных пределах оптимальным, т. е. обеспечивающим наибольшую прибыль, является выпуск той же продукции x 1 и х 3, но в объеме x1 = 10 + 5 / 3( b1 ); x 3 = 6 2 / 3( b1 ). При этом целевая функция F = 1320 + 20 b1. Например, если трудовые ресурсы в количестве 5 чел. отвлечь на другие работы, то оптимальным планом с учетом b1 = 5 будет:

Таким образом, уменьшение трудовых ресурсов на (5/16) 100 = 31 % привело к ухудшению целевой функции только на (1320-1220) 100/1320 = 7,6 %, что не является очевидным.

Аналогично для оборудования можно найти, что структура оптимального плана сохранится в пределах 64 b3 160; при этом будут справедливы зависимости, приведенные в табл. 7.8 в столбце свободных членов.

С помощью этих зависимостей нетрудно дать ответ, скажем, на такой вопрос:

сколько для обеспечения максимальной прибыли надо выпустить продукции, если оборудование увеличить на 10 ед. Из зависимостей в табл. 7.8 видно, что при этом Видимо, было трудно представить, что при увеличении оборудования для обеспечения максимизации прибыли выпуск продукции х 1 целесообразно уменьшить, а х 3 – увеличить. Такое решение объясняется следующим. Как видно из условий задачи (табл. 7.1), прибыль с единицы продукции c1 = 70, а с3 = 120, т. е. единица продукции вида ПЗ в 120/70=1,7 раза дает большую прибыль по сравнению с единицей продукции вида П1. В связи с этим оказалось целесообразным предусмотреть такое перераспределение выпуска продукции.

Таким образом, оптимальный план будет П1 = 1,7, П2 = 0, П3 = 9,3, П4 = 0, при этом прибыль составит F = 1220.

Итак, получен еще один ответ на вопрос типа: «что будет, если...?»

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

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

табл. 7.3.

Найденные предельные значения отклонений ресурсов дают возможность установить еще одно очень важное положение. Рассматривая двойственные оценки, мы отмечали, что они показывают, как влияет на целевую функцию изменение ресурсов на единицу. Так мы выяснили, что с увеличением трудовых ресурсов на единицу целевая функция возрастает на 20. Возникает естественный вопрос: а с ростом ресурсов, скажем, на 10 увеличится л и целевая функция на 200? Иными словами, в каком интервале изменения ресурсов справедливы найденные значения двойственных оценок?

Оказывается, что двойственные оценки сохраняют свое значение в том же самом установленном нами интервале изменения ресурсов, при котором сохраняется структура оптимального плана. Значит, для трудовых ресурсов двойственные оценки будут справедливы при изменении ресурсов в интервале 10 b1 19,55.

Аналогично анализу влияния ресурсов b1 можно установить влияние коэффициентов в целевой функции сj, а также норм расхода ресурсов или производительности труда и оборудования a i j входящих в модель линейного программирования.

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

Все, что мы рассматривали в этой главе, имело отношение к содержанию анализа.

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

8.1. Общие понятия о задачах целочисленного программирования Целочисленные задачи представляют такие уравнения, в которых искомые переменные могут быть только целыми числами. Поясним это на примерах. Для этого рассмотрим уравнение первой степени с одним неизвестным Принимаем, что коэффициентами уравнения а1 и а0 могут быть только целые числа. Тогда решение этого уравнения будет целым числом только в том случае, если а0 делится на а1 без остатка.

Значит, уравнение (8.1) не всегда разрешимо в целых числах.

Так, из двух уравнений первое имеет целое решение а второе, в котором решения в целых числах не имеет.

Перейдем теперь к рассмотрению уравнения первой степени с двумя неизвестными где а1, а2 – целые числа. Решение уравнения (8.2) запишем так:

Очевидно, что хi будет принимать целые значения только в том случае, если x2 делится на а1 без остатка. Так, для примера получим Из этого примера сделаем следующие выводы: уравнение (8.3) имеет бесчисленное множество решений; решение в целых числах будет существовать только в том случае, если x2 будет четным. По поводу первого вывода можно сказать, что в нем нет ничего неожиданного, ведь в уравнениях (8.2) и (8.3) число неизвестных n = 2, а число уравнений т = 1. А в случае n > т, как знаем, может быть ряд допустимых решений. А там, где есть допустимые решения, для выбора одного – оптимального – необходимо добавить, как мы уже тоже знаем, целевую функцию.

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

В рассматриваемом примере (8.3) добавим граничные условия:

Введение дополнительного условия привело к тому, что система, состоящая из уравнения (8.3) и граничных условий (8.4), решена быть не может. Из приведенного примера видно, что задача целочисленного программирования не всегда имеет решение. Если задача не имеет решения, то про нее говорят, что она несовместна.

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

8.2. Особенности решения задач. Метод целочисленного программирования Математическая модель задачи целочисленного программирования может быть записана следующим образом:

Система (8.5) с точки зрения зависимостей ничем не отличается от задачи линейного программирования (3.13). Единственное отличие заключается в том, что в ней есть строка x j ( j = 1, k n) ) – целые, которая оказывает существенное влияние на решение задачи, и значительно его усложняет. Число целочисленных переменных k может удовлетворять одному из двух вариантов. Если k = n, где п – общее число всех переменных, то в ответе все переменные должны быть только целыми. В таком случае задачу называют полностью целочисленной.

Если k < n, в ответе только k переменных должны быть целыми, а остальные в заданных граничных условиях могут принимать любые значения. Иными словами, в ответе должны быть целые (но не все). В этом случае задачу называют частично целочисленной.

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

Решение целочисленных и непрерывных задач оптимизации имеет принципиальные различия. Суть их заключается в следующем. Непрерывные задачи решают симплекс-методом с применением так называемых симплекс-таблиц.

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

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

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

Некоторые вопросы, связанные с решением целочисленных задач, рассмотрим на таком примере:

Решим эту задачу графически. Графическое решение целочисленной задачи включает следующие этапы: графическое решение непрерывной задачи;

наложение требований целочисленности; анализ полученных результатов. Графическое решение непрерывной задачи показано на рис. 8.1.

Рис. 8.1. Графическое решение задачи целочисленного программирования Требование целочисленности переменных состоит в том, что решением задачи могут быть только точки, находящиеся на пересечении целочисленных значений x1 и х2.

Из рис. 8.1 видно, что оптимальным решением задачи без учета требований целочисленности являются координаты точки А, приведенные в табл. 8.1.

Как следует из этой таблицы, значения х1 и х2 в точке А требованиям целочисленности не удовлетворяют.

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

Предположение, что решение недопустимое, потому что округление было произведено в большую сторону, неверно. В точке С координаты также округлены в большую сторону, а решение допустимое. И наконец, из рис. 8.1 видно, что оптимальным решением будут координаты точки D, которые не являются ближайшими к непрерывному оптимальному решению.

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

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

Для нахождения оптимального решения целочисленных задач применяют специальные методы, в которых учитывается, что число возможных решений любой целочисленной задачи является конечным. Так, в задаче с переменными х1 и х2, удовлетворяющими граничным условиям 0 x1 4; 0 x2 5, число возможных решений N = 4 5 = 20. Следовательно, можно рассмотреть все возможные сочетания х1 и х2, проверить, удовлетворяют ли они ограничениям, и из числа удовлетворяющих ограничениям, т. е. допустимых, выбрать наилучшее в смысле принятой целевой функции.

Такой метод называют методом полного перебора. Его трудоемкость с ростом числа переменных и расширением области граничных условий значительно возрастает. Поэтому для реальных задач он неприменим.

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

Данную задачу без наложения требований целочисленности назовем задачей 1. В результате решения этой задачи как непрерывной найдем оптимальное решение: x1 = 1, x1 = 7,5, F1 = 29,5, где верхний индекс у переменных и нижний у целевой функции соответствуют номеру задачи. В полученном решении x2 = 7,5 не удовлетворяет требованиям целочисленности.

В связи с этим для дальнейшего решения составим две задачи с граничными условиями, исключающими возможность получения x2 = 7,5:

В результате решения непрерывных задач 2 и 3 были получены следующие значения: x12 = 1,2, x2 = 7, F2 = 29,4 ; x13 = 0,75, x2 = 8, F3 = 29,25. При решении дальнейших задач (рис. 8.2) накладываем требования на граничные условия х1, исключающие возможность сохранения значений x12 = 1,2 и x13 = 0,75.

Впишем в табл. 8.2 решения непрерывной задачи 1 и тех задач, которые удовлетворяют требованиям целочисленности. Из данной таблицы видно, что Рис. 8.2. Решение задачи методом ветвей решение задачи 4 наиболее близко к непрерывному по значениям переменных.

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

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

Схему расчета по методу ветвей и границ, приведенную на рис. 8.2, можно представить как дерево, перевернутое корнем вверх. Поэтому принятие решения с помощью метода ветвей и границ называют принятием решения на дереве возможных вариантов. Такой метод решения целочисленных задач реализован в программных средствах, в том числе для ЕС ЭВМ в ППП «Линейное программирование в АСУ».

8.3. Задачи раскроя в целочисленном программировании Достаточно часто на производстве, чтобы получить из заготовки необходимые различные детали, эту заготовку надо раскроить. Раскрой может быть линейным и на плоскости. Примером линейного раскроя служит изготовление деталей различной длины из прутка. Примером раскроя на плоскости является выкройка одежды. В производстве такой «раскрой встречается при изготовлении вагонов, корпусов судов, самолетов и т. д. Раскрой деталей на плоскости в общем случае достаточно сложен.

Знакомство с задачами раскроя мы начнем, естественно, с самых простых. Такими самыми простыми являются задачи линейного раскроя. Рассмотрим такую задачу.

Допустим, у нас есть заготовка, длина которой L=6,5 м. Таких заготовок имеется k=50 шт. Необходимо изготовить детали: А длиной l1=2 м; В длиной l2=1,25 м. В один комплект входит деталей А 2 шт.; деталей В 3 шт. Требуется определить, как раскроить заготовку, чтобы из 50 листов получить наибольшее число комплектов. Составим математическую модель такой задачи. Обозначим х1 – число деталей А, получаемых из одной заготовки; х2 – число деталей В, получаемых из одной заготовки. Тогда для одной заготовки можно записать где, совершенно естественно, накладывается требование целочисленности, т. е.

x1, x2 – должны быть целыми, так как число заготовок не может быть дробным.

В левой части выражения (8.6) записана суммарная длина прутка, используемого при раскрое на детали; в правой части – имеющаяся длина. Так как x1, x2 должны быть целыми, то равенство может быть удовлетворено не всегда. В том случае, если будет удовлетворено равенство, отходов при раскрое нет. Если левая часть окажется меньше правой, то разность между ними будет равна размеру отхода. Теперь мы должны сформулировать требования на комплектность. Из всех деталей А, выкраиваемых из одного листа, число которых x1, можно получить число комплектов так как в один комплект входит 2 детали А, где x1, Y – целые. Заметим, что требование целочисленности, наложенное на x1, не обеспечивает целочисленности числа комплектов Y. Так, если x1 будет нечетным, то Y будет дробным. Действительно, при x1 = 5 Y = 5/2 = 2,5, что не имеет смысла. Поэтому в зависимости поставлен знак неравенства. Аналогично число комплектов, обеспеченных деталями В, будет равно Зависимости (8.7) и (8.8) показывают число комплектов, которые могут быть получены из одной заготовки. В общем случае, если число заготовок принять равным k, то можно записать Откуда Если зависимости (8.6) и (8.9) совместно обозначить (**), то задачу оптимального раскроя можно сформулировать в двух постановках:

В первой постановке требуется максимизировать Y – число комплектов, которое может быть получено из kзад – заданного числа заготовок при удовлетворении системы ограничений (**). Во второй постановке требуется минимизировать k – число заготовок, которое необходимо иметь, чтобы получить число комплектов не меньше, чем Yзад – их заданное значение при удовлетворении системы ограничений (**).

Будем решать нашу задачу в первой постановке, которая для нашего случая при k = 50 имеет вид Система (8.12) представляет собой целочисленную задачу. В результате решения этой задачи было получено x1 = 2; x2 = 2; Y = 33. Значит, из одной заготовки надо выкраивать две детали А и две детали В. При этом отходов при раскрое не будет.

Действительно, если в выражение (8.6) подставить найденные значения х1, х2, то получим 2,2+1,25 2 = 6,5. При этом общее число комплектов окажется Y = 33.

Итак, мы решили задачу линейного раскроя. При этом нашли такой раскрой, в котором вообще нет отходов.

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

8.4. Булевы переменные в задачах целочисленного программирования Перейдем теперь к частному случаю задач целочисленного программирования. В этом частном случае искомая переменная хj, в результате решения может принимать не любое целое значение, а только одно из двух: либо 0, либо 1.

Чтобы такие переменные отличать от обычных и каждый раз не писать хj, [0; 1], будем их вместо хj обозначать j. И это уже будет означать, что в результате решения задачи j, может быть равным или 0, или 1, т. е. всегда j [0; 1]. Такие переменные обычно называют булевыми в честь предложившего их английского математика Джорджа Буля (1815 – 1864).

Рассмотрим две распространенные задачи, для решения которых применяют булевы переменные: задачу выбора вариантов; задачу дискретного программирования.

Задача выбора вариантов. Примем, что для получения результата в виде прибыли необходимо два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли.

Количество расходуемого ресурса и получаемая прибыль для каждого варианта приведены в табл. 8.3.

Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех, т. е. k 3. Для составления модели принимаем, что j-му варианту будет соответствовать j ( j = 1, 4 ). При этом Математическая модель задачи будет иметь вид:

Последняя строка системы (8.13) обеспечивает удовлетворение требования, чтобы общее число принятых вариантов не превышало трех. Результаты решения задачи приведены в первом столбце табл. 8.4, из которого видно, что наибольшая прибыль F = 300 будет получена в том случае, если будут приняты третий и четвертый варианты. С помощью булевых переменных можно накладывать дополнительные различные логические условия связи между вариантами.

Например, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй. Если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так: 2 = 4,или в форме записи ограничений Результат решения задачи с учетом этого дополнительного условия приведен также в табл. 8.4.

Рассмотрим еще один вариант дополнительных условий. Допустим, нам надо, чтобы был принят либо третий вариант, либо четвертый. Это условие записывается так:

Результат решения задачи с этим дополнительным условием приведен также в табл. 8.4.

Сравнивая значение прибыли в оптимальном решении F = 300 с полученными значениями прибыли при выполнении дополнительных условий, можно сделать вывод, что дополнительные условия, как всегда, привели к снижению прибыли.

Переходя от нашего примера, описываемого системой (8.13) с дополнительными условиями (8.14) и (8.15), к общему случаю, задачу выбора вариантов можно записать так:

В этой системе ограничение j k. может учитывать самые разноj = образные условия. Рассмотрим некоторые из них. Если накладывается неравенства.

Так, требование «должен», то в ограничениях ставится знак равенства, если «может» – знак если число принимаемых вариантов в нашем примере должно было бы быть равным 3, то надо было записать Если накладывается требование «и», то условие записывается следующим образом:

Например, если могут быть приняты и первый и третий варианты, то 1 + 3 1. Если для вариантов накладывается требование «или», то это условие записывается так:

т. е., если из двух вариантов надо принять только один, то должно быть выполнено условие 1 + 2 = 1.

Значит, если обозначить б – соответствует «быть», нб – «не быть», то вопрос «быть или не быть» может быть записан следующим образом:

В этом случае есть два допустимых решения: б = 1; нб = 0 – означает «быть»; б = 0; нб = 0 – означает «не быть». Так как целевая функция не сформулирована, то дать оптимальный ответ на этот извечный вопрос невозможно.

Чтобы принять решение, необходимо знать, чего мы хотим.

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

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

где Введение дополнительно булевых переменных дает возможность обеспечить выпуск деталей в кратном заданном количестве. Так, для подлокотников х может принимать следующие значения: если в результате решения будет получено 21 = 1, а остальные 22 = 23 = 24 = 0, то x2 = 2; если 22 = 1, а остальные 21 = 23 = 24 = 0, x2 = 4 и т. д.

Для решения задачи с учетом дополнительных условий мы ввели еще семь переменных и четыре ограничения. Следовательно, введение дополнительных требований привело к увеличению размерности задачи. Заметим, что если бы нам требовалось определить выпуск спинок, подлокотников и ножек для одного изделия, то можно было бы записать: х2 = 2х1; x3 = 4x1 и не вводить дополнительные ограничения и булевы переменные. Но это была бы другая задача.

В результате решения задачи (8.16) были получены следующие значения: F=320; x1 = 10; x2 = 4; x3 = 12; 22 = 33 =1; 21=23 = 24 = 31=32 = 0. При этом оказались не полностью использованы ресурсы: резерв первого равен 44, а второго – 4 ед. Такое положение является характерным для задач целочисленного программирования. Ресурс остается, но для использования на увеличение выпуска дискретного количества продукции его оказывается недостаточно.

Рассмотренную задачу распределения ресурсов с учетом требования дискретного значения переменных в общем виде можно записать так:

где dj1, dj2,…djk – дискретные значения, которые может принимать переменная x j. Система (8.17) отличается от обычной задачи распределения ресурсов, которая имеет вид отличается появлением булевых переменных и увеличением числа ограничений. Значит, в данном случае, за удовлетворение дополнительных требований приходится платить. И такой платой оказывается увеличение размерности задачи и ее целочисленность.

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

8.5. Решение задач оптимизации с использованием булевых переменных Мы убедились, что с помощью булевых переменных можно решать достаточно часто встречающиеся задачи оптимизации. Каким же образом решать такие задачи? Есть два метода решения задач с булевыми переменными.

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

Поясним, это, помня, что ОДР – это область допустимых решений. Возможным видом штрафной функции может быть где М – большое число. Так, если ожидаемое оптимальное значение целевой функции порядка единиц, то можно принять М = 1000.

Рассмотрим условие (10.13). Когда x j находится в ОДР, выполняются все ограничения. Значит, g i ( x j ) = 0. При этом штрафная функция (10.14) равна нулю и новая целевая функция (10.12) оказывается равной заданной, т. е.

Если x j не находится в ОДР, при этом, следовательно, не выполняются ограничения, т. е. g i ( x j ) 0. Значит g i2 ( x j ) > 0, а большое число М приводит к тому, что в новой целевой функции (10.12) штрафная функция (10.14) оказывается существенно больше заданной целевой функции f ( x j ). Поэтому в xoде минимизации благодаря большему градиенту в первую очередь будет уменьшаться штрафная функция [g i ( x j )], пока она не станет равной нулю, т. е пока значения x j не войдут в ОДР. Иными словами, пока мы не получим допустимого решения. А далее начнется процесс минимизации заданной целевой функции, о чем мы уже говорили.

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

Глава 11. ОПТИМАЛЬНОЕ ПРОЕКТИРОВАНИЕ 11.1. Основные понятия о системе автоматизированного проектирования (САПР) Прежде чем что-то изготовить, построить, отладить, это что-то надо спроектировать. Процесс проектирования любого объекта с точки зрения содержания включает принятие решений и оформление документов. А с точки зрения формы результатом проектирования являются чертежи, расчеты, техническая документация, которые служат основой при превращении проекта в готовую продукцию. Использование вычислительной техники при выполнении работ по проектированию принято называть САПР, что расшифровывается как система автоматизированного проектирования. Итак, под САПР понимается применение вычислительной техники для автоматизации работ, выполняемых при проектировании.

Автоматизацию проектирования обычно начинают с выполнения на ЭВМ тех работ, которые выполнялись и без ЭВМ. Это так называемые рутинные работы:

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

Классификация основных объектов проектирования, наиболее часто встречающихся в машиностроении, показана на рис. 11.1.

Рис. 11.1. Классификация объектов проектирования Одним из мощных средств повышения качества объектов проектирования является их оптимальное проектирование.

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

11.2. Инженерные и экономические расчеты в САПР Чтобы что-то получить, необходимо что-то затратить. Улучшение технических характеристик объекта проектирования всегда приводит к его удорожанию, т. е, снижению его экономических характеристик.

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

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

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

Применительно к нашему баку учет технических и экономических параметров, будет выглядеть так. Техническим параметром бака будем считать его объем V = abh. В качестве экономического параметра принимаем стоимость бака С, равную где S – площадь бака; l – длина сварного шва; а – стоимость единицы площади материала, из которого изготавливают бак; – стоимость единицы длины сварного шва.

Постановка задачи оптимизации бака, как и любая задача оптимизации, может иметь различные варианты. Рассмотрим два из них.

Первая постановка записывается так:

Она означает, что мы хотим определить, какие размеры a, b, h должен иметь бак, чтобы при данных значениях а и его стоимость равнялась заданной, а объем был максимальным.

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

Эта постановка задачи оптимизации предусматривает определение таких размеров бака заданного объема, чтобы его стоимость была минимальной.

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

В оптимизационных задачах важно не столько получить решение, сколько провести анализ решаемой задачи. Одной из основных форм анализа типа «что будет, если...» является параметрирование. При параметрировании одна из заданных величин принимается не постоянной, а переменной и задача решается в несколько шагов для различных значений параметрируемой величины. Так, решим задачу, когда параметрируемой величиной является стоимость. Обозначим где C 0 зад – начальное значение Сзад; с – приращение С на одном шаге; t – число шагов. Принимаем с = 1. Учитывая, что мы решили нашу задачу при Сзад = 3, получим значение параметрируемой величины Сзад = 3+t.

Аналогично можно параметрировать по а и.

Основным в задачах САПР является необходимость составления математической модели, включающей одновременно технические и экономические параметры и нахождение оптимальных решений для различных вариантов исходных данных.

11.3. Структура и параметры объекта проектирования Каждый объект проектирования характеризуется структурой и параметрами. Структура, которая определяет элементы объекта проектирования и связи между ними, должна обеспечить надежное функционирование и достижение целей, поставленных перед объектом. Надо сказать, что понятие объекта проектирования и элемента является, в известной степени, относительным. Так, с точки зрения организации дорожного движения автомобиль представляет собой элемент, в то время как для завода автомобиль – это объект проектирования, а его составляющие – двигатель, ходовая часть и т. д. – это элементы и т. д. В дальнейшем под элементом будем понимать такую составляющую объекта проектирования, структуру которой мы не рассматриваем. Такую элементарную составляющую будем называть звеном. Каждое звено характеризуется своими параметрами. В общем случае в качестве звена может рассматриваться человек как непременный участник системы человек-машина.

Структура объекта проектирования может быть представлена с помощью графов. При этом возможны два способа представления структуры. При первом способе звено изображается как вершина графа, а связи между звеньями представляются его дугами. Примером такого изображения являются обычные блоксхемы (pиc. 11.2). Такой способ изображения структуры целесообразен в тех случаях, когда процесс функционирования объекта проектирования является непрерывным. Если же процесс функционирования Рис. 11.2. Блок-схема структуры объекта проектирования является дискретным, то его удобно представлять с помощью сетевых графиков, рассмотренных в гл. 9. При описании структуры звено обозначают l, а общее число звеньев L.

Рассмотрим методику оптимального проектирования, которая состоит из трех частей: сбора исходных данных; составления математической модели; решения задач и его анализа.

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

1. Назначение, структура, параметры объекта проектирования. Объект проектирования предназначается для преобразования информации. Его структура приведена на рис. 11.3, из которого видно, что число звеньев L = 3. Принимаем, что объект проектирования характеризуется двумя параметрами: техническим Р – вероятностью безотказной работы и экономическим С – стоимостью.

2. Характеристики звеньев. Каждое звено характеризуется теми же параметрами, что и объект проектирования в целом: pl – вероятностью безотказной работы l-го звена; c l – стоимостью l-го звена. Принимаем, что между этими параметрами для каждого звена имеет место экспоненциальная зависимость вида y = 1 e t. Если обозначать = t / T, то можно записать y = 1 e l.

Проведение каждого опыта достаточно трудоемко, поэтому естественно стремление уменьшить число опытов до допустимого значения.

Таким вариантом может быть составление композиционных планов. В композиционных планах за основу принимают двухуровневый ПФЭ и к нему добавляют эксперименты, проводимые на других уровнях: как в центре, так и при различных значениях ±, где > 1. Поскольку в нашей задаче | |> 1 выходит за заданные для факторов граничные условия, мы такие варианты рассматривать не будем. Остановимся только на одном варианте составления композиционных планов. В этом варианте за основу принимают двухуровневый ПФЭ и к нему добавляют опыты, которые проводят только в центре, т. е. при j = 0.

Есть различные рекомендации по числу дополнительных опытов. Одна из них заключается в том, что в центре проводится опытов, т. е. столько же, сколько проводится на каждом уровне: верхнем и нижнем. Тогда общее число опытов при таком композиционном плане Значения NДОП и N k для различных р приведены в табл. 11.11, из которой, видно, что l < N k < N 3 ПФЭ, т. е. число опытов в композиционном плане N k достаточно для определения l коэффициентов и в то же время существенно меньше, чем число опытов в трехуровневом ПФЭ. Поясним это на примере для случая р = 3. При р = 3 число опытов в композиционном плане состоящий из N k = 12 опытов, дает возможность определить необходимые 6 коэффициентов, и в то же время по числу опытов он меньше, чем N 3 ПФЭ = 27.

Пример композиционного плана для трех факторов (р = 3) приведен в табл. 11.12, из которой видно, что первые восемь опытов представляют собой план при двухуровневом ПФЭ (табл. 11.6), а последние четыре опыта проводятся в центре плана После составления плана эксперимента следует проведение эксперимента, получение искомых результатов и их обработка. Проведение эксперимента и получение результатов в каждом эксперименте свое, поэтому их рассматривать не будем. Займемся только обработкой полученных экспериментальных данных. Разные цели обработки данных реализуются различными методами. Наша цель – нахождение функции отклика – обеспечивается применением метода наименьших квадратов.

Допустим, что мы провели N опытов и получили результаты, сведенные в табл. 11.3.

Рис. 11.9. Графическая зависимость функции отклика y от фактора x Нам надо найти аналитическую зависимость, описывающую функцию отклика y = f ( x ). При этом надо, с одной стороны, точно отразить общую тенденцию зависимости отклика от факторов, а с другой – не учитывать случайные отклонения в отклике, связанные с неизбежными погрешностями в проведении эксперимента. Нахождение такой зависимости включает два этапа: выбор аналитической зависимости y = f ( x ) ; определение коэффициентов в зависимости от выбранного вида.

Выбор вида аналитической зависимости осуществляют по виду экспериментальных данных. В подавляющем большинстве случаев достаточно универсальным видом функции отклика можно считать многочлен второго порядка (11.7). Идею определения коэффициентов многочлена по опытным данным покажем на примере однофакторного эксперимента. Допустим, в качестве функции отклика мы принимаем Экспериментальные данные и принятая функция отклика y = f ( x ) показаны на рис. 11.9. Нам надо определить значения коэффициентов а0, а 1 а11. Эти коэффициенты будем определять так, чтобы минимизировать отклонения принятой функции отклика в каждой точке хi, равной y = f ( x i ) от значения yi, замеренного в эксперименте. Определение коэффициентов а0, а 1 а11 в результате решения такой задачи производят с помощью исключительно трудоемкого и достаточно сложного метода наименьших квадратов.

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

Уравнения регрессии могут быть линейными и нелинейными, однофакторными и многофакторными. Точность подбора функции отклика оценивают различными достаточно сложными методами, которые рассматривать не будем. Определив функцию отклика y = f ( x i ), ее можно записать в форме записи ограничений в задаче оптимизации g(xj) = f(xj)- yi=0.

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

1. Разделить параметры объекта проектирования x j = ( j = 1, n) на факторы x j = ( j = 1, p ) и отклики yi = (i = 1, m) так, чтобы р + т = п.

2. Установить граничные условия для факторов a j x j b j.

3. Перейти к относительным переменным по зависимости (11.8).

4. Задаться порядком аппроксимирующего многочлена и установить число искомых коэффициентов l.

5. Выбрать план эксперимента.

6. По составленному плану провести эксперимент и составить таблицу экспериментальных данных по форме табл. 11.13. Заметим, что число откликов, замеряемых в каждом опыте, на план эксперимента не влияет.

опыта 7. С помощью имеющегося программного обеспечения подобрать аппроксимирующие зависимости для функций отклика:

y1 = f1(xj); y2 = f2(xj);…, ym = fm(xj) и оценить точность аппроксимации.

8. Полученные зависимости записать в форме ограничений; при этом вернуться к первоначальному обозначению отклика (xp+i):

9. Полученные ограничения g i ( x j ) ввести в модель задачи оптимизации:

Поясним приведенную методику.

1. Объект проектирования характеризуется пятью параметрами: x1, x2, x3, x4, x5. Принимаем, что три первых параметра x1, x2, x3 являются факторами, а остальные – откликами. Обозначим y1=x4; y2=x5.

2. Устанавливаем граничные условия для факторов: 30 x1 50 ;

3. Переходим к относительным переменным: от х1 к 1, от х2 к 2. от х3 к 4. Принимаем, что аппроксимирующий многочлен второго порядка x2.

При этом число искомых коэффициентов l = 6.

5. В качестве плана экспериментов принимаем композиционный план, приведенный в табл. 11.12.

6. Результаты эксперимента приведены в табл. 11.14.

7. С помощью имеющегося программного обеспечения находим следующие функции отклика:

Как видим, в системе (11.10) величина у1 не зависит от х2, а у2 не зависит от x3.

8. Полученные функции отклика с переходом к начальным обозначениям уi запишем в форме ограничений:

На этом составление ограничений для задачи оптимизации в том случае, когда не было исходных данных, считаем выполненным.

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

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

В общем виде непрерывный технологический процесс можно представить в виде схемы, показанной на рис. 11.10. Из этой схемы видно, что на вход технологического процесса поступает сырье, которое характеризуется параметрами х1, x2,…, хп или X. Это сырье с помощью технологического процесса, имеющего параметры у 1, у2,...ут или Y, превращается в готовую продукцию с параметрами z1, z2,…,zk или Z. Естественно между всеми параметрами X, Y, Z существуют зависимости. А раз есть зависимость, то возникают задачи оптимизации. При этом они могут быть в различных постановках. Одной из возможных постановок задачи оптимизации может быть такая: определить параметры технологического процесса Y, которые при данных параметрах сырья X обеспечат требуемые параметры готовой продукции Z. При этом принятая целевая функция будет иметь оптимальное значение. Задача оптимизации параметров технологического процесса решается в такой последовательности:

1) описать сущность технологического процесса; 2) дать схему этого процесса и определить параметры, которые будут учитываться при оптимизации; 3) составить математическую модель задачи оптимизации; 4) идентифицировать вид модели и выбрать метод решения; 5) решить задачу оптимизации; 6) выполнить анализ задачи.

Рис. 11.10. Схема непрерывного технологического процесса Дальнейшее рассмотрение задачи оптимизации технологического процесса будем вести на примере нанесения лакового покрытия при отделке деталей из древесины. Работу будем выполнять по приведенным выше пунктам.

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

2. Схема технологического процесса приведена на рис. 11.11. При оптимизации будем учитывать следующее.

Сырье включает два элемента: древесину, на которую наносится лак, в дальнейшем называемую подложкой; наносимый лак. Параметрами сырья будут: х1 – вязкость лака, с; х2 – температура подложки, °С.

Технологический процесс будем определять одним параметром у1 – скоростью движения конвейера, м/мин. Готовая продукция характеризуется двумя параметрами: z1 – внешним видом, оцениваемым в баллах; z2 – толщиной покрытия, мкм.

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

Для решения этой задачи необходимо знать зависимости:

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

11.15. В соответствии с новыми обозначениями надо Рис. 11.11. Схема технологического процесса составить план эксперимента и в ходе эксперимента определить значения откликов. Такой эксперимент мы проводить не будем. План этого эксперимента и его результаты будем считать, что нам уже известны. Они приведены в табл.

11.14 – а функции отклика имеют вид (11.10). Возвращаясь к нашим первоначальным обозначениям (11.12), с учетом найденных зависимостей запишем следующим образом:

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

5. В результате решения задачи получили следующие значения:

6. В ходе анализа можно осуществить параметрирование по верхним границам х1 и x2, а также построить графики, приведенные на рис. 11.12.

Рис. 11.12. Графическая зависимость результатов решения задачи По таким графикам, задаваясь требованием по качеству z1, можно находить для заданного сырья х1 требования к технологическому процессу у 1. Не вызывает сомнения, что такие графики, несомненно, могут принести большую пользу для оптимизации технологических процессов.

11.6. Методы перебора возможных вариантов и методы решения задач оптимизации в САПР В задачах проектирования часто приходится выбирать оптимальный вариант при различном сочетании комплектующих.

Допустим, объект проектирования состоит из трех звеньев, а каждое звено может быть реализовано несколькими вариантами, как это показано на рис. 11.13. На этой схеме объект проектирования характеризуется двумя параметрами: Р – вероятностью безотказной работы; С – стоимостью. Поэтому каждый вариант звеньев, входящих в объект проектирования, будем характеризовать этими же параметрами. Значения этих параметров для различных вариантов звеньев приведены в табл. 11.16, в которой нижний индекс параметра соответствует строке, т. е. варианту, а верхний – столбцу, т. е. звену. Параметры системы определяются параметрами звеньев и равны:

где p1, p2, p3 – вероятность безотказной работы звена; c1, c2, c3 – стоимость звена.

Рис. 11.13. Объект проектирования Значение параметров р и с в решении задачи оптимизации Задача заключается в выборе такого варианта реализации каждого звена, чтобы объект проектирования в целом был оптимальным. Мы уже знаем, что оптимальных объектов проектирования вообще быть не может. Надо обязательно сказать, в каком смысле оптимальным мы хотим иметь объект проектирования. Есть два варианта постановки задачи оптимизации. Первая постановка записывается так:

При такой постановке будем искать такие варианты реализации звеньев, чтобы объект проектирования был самым дешевым при условии, что вероятность его безотказной работы будет не ниже заданной. Во второй постановке будем искать такие варианты звеньев, чтобы т. е. мы хотим получить самый надежный объект проектирования при условии, что его стоимость не должна быть выше заданной. Для конкретности уточним поставленные задачи оптимизации (11.15), (11.16) и примем значения Pзад и Cзад. Будем искать оптимальные варианты при двух постановках:

Есть два метода решения таких задач: перебор возможных вариантов;

решение задачи оптимизации.

Начнем с перебора возможных вариантов. Возможные варианты структуры объекта проектирования и их характеристики приведены в табл. 11.17, в которой значения Р и С определены по формулам (11.14). В данном случае общее число вариантов N = 3 1 2 = 6, где 3, 1, 2 – это число вариантов реализации 1-го, 2-го и 3-го звеньев.

Решение задачи методом перебора будем вести в такой последовательности. Начнем с первой постановки.

Значение параметров р и с в зависимости от варианта структуры Значение параметров р и с при граничном условии p 0, Значение параметров р и с при граничном условии с 1. Из общей таблицы вариантов табл. 11.17 выпишем в табл. 11.18 все варианты, которые удовлетворяют граничным условиям p 0,93.

2. Из выписанных вариантов найдем тот, в котором значение С минимально. Таким вариантом является четвертый. Значит, оптимальная структура будет в четвертом варианте сочетания вариантов, содержание которого видно в табл. 11.17, т. е. в этом случае первое звено должно быть принято в первом варианте; второе – в первом; третье – во втором. Принятые варианты заштрихованы на рис. 11.13. Аналогично при оптимизации по второй постановке надо составить таблицу для вариантов, в которых с 65 (табл. 11.19) и из них выбрать такой, в котором значение Р максимально. Таким вариантом является первый. Так выбираются варианты методом перебора. Этот метод, безусловно, нагляден. Но он применим лишь в задачах небольшой размерности.

Другим методом решения задачи выбора оптимальной структуры является решение задачи оптимизации. Чтобы решить задачу оптимизации, как мы уже хорошо знаем, прежде всего, надо составить модель. Для составления модели введем булевы переменные m, где l – номер звена; m – номер варианта реализации, которые надо определить в результате решения задачи.

Принимаем, что 1, если для l - го звена принят m - й вариант его решения; л После введения переменных перейдем к составлению модели, Начнем с ограничений. Каждое звено может быть реализовано только одним вариантом.

Это условие записывается так:

где верхний индекс указывает номер звена.

Стоимость каждого звена в зависимости от принятого варианта будет равна (значения сm взяты из табл. 11.16):

Действительно, если будет принят для 1-го звена 2-й вариант, который стоит с1 = 30 (см. табл. 11.16), то 2l = 1; 1l = 3l = 0. Стоимость звена будет равна стоимости принятого варианта с1 = с1 = 30. Аналогично для вероятности безотказной работы запишем:

Параметры системы от параметров звеньев зависят, как это было принято, в формулах (11.14), обозначим эти ограничения, (г). На этом ограничения заканчиваются.

Для краткости записи в дальнейшем все ограничения будем обозначать (д). Это условно можно записать так:

Теперь можно приступить к формулировке задачи оптимизации. Как всегда, будем рассматривать две постановки:

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

Результат решения рассматриваемой задачи в обеих постановках приведен в табл. 11.20. Из этой таблицы видно, что в первой постановке 1-е и 2-е звенья реализованы первым вариантом, а 3-е – вторым. Во 2-й постановке все звенья реализованы первыми вариантами.

Такой же результат мы получили при решении этой задачи методом перебора на основе составленной таблицы вариантов (табл. 17). Так в чем же дело?

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Андреев, B. H. Эти замечательные цепи [Текст] / B. H. Андреев. – М. :

Знание, 1986. – 120 с.

2. Андреев, В. Н. Повышение качества и надежности манипуляторного технологического оборудования лесных машин при проектировании [Текст] : в 2 т. / В. Н. Андреев, Ю. Ю. Герасимов. – Петрозаводск, 1995. – 255 с.

3. Беллман, Р. Динамическое программирование и современная теория управления [Текст] / Р. Беллман, Р. Калаба. – М. : Наука, 1969. – 120 с.

4. Валтер, Я. Стохастические модели в экономике [Текст] / Я. Валтер ;

пер. с чешск. – М. : Статистика, 1976. – 231 с.

5. Вентцель, Е. С. Исследование операций. Задачи, принципы, методология [Текст] / Е. С. Вентцель. – М. : Наука, 1988. – 206 с.

6. Вентцель, Е. С. Элементы динамического программирования [Текст] / Е. С. Вентцель. – М. : Наука, 1964. – 176 с.

7. Дубов, Ю. Многокритериальные модели формирования и выбора вариантов систем [Текст] / Ю. Дубов, С. И. Травкин, В. Н. Якимец. – М. :

Наука, 1986. – 296 с.

8. Жак, С. В. Математическое программирование. Нелинейные и стохастические задачи [Текст] / С. В. Жак. – Ростов-н/Д., 1972. – 90 с.

9. Калихман, И. Л. Динамическое программирование в примерах и задачах [Текст] / И. Л. Калихман, М. А. Войтенко. – М. : Высш. шк., 1979. – 125 с.

10. Катулев, А. Н. Современный синтез критериев в задачах принятия решений [Текст] / А. Н. Катулев, В. Н. Михно, Л. С. Виленчик. – М. : Радио и связь, 1992. – 120 с.

11. Кузнецов, А. В. Руководство к решению задач по математическому программированию [Текст] / А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. – М. :

Вышэйш. шк., 1978. – 256 с.

12. Курицкий, Б. Я. Оптимизация вокруг нас [Текст] / Б. Я. Курицкий. – Л. : Машиностроение, 1989. –144 с.

13. Модели выбора недоминируемых вариантов в численных схемах многокритериальной оптимизации [Текст] / С. В. Белокуров, Ю. В. Бугаев, С. А. Максина, Ю. С. Сербулов, С. В. Чикунов. – Воронеж. : Научная книга, 2005. – 199 с.

14. Моисеев, Н. Н. Математические методы системного анализа [Текст] / Н. Н. Моисеев. – М. : Наука, 1981. – 487 с.

15. Мушик, Э. Методы принятия технических решений [Текст] / Э. Мушик, П. Мюллер. – М. : Мир, 1990. – 208 с.

16. Сысоев, В. В. Системное моделирование [Текст] : учеб. пособие / В. В. Сысоев. – Воронеж, 1991. – 80 с.

17. Юдин, Д. Б. Задачи и методы стохастического программирования [Текст] / Д. Б. Юдин. – М. : Сов. радио, 1979. – 392 с.

18. Bazaraa М., Shetty С. Nonlinear programming. Theory and algorithms.

New York: John Wiley & Sons, 1979. – 560 p.

19. Davis L.S., Johnson K.N. Forest management. New York: McGraw-Hill Book Company, 1987. – 790 p.

20. Klemperer W.D. Forest resource economics and finance. New York:

McGraw-Hill Book Company, 1996. – 551 p.

21. Leuschner W.A. Forest regulation, harvest scheduling, and planning techniques. New York: John Wiley & Sons, Inc, 1990. – 281 p.

22. Taha H. Operations research. An intoduction. New York: MacMillan Publishing Company, 1987. – 876 p.

Владимир Петрович Белокуров Сергей Владимирович Белокуров Геннадий Александрович Денисов Наталья Ивановна Злобина Эдуард Николаевич Бусарин

ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ

В ТЕХНОЛОГИИ ТРАНСПОРТНЫХ ПРОЦЕССОВ

Подписано в печать 02.12.2013. Формат 6090 /16. Объем 11,7 п. л.

Усл. печ. л. 11,7. Уч.-изд. л. 11,9. Тираж 65 экз. Заказ ФГБОУ ВПО «Воронежская государственная лесотехническая академия»

РИО ФГБОУ ВПО «ВГЛТА». 394087, г. Воронеж, ул. Тимирязева,