Оптимальное управление экономическими процессами

ВВЕДЕНИЕ Система оптимального управления экономическими процессами базируется на определенной теоретической основе, разработкой которой занимается теория оптимального функционирования и управления экономикой. Эта теория исходит из характера производственных отношений и законов развития общества. Специфика теории оптимального функционирования экономики заключается в том, что на основе познанных закономерностей развития общества она обосновывает принципы реализации объективно заложенной в природе тенденции к оптимальному развитию, обеспечивающие максимально полное удовлетворение потребностей общества при рациональном использовании всех его ресурсов и управления. Теория оптимального функционирования экономикой исходит из некоторых предпосылок аксиоматического характера, являющихся исходной базой для ряда важных следствий, выводов и обобщений. Системный подход является определяющим в теории оптимального функционирования экономики. Экономика рассматривается как очень сложная динамическая вероятностная система, реализующая объективную цель своего развития в условиях ограниченности трудовых и материальных ресурсов и научно-технических знаний при достаточно широкой взаимозаменяемости ресурсов, потребностей, технологий. Ограниченность ресурсов понимается в теории оптимального управления экономикой не в смысле хронического их дефицита, постоянной их нехватки, а как объективное условие осуществления процессов производства и потребления. Именно в оптимальном плане происходит строгое балансирование ресурсов и потребностей, то есть преодолевается дефицитность ресурсов в смысле превышения предъявляемого спроса над реальным предложением. Взаимозаменяемы также и потребности, максимально возможное удовлетворение которых является целью оптимизации развития экономики. Взаимозаменяемость потребностей, ресурсов, технологий, территориального размещения производства, маршрутов перевозок создает огромное множество вариантов решения экономических и управленческих задач и определяет проблему выбора из имеющихся вариантов лучшего, удовлетворяющего поставленной цели, что, по сути, приводит к задачам оптимального функционирования и управления экономическими системами. 1. Пять основных задач оптимального управления В последние годы большое внимание уделяется вопросам оптимального функционирования сложных систем. В частности, задача может заключаться в максимизации дальности полета ракеты, максимизации доходов какого-либо предприятия, минимизации ошибки оценивания координат объекта, минимизации энергии или затрат, требуемых для достижения некоторого заданного конечного состояния. Можно указать множество аналогичных задач. Исследование управления, с помощью которого может быть достигнута заданная цель при условии минимизации (или максимизации) определенного критерия качества системы, составляет фундаментальную задачу теории оптимизации. Эта задача может быть разделена на четыре взаимосвязанные части: 1. Определение цели. 2. Определение положения системы относительно цели. 3. Определение внешних факторов, оказывающих влияние на прошлое, настоящее и будущее системы. 4. Выбор наилучшей тактики поведения, исходя из определения цели (1), знания текущего состояния (2) и внешних факторов (3). Для решения задачи оптимизации в первую очередь необходимо определить целевую и стоимостную функцию оптимизируемого процесса. При этом требуется дать соответствующую формулировку задачи в физической форме и осуществить перевод этого физического описания на язык математики. Для осуществления эффективного управления процессом необходимо знать его текущее состояние. Будем называть это задачей оценки состояния. Кроме того, необходимо охарактеризовать процесс с помощью адекватной модели, зависящей от различных внешних факторов. Будем называть это идентификацией системы. При условии знания функции стоимости, состояния и параметров системы можно затем определить наилучшее управление, минимизирующее (или максимизирующее) функцию стоимости. Таким образом, можно сформулировать пять взаимосвязанных задач, решение которых даст возможность построить наилучшую, или оптимальную, систему. 1.1. Задача управления. Рассматривается система с заданной связью между входным управляющим воздействием и состояниями системы. Требуется найти управление, меняющее состояние х(t) так, чтобы была достигнута некоторая заданная цель. На рис.1 показаны основные особенности задачи управления. Это может быть задача с замкнутым или разомкнутым контуром, в зависимости от того, является ли управление функцией состояния системы. Рис.1. Задача детерминированного оптимального управления 1.2. Задача оценки состояния. Рассматривается известная система со случайным входным воздействием и шумом измерения, так что измеренный входной сигнал z(t) представляет собой, как показано на рис.2, искаженное состояние х(t). Известны законы распределения шума устройства w(t) и шума измерения v(t). Требуется найти "наилучшую" оценку х*(t) истинного состояния системы х(t) по известному z(t). Рис.2. Задача оценки состояния 1.3. Задача стохастического управления. Задача стохастического управления может быть получена путем объединения задач 1 и 2. Требуется определить управление v(t), такое, чтобы выходное состояние x(t) менялось желаемым образом. Присутствуют шум устройства w(t) и шум измерения v(t). Известны законы распределения этих шумов. Требуется найти наилучшую оценку x*(t) по наблюдаемому входному состоянию z(t), прежде чем можно будет определить "наилучшее" управление, которое может быть управлением с разомкнутым или замкнутым контуром. Рис.3. Задача стохастического управления 1.4. Задача оценивания параметров. Во многих задачах приходится вводить некоторые методы идентификации параметров систем, которые могут меняться в зависимости от окружающих условий. Дана система, такая, как показана на рис.4. Известны статистические характеристики шумов устройства и измерения и требуется найти наилучшую оценку некоторых параметров устройства, основываясь на знании детерминированного входного сигнала v(t), измеренного входного сигнала z(t) и знании некоторой априорной информации о структуре устройства. 1.5. Задача адаптивного управления. Задача адаптивного управления может быть составлена в результате комбинации задач 1–4. При этом задаются статистические характеристики шумов w(t) и v(t). Параметры устройства случайные. Требуется найти управление n(t), зависящее от шумов измерения и устройства, а также изменение динамики системы, такое, чтобы наилучшим образом выполнялись некоторые заданные условия. Рис.4. Задача стохастического управления 2. Оптимальное управление для дискретныхи непрерывных процессов Теория оптимального управления экономическими процессами представляет собой раздел науки оптимального управления сложными системами. Одним из основных принципов, на который она опирается, является принцип максимума Понтрягина. Поэтому прежде, чем перейти к рассмотрению разделов, связанных с оптимизацией экономических процессов, рассмотрим основные понятия и определения теории управления и начнем с классического примера движения материальной точки. 2.1 Постановка задачи оптимального управления для непрерывных процессов Рассмотрим прямолинейное движение материальной точки. Состояние движущегося объекта можно охарактеризовать функцией x1(t) и скоростью x2(t). На движение можно влиять выбором ускорения u(t). Уравнения движения при этом имеют вид Существенно, что состояние объекта, описываемое указанным законом (системой обыкновенных дифференциальных уравнении), изменяется под внешним воздействием (управлением). Функции x1(t), ..., xn(t), описывающие состояние объекта, называют фазовыми координатами объекта. Вектор х(t) с координатами x1(t), ..., хn(t) называют фазовым вектором, n-мерное пространство точек х – фазовым пространством. Состояние объекта зависит от величин управления u1(t), ..., ur(t), которые объединяются в вектор управления u(t): Ur-мерное пространство точек, и называется пространством управления. Если х0 = х(t0) есть начальное состояние объекта, то состояние х(t) должно однозначно определяться заданием х0 и u(t)(t  t0). Соответствующую кривую в пространстве состояний, исходящую из точки х0, называют траекторией. Пусть закон изменения состояния описывается системой обыкновенных дифференциальных уравнений (динамической системой): или, в векторном виде, Если функции fi(х, u, t) и fi/xj(i = 1, ..., n) непрерывно дифференцируемы по всем аргументам, то говорят о непрерывной динамической системе. Динамическая система т. е. где А есть n х n-матрица с элементами aij, а B – n х r-матрица с элементами bik, называется линейной. Две динамические системы называются эквивалентными, если существует невырожденная матрица Р размера n х n с постоянными элементами, такая, что Тогда В общем случае вектор управления не может выбираться произвольно, так как в силу реальных технических условий на него накладываются определенные ограничения. Пусть U есть подмножество в пространстве управления, определенное, например, посредством неравенств |ui|  аi, или ||u||  a, или h(u)  0, и пусть u(t) принимает значения только из U; тогда U называется областью управления (зачастую область U является замкнутой или даже замкнутой, ограниченной и выпуклой). Очень часто на u(t) накладываются дополнительные требования гладкости. Если, например, управляющие устройства работают безынерционно, то это значит, что управление должно быть кусочно-непрерывным. Управление называется допустимым на отрезке [t0, t1], если 1) u(t) принимает значения только из U; 2) u(t) кусочно-непрерывна. Состояние х1 называется достижимым из состояния х0 = х(t0), если существуют допустимое управление и такое t1  t0, что для соответствующей траектории х(t1) = х1. Множество всех состояний, достижимых из х0, называют множеством достижимости, относящимся к начальному состоянию х0 = х(t0) и области управления U. Если при этом задано и t1, то говорят о множестве достижимости, относящемся к х0, U и t1. Если множество U выпукло, то для линейной системы множество достижимости, относящееся к фиксированному t1, является также выпуклым (множество достижимости в общем смысле при этом не обязательно выпуклое). Всюду в дальнейшем будем считать, что область управления совпадает со всем пространством управления. Если состояние х1 = 0 является достижимым из состояния х0 = х(t0), то говорят, что х0 – управляемое состояние в момент времени t0. Если каждое состояние х0 является управляемым в момент времени t0, то систему для времени t0 называют управляемой; если каждое состояние х0 является управляемым для каждого t0, то систему называют полностью управляемой (т.е. каждую точку пространства состояний при любом начальном моменте времени можно перевести в начало координат). Система управляема тогда и только тогда, когда любая эквивалентная ей система является управляемой. Однако это утверждение трудно использовать для практического анализа. Для линейной системы, у которой элементы матриц А и В являются постоянными (автономная линейная система), справедливо следующее утверждение. Пусть G есть матрица размера n х nr: линейная автономная система является полностью управляемой тогда и только тогда, когда выполняется равенство 2.2. Принцип максимума Понтрягина При одинаковых начальных состояниях данной динамической системы, но при разных допустимых управлениях получают, вообще говоря, различные функции состояний и, следовательно, различные процессы [u(t), x(t)]. Поэтому имеет смысл говорить о таком процессе, который оптимален в некотором смысле. Тогда говорят об оптимальном процессе: соответствующее управление называют оптимальным управлением, соответствующее состояние – оптимальным и соответствующую кривую – оптимальной траекторией. Основная задача. Пусть задана динамическая система с начальным условием х(t0) = x0 и областью управления U. Ищется такое допустимое управление и соответствующая траектория, что для фиксированного конечного момента времени t1 выражение где сi – заданные постоянные, является минимальным. (Очевидно, что речь идет о минимизации линейной комбинации координат конечного состояния.) Введем присоединенную вектор-функцию p(t) с координатами p1(t), ..., pn(t), удовлетворяющими соотношению Вводя обозначения с = (с1, ..., сn)T, р = (p1, ..., pn)T, получаем векторное представление: Под функцией Гамильтона понимают выражение Таким образом, динамическая и присоединенная системы могут быть представлены в форме канонических уравнений: где и  – градиенты H по р и x. Принцип максимума Понтрягина. Для того чтобы процесс [u(t), x(t)] решал заданную основную задачу (т.е. являлся оптимальным процессом в смысле постановки задачи), необходимо существование присоединенной функции р(t), являющейся решением присоединенной системы с соответствующим граничным условием и такой, что для почти всех t[t0, t1] выполняется условие Если нужно максимизировать J, то указанное относительно Н условие максимума заменяется соответствующим условием минимума или граничное условие записывается в виде p(t1) = +с. Существенное преимущество принципа максимума по сравнению с классическими теоремами вариационного исчисления состоит в том, что он применим для любого (в частности замкнутого) множества U. Расширение класса возможных областей управления U по сравнению с классическим случаем открытых множеств весьма существенно для приложений теории. Если нужно минимизировать дважды дифференцируемую по всем аргументам функцию то в принципе максимума Понтрягина начальные условия для присоединенной системы следует заменить на . Если нужно минимизировать функционал где функция f0 удовлетворяет таким же условиям, что и fi, то функция Гамильтона определяется формулой а присоединенная система имеет вид Пример. Пусть динамическая система описывается законом Найдем оптимальное управление, при котором функционал оказывается минимальным. Имеем т.е. Следовательно, Максимум H* доставляет u = –1/2. 2.3. Постановка задачи оптимального управления для дискретных процессов Если область определения функции состояния x(t) является множеством конечного числа значений t1, t2, ..., tN и изменение состояния происходит согласно закону то говорят о дискретной системе. При этом u(tk) является r-мерным вектором управления в момент времени tk с областью управления Uk. Вводя обозначения uk = u(tk), xk = x(tk), представим систему в виде Если положить tk = k, то систему можно наглядно описать при помощи N-ступенчатого процесса (рис. 5). При этом хk есть выходное состояние ступени k, хk-1 – соответствующее входное состояние, а uk – управление, действующее на этой ступени. Выходное состояние получается в зависимости от входного состояния и соответствующего управления. Рис. 5 Особое значение имеет следующая оптимизационная задача. Дана система где fk по меньшей мере один раз дифференцируема по всем переменным, ukUk (замкнутое), начальное значение х0 задано; найти такое допустимое управление uk, чтобы сумма была минимальна ( – координаты выходного состояния ). Если нужно минимизировать , то для каждой ступени вводят величину состояния : Цель оптимизации – минимизировать . Для таких систем могут быть сформулированы некоторые типичные постановки задач, подобно тому как это делалось для непрерывных систем. Гамильтониан ступени k (k = l, ..., N): Присоединенный вектор рk и присоединенная система ступени k: Принцип максимума. Если uk оптимально в смысле поставленной задачи, то необходимо существование N присоединенных, отличных от нуля, векторов pk, представляющих собой решения присоединенной системы и таких, что в случае, если uk лежит внутри Uk, и максимально в случае, если uk лежит на границе Uk. В отличие от так называемого сильного принципа максимума для непрерывных процессов, эту форму называют слабым принципом максимума. 2.4. Дискретная оптимизация на примере планирования производства и запасов Проиллюстрируем постановку задачи оптимального управления с дискретным временем на следующем примере. Предположим, что некоторая компания производит определенный продукт, спрос на который известен. Спрос на продукт в любой период времени может удовлетворяться как за счет продукции, хранимой на складе к началу этого периода, так и за счет произведенной в течение этого же периода продукции. Количество продукции, производимое в каждом периоде времени, ограничено имеющимися производственными мощностями. Трудовые ресурсы не ограничены. Чтобы обеспечить бесперебойную работу, производственный план должен быть составлен на несколько (например, К) периодов времени. Задача заключается в составлении плана производства на К периодов, гарантирующего удовлетворение спроса на продукцию в каждом периоде при минимальных суммарных затратах. Пусть Lk – число рабочих, используемое в производстве в k-м периоде. Тогда uk=Lk – Lk-1 – изменение потребности в рабочей силе при переходе от (k-1)-го к k-му периоду. Обозначим через Ik запасы продукции в k-м периоде. Предполагается, что затраты определяются нестабильностью в требуемой рабочей силе – значениями uk для k=1, ..., К – и затратами на поддержание уровня запасов Ik в каждом из планируемых периодов. Чтобы сократить колебания в требуемой рабочей силе, целесообразно считать, что затраты на изменение uk пропорциональны . Пусть при этом затраты на поддержание уровня запасов Ik пропорциональны величине запасов. Требуется найти такие интенсивности труда Lk (требуемое число рабочих) и такие запасы продукции Ik в каждом из периодов k = 1, ..., K, при которых удовлетворяется спрос dk, a суммарные затраты минимальны. В этой задаче каждому периоду времени отвечают две фазовые переменные Ik – уровень запасов и Lk – требуемое число рабочих. Параметром управления является: Uk – изменение требуемых трудовых ресурсов (uk < 0 означает сокращение необходимой рабочей силы). Задача может быть формализована следующим образом: минимизировать при условиях Здесь I0 – начальный запас продукции, L0 — начальное число рабочих, нанятых компанией, dk – известный спрос на продукцию в каждом из периодов, р – количество единиц продукции, выпускаемых одним рабочим в течение одного периода, b – максимальный объем производимой в одном периоде продукции, определяемый ограниченными производственными мощностями. 2.5. Непрерывная оптимизация на примере задачи строительства шоссе Предположим, что требуется проложить дорогу по неровной местности между двумя пунктами, причем затраты на строительство пропорциональны количеству завезенного и вывезенного с трассы грунта. Пусть Т – длина дороги, a c(t) – известная высота местности в точке на расстоянии t[0, T] от начального пункта трассы. Требуется определить функцию y(t), описывающую высоту дороги в каждой ее точке t[0, Т] и отвечающую минимальным затратам на ее строительство. При этом предполагается, что наклон дороги в любой точке трассы не должен превосходить величины b1, т.е. для t[0, T]. Целесообразно также потребовать, чтобы скорость изменения наклона дороги не превышала заданной величины b2, т.е. для t[0, T]. Пусть уровень дороги в начальном и конечном пунктах определяется равенствами y(0) = a и у(Т) = b. Задача формулируется следующим образом: минимизировать при условиях Заметим, что параметром управления здесь является объем грунта, вывезенный или завезенный в точку трассы на расстояние t от начального пункта, т.е. величина, пропорциональная Разделим теперь всю длину дороги на K интервалов длины  каждый и положим у1 = у; y2 = . Для простоты будем считать, что  = 1. Обозначим c(k), y1(k) и y2(k) через сk, y1, k и y2, k соответственно для k = 1, ..., K. Тогда исходная задача аппроксимируется следующей задачей нелинейного программирования: минимизировать при условиях Более детальное рассмотрение этой задачи содержится в работе Citron [1969]. 3. Основы моделирования управленческих решений в экономике 3.1. Основные понятия и определения Образование стран – новых субъектов международного права, реформы в ряде стран, научно-техническая революция в развитых странах, конверсия военно-промышленного комплекса обострили актуальность проблемы повышения эффективности управления большими организационно-производственными системами (ОПС). Организационно-производственными системами условимся называть совокупность персонала, средств производства и других элементов, объединенных для того, чтобы на некотором множестве условий достичь соответствующего множества целей через производство некоторого множества товаров. Будем исходить из того, что в организационно-производственных системах могут быть выделены контуры управления: финансами, средствами производства, технологическими, материальными потоками, персоналом и другие. В рамках организационно-производственных систем могут быть выделены субъекты управления (система управления и объект управления) и производственно-технологические мощности с соответствующим персоналом. Под управлением будем понимать циклически повторяющийся процесс воздействия органа управления на управляемый объект, в котором последовательно на основании обработки исходной информации о состоянии объекта и оценки обстановки вырабатываются план достижения цели и меры для его реализации, осуществляются передача воздействий на объект управления и контроль их выполнения, коррекция планов в зависимости от изменения условий обстановки и состояния объекта, выработка и передача новых воздействий, выбранных из множества возможных вариантов и обеспечивающих достижение конкретной цели при оптимальных затратах ресурсов. Составными элементами управления являются: • целеполагание (определение цели); • сбор, обработка и оценка информации об объекте управления и обстановке; • динамическое планирование (планирование с периодическим вводом корректур в ранее разработанный план) воздействий на объект управления; • контроль исполнения (оценка результата воздействия). Эти элементы циклически повторяются. Применение вычислительной техники позволяет повысить результативность управления экономическими объектами и техническими системами путем создания автоматизированных рабочих мест для персонала управления и автоматизации производства. Решение является определяющим и ключевым центральным звеном процесса управления (менеджмента). Решения направлены на достижение целей организационно-производственных систем. Целью будем называть идеальный результат деятельности. Для того чтобы быть эффективным, то есть достигать поставленных целей, решение должно отвечать определенным требованиям и обладать соответствующими свойствами. В частности, решения должны быть: реальными – требовать не более располагаемого расхода ресурсов времени и средств; эффективными – достигать поставленных целей (при этом могут выделятся как синергичные, так и асинергичные решения); реализуемыми – быть выполнимыми с учетом возможных мотивов, противодействий и конфликтов всех элементов внешней и внутренней среды и персонала. Синергия решений может быть обеспечена комплексированием – повышением степени избыточности в одном варианте по отношению к другому варианту. Для этого управленческие решения разрабатываются и реализуются в соответствии с типовыми (запрограммированными решениями) или индивидуальными алгоритмами. Алгоритмом будем называть точное предписание, определяющее процесс преобразования информации и (или) исполнения, контроля управления управленческих решений. Момент получения информации об объекте отстоит от момента исполнения решения на период времени, необходимого для получения, обработки, анализа информации, принятия решения, его передачи и исполнения. Поэтому любое решение является прогнозируемым, или плановым. Любой из людей, вне зависимости от желания, подсознательно и (или) сознательно прогнозирует последствия своих действий. Следовательно, важно учитывать, что всякое управленческое решение является прогнозным. Результаты рыночной деятельности свидетельствуют, что справедлива формула Прогнозирование => Планирование => Реализация => Успех В условиях усложнения объектов управления и динамичной внешней среды переходной экономики это положение только усиливается. 3.2. Разработка управленческих решений – центральное звено менеджмента Определим связь решения с предпринимательством и менеджментом. Предприниматель (бизнесмен) и менеджер являются ключевыми фигурами рыночной экономики. Они не могут реализовать свое предназначение без разработки и принятия эффективных решений. "Предприниматель (бизнесмен) – это человек, способный понять структуру потребностей и сочетать это свое понимание со знаниями в области управления производством в целях создания благ. Предприниматель способен творчески решать задачи согласования потребностей с производственными ресурсами, располагает капиталом, энергией и несет расходы, необходимые для организации дела (бизнеса)". Предприниматель несет риск бизнеса, и в этом состоит его основное отличие от менеджера. Менеджер организует и управляет трудом других людей. От специалиста менеджера отличает наличие: 1) подчиненных; 2) полномочий по принятию решений в оговоренной соответствующим образом сфере. К названным выше отличиям можно добавить поддержание баланса между функциями владения собственниками, управления менеджерами, исполнения работ специалистами. В управлении выделяют субъект – активную часть, вырабатывающую управляющие воздействия, и объект управления – часть, подвергающуюся воздействию управляющих сигналов. Субъектом управленческого решения может быть как управляющая подсистема ОПС, так и лицо, принимающее решение. Субъект управления (лицо, принимающее решение) – менеджер или группа менеджеров, которым предоставлено право разработки и окончательного выбора одного из альтернативных вариантов системы (товара, услуги) или операции. 3.3. Модели систем и операций Объекты управленческих решений – это система (товар) и операция. Известны следующие определения. Система – это то, что решает проблему. Товар или услуга – это то, что удовлетворяет потребность, нужду и предлагается рынку с целью привлечения внимания, приобретения, использования или потребления. В качестве системы могут выступать товар или ОПС для разработки, производства, продвижения, утилизации определенных товаров. Поэтому определим систему как множество элементов, объединенных структурно и алгоритмически таким образом, чтобы на некотором множестве условий реализовать некоторое множество функций. Услуга – это нечто, предающее новое качество существующим объектам и товарам. В некоторых случаях представляется возможным рассматривать услугу в качестве операции. Подготовку управленческих решений, связанных с выбором вариантов системы, изучает системотехника. Операция – это любое мероприятие (или система действий), объединенное единым замыслом и направленное на достижение цели. При подготовке управленческих решений по осуществлению операций – конкретных вариантов продвижения и использования товаров – могут использоваться методы исследования операций. Отметим, что товары и системы создаются для реализации некоторых операций, а операции можно реализовывать, только используя соответствующие товары и системы. В процессе подготовки и обосновании решения используют модели. Модель – это упрощенное представление товара, операции (или их отдельных сторон), используемое с целью снижения затрат и (или) риска при изучении, диагностике, оптимизации объекта моделирования. Под оптимизацией будем понимать процесс нахождения экстремума рассматриваемой функции, т.е. выбор наилучшего варианта из множества возможных, процесс выработки оптимальных решений по приведению системы в наилучшее (оптимальное) состояние. Представляется возможным сформулировать модель задачи выбора оптимального управленческого решения в следующем виде: При заданных внешних условиях х1, х2, …, хn (i = 1, 2, …, n) найти 1) такие состояния z1, z2, …, zk (j = 1, 2, …, k); 2) такие управления u1, u2, …, um (l = 1, 2, …, m), которые бы приносили некоторому критерию W (x, z, u) наилучшее (наименьшее или наибольшее) значение. В целях снижения сложности объекта исследования до приемлемого уровня в конкретных ситуациях принятия решений, упрощения задачи для лиц, принимающих решения, предпочитают разделять задачу на две части: 1) задача системного анализа – выбора или синтеза системы – набора неизвестных (оптимизируемых) переменных – состояний z1, z2, …, zk (j = 1, 2, …, k), доставляющих экстремум критерию W0(x3, u3, z3), при условии известных наборов: внешних условий x3 = {x1, x2, …, xn}, (i = 1, …, n); управлений u3 = {u1, u2, …, un}, (l = 1, …, m); 2) оптимизация и выбор наилучшей операции с имеющимся товаром (системой), то есть управлений u1, u2, …, um (l = 1, 2, …, m), доставляющих экстремум (максимум или минимум) критерию W0(x3, u3, z3), при условии известных наборов: внешних условий x3 = {x1, x2, …, xn}; состояний системы (товара) z3 = {z1, z2, z3, …, zk}. 3.4. Цели и критерии оптимального управления Цель определяет то, ради чего создают систему. Целью решения условимся называть те конкретные результаты, которые предполагается получить после реализации этого решения в определенных условиях и фиксированном периоде времени. При этом цель лежит всегда вне системы. Она отражает реакцию среды на систему. Качество цели определяет успех или неудачу ОПС. Перечислим известные требования, предъявляемые к целям: 1. Цели должны быть недвусмысленно сформулированы и понятны исполнителям. 2. Цель должна быть измеряема. Для этого используется обратная связь. 3. Цель должна иметь сроки исполнения. 4. Цель должна мотивировать действия исполнителя в необходимом для ее достижения направлении. 5. Цели организации и отдельных исполнителей должны быть совместимы. 6. Цель должна быть формализуема. Формулирование целей – процесс очень сложный. Формальных методов синтеза целей не существует. Процесс формулировки целей носит эвристический характер. Для коммерческих организаций основной целью является оптимизация прибыли. Формализация целей имеет место при формировании критерия оценки эффективности системы. Сложность систем породила различные варианты определения критерия. В первом варианте критерий определяют как количественное отражение степени достижения системой поставленных перед ней целей. В оптимальном управлении удобней рассматривать критерий как правило выбора предпочтительного варианта решения из ряда альтернативных. В соответствии с прогнозной эффективностью можно выделить следующие варианты решений: 1) неэффективные, не позволяющие решить проблему; 2) рациональные, т.е. позволяющие решить проблему; 3) оптимальный вариант решения – вариант, позволяющий решить проблему наилучшим в определенном критерием смысле. Для сложной системы в силу ее многогранности критерий является вектором. При этом задача оптимизации сложной системы является многокритериальной. Критерий включает в себя в качестве компонентов параметры эффективности (эффекта). Параметром эффективности называют наиболее важные параметры системы, которые позволяют оценить качество решения проблемы и достижения поставленных перед системой целей. Для ОПС в качестве параметров эффекта могут рассматриваться: стоимость и (или) время создания, доход, прибыль (убытки) за фиксированный период времени и т.д. Параметры эффекта представляют систему ее создателю и среде. Поэтому при выборе состава параметров эффекта учитывают как то, ради чего создается система, так и цели исследования. Существуют различные подходы к формированию критериев. В зависимости от числа параметров оптимизации в критерии говорят о многокритериальной и поликритериальной (векторной) постановке задач. При многокритериальной постановке оптимизируют (максимизируют или минимизируют) один из параметров эффекта. При поликритериальной постановке проводится совместная оптимизация ряда параметров эффекта. При оптимизации объектов машиностроения в состав критерия могут включаться параметры, характеризующие эффективность, стоимость, время, безопасность. Чаще всего в качестве оптимизирующего параметра выбирают либо эффективность, либо стоимость. При оценке экономической эффективности измеряют и оптимизируют: доход, прибыль, убытки, производительность труда и т.п. Сложности векторной оптимизации привели к тому, что значительное распространение получили приемы линеаризации критериев. Эти приемы предусматривают переход от векторной формы критерия к одномерной линейной. Известны аддитивные, мультипликативные критерии и индексы. Аддитивный критерий А формируется путем деления на число показателей эффекта n суммы произведений частных показателей эффекта li на gi (коэффициенты значимости i-го параметра), сумма которых равна 1: Мультипликативный критерий М определяется как произведение частных показателей эффекта li на коэффициенты значимости gi i-го параметра, сумма которых равна 1. . Принципиальный недостаток такого типа критериев заключается в том, что подразумевается возможность компенсировать недостаток одних качеств за счет избытка других. В теоретическом плане это верно, так как качества системы (например, опасность, эффективность) несравнимы между собой. В реальной жизни такой подход может привести к нежелательным последствиям. Кроме того, коэффициенты веса определяются экспертным путем, что снижает точность и объективность оценки. Второй подход к формированию критериев состоит в том, что одну часть параметров эффекта (которые нужно улучшить) относят к числителю, а другую часть параметров (которые нужно уменьшить) относят к знаменателю. Главным недостатком этого подхода является то, что, уменьшая знаменатель при незначительной величине числителя, можно обеспечить большое значение критерия. Поэтому такого рода критерий может быть применен с использованием ограничений или на величину критерия, или числителя, или знаменателя. Наиболее известным из этого типа критериев является критерий "эффективность/затраты". Третий подход состоит в том, что один из параметров эффекта максимизируют или минимизируют, а на остальные накладывают ограничения. Приведем некоторые критерии, относящиеся к третьему подходу. 1. Максимизировать прибыль Пi (или другой параметр эффекта) при заданных ограничениях на объем затрат Зз и уровень риска Рз: ; , где i – номер варианта. 2. Минимизировать объем затрат Зi при заданных ограничениях на прибыль Пз и уровень риска Рз: ; , 3. Минимизировать уровень риска Pi при заданных ограничениях на прибыль Пз и объем затрат Зз: ; . Многофункциональные системы применяют на некотором фиксированном множестве условий. Для оптимизации системы оценивают эффективность вариантов системы в каждом из условий. 4. Оптимальное планирование – составная часть оптимального управления ОПС Если проанализировать производство какого-либо определенного вида продукции, то, как правило, выявится возможность получения этого продукта несколькими технологическими способами с применением различных взаимозаменяемых средств производства. Так, существует несколько способов выплавки стали (мартеновский, конверторный, в электропечах), добычи угля (шахтный, открытый, гидравлический), производства электроэнергии (на гидростанциях, на тепловых электростанциях, на атомных электростанциях, с использованием энергии приливов и отливов). Нередко сходные продукты получаются с применением не только различных технологических способов, но и совершенно разных видов исходного сырья (например, получение натурального и искусственного волокна). В ряде производств допустима замена одних материалов другими (например, металлов пластмассами), использование различных видов топлива (твердого, жидкого, газообразного). Произведенная продукция может обычно доставляться потребителям не одним, а несколькими (на выбор) видами транспорта, причем сам маршрут доставки также не является единственно возможным. Самый эффективный вариант называется оптимальным вариантом. Таким образом, оптимальным является план, обеспечивающий заданный производственный результат при минимальных затратах или максимальный производственный эффект при заданном объеме ресурсов. Решение проблемы оптимального планирования не может быть получено без широкого применения математики и электронной вычислительной техники в плановых расчетах. Современные математические методы позволяют отыскать действительно оптимальный вариант плана, избежав при этом прямого перебора всех возможных вариантов. И хотя объем вычислений может оставаться все же достаточно большим, использование электронных вычислительных машин помогает выполнить их в приемлемые сроки и с относительно невысокими затратами. 4.1. Общая постановка задачи линейного программирования Одним из наиболее эффективных, глубоко разработанных и широко проверенных на практике методов решения задач оптимального планирования является линейное программирование. Рассматриваемые в данном разделе модели оптимального планирования в основном приводятся именно к задачам линейного программирования. Однако в целом понятие оптимального планирования значительно шире, чем понятие математической задачи вообще и задачи линейного программирования в частности. Оптимальное планирование – сложная экономическая проблема, достаточно назвать хотя бы первостепенной важности вопрос о критерии эффективности плана. Линейное программирование объединяет теорию и методы решения определенного класса задач, в которых требуется найти совокупность значений переменных величин, удовлетворяющую заданным линейным ограничениям и максимизирующую (или минимизирующую) некоторую линейную функцию этих переменных. В общей постановке задача линейного программирования сводится к следующему: максимизировать при условиях Задача линейного программирования в сокращенной записи выглядит следующим образом: максимизировать при условиях Здесь хj, – переменные величины задачи линейного программирования, aij, bi, cj – константы задачи. В математической модели задачи линейного программирования выделяются три составные части: целевая (максимизируемая) функция, система ограничений и условие неотрицательности переменных. Всякое решение задачи, удовлетворяющее системе ограничений и условию неотрицательности, называется допустимым решением, а удовлетворяющее всем трем группам требований – оптимальным решением. Коэффициенты с целевой функции в экономических задачах линейного программирования могут обозначать прибыль на единицу продукции, цены, уровень затрат и т.д. Для содержания задачи очень важно, решается ли она на максимум (прибыль, объем продукции, производительность труда) или на минимум (текущие затраты, капиталовложения, время выполнения работ и пр). Формально же минимизируемая целевая функция легко сводится к максимизируемой умножением на "–1". Поэтому приведенная выше общая запись задачи линейного программирования охватывает не только задачи на максимум, но и задачи на минимум. Система ограничений общей задачи линейного программирования включает m уравнений. При m = n система ограничений имеет единственное решение, которое должно считаться оптимальным решением (если соблюдается условие неотрицательности переменных). Очевидно, что практически представляют интерес лишь задачи, в которых m < n, т.е. неизвестных больше, чем уравнений. В этом случае система может иметь бесконечное множество решений; именно тогда возникает необходимость в специальных методах отыскания среди них решения, наилучшего с точки зрения принятого критерия эффективности. Разумеется, система может оказаться и несовместной, т.е. не имеющей решений вообще. В экономических задачах линейного программирования чаще всего система ограничений первоначально имеет форму неравенств. Например, коэффициенты аij, обозначают нормы затрат ресурсов на единицу продукции, величины bi – располагаемый объем ресурсов, а ограничения-неравенства требуют, чтобы расход не превышал объема ресурсов. Такой характер имели ограничения в приведенном выше примере определения месячного выпуска продукции, обеспечивающего наибольшую сумму прибыли. В общем виде эти ограничения можно записать следующим образом: Для общей постановки и решения задачи линейного программирования исходные ограничения-неравенства должны быть преобразованы в уравнения. Это может быть достигнуто добавлением к левой части каждого ограничения дополнительной неотрицательной переменной величины: Если совокупность значений основных переменных обращает какое-либо из исходных неравенств в строгое равенство, то соответствующая дополнительная переменная равна нулю, в противоположном случае она дополняет численное значение левой части неравенства до величины &" в правой части. В задачах линейного программирования дополнительные переменные имеют вполне определенный экономический смысл. Так, если в ограничениях задачи отражается расход и наличие производственных ресурсов, то дополнительные переменные в оптимальном плане будут характеризовать объем неиспользованных ресурсов. Во многих задачах исходные ограничения имеют форму неравенств вида "больше или равно": Такая система преобразуется в уравнение путем вычитания из левой части неравенств дополнительных неотрицательных переменных: Количество вводимых дополнительных переменных равно числу неравенств m. Поэтому во всех задачах, где ограничения выражены только неравенствами, после введения дополнительных переменных общее количество неизвестных величин (k + m) превышает число уравнений. Как видим, при любом характере исходных ограничений задачи линейного программирования они в конечном счете приводятся к общей форме. Условие неотрицательности переменных также относится ко всем рассматриваемым здесь задачам линейного программирования. Для экономических задач это условие не является обременительным, так как переменные здесь по самому смыслу, как правило, не могут быть отрицательными. Вместе с тем в математическом отношении условие неотрицательности играет существенную роль, так как ограничивает область допустимых решений задачи лишь теми решениями, которые не содержат отрицательных значений переменных величин. Из математических особенностей общей модели линейного программирования вытекает ряд требований, которые необходимо учитывать при постановке экономической задачи. Как уже отмечалось, далеко не каждая задача оптимального планирования может быть сформулирована и разрешена в рамках линейного программирования. Укажем четыре основных условия, при которых это становится возможным. 1. В задаче должен быть четко сформулированный и количественно определенный показатель эффективности – критерий оптимальности плана. В конкретных задачах не всегда легко найти единственный критерий, позволяющий безусловно отбрасывать одни варианты и принимать другие. На практике о работе предприятий судят по ряду показателей – объему, ассортименту и качеству продукции, рентабельности и др.; о различных вариантах капитального строительства – по величине капиталовложений, объему и себестоимости продукции, срокам строительства. Наиболее рентабельный вариант плана может оказаться далеко не лучшим с точки зрения объема продукции, и наоборот. Но в математической задаче должен быть один критерий оптимальности, одна целевая функция, хотя она может объединять и несколько экономических показателей, например, текущие производственные затраты, приведенные капиталовложения, транспортные расходы в некоторых задачах объединяются в единый критерий – минимум приведенных затрат. Однако единый и безусловный предпочтительный критерий оптимальности плана удается пока сформулировать лишь для ограниченного круга сравнительно простых задач оптимального планирования. 2. Важнейшей составной частью задачи являются особые условия и ограничения, связанные с наличными ресурсами, потребностями и другими факторами, определяющими допустимые решения. В реальной экономической действительности взаимодействует слишком большое количество факторов, чтобы все они могли быть учтены в задаче. К этому и не следует стремиться. Однако необходимо отобрать и ввести в условия задачи все решающие факторы и ограничения, чтобы упрощенная по сравнению с действительностью модель не потеряла реального характера и практической ценности. Ответственным этапом постановки задачи является также определение нормативов затрат и других числовых характеристик, входящих в систему ограничений. От качества и обоснованности этих данных во многом зависит конечный результат расчетов. 3. Линейное программирование предназначено для выбора оптимальной программы среди многих допустимых программ, и оно применяется только тогда, когда конкретные условия экономической задачи обусловливают свободу выбора вариантов. Переменные величины в моделях линейного программирования взаимозаменяемы; они не только зависимы между собой по величине, но и могут непосредственно замещать друг друга в плане. Следовательно, свойство взаимозаменяемости должно быть присуще и тем экономическим величинам, которые выступают в задаче в качестве ее переменных. Так, в приведенных выше примерах столы и шкафы могли производиться в любых соотношениях, взаимозаменяемыми были два вида кормов. Взаимозаменяемость и многовариантность – непременные условия, определяющие возможность применения к экономической задаче методов линейного программирования. 4. Модель задачи линейного программирования должна содержать только линейные уравнения и неравенства, иными словами, как в целевую функцию, так и в ограничения задачи переменные могут входить лишь в первой степени. Реальные экономические зависимости далеко не всегда носят линейный характер. Тогда необходимо либо ограничиться приближенным решением, аппроксимировав нелинейные функции линейными, либо прибегнуть к более сложным методам (в частности, к нелинейному программированию). Возвращаясь к математической характеристике задачи линейного программирования, отметим некоторые общие особенности получаемого решения, не связанные с тем или иным применяемым методом. Прежде всего отметим четыре основных возможных результата решения задачи линейного программирования: 1) условия задачи могут оказаться несовместными, и задача вообще не имеет неотрицательных решений; 2) неотрицательные решения имеются, но максимум (минимум) целевой функции не ограничен (стремится к бесконечности); 3) оптимум целевой функции представляет собой конечное число и достигается при единственном сочетании значений переменных величин; 4) максимальное (минимальное) значение целевой функции достигается при многих вариантах программы (случай множества оптимальных планов). При правильной постановке экономической задачи первый и второй результаты исключаются, однако следует учитывать, что наложение на переменные величины слишком жестких ограничений может привести к противоречивости всей системы исходных условий задачи. В линейном программировании доказывается, что если задача включает n переменных и m ограничений (линейно независимых), причем n > m, то в оптимальном плане положительные значения будут иметь не более m переменных, а остальные n – от переменных равны нулю. Это важно иметь в виду при постановке экономической задачи. Если, например, в задаче планирования производственной программы фигурируют 5 видов продукции и всего 2 ограничения, то еще до решения задачи можно утверждать, что в оптимальный план войдет не больше двух видов продукции из 5-ти. Лишь в случае множества оптимальных планов можно рассчитать оптимальные варианты, в которых количество положительных переменных больше числа ограничений. Перейдем к общей характеристике методов решения задач линейного программирования. Они различаются не только по принципам расчета оптимальной программы, но и по кругу решаемых задач, по эффективности в вычислительном отношении. Общий принцип решения заключается в поэтапном, последовательном переходе от исходного варианта программы к оптимальному варианту. При этом используются в основном два различных способа отыскания оптимальной программы. Первый способ состоит в том, что вначале получают допустимый вариант (удовлетворяющий всем ограничениям), но не обязательно оптимальный; оптимальность достигается за определенное число этапов путем последовательного улучшения исходного варианта. При втором способе получают с самого начала условно-оптимальный план, который обеспечивает максимум (минимум) целевой функции, но может не быть допустимым и становится допустимым вариантом плана лишь после определенных преобразований. По кругу решаемых задач методы линейного программирования можно разбить на две группы. В первую группу входят универсальные методы, с помощью которых могут решаться любые задачи линейного программирования. Из универсальных методов наибольшее распространение получил симплексный метод, предложенный Дж. Данцигом. Наряду с обычным симплексным методом применяются и некоторые его разновидности (например так называемый модифицированный симплексный метод). К универсальным методам (в модифицированном варианте) относится и метод разрешающих множителей академика Л. В Канторовича. Этот метод являлся первым по времени разработки: он предложен в 1939 г., примерно за 10 лет до разработки симплексного метода и появления первых работ по линейному программированию за рубежом. Ко второй группе относятся специальные методы, применяемые для решения отдельных типов задач линейного программирования. Специальные методы, как правило, проще универсальных, но пригодны не для всех задач. Характерными для этой группы являются методы решения транспортной задачи, занимающей важное место в теории и приложениях линейного программирования. Для решения транспортной задачи предложен ряд методов. Переход от допустимого варианта к оптимальному используется в распределительном методе и его модификациях. Второй подход (приближение условно-оптимальными планами) лежит в основе метода разрешающих слагаемых А.Л. Лурье, метода дифференциальных рент А.Л. Брудно и так называемого венгерского метода. К особой группе методов линейного программирования относятся приближенные методы, отличающиеся от остальных тем, что они не гарантируют строго оптимального решения задачи, хотя, как правило, дают довольно хорошее приближение к оптимуму. Приближенные методы просты и хорошо приспособлены к ручным вычислениям. К этой группе относятся индексный, метод, метод аппроксимации Фогеля и др. 4.2. Симплексный метод Для уяснения общей идеи симплексного метода вернемся к изложенному выше примеру определения месячного выпуска продукции, обеспечивающего наибольшую величину прибыли. Пример, был решен с помощью графика (см. рис. 1), на котором сначала очерчена область допустимых решений (пятиугольник OAPFE), а затем с помощью прямой, соответствующей целевой функции данной задачи, установлено, что оптимальный план достигается в точке Р. При иных соотношениях между прибылью за столы и шкафы прямые KL и MN имели бы другой наклон. Наиболее удаленная от начала координат прямая могла бы при этом пройти не через точку Р, а например, через точку F или совпасть с отрезком FP либо отрезком АР. Если прямая, отвечающая целевой функции, проходит через одну вершину многоугольника, то задача имеет единственный оптимальный план, а если совпадает со стороной многоугольника, то задача имеет множество оптимальных планов. Из графика видно, что при любом наклоне прямых, характеризующих прибыль, "крайняя" прямая, указывающая оптимальное решение, обязательно пройдет либо через вершину, либо через сторону многоугольника, т.е. по меньшей мере одна из его вершин непременно отвечает оптимальному плану (хотя вначале и неизвестно, какая именно). Графический метод прост и нагляден, однако практически его применение ограничивается задачами, в которых всего две основные переменные величины. При трех переменных пришлось бы строить многогранник допустимых решений в пространственной системе координат. При четырех и более переменных графические построения вообще неосуществимы, однако абстрактно можно представить и десятимерное и любое многомерное пространство. Если условия задачи линейного программирования непротиворечивы, то область ее допустимых решений образует выпуклый многогранник в n-мерном пространстве. При этом оптимальное решение, если оно существует, обязательно достигается в некоторой вершине многогранника (возможно, и более чем в одной). Таким образом, чтобы найти решение задачи линейного программирования, достаточно перебрать лишь планы, соответствующие вершинам многогранника допустимых решений (в случае двух переменных – вершинам многоугольника). Такие планы называются опорными планами. Однако в сложных задачах и число вершин может оказаться чрезмерно большим, вследствие чего нахождение всех опорных планов потребует огромного объема вычислений. Симплексный метод позволяет осуществить упорядоченный перебор вершин многогранника. После определения одной из вершин этот метод помогает установить, является ли найденный план оптимальным, т.е. достигнут ли в этой вершине максимум целевой функции. Если план неоптимален, то производится переход к такой соседней вершине многогранника, которая обеспечивает большее (или в крайнем случае равное предыдущему) значение целевой функции. Повторное применение указанной процедуры приводит в конце концов к вершине, соответствующей оптимальному плану. Количество шагов (переходов) от исходной вершины до точки оптимума обычно представляет собой величину одного порядка с числом уравнений (ограничений) решаемой задачи. Предполагается, что задача может быть представлена в следующем виде. максимизировать при условиях Важной особенностью такой постановки задачи является то, что исходные уравнения в числе неизвестных величин содержат т. переменных величин (хk+1, xk+2, …, xk+m), коэффициенты при которых в данной системе уравнений образуют единичную матрицу порядка т (т.е. каждая из этих переменных входит лишь в одно уравнение и с коэффициентом +1). Такая система уравнений получается, например, в результате преобразования в уравнения исходных ограничений, имеющих форму неравенств вида "меньше или равно". Указанный характер ограничений является достаточным, но не необходимым условием наличия единичной матрицы порядка т в общей матрице коэффициентов задачи. В целевую функцию каждая переменная может входить с любым коэффициентом (положительным, отрицательным, нулевым), что и отражено в общей постановке задачи. В качестве исходного опорного плана задачи принимается следующий план: . При данном исходном плане матрица приведенной выше задачи может быть представлена так, как показано в табл. 4. Показатели первых m строк переносятся в таблицу непосредственно из исходных данных, показатели (m+1)-й строки вычисляются. Величина z0 –значение целевой функции при исходною варианте программы – определяется по формуле . Для всех j от 1 до k элементы (m+1)-й строки определяются следующим образом: . В частном случае, когда переменные хk+1, xk+2, …, xk+m входят в целевую функцию с нулевыми коэффициентами (как в приведенном выше примере), имеем Первым шагом в анализе исходного опорного плана является проверка его на оптимальность. План является оптимальным, если в (m+1)-й строке отсутствуют отрицательные числа, т.е. если соблюдается условие zj – cj  0 для всех j = 1, 2, ..., k. Если же среди элементов (m+1)-й строки есть хотя бы одно отрицательное число, а в соответствующем ему столбце имеется один положительный коэффициент, то это свидетельствует о возможности отыскания другого опорного плана, при котором значение целевой функции будет больше (точнее говоря – не меньше) величины z0 исходного плана. Вычислительный процесс при переходе от одного опорного плана к другому заключается в следующем. 1. Если в (m+1)-й строке имеется несколько отрицательных чисел, то прежде всего необходимо выбрать переменную, которая будет вводиться в базис. Наиболее простой и чаще всего применяемый способ состоит в выборе переменной, которой соответствует в (m+1)-й строке наибольшее по абсолютной величине отрицательное число. Если такое наибольшее число отвечает не одной, а нескольким переменным, то предпочтение отдается переменной, введение которой обеспечит больший прирост значения целевой функции. Например, если два изделия обеспечивают одинаковую прибыль, то следует предварительно рассчитать, какое количество тех и других изделий может быть введено в план, и выбрать то, которое войдет в большем количестве. В общем случае, когда все отрицательные числа в (m+1)-й строке различаются по величине, также целесообразнее вводить в план переменную, дающую наибольший прирост значения целевой функции в целом, а не на одну вводимую единицу. Хотя это требует некоторых дополнительных вычислений, но может уменьшить общее число шагов (итераций) перехода от исходного плана к оптимальному. Предположим, что в базис будет вводится переменная хj (см. табл. 4). Таблица 4. Матрица исходного опорного плана Строка Базис с План с1 с2 … сj … ck ck+1 ck+2 … ck+i … ck+m x1 x2 … xj … xk xk+1 xk+2 … xk+i … xk+m 1 xk+1 ck+1 b1 a11 a12 … a1j … a1k 1 … … 2 xk+2 ck+2 b2 a21 a22 … a2j … a2k 1 … … ………………………………………………………………………………………………………………… i xk+I ck+i bi ai1 ai2 … aij … aik … 1 … ………………………………………………………………………………………………………………… m xk+m ck+m bm am1 am2 … amj … amk … … 1 m+1 z0 z1–c1 z2–c2 … zj-cj … zk-ck … … 2. Необходимо установить, какая переменная будет выводиться из базиса. Для всех положительных коэффициентов j-го столбца определяются отношения Минимальное из этих отношений указывает строку выводимой из базиса переменной. Допустим, что это строка i; следовательно, переменная х будет замещать в базисе переменную хk+1. Направляющим элементом является элемент aij2. Заметим, что если минимальное отношение получилось одновременно для двух (или более) строк, то в принципе для исключения из базиса можно выбрать любую из них (обычно берут меньшую по индексу). 3. Производится переход к новой симплексной таблице, в которой прежде всего, заполняется строка вводимой переменной хj. Новые элементы этой строки определяются путем деления элементов 1-й строки исходного варианта на величину направляющего элемента: В столбце с в i-й строке нового варианта проставляется величина cj. 4. Пересчитывается столбец "План". В строке i этого столбца уже находится величина . Пересечет остальных элементов плана осуществляется по правилу трех чисел, из которых первое и второе находятся соответственно в столбцах "План" и хj исходного варианта, а третьим является частное . При расчете из первого числа вычитается произведение двух других чисел. Таким образом, элементы столбца "План" для нового варианта равны . 5. Производится пересчет матрицы коэффициентов. Формулы пересчета аналогичны рассмотренным в пункте 4. Так, элементы столбца х1 в новом плане выражаются через элементы исходной матрицы коэффициентов следующим образом: . По аналогичным формулам пересчитываются столбцы остальных переменных. Если в столбце какой-либо переменной коэффициент в i-й строке равен нулю, то этот столбец переписывается из предыдущего в новый план без изменений. Переменным, входящим в базис, всегда соответствуют в матрице коэффициентов единичные векторы-столбцы. 6. Определяются элементы (m+1)-й строки нового плана. Элементы (m+1)-й строки нового плана могут быть рассчитаны двумя способами: 1) либо непосредственно вычисляются разности z`1 – c1, z`2 – с2. и т. д., где z` представляет сумму произведений коэффициентов соответствующего столбца (1-го, 2-го и т. д.) и столбца с в новом варианте плана (так называемое скалярное произведение двух векторов-столбцов); 2) либо пересчет производится по общему правилу трех чисел, например, элемент (m+1)-й строки в столбце х1 нового плана равен в столбце х2 и т. д. В столбце "План" новое значение целевой функции z`0 также может быть получено либо как скалярное произведение вновь вычисленных векторов-столбцов "План" и с, либо по правилу трех чисел: . Последний способ требует обычно меньшего объема вычислений; кроме того, в этом случае сохраняется единый принцип пересчета всей матрицы коэффициентов. Вместе с тем наличие двух способов расчета облегчает контроль правильности вычислений. 7. По завершении расчета нового варианта плана в нем просматривается (m+1)-я строка. Если в этой строке имеются отрицательные числа, то в столбцах, к которым они относятся, просматриваются коэффициенты от 1-й до m-й строки. Если среди этих коэффициентов нет положительных, то в данной задаче максимум линейной формы не ограничен и можно построить планы со сколько угодно большим значением целевой функции. Если же в каком-либо столбце (т + 1)-й строки стоит отрицательное число, а среди коэффициентов первых т строк есть хотя бы один положительный, то можно перейти к другому опорному плану, связанному с увеличением значения целевой функции. Если после расчета очередного варианта окажется, что среди коэффициентов (m+1)-й строки отсутствуют отрицательные числа, то полученный план оптимален. При этом возможно, что некоторой переменной, не входящей в окончательный базис, соответствует в (m+1)-й строке не положительное число, а нуль. Тогда можно обычным образом ввести эту переменную в базис и получить новый план, который также будет оптимальным. При наличии двух или нескольких опорных оптимальных планов оптимальными будут и любые их выпуклые линейные комбинации (средние взвешенные этих планов при любых весах). При решении задач симплексным методом могут встретиться случаи так называемого "вырождения". При m ограничениях невырожденный план всегда содержит m положительных переменных, а остальные n–m переменных задачи в базис не входят и равняются нулю. Однако возможно равенство нулю и одной или нескольких переменных из входящих в базис (т.е. наличие одного или нескольких нулей в столбце "План" симплексной таблицы). Такой план и называется вырожденным. При вырожденном плане наличие отрицательных чисел в (m+1)-й строке еще не означает, что следующий вариант обеспечит увеличение значения целевой функции. Оно может остаться и неизменным, причем на протяжении не только одного, но и нескольких последовательных шагов (итераций). Поскольку линейная форма не возрастает, после ряда итераций может в точности повториться план, уже полученный раньше. Так происходит зацикливание, которое препятствует дальнейшим расчетам и может быть преодолено лишь с помощью специальных приемов. Если вырождение встречается довольно часто, то цикл, наоборот, крайне редко; исследовался он в основном на искусственно сконструированных примерах. Поэтому специально разработанные приемы преодоления вырождения практически почти не применяются. Как правило, вырождение не является препятствием для обычных расчетов и получения в конечном счете оптимального плана. 4.3. Двойственная задача Вернемся к общей характеристике задач линейного программирования и сформулируем экономическую задачу наилучшего распределения ограниченных ресурсов для достижения максимального выпуска продукции. Предположим, что в производстве используется от различных видов ресурсов (ресурсы труда, сырья и материалов, оборудования и т. д.), объем которых ограничен величинами b1, b2, …, bm. Может производиться п видов продукции, величина выпуска которых характеризуется переменными х1, х2, ..., xn. Известны нормы затрат каждого ресурса на единицу каждого вида продукции, образующие следующую матрицу: В задаче известна также стоимостная оценка (цена) единицы продукции каждого вида – c1, c2, ..., cn. Задача сводится к следующему: найти такие значения переменных величин х1, х2, ..., xn (т.е. уровни выпуска продукции), при которых расход ресурсов не превышает заданного их количества, а стоимость всей продукции достигает максимума. В математической форме задача записывается следующим образом: максимизировать при условиях Оказывается, что на базе тех же исходных данных может быть поставлена еще одна задача, в которой переменными величинами, подлежащими определению, являются оценки y1, у2, ..., ym, приписываемые каждому виду ресурсов. Они должны быть такими, чтобы общая оценка всего имеющегося количества ресурсов была минимальной, но при условии, что суммарная оценка ресурсов, расходуемых на единицу любого вида продукции, будет не меньше, чем цена за эту единицу. Математически задача сводится к следующему: минимизировать при условиях Сопоставим обе задачи. Первая из них – задача на максимум, вторая – задача на минимум; в соответствии с этим изменился и характер ограничений (знак неравенств). В первой задаче n неизвестных и m ограничений, во второй – m неизвестных и n ограничений. Коэффициенты в целевых функциях (в максимизируемом и минимизируемом выражениях) и величины в правых частях неравенств при переходе от одной задачи к другой меняются местами. Матрица коэффициентов для второй задачи имеет следующий вид: Она может быть получена из матрицы коэффициентов первой задачи путем замены строк столбцами. Такая матрица называется транспонированной. Как видим, обе задачи тесно между собой связаны. Они образуют пару задач, называемую в линейном программировании двойственной парой. Первую из них называют обычно прямой (или исходной) задачей, а вторую –двойственной задачей (с чисто математической точки зрения за исходную может быть принята любая из задач двойственной пары). С экономической стороны решение прямой задачи дает оптимальный план выпуска продукции, а решение двойственной задачи – оптимальную систему условных оценок применяемых ресурсов. Рассмотренную пару задач называют симметричными двойственными задачами. В более общем случае в качестве ограничений исходной задачи могут выступать не только неравенства вида "меньше или равно", но также уравнения и неравенства вида "больше или равно". Как было показано в § 2 этой главы, задача линейного программирования всегда может быть приведена к общей форме: максимизировать при условиях Этой исходной задаче соответствует следующая двойственная: минимизировать при условиях Две приведенные задачи называются несимметричными двойственными задачами. Это наиболее общий случай, к которому могут быть сведены и симметричные задачи. Для самой двойственной задачи единственное отличие заключается в том, что в симметричном случае ее переменные неотрицательны, а в несимметричном – могут иметь любой знак. Переменные исходной задачи всегда неотрицательны. Дальнейший анализ ведется в основном на примере симметричных двойственных задач. Если сосредоточить внимание на экономическом содержании и размерности постоянных и переменных величин рассматриваемых задач, то для прямой (исходной) задачи можно записать следующие соотношения: ограничивающие условия ; максимизируемая функция Соотношения для двойственной задачи:тограничивающие условия минимизируемая функция В линейном программировании доказывается следующая основная теорема двойственности: если одна из задач двойственной пары имеет оптимальное решение, то другая также имеет оптимальный план, причем максимум целевой функции исходной задачи и минимум двойственной численно равны. Оптимальные планы двух задач связаны не только равенством значений целевых функций. В них соблюдаются и другие важные соотношения. Если в оптимальном плане исходной задачи какое-либо i-е ограничение выполняется как строгое неравенство, то соответствующая i-я переменная в оптимальном плане двойственной задачи равна нулю. По экономическому содержанию это означает, что положительную двойственную оценку могут иметь лишь ресурсы, полностью используемые в оптимальном плане; оценки неполностью используемых ресурсов всегда равны нулю (именно для неполностью используемых ресурсов ограничения исходной задачи выполняются в оптимальном плане как строгие неравенства). С другой стороны, если какая-то j-я переменная исходной задачи входит в оптимальный план с положительным значением, то соответствующее ограничение в оптимальном плане двойственной задачи будет выполняться как строгое неравенство. Если же 1-я переменная исходной задачи не входит в оптимальный план, то в оптимальном плане двойственной задачи соответствующее j-е ограничение будет, как правило, обращаться в строгое неравенство. Экономическое содержание этой математической зависимости следующее: если данный вид продукции вошел в оптимальный план, то двойственная оценка ресурсов, затрачиваемых на единицу этой продукции, в точности равна ее цене и производство продукции по оценкам оправдано. Если же выпускать данную продукцию нерационально и она не вошла в оптимальный план, то и по оценкам ее производство будет убыточным, т.е. оценка затрачиваемых на нее ресурсов окажется выше цены этой продукции (и, как крайний случай, может быть равна ей при наличии в задаче множества оптимальных планов). Каждая из задач двойственной пары формально является самостоятельной задачей линейного программирования и может решаться независимо от другой. Характерно, что при использовании симплексного метода (как и некоторых других, например, метода разрешающих множителей) решение одной из задач двойственной пары автоматически приводит к решению другой задачи. Двойственные оценки обладают тем свойством, что гарантируют рентабельность оптимального плана (равенство общей оценки продукции и ресурсов) и обусловливают "убыточность" всякого другого плана, отличного от оптимального. Двойственные оценки самым тесным образом связаны с оптимальным планом. Объем имеющихся ресурсов, нормы их затрат на единицу продукции, установленные соотношения в ассортименте продукции, коэффициенты целевой функции (прибыль, стоимость продукции) – все эти исходные показатели конкретной задачи, определяющие единственный (как правило) оптимальный вариант плана, определяют и единственную в данных условиях систему оценок. Если с течением времени исходные условия претерпевают изменения, то это может означать, что иными станут и оптимальный план, и соответствующая ему система оценок. Система оценок является конкретной и гибкой, обусловлена всей совокупностью исходных условий задачи и реагирует на их изменения. Однако конкретность и гибкость оценок не означают, что при всяких, даже незначительных колебаниях исходных данных систему оценок нужно пересматривать заново. Если бы в приводившемся примере изменился фонд времени по одной или нескольким группам оборудования, то оптимальный план выпуска продукции стал бы иным, но оценки могли остаться на прежнем уровне, если изменения фонда времени были не слишком большими. Если же меняются нормы затрат ресурсов на единицу продукции, прибыль (или цена) за единицу, то оценки, как правило, принимают другие значения. Таким образом, оценки обладают определенной устойчивостью по отношению к изменениям одних исходных данных (например, объем располагаемых ресурсов), но чувствительны к изменениям других данных. Устойчивость оценок является очень важным свойством. Если бы систему оценок приходилось пересматривать при каждом отклонении того или иного показателя, то они во многом потеряли бы свое практическое значение. Многообразие свойств двойственных оценок говорит о том, что они должны рассматриваться как неотъемлемый и важный элемент оптимального плана. Двойственные опенки могут служить тонким инструментом анализа и принятия правильных решений в условиях постоянно изменяющегося производства. Некоторые аналитические возможности двойственных оценок прямо вытекают из их свойств (анализ сравнительной дефицитности ресурсов, определение расчетных норм замены, сопоставление условных затрат и результатов производства в оптимальном плане). Однако применение оценок не ограничивается только анализом оптимального плана, оно помогает также оценить целесообразность и эффективность тех или иных изменений в этом плане (если эти изменения не являются слишком резкими, т.е. не приводят к необходимости пересматривать все оптимальное решение в целом).