Основы математического моделирования экономических процессов и систем

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЭКОНОМИКЕ Конспект лекций Введение Целью освоения дисциплины является изучение основ математического моделирования экономических процессов и систем, а также решения экономических задач, формализованных в виде математических моделей. Задачи дисциплины: • овладение основами построения математических моделей экономических процессов и систем; • овладение основами представления экономической задачи в виде задачи принятия решения и математическими инструментами поиска оптимального решения; • овладение математическими и инструментальными методами решения экономических задач, формализованных в виде математических моделей; • формирование умений и навыков количественного обоснования принимаемых экономических решений по организации эффективного управления хозяйственной деятельностью предприятий. В процессе освоения дисциплины формируются следующие компетенции: • владение культурой мышления, способностью к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения (ОК-1); • осознание социальной значимости своей будущей профессии, обладание высокой мотивацией к выполнению профессиональной деятельности (ОК-11); • способность осуществлять сбор, анализ и обработку данных, необходимых для решения поставленных экономических задач (ПК-4); • способность выбрать инструментальные средства для обработки экономических данных в соответствии с поставленной задачей, проанализировать результаты расчетов и обосновать полученные выводы (ПК-5); • способность на основе описания экономических процессов и явлений строить стандартные теоретические и эконометрические модели, анализировать и содержательно интерпретировать полученные результаты (ПК-6); • способность использовать для решения аналитических и исследовательских задач современные технические средства и информационные технологии (ПК-10); • способность критически оценить предлагаемые варианты управленческих решений и разработать и обосновать предложения по их совершенствованию с учетом критериев социально-экономической эффективности, рисков и возможных социально-экономических последствий (ПК-13). 3 Понятие моделирования В узком смысле моделирование − это метод научного исследования (познания) окружающего нас мира, заключающийся в подмене реальных объектов или явлений их заведомо упрощенными образами (моделями) с целью изучения этих образов и последующего переноса полученных результатов и выводов на объекты и явления реального мира. В широком смысле моделирование представляет собой научную дисциплину, в рамках которой изучаются методы построения и использования моделей для познания реального мира. Связь (отношение) между объектом реального мира и его моделью можно проиллюстрировать графически с помощью укрупненного цикла моделирования (рис. 1). Исследование модели Выводы об объекте Модель объекта Интерпретация результатов модели Разработка результатов Применение Реальный объект Выводы о модели Рис. 1. Укрупненный цикл моделирования Философскую основу моделирования составляют теория отражения и теория познания, формально-методическую основу − теория подобия, теория эксперимента, математическая статистика, математическая логика и научные дисциплины, изучающие те предметные области, которые подлежат исследованию методами моделирования. Теория подобия, в частности, утверждает, что абсолютное подобие может иметь место лишь при замене одного объекта другим, точно таким же. При моделировании абсолютного подобия нет, стремятся 4 только к тому, чтобы модель достаточно хорошо отображала исследуемую сторону функционирования объекта [1, 2]. Классификация видов моделирования Классификацию видов моделирования и, соответственно, моделей (от лат. modulus − мера, образец) можно проводить по разным признакам: по сфере приложения (области применения), по характеру моделируемых объектов, по степени подробности моделей и т.д. Для исследования экономических систем применяются различные средства моделирования, поэтому модели могут классифицироваться на основании используемых средств моделирования [3]. В этом случае различают две большие группы моделей, относящихся соответственно к материальному и идеальному моделированию (рис. 2). Моделирование Материальное Идеальное Неформализованное Образное Знаковое Аналоговое Физическое Пространственное Формализованное Рис. 2. Классификация видов моделирования Материальное моделирование предполагает наличие связи, имеющей материальный характер, между моделью и исследуемым объектом1. В материальном моделировании можно условно выделить три основные группы методов: пространственное, физическое и аналоговое моделирование. 1 Материальное моделирование называют также натурным моделированием, а соответствующие ему модели − натурными (от лат. natura − природа). 5 В пространственном моделировании используются модели, предназначенные для воспроизведения или отображения пространственных (геометрических) свойств изучаемых объектов. В качестве примеров такой группы моделей можно назвать макеты разнообразных типов (зданий, устройств и т.д.). В физическом моделировании используются модели, предназначенные для воспроизведения динамики процессов, происходящих в изучаемых объектах, причем общность процессов, происходящих в объекте исследования и модели, основывается на сходстве их физической природы. Этот метод моделирования особенно широко распространен в технике, где физическое моделирование используется для проектирования технических систем различного типа. Наиболее известным примером физического моделирования является исследование летательных аппаратов на основе экспериментов в аэродинамической трубе. В аналоговом моделировании используются материальные модели, физическая природа которых отличается от природы исследуемых объектов, но, вместе с тем, они описываются сходными математическими соотношениями, т.е. связь между моделью и объектом основывается на аналогии их математического описания. В качестве примера аналогового моделирования можно привести изучение механических колебаний груза, подвешенного на пружине, с помощью электрической схемы, описываемой аналогичным дифференциальным уравнением, но более удобной для проведения экспериментов (рис. 3). Необходимо отметить, что во всех случаях материального моделирования модель − это материальное отражение изучаемого (исходного) объекта. Исследование состоит в материальном воздействии на нее, т.е. в эксперименте с моделью. Таким образом, материальное моделирование по своей природе является экспериментальным методом. Идеальное моделирование принципиально отличается от материального, поскольку оно основывается не на материальной аналогии между моделью и изучаемым объектом, а на идеальной, т.е. мыслимой связи между ними. Методы идеального моделирования можно условно разделить на две подгруппы: формализованное и неформализованное (интуитивное) моделирование. В формализованном моделировании моделями служат системы знаков или образов, вместе с которыми задаются правила их преобразования и интерпретации. В знаковом моделировании в качестве моделей используются системы знаков, которые могут существенно отличаться друг от друга (например, это могут быть чертежи, схемы, формулы и т.д.). Важнейшим видом знакового моделирования является математическое моделирование, при использовании 6 которого модель записывается в виде совокупности формул, преобразуемых на основе правил логики и математики. В образном моделировании при построении модели используются такие наглядные элементы, как упругие шары, потоки жидкости, траектории движения тел. Анализ образных моделей осуществляется мысленно и может быть отнесен к формализованному моделированию в том случае, когда правила взаимодействия образов, используемых в модели, четко фиксированы. Например, в идеальном газе столкновение двух молекул рассматривается как упругое соударение двух шаров; при этом результат соударения мыслится всеми одинаково. Модели такого типа широко используются при проведении исследований, которые принято называть мысленным экспериментом. Неформализованное моделирование − это анализ проблем разнообразного типа, когда модель не формулируется, а вместо нее используется некоторое, не зафиксированное точно, мысленное ощущение реальности, служащее основой для рассуждения и принятия решений. Таким образом, всякое рассуждение, не использующее формализованные модели, можно считать неформализованным моделированием, поскольку в этом случае исследователь имеет некоторый образ объекта исследования, который можно интерпретировать как неформали-зованную модель реальности. Принятие решения, основанное только на опыте (своем или чужом) и на интуиции, может приводить к ошибкам или неэффективным результатам. Предпочтительность использования неформализованных методов в ряде случаев объясняется наличием важных факторов, понятных лицу, принимающему решение (ЛПР), но трудно формализуемых. Кроме того, этот вид моделирования является наиболее быстрым и дешевым. По этой причине в большинстве обыденных ситуаций неформализованное моделирование по-прежнему является основным средством принятия решения. 7 Использование различных видов моделирования в экономических исследованиях Пространственное моделирование, как первый вид материального моделирования (см. выше), не получило широкого распространения при исследовании экономических систем, так как геометрическая форма различных экономических объектов, как правило, не является их основной характеристикой. Второй вид материального моделирования − физическое моделирование, основанное на общности материальной природы модели и исследуемого объекта, использовалось при изучении экономических процессов. При этом технологические процессы должны моделироваться аналогичными технологическими процессами, а поведение людей в изучаемом экономическом процессе − также действиями людей. Например, для изучения функционирования какого-либо крупного предприятия можно было бы использовать в качестве модели небольшое предприятие, на котором проведение исследования обойдется дешевле. Другой пример: для анализа деятельности промышленного объединения, в состав которого входят несколько предприятий с тесной кооперацией, можно взять одно из них, а затем полученные результаты распространить на другие предприятия. Ряд подобных исследований, получивших название «экономических экспериментов», был осуществлен в бывшем СССР во второй половине 1960-х гг. с целью анализа конкретных форм стимулирования производства и их воздействия на повышение эффективности деятельности предприятий [3]. Третий вид материального моделирования − аналоговое моделирование − привлек внимание исследователей экономических систем в 1940-50 гг. в связи с возникновением и быстрым развитием новой науки − кибернетики, постулирующей аналогичность процессов управления в системах различной природы. В этот период предпринимались попытки создания электрических схем, в которых динамика физических величин напоминала бы поведение экономических величин. Анализируя структуру этих схем и связь между физическими величинами, исследователи надеялись выявить закономерности экономических процессов. Однако вскоре стала очевидна бесплодность подобного подхода и дальнейшие попытки моделирования экономических систем с помощью электрических схем были прекращены. Тем не менее, кибернетический подход к исследованию и ряд соответствующих понятий, таких, например, как «обратная связь», утвердились в экономике и широко используются. 8 Таким образом, можно констатировать, что материальное моделирование может применяться для анализа экономических явлений в крайне ограниченном объеме. В отличие от материального, идеальное моделирование экономических процессов используется широко и постоянно. В течение длительного времени при исследовании экономических объектов и явлений использовалось, главным образом, неформализованное моделирование. Однако, как отмечалось выше, этот способ не гарантирует выработки оптимальных экономических решений, поэтому в дополнение к нему необходимо использовать формализованные виды моделирования. Появление формализованных образных моделей, а затем и математических моделей создало предпосылки для точного описания экономических явлений и их строго анализа с помощью методов математики и логики. Понятие математической модели Математическое (логико-математическое) моделирование заключается в построении и анализе математической модели средствами математики и логики. Математическая модель − это образ исследуемого объекта, создаваемый исследователем (субъектом) с помощью определенной формальной (математической) системы с целью изучения (оценки) определенных свойств (или функционирования) данного объекта. 9 При построении математической модели можно выделить следующие основные этапы [4]: 1. Определение цели решения задачи, т.е. чего хотят добиться, решая данную задачу. 2. Определение параметров модели, т.е. заранее известных фиксированных факторов, на значение которых исследователь не влияет. 3. Формирование управляющих переменных, значения которых являются решением задачи и при изменении которых можно достичь поставленной цели. 4. Определение области допустимых решений, т.е. ограничений, которым должны удовлетворять управляющие переменные. 5. Выявление неизвестных факторов, т.е. величин, которые могут изменяться случайным или неопределенным образом. 6. Выражение цели через управляющие переменные, параметры и неизвестные факторы, т.е. формирование целевой функции, называемой также критерием эффективности или критерием оптимальности задачи. С учетом перечисленных выше этапов построения математической модели введем следующие условные обозначения: α − параметры модели; x − управляющие переменные или решения; X − область допустимых решений (ОДР); ξ − случайные или неопределенные факторы; Z − целевая функция, или критерий эффективности (критерий оптимальности), которая записывается как Z = Z ( x,α , ξ ) . В соответствии с введенными обозначениями математическая модель задачи имеет следующий вид: min  Z = Z ( x, α , ξ ) → extr , где extr =  . x∈ X max Задача предполагает нахождение такого оптимального решения x ∈ X , * чтобы при данных фиксированных параметрах α и с учетом неизвестных факторов ξ был получен экстремум целевой функции Z , т.е. Z * = Z ( x* , α , ξ ) = extr {Z ( x, α , ξ )}. x∈ X Таким образом, оптимальное решение − это решение, предпочтительное (наилучшее) перед другими по определенному критерию эффективности (одному или нескольким). 10 Принципы построения математической модели При построении математической модели необходимо руководствоваться следующими основными принципами [4]: 1. Необходимо соизмерять точность и подробность модели, во-первых, с точностью тех исходных данных, которыми располагает исследователь, и, во-вторых, с теми результатами, которые требуется получить. 2. Математическая модель должна отражать существенные черты исследуемого объекта или явления и при этом не должна его сильно упрощать. 3. Математическая модель не может быть полностью адекватна объекту или явлению, поэтому для его исследования лучше использовать несколько моделей, для построения которых применяют разные математические методы. Если при этом получаются сходные результаты, то исследование заканчивается. Если же результаты сильно различаются, то следует пересмотреть постановку задачи. 4. Любая сложная система всегда подвергается малым внешним и внутренним воздействиям (возмущениям), следовательно, математическая модель должна быть устойчивой, т.е. сохранять свои свойства и структуру при этих воздействиях. Особенности математического моделирования экономических процессов Как отмечалось выше, для экономических систем характерно наличие человеческих, социально-психологических факторов, часто играющих важную и решающую роль в экономических явлениях. Влияние подобных факторов на протекание экономических процессов не только препятствует проведению экспериментальных исследований в экономике, но и создает значительные трудности при выполнении математического моделирования. В качестве примера можно рассмотреть одну внешне простую и весьма ограниченную по масштабу задачу − математическое описание деятельности небольшого производственного участка, принадлежащего крупному заводу [3]. Предположим, этот участок выпускает различные детали мелкими партиями в соответствии с потребностями предприятия. Мастер, руководящий работой участка, ежедневно получает план выпуска деталей и распределяет сменное задание между рабочими таким образом, чтобы оно было выполнено. При рас- 11 пределении сменного задания между рабочими мастер должен учитывать как их квалификацию, так и технические характеристики станков, на которых они работают. Попытаемся построить математическую модель работы данного производственного участка. В качестве переменных в такой модели естественно взять число деталей каждого из типов, которые должен выпустить каждый из рабочих. Также в модели должны быть выделены операции, необходимые для изготовления каждой детали, указана производительность рабочих на каждой из операций, описана технологическая последовательность операций и т.д. Эта информация позволяет построить ограничения, которым должны удовлетворять сменные задания. Полученные ограничения могут отражать, например, необходимость выполнения каждым рабочим полученного им задания в течение смены и т.д. Если считать, что производительность рабочего в каждой из операций зафиксирована заранее, то сформулированная модель будет описывать технологические ограничения, которым должна удовлетворять работа производственного участка. С помощью этой модели для любого варианта распределения заданий, удовлетворяющего сформулированным технологическим ограничениям, можно подсчитать затраты времени на выполнение плана выпуска деталей, а также другие показатели работы участка за смену. Однако если нас заинтересует вопрос о том, какие результаты будут получены на участке в действительности, ответить на него с помощью сформулированной модели окажется невозможно: обычно существует большое число вариантов распределения заданий, удовлетворяющих заданным технологическим ограничениям. Для ответа на поставленный вопрос необходимо построить модель, описывающую принятие решения мастером, т.е. модель, учитывающую его опыт, интересы и цели, связанные с руководством производственным участком. Можно было бы, конечно, выбрать такой вариант распределения заданий, который привел бы к наиболее эффективной загрузке оборудования или к наискорейшему выполнению задания. Однако на практике такой вариант распределения заданий может не удовлетворять мастера. Дело в том, что с точки зрения оплаты все операции делятся на «выгодные» и «невыгодные». Поэтому мастер обязан следить, чтобы все рабочие получили в итоге такую зарплату, которую и сам рабочий, и мастер считали бы «нормальной». Кроме того, неизвестно, желает ли мастер получить дополнительное задание после того, как будет выполнено основное. Возможно, мастер опасается, что в случае слишком быстрого выполнения основного задания будут снижены расценки на выполняемые операции или повышен план выпуска деталей. Ответ на эти вопросы за- 12 висит уже не от технологических факторов производства, а от факторов социально-психологических и организационных, в частности от системы стимулирования эффективности производства. Приведенный выше пример отражает проблемы, с которыми приходится постоянно сталкиваться исследователю при моделировании экономических процессов. Он показывает, что задача моделирования социально-экономических явлений, в том числе и процессов принятия экономических управленческих решений, чрезвычайно сложна. Для построения адекватных математических моделей явлений этого типа необходимо правильно описывать цели групп людей и отдельных индивидуумов, а также факторы, влияющие на эти цели, уметь анализировать конфликты, возникающие в человеческом обществе, и пути их разрешения. В настоящее время математика еще не обеспечила в полной мере адекватных средств для описания влияния различных социально-психологических факторов на принятие экономических решений (хотя попытки успешного создания соответствующего математического аппарата имеются: теория игр, теория конфликтов и т.п.). Чтобы обойти это препятствие на пути практического использования математического моделирования экономических процессов, применяют следующий методический прием: выделяют два уровня − производственно-технологический и социально-экономический. Далее можно использовать хорошо разработанные принципы моделирования неживой природы (например, законы сохранения) для построения моделей производственнотехнологического уровня. Незамкнутость моделей этого уровня, т.е. наличие в них внешних (управляющих) воздействий в течение производственных процессов, не является препятствием на пути исследования в том случае, когда рассматривается задача выбора наиболее рационального варианта производственного процесса. Поэтому умение строить и анализировать математические модели производственно-технологического уровня экономических систем имеет огромное прикладное значение. Понятие компьютерного моделирования Компьютерное моделирование − метод решения задачи анализа или синтеза сложной системы на основе использования ее компьютерной модели. В настоящее время под компьютерной моделью чаще всего понимают [5]: структурно-функциональную модель, представляющую собой условный образ объекта, описанный с помощью взаимосвязанных компьютерных 13 таблиц, блок-схем, диаграмм, графиков, рисунков, анимационных фрагментов, гипертекстов и т.д. и отображающий структуру и взаимосвязи между элементами объекта; имитационную модель, представляющую собой отдельную программу или совокупность программ, позволяющих с помощью последовательности вычислений и графического отображения их результатов, воспроизводить (имитировать) процессы функционирования объекта при условии воздействия на объект различных, как правило, случайных факторов. В основе современных методов структурно-функционального анализа и моделирования лежат результаты, полученные профессором Дугласом Россом (Массачусетский технологический институт − МТИ, США) более 40 лет назад в ходе работы над алгоритмическим языком АРТ, ориентированным на модульное программирование. Развитие идеи Росса, заключающейся в описании сложных объектов как иерархических, модульных систем с помощью относительно небольшого набора типовых элементов, привело к появлению методологии структурного анализа и проектирования, ныне известной как SADT − Structured Analyses and Design Technique [6]. В настоящее время существует ряд программных продуктов, реализующих основные принципы методологии SADT, которые используются для решения различных проблем, таких, например, как совершенствование управления финансами и материально-техническим снабжением крупных фирм, разработка программного обеспечения АСУ телефонными сетями, долгосрочное и стратегическое планирование фирм, проектирование вычислительных систем и сетей и др. Имитационное моделирование как вид компьютерного моделирования экономики, применяется с начала 1960-х гг. (см. ниже пример динамической модели Форрестера). Чуть позже были созданы первые инструментальные средства имитационного моделирования, называемые языками моделирования, число которых к концу 1970-х гг. насчитывало уже более сотни. В настоящее время ситуация стабилизировалась, поскольку широко используются лишь несколько известных языков, проверенных практикой (GPSS, SIMSCRIPT, SLAM-II и некоторые другие). Вообще имитация (от лат. imitation − подражание) означает воспроизведение определенным образом явлений, событий, действий, объектов и т.п. В известном смысле термин «имитация» является синонимом понятия «модель», которая определяется как некоторый материальный или нематериальный (идеальный) образ (см. выше). По сути, словосочетание «имитационная модель» не- 14 корректно, однако, будучи введенным в середине XX века, оно широко используется и сегодня [7]. Суть имитационного моделирования заключается в том, чтобы как можно точнее, полнее, нагляднее отобразить моделируемый объект и динамику его функционирования. По возможности нужно как можно меньше деформировать структуру объекта, т.е. желательно, чтобы в модели все части объекта имели реальное отображение, а потоки информации о них представляли реальные потоки заказов, ресурсов, людей, идей и т.п. Данное пожелание выполняется в наибольшей степени, если основу построения имитационной модели составляют системный анализ моделируемого объекта и системный синтез его модели. Системный анализ и синтез лежат в основе так называемого системного подхода, при реализации которого необходимо выполнить следующие действия [7]: − изучить и выделить все главные и второстепенные черты и свойства объекта моделирования; − расположить их в определенной последовательности друг за другом; − указать взаимосвязи между ними, характеристики этих взаимосвязей; − четко поставить цель исследования или моделирования объекта, построив для этого «дерево» целей; − определить критерии (показатели) достижения цели; − выбрать основные черты и свойства, которые следует учитывать при исследовании или моделировании в соответствии с поставленной целью; − разработать методы и средства достижения цели; − определить необходимые для этого ресурсы; − построить план достижения целей исследования или моделирования объекта; − осуществить исследование или моделирование. Процедура построения имитационных моделей с использованием системного подхода предполагает выполнение следующих этапов [7]: 1. Содержательное описание объекта моделирования в виде системы, постановка задачи и формулирование целей. 2. Формализация задачи, построение структуры модели, определение целевых функций и критериев достижения целей. 3. Выбор методов моделирования для конкретных элементов моделируемой системы. 15 4. Построение модели, разработка моделирующего алгоритма и апробация на контрольном примере, необходимая корректировка модели. 5. Моделирование системы, включая планирование имитационных реализаций, имитирование входных и управляющих сигналов, помех, пробных и несанкционированных воздействий на те или иные атрибуты системы, вычисление различных статистических характеристик. 6. Анализ результатов моделирования, выбор наиболее эффективной структуры и стратегии поведения моделируемой системы с учетом наиболее вероятных входных или возмущающих воздействий. 7. Подготовка отчета об имитационном моделировании в терминах данного объекта или процесса и планирование внедрения результатов моделирования в практику. В качестве примера одного из первых применений имитационного моделирования (совместно с расширенным кибернетическим подходом) для анализа экономических явлений рассмотрим динамическую модель, предложенную профессором МТИ Джеем Форрестером [8]. Согласно этой модели, промышленное предприятие можно представить структурной схемой с рядом уровней (резервуаров), связанных шестью потоками. Пять из них − это управляемые потоки: материалы, заказы, денежные средства, оборудование и рабочая сила. Шестой поток − информационный, связывающий пять других потоков и выполняющий функцию обратной связи. Структурная схема потоков, моделирующая деятельность предприятия, дополняется системой достаточно простых алгебраических уравнений, которые позволяют представить в количественном выражении динамику, т.е. изменения, происходящие в процессе протекания этих потоков. Подобная математическая модель предприятия позволяет оценить, каким образом система будет реагировать на ввод тех или иных данных (возмущающих воздействий) при разных параметрах запаздываний и усилений. Методика построения и анализа динамической модели предприятия, по Форрестеру, включает следующие шесть этапов: 1. Определяется конкретный производственно-хозяйственный вопрос, который подлежит анализу методом динамического анализа. 2. Формулируются (в вербальном выражении) основные связи или причинно-следственные зависимости, характеризующие структуру изучаемой системы, и представляются в виде графической схемы потоков. 16 3. Выполняется построение математической модели, причем каждая часть этой модели создается на основе графической схемы, выражающей содержание предыдущего этапа. 4. Проектируется поведение моделируемой системы или ее изменений во времени. 5. Выполняется имитация динамики системы на ЭВМ. Результаты вычислений, полученные при прогоне программы, сравниваются с имеющимися данными об аналогичных реальных процессах. 6. Выполняется корректировка модели путем включения в нее пересмотренных параметров или мероприятий с последующим моделированием на ЭВМ для определения их воздействия на конечные результаты. Таким образом, методика динамического моделирования, предложенная Форрестером, позволяет имитировать деятельность предприятия на ЭВМ с привлечением математической модели, состоящей из множества последовательно решаемых уравнений. Наличие у имитационной модели контуров обратной связи позволяет отслеживать периодические колебания уровня запасов материалов, объемов выработки и численности рабочей силы при случайных изменениях спроса на продукцию предприятия. 17 Глава 1. Экономико-математическое моделирование Экономико-математическое моделирование заключается в использовании методов и средств математического моделирования для исследования экономических объектов и явлений. Экономико-математическая модель − это математическое описание исследуемого экономического объекта или явления (процесса). Экономико-математическое моделирование можно разделить на следующие три этапа [9]: I этап − составление экономической модели: определяется цель исследования, выполняется постановка задачи, проводится качественное описание объекта или процесса в виде экономической модели. II этап − построение экономико-математической модели и ее машинная реализация: на основе экономической модели формируется математическая модель изучаемого объекта или процесса (основные этапы построения математической модели см. выше). Затем осуществляется выбор (или разработка) методов исследования, выполняется программирование модели на ЭВМ, подготавливаются исходные данные. Далее проверяется пригодность машинной модели на основании правильности получаемых с ее помощью результатов и оценка их устойчивости. III этап − анализ экономико-математической модели и использование результатов решения: анализ математической модели, реализованной в виде программ для ЭВМ, проведение машинных расчетов, обработка и анализ полученных результатов. Исследование операций В основе экономико-математического моделирования лежит комплексная научная дисциплина, называемая исследованием операций. В рамках исследования операций занимаются разработкой и практическим применением методов наиболее эффективного управления различными организационными системами. Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все 18 параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Следовательно, цель исследования операций состоит в количественном обосновании принимаемых решений по организации управления [9]. Применение методов исследования операций при решении конкретной задачи управления предполагает: − построение экономических и математических моделей для задач принятия решений в сложных ситуациях или в условиях неопределенности; − изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия. Основные понятия исследования операций Приведем определения основных понятий, используемых при описании моделей и методов исследования операций [9]. Операция − любое управляемое действие (мероприятие), направленное на достижение цели. Результат операции зависит от способа ее организации и проведения, иначе − от выбора некоторых изменяемых параметров. Всякий определенный выбор изменяемых параметров называется решением. Решения, которые по тем или иным соображениям предпочтительнее других, считаются оптимальными. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений. Следует обратить внимание на то, что само принятие решений выходит за рамки исследования операций и относится к компетенции ЛПР, которое может учитывать и другие соображения, отличные от математически обоснованных (см., например, «Особенности математического моделирования экономических процессов» во введении). Модель и эффективность операции Для применения количественных методов исследования требуется построить математическую модель операции. При построении модели операция, 19 как правило, упрощается, т.е. создается схема операции, которая описывается с помощью того или иного математического аппарата. Модель операции − это достаточно точное описание операции с помощью математического аппарата (различного рода функций, уравнений, систем уравнений и неравенств и т.п.). Составление модели операции требует понимания сущности описываемого явления и знания математического аппарата. Эффективность операции − степень ее приспособленности к выполнению задачи, которая количественно выражается в виде критерия эффективности, т.е. целевой функции. Например, в задаче об использовании ресурсов критерий эффективности − прибыль от реализации произведенной продукции, которую нужно максимизировать; в транспортной задаче − суммарные затраты на перевозку грузов от поставщиков к потребителям, которые нужно минимизировать. Выбор критерия эффективности определяет практическую ценность исследования операций. Общая постановка задачи исследования операций Продолжая классификацию видов моделирования и моделей соответственно (см. выше рис. 2), математические модели можно разделить на однокритериальные и многокритериальные, которые, в свою очередь, делятся на [4, 10]: − детерминированные; − стохастические (вероятностные); − неопределенные. В однокритериальных моделях используется единственный критерий эффективности, а в многокритериальных − два и более. В детерминированных моделях случайные или неизвестные факторы не учитываются. В стохастических моделях неизвестные факторы учитываются и представляют собой случайные величины, для которых известны функции распределения и различные статистические характеристики, такие как математическое ожидание, дисперсия, среднеквадратичное отклонение и т.п. В неопределенных моделях или, точнее, в моделях с элементами неопределенности используются случайные факторы, но статистических данных по ним нет, поскольку отсутствуют условия для их сбора. 20 При построении детерминированных моделей задач исследования операций случайные или неопределенные факторы не учитываются. Все остальные факторы, входящие в описание операции, можно разделить на следующие две группы [9]: − постоянные факторы, или параметры модели (условия проведения операции), на которые мы влиять не можем, но обязаны учитывать. Обозначим их α = {α1 ,α 2 , ...,α m } ; − зависимые факторы, или управляющие переменные (элементы решения), которые в известных пределах мы можем выбирать по своему усмотрению. Обозначим их x = { x1 , x2 , ..., xn } . Например, в задаче об использовании ресурсов к постоянным факторам α i следует отнести запасы ресурсов каждого вида, производственную матрицу, элементы которой определяют расход сырья каждого вида на единицу выпускаемой продукции каждого вида. Зависимые факторы x j − план выпуска продукции каждого вида. Критерий эффективности, выражаемый целевой функцией Z , зависит от факторов обеих групп и может быть записан в общем виде Z = f ( x,α ) = f ( x1 , x2 ,..., xn ,α1 , α 2 ,...,α m ) . Все модели могут быть классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов. Прежде всего необходимо выделить большой класс оптимизационных моделей. Такие задачи возникают при попытке оптимизировать планирование и управление сложными системами, в первую очередь экономическими системами. Оптимизационную задачу можно сформулировать следующим образом: найти значения переменных x1 , x2 , ..., xn , которые при заданных условиях α1 , α 2 , ...,α m , удовлетворяют системе неравенств (уравнений) ϕ i ( x1 , x2 , ..., xn ,α1 ,α 2 , ...,α m ) ≤ bi , i = 1,2,..., k (1.1) и обращают в экстремум (минимум или максимум) целевую функцию, т.е. Z ( X ) = f ( x1 , x2 , ..., x n ,α1 ,α 2 , ...,α m ) → extr . (1.2) Если имеются условия неотрицательности x1 , x2 , ..., xn , то они также входят в ограничение (1.1). значений переменных В тех случаях, когда функции f и ϕ i дважды дифференцируемы, для поиска условного экстремума (максимума или минимума) функции f можно ис- 21 пользовать классические методы оптимизации. Однако их применение в исследовании операций весьма ограничено или вообще невозможно, если множество допустимых значений аргументов дискретно или же функция Z представлена в табличном виде. В этих случаях для решения задачи, представленной отношениями (1.1) и (1.2), используются методы математического программирования. Классификация задач математического программирования В основе классификации задач математического программирования лежит вид функций, задающих критерий эффективности и ограничения, зависимость их от такого параметра, как время, стохастический характер поведения и т.п. Ниже приведена общепринятая классификация подобных задач и даны краткие пояснения. Если критерий эффективности Z в (1.2) представляет собой линейную функцию, а функции ϕ i в системе ограничений (1.1) также линейны, то такая задача является задачей линейного программирования (ЗЛП). Если, исходя из содержательного смысла ЗЛП, ее решения должны быть целыми числами, то это − задача целочисленного программирования. Если критерий эффективности (1.2) и (или) система ограничений (1.1) задаются нелинейными функциями, то это − задача нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то это − задача выпуклого программирования. В свою очередь среди задач выпуклого программирования выделяют наиболее простые задачи квадратичного программирования, в которых целевая функция представляет собой полином второй степени (квадратичную форму) относительно переменных x1 , x2 , ..., xn , а область допустимых значений решений задается линейными ограничениями [11]. Если в задаче имеется переменная времени и критерий эффективности (1.2) выражается не в явном виде как функция переменных, а косвенно − через уравнения, описывающие протекание операций во времени, то это − задача динамического программирования. Если критерий эффективности (1.2) и система ограничений (1.1) задаются функциями вида с ⋅ x1α1 xα2 2 ...xαn n , то имеет место задача геометрического программирования. 22 Если функции f (1.2) и/или ϕ i (1.1) зависят от параметров, то получается задача параметрического программирования. Если эти функции носят случайный, точнее вероятностный, характер, то это − задача стохастического программирования. Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решений, прибегают к методам эвристического программирования, которые позволяют существенно сократить просматриваемое число вариантов и получить, если не оптимальное, то вполне удовлетворительное с точки зрения практики, решение. Классификация других задач исследования операций По своей содержательной постановке множество других, типичных задач исследования операций может быть разбито на ряд классов [9]. Задачи сетевого планирования и управления (СПУ) рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения. Подробно задачи СПУ и методы их решения рассмотрены в главе 6. Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например, в определении числа каналов обслуживания, времени обслуживания и т.п. Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но, с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта. Задачи распределения ресурсов (задачи распределительного типа, ЗРТ) возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций. Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. 23 Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены устаревшего оборудования более эффективным. Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования. Задачи планировки и размещения состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой. Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов. Среди моделей исследования операций особо выделяются модели принятия оптимальных решений в конфликтных ситуациях, изучаемые теорией игр. К конфликтным ситуациям, в которых сталкиваются интересы двух (или более) сторон, преследующих разные цели, можно отнести ряд ситуаций в области экономики, права, военного дела и т.п. В задачах теории игр необходимо выработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии. Многокритериальные задачи исследования операций На практике во многих случаях успех операции оценивается не по одному, а сразу по нескольким частным критериям, причем одни из них следует максимизировать, другие − минимизировать (и наоборот). Такого рода задачи носят название многокритериальных, или задач векторной оптимизации. Большинство известных методов векторной оптимизации непосредственно или косвенно сводят решаемые задачи к задачам скалярной (однокритериальной) оптимизации. Другими словами, частные критерии Z i ( X ), i = 1, n тем или иным способом объединяются в один составной (обобщенный, совокупный или интегральный) критерий. При этом используются различные способы получения составного критерия, называемые способами свёртки критериев [10]. Простейший из способов заключается в выборе одного главного из множества частных критериев, который затем используется в решении задачи. На все остальные критерии накладываются лишь некоторые ограничения. Напри- 24 мер, имеются пять критериев: Z1 , Z 2 , Z 3 , Z 4 и Z 5 , причем первые три ( Z1 , Z 2 , Z 3 ) необходимо максимизировать, а последние два ( Z 4 , Z 5 ) − минимизировать. Пусть в качестве главного критерия выбран Z1 , тогда задача решается с позиций максимума этого критерия, т.е. Z1 → max , а остальные критерии включаются в постановку задачи в виде неравенств (ограничений): Z 2 ≥ Z 20 ; Z 3 ≥ Z 30 ; Z 4 ≤ Z 40 ; Z 5 ≤ Z 50 , (1.3) где Z 20 , Z 30 , Z 40 , Z 50 − некоторые заданные числовые значения соответствующих показателей, для отыскания которых используются результаты анализа объекта и условий его функционирования. Анализ объекта и условий его функционирования используется также и для выбора главного критерия. Другой распространенный способ свертки критериев заключается в формировании некоторого составного критерия Z , представляющего собой функцию от частных критериев Z1 , Z 2 , ..., Z n . Предположим сначала, что все критерии имеют одинаковые размерности и диапазоны изменения своих значений. Тогда составной критерий Z можно записать в виде обыкновенной дроби, числитель которой представляет собой произведение всех частных критериев, которые необходимо обратить в максимум, а знаменатель − произведение всех минимизируемых критериев. Отыскивается максимум составного критерия Z . Для рассмотренного выше примера составной критерий имеет следующий вид: Z ⋅Z ⋅Z Z = 1 2 3 → max . (1.4) Z4 ⋅ Z5 Очевидно, что максимум Z будет достигаться, когда критерии Z1 , Z 2 и Z 3 достигают своих максимальных значений, а Z 4 и Z 5 − своих минимальных значений. Основной недостаток данного способа заключается в том, что при его использовании может достигаться приемлемое значение Z даже при неудовлетворительных значениях некоторых частных критериев за счет улучшения других оптимизируемых показателей. Например, низкое качество продукции может компенсироваться высокой производительностью, если оба эти показателя входят в выражение для составного критерия оптимальности в виде частных критериев. Чтобы пояснить это, вспомним «критерий оценки человека», полушутяполусерьезно предложенный когда-то Л.Н. Толстым. По его мнению, этот кри- 25 терий должен иметь вид дроби, в числителе которой стоят действительные достоинства человека, а в знаменателе − его мнение о себе. Однако можно представить ситуацию, когда человек, почти не имеющий достоинств, но при этом лишенный самомнения, окажется, согласно этому критерию, высокоценным, с чем, конечно же, нельзя согласиться [12]. Нередко используют еще один, более замысловатый, способ формирования составного критерия Z , который заключается в использовании «взвешенной суммы» частных критериев: n Z = λ1Z1 + λ2 Z 2 + ... + λn Z n = ∑ λi Z i , (1.5) i =1 где λi − весовой коэффициент (кратко − вес) соответствующего критерия Z i , i = 1, n . Этот коэффициент берется со знаком «+», если частный критерий Z i должен обращаться в максимум, или со знаком «−», если частный критерий должен обращаться в минимум. При этом ищется максимум составного критерия Z , т.е. Z → max . Абсолютные величины весовых коэффициентов λi берутся пропорциональными важности соответствующего частного критерия Z i с учетом требования нормированности: n | λ1 | + | λ2 | +...+ | λn | = ∑ | λi | = 1 . (1.6) i =1 Чтобы упорядочить частные критерии по степени их важности и найти соответствующие веса, часто используют экспертные оценки. Кроме того, следует заметить, что требование Z i → min можно заменить требованием − Z i → max . Поэтому в дальнейшем без ограничения общности можно считать, что каждый из n частных критериев Z i → max . Если частные критерии Z i имеют различные размерности, то выполняют их нормирование, т.е. переходят к безразмерным показателям zi , вычисляемым по следующей формуле: zi = Z i − Z i min , Z i max − Z i min (1.7) где Z i max и Z i min − соответственно максимальное и минимальное значения критерия Z i . Из приведенной выше формулы видно, что безразмерный показатель zi изменяется в диапазоне от 0 до 1: 0 ≤ zi ≤ 1 . 26 Для составного критерия z , который формируется как взвешенная сумма показателей zi , отыскивается максимум: n n z = ∑ λi zi = ∑ λi i =1 где λi > 0 и n ∑λ i =1 i i =1 Z i − Z i min → max , Z i max − Z i min (1.8) = 1 . Составной критерий подобного типа называется адди- тивным, поскольку он образуется путем сложения нормированных значений частных критериев. Аддитивные критерии основаны на использовании принципа справедливой компенсации абсолютных значений нормированных частных критериев. Однако в ряде случаев более целесообразно оперировать не абсолютными, а относительными изменениями значений частных критериев, т.е. использовать мультипликативный составной критерий оптимальности. Если все частные критерии имеют одинаковую важность, то составной мультипликативный критерий образуется путем их перемножения: n Z ( X ) = ∏ Zi ( X ) . (1.9) i =1 В случае неравнозначности частных критериев необходимо ввести весовые коэффициенты λi , и составной мультипликативный критерий принимает вид n Z ( X ) = ∏ Zi i ( X ) . λ (1.10) i =1 Еще одним, менее формальным по сравнению с рассмотренными выше способами, является так называемый метод последовательных уступок. Кратко суть этого метода состоит в следующем. Предположим, что частные критерии пронумерованы в порядке убывания их важности. Сначала ищется решение, обращающее в максимум первый (важнейший) критерий Z1 = Z1 max . Далее по результатам проведенного анализа определяют величину ∆Z1 , на которую можно отступить от максимального значения Z1 max , чтобы за счет этого добиться максимума по второму критерию Z 2 . Таким образом, второй раз задача решается с позиции максимума критерия Z 2 при условии Z1 ≥ Z1max − ∆Z1 . Затем аналогичным образом назначается уступка по второму критерию, т.е. ∆Z 2 , за счет чего достигается максимум критерия Z 3 и т.д. В заключение получается 27 такая совокупность оптимальных значений Z1 , Z 2 , ..., Z n , которая обеспечивает максимум составного критерия Z . Рассмотрим способ свертки критериев, позволяющий одновременно оперировать как с количественными, так и качественными критериями, т.е. такими, значения которых не могут однозначно и исчерпывающе характеризоваться единственным числом. Сначала решим задачу оценки объекта по совокупности нескольких показателей, в число которых входят только качественные критерии [10]. Предположим, необходимо рекомендовать к производству один из нескольких имеющихся проектов набора корпусной мебели. При определении лучшего варианта учитывается целый ряд критериев, в том числе и качественные показатели: эстетичность, технологичность и функциональность. Для перехода к количественной оценке каждому качественному критерию Z i следует сопоставить количественный показатель d i , величина которого находится в диапазоне от 0 до 1 (причем лучшему значению Z i соответствует большее значение d i ). В зависимости от предъявляемых требований качественный критерий Z i может принимать два, три или больше значений. В соответствии с этим диапазон [0,1] делится на столько же равных поддиапазонов и с каждым значением Z i сопоставляется некоторая величина d i из соответствующего поддиапазона. Если, например, Z1 принимает три значения, которые можно назвать «плохо», «удовлетворительно» и «хорошо», то оценке «плохо» будет соответствовать одно из значений 0 ≤ d1 ≤ 0,33 , оценке «удовлетворительно» − 0,33 ≤ d1 ≤ 0,67 , оценке «хорошо» − 0,67 ≤ d1 ≤ 1 . Допустим теперь, что количественная оценка для каждого качественного критерия d i уже получена. Тогда составной критерий D , обобщающий все частные количественные показатели d i , может быть вычислен по следующей формуле: D = n d1 ⋅ d 2 ⋅ ... ⋅ d n = n n ∏d i . (1.11) i =1 Подобное представление составного критерия оптимальности имеет ряд достоинств. Его область допустимых значений 0 ≤ D ≤ 1 совпадает с областью допустимых значений каждого из частных критериев d i . При этом величина D равна нулю, если хотя бы один из показателей d i равен нулю, и равна единице 28 только в том случае, если равны единице все частные критерии d i , i = 1, n . Если все показатели d i принимают одно и то же значение, то это же значение принимает и критерий D . Поэтому область допустимых значений составного критерия D можно разбить на столько же поддиапазонов и с теми же границами, что и для частных критериев d i . Когда среди n критериев оказываются как качественные, так и количественные критерии, поступают следующим образом. Предположим, желательно увеличить количественный критерий Z i , изменение которого в рассматриваемом диапазоне может быть сопоставлено с показателем d i : 0 ≤ d i ≤ 1 (как это сделано выше для качественных критериев). Наибольшему значению Z i = Z i max будет соответствовать значение d i = 1 , наименьшему значению Z i = Z i min − значение d i = 0 . Во многих случаях пропорциональная зависимость между изменениями значений этого показателя и соответствующего ему критерия имеет место лишь внутри некоторого поддиапазона рассматриваемого диапазона Z i . Функция, описывающая зависимость d i ( Z i ) , имеет точки изломов на концах этого поддиапазона, в которых она недифференцируема. Поэтому на практике ее аппроксимируют гладкой функцией, называемой функцией желательности, которая описывается следующей формулой: − ( b0 +b1Z i ) d i = e−e . (1.12) Для вычисления коэффициентов b0 и b1 сначала необходимо дважды прологарифмировать выражение (1.12): 1 b0 + b1Z i = − ln ln   . (1.13) d  i Затем выбирают значения d i для двух произвольных значений критерия Z i : d i1 для Z i1 и d i 2 для Z i 2 (как правило, в качестве значений Z i1 и Z i 2 используют Z i min и Z i max , которым соответствуют d i1 = 0,2 и d i 2 = 0,8 ). Далее для выбранных значений записывают систему двух линейных уравнений с двумя неизвестными b0 и b1 : 29   1  b0 + b1 Z i1 = − ln ln  ,   d i1  (1.14)    b + b Z = − ln ln  1 . d   0 1 i2  i2   Приведенная выше функция желательности хорошо соответствует требованиям увеличения критерия Z i в диапазоне от Z i min до Z i max , где она возрастает почти линейно (в предположении, что увеличение Z i свыше Z i max не требуется). С учетом изложенного выше, диапазон значений d i : 0 ≤ d i ≤ 1 можно разделить на пять поддиапазонов, поставив каждому из них соответствующую качественную оценку (табл. 1). Таблица 1 Качественная оценка Диапазон d i y = b0 + b1 Z i очень плохо 0,00 − 0,20 (−∞) − (−0,476) плохо удовлетворительно 0,20 − 0,37 0,37 − 0,63 (−0,476) − 0 0 − 0,772 хорошо 0,63 − 0,80 0,772 − 1,5 очень хорошо 0,80 − 1,00 1,5 − (+∞ ) Основное применение функция желательности находит при решении задач многокритериальной оптимизации с количественными критериями. После того, как для каждого из них построена частная функция желательности d i , имеющая вид (1.12), можно по формуле (1.11) сформировать составной критерий − обобщенную функцию желательности D . Затем для нее решают однокритериальную задачу оптимизации. При этом выражение для совокупного критерия D можно обобщить, если учесть весовые коэффициенты λi соответствующих критериев d i ( 0 ≤ λi ≤ 1 ). В этом случае формула (1.11) примет следующий вид: 1 1 1 ∑ 1  λ1   1 + 1 + ... + 1   λ λ 1 2 n λn  d  i = 1 λ i . (1.15) D =  d 1 ⋅ d 2 ⋅ ... ⋅ d n   λ 1 λ 2 =     i =1    При решении задач оптимизации важно сократить количество рассматриваемых решений, исключив те из них, которые приводят к заведомо худшим показателям, чем другие. Для однокритериальных задач разработаны эффек1 n ∏ 1 λi i n 30 тивные методы, позволяющие не только существенно ограничить множество возможных решений, но и найти оптимальное решение (см. главу 4). При анализе решений многокритериальных задач поступают следующим образом [12]. Пусть имеется многокритериальная задача исследования операций с k критериями Z1 , Z 2 , ..., Z k , которые желательно максимизировать (если это не так, то для перехода от «минимума» к «максимуму» достаточно изменить знак у соответствующего показателя). Предположим, что в составе множества возможных решений X есть два решения х1 и х2 такие, что все критерии Z1 , Z 2 , ..., Z k для первого решения больше или равны соответствующим критериям для второго решения (причем хотя бы один из них действительно больше). Очевидно, что в составе множества X нет смысла сохранять решение х2 , поскольку оно хуже и вытесняется (или, как говорят, доминируется) решением х1 . Аналогичным образом сравниваются другие решения и в результате множество X существенно сокращается, в нем сохраняются только так называемые эффективные, оптимальные по Z2 Парето решения, характерные тем, что 6 15 1 среди них нет доминирующих решений . 3 10 1 14 19 2 5 8 12 Проиллюстрируем прием выделе17 20 7 16 18 ния паретовских решений на примере 4 13 9 двухкритериальной задачи [13]. Предпо11 ложим, что множество X состоит из 20 возможных решений, которые можно Z1 изобразить точками на плоскости с коорРис. 4. Множество возможных решений и паретовские решения динатами Z1 и Z 2 (рис. 4). Очевидно, из всего множества X эффективными будут только решения x6 , x15 , x19 , x20 , лежащие на правой верхней границе области возможных решений (точки, соединенные пунктиром). Для всякого другого решения существует хотя бы одно доминирующее, для которого либо Z1 , либо Z 2 , либо оба критерия будут больше. После того как из множества X выделены эффективные решения, можно выбрать среди них приемлемое решение. Выбор одного из паретовских решений, которому будет отдано предпочтение, относится к компетенции ЛПР. 1 По фамилии итальянского экономиста Вильфредо Парето, впервые сформулировавшего проблему многокритериальной (векторной) оптимизации (1898 г.). 31 Глава 2. Задачи линейного программирования в экономике Линейные модели являются одним из наиболее простых и часто используемых классов математических моделей, используемых в экономике. Они изучаются в рамках линейного программирования − одного из наиболее ранних и проработанных разделов исследования операций. Линейное программирование (англ. linear programming) − это набор математических методов и приемов решения задачи оптимального распределения имеющихся ограниченных ресурсов (денег, материалов, времени и т.п.) для достижения определенной цели (максимума прибыли или минимума издержек). Появление линейного программирования обычно связывают с именем американского математика Джорджа Данцига, который в 1947 году применил методы линейной алгебры для определения оптимальных решений задач, содержащих определенные ограничения. Другим основоположником линейного программирования по праву является советский математик, академик Леонид Витальевич Канторович (19121986), которому в 1975 году была присуждена Нобелевская премия по экономике (совместно с американским экономистом Т. Купмансом) за вклад в развитие теории оптимального распределения ресурсов. В 1939 году Л.В. Канторович опубликовал научную работу, в которой на основе метода разрешающих множителей (мультипликаторов) исследовались различные классы плановопроизводственных задач, давалась математическая постановка производственных задач оптимального планирования и предлагались эффективные методы решения и приемы экономического анализа этих задач. В данной работе, которая стала известна в США лишь в 1959 году, было показано, что все экономические проблемы распределения могут рассматриваться как задачи максимизации при многочисленных ограничениях и, следовательно, могут быть решены при помощи методов линейного программирования. Термин «линейное программирование» нуждается в кратком комментарии. В данном случае слово «программирование» означает планирование, а слово «линейное» − поиск экстремума (минимума или максимума) линейной целевой функции при линейных ограничениях, представленных системой линейных уравнений или неравенств. Вот что по этому поводу вспоминает нобелевский лауреат Дж. Данциг: «Военные называли программами свои различные 32 планы и предлагаемые расписания для подготовки, тылового снабжения и перемещения боевых частей. Когда я впервые проанализировал задачу планирования для ВВС и увидел, что она может быть сформулирована как система линейных неравенств, то назвал свою первую статью «Программирование с линейной структурой». Однажды летом 1948 г. Купманс, прогуливаясь со мной по пляжу городка Санта-Моника, предложил сократить этот термин до «линейного программирования» и я согласился» [14]. Имеется целый ряд различных методов линейного программирования; одни из них являются специализированными или узконаправленными (т.е. предназначены для решения определенного класса задач), другие имеют общий характер. Наиболее распространенным методом решения задач линейного программирования является так называемый симплекс-метод, разработанный Дж. Данцигом, а наиболее эффективным из известных − метод эллипсоидов. В простейшем случае, когда число переменных равно двум, удобен простой и наглядный графический способ. Другой важный класс линейных задач образуют задачи, сводимые к системам линейных уравнений, − это линейные задачи, ограничения в которых имеют характер равенств. Как известно, одним из наиболее простых и одновременно эффективных подходов к решению линейных систем является метод последовательного исключения неизвестных. Эффективное применение линейного программирования достигается при решении следующих общих классов задач [15]: − задачи о составлении смеси, цель которых заключается в выборе наиболее экономичной смеси ингредиентов, т.е. составляющих (руды, нефти, пищевых продуктов и др.) при учете ограничений на физический или химический состав смеси и на наличие необходимых материалов; − задачи планирования производства, цель которых подбор наиболее выгодной производственной программы выпуска одного или нескольких видов продукции при использовании некоторого числа ограниченных источников сырья; − задачи распределения товаров, цель которых состоит в том, чтобы организовать доставку товаров от некоторого числа поставщиков к некоторому числу потребителей так, чтобы оказались минимальными либо расходы по этой доставке, либо время, либо некоторая комбинация того и другого. В простейшем случае это задача о перевозках (транспортная задача). 33 Рассматриваются и комбинированные задачи (например, в случае, когда какой-то товар производится в разных местах, задачи производства и распределения объединяют в единую модель). Задачи о составлении смеси Исторически задача о составлении смеси (диеты, рациона) является одной из первых ЗЛП. Ниже рассмотрено построение экономико-математических моделей для нескольких задач, относящихся к данному классу [9, 16]. Цены, заработная плата и некоторые другие количественные величины, представленные в задачах, которые приведены ниже, выбраны достаточно условно и не отражают их нынешнего фактического состояния. Задача № 1. Металлургическому комбинату требуется уголь с содержанием фосфора не более 0,03 % и с долей зольных примесей не более 3,25 %. Комбинат закупает три сорта угля, условно обозначенных A, B и С, с известным содержанием примесей. В какой пропорции нужно смешивать сорта угля A, B и C, чтобы полученная смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену? Содержание примесей и цена каждого сорта угля приведены в табл. 2. Таблица 2 Цена Содержание, % Сорт угля 1 т, р. Фосфора Золы 0,06 2,0 30 A 0,04 4,0 30 B 0,02 3,0 45 C Решение. Построим экономико-математическую модель задачи. Обозначим x1 − количество угля сорта A в тонне смеси, x2 − количество угля сорта B в тонне смеси, x3 − количество угля сорта С в тонне смеси. Стоимость 1 т смеси (целевая функция) с учетом введенных обозначений и данных графы «Цена 1 т, р.» запишется в следующем виде: Z = 30 x1 + 30 x2 + 45 x3 . Ограничение на содержание фосфора в смеси запишется в виде 0,06 x1 + 0,04 x2 + 0,02 x3 ≤ 0,03 (%). Ограничение на содержание зольных примесей в смеси запишется в виде 34 2 x1 + 4 x2 + 3 x3 ≤ 3,25 (%). Ограничение на состав 1 т смеси запишется в виде x1 + x2 + x3 = 1 . Таким образом, экономико-математическая модель задачи примет следующий вид: определить количества x1, x2, x3 угля сортов A, B, C, соответственно, в тонне смеси, при которых достигается минимум целевой функции: Z ( X ) = 30 x1 + 30 x2 + 45 x3 → min при ограничениях 0,06 x1 + 0,04 x2 + 0,02 x3 ≤ 0,03 2 x + 4 x + 3 x ≤ 3,25  1 2 3   x1 + x2 + x3 = 1  x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Задача № 2. В отделе технического контроля (ОТК) предприятия работают контролеры 1-го и 2-го разрядов. Норма выработки ОТК за 8-часовой рабочий день составляет не менее 1800 изделий. Контролер 1-го разряда проверяет 25 изделий в час, причем не ошибается в 98 % случаев. Контролер 2-го разряда проверяет 15 изделий в час, его точность составляет 95 %. Заработная плата контролера 1-го разряда равна 4 р. в час, контролер 2-го разряда получает 3 р. в час. При каждой ошибке контролера предприятие несет убыток в размере 2 р. Предприятие может использовать не более восьми контролеров 1-го и десяти контролеров 2-го разряда. Руководство предприятия хочет определить оптимальный состав ОТК, при котором общие затраты на контроль будут минимальными. 35 Решение. Обозначим через x1, x2 − количество контролеров 1-го и 2-го разрядов соответственно. Число контролеров каждого разряда ограничено, т.е. имеются следующие ограничения: x1 ≤ 8 (1-й разряд), x2 ≤ 10 (2-й разряд). Ежедневно необходимо проверять не менее 1800 изделий. Поэтому выполняется неравенство 8 ⋅ 25 x1 + 8 ⋅ 15 x2 = 200 x1 + 120 x2 ≥ 1800 , или 5 x1 + 3 x2 ≥ 45 . При построении целевой функции следует иметь в виду, что расходы предприятия, связанные с контролем, включают две составляющие: 1) зарплату контролеров, 2) убытки, вызванные ошибками контролеров. Исходя из этого, расходы на одного контролера 1-го разряда в час составляют 4 р. + 2 р. ⋅ 25 ⋅ 0,02 = 5 р. , а расходы на одного контролера 2-го разряда 3 р. + 2 р. ⋅ 15 ⋅ 0,05 = 4,5 р. Целевая функция, выражающая ежедневные расходы на контроль, запишется в виде: 8 ⋅ (5 x1 + 4,5 x2 ) = 40 x1 + 36 x2 . Таким образом, экономико-математическая модель задачи примет следующий вид: определить количественный состав ОТК, включающего контролеров 1-го и 2-го разрядов, при котором достигается минимум целевой функции: Z ( X ) = 40 x1 + 36 x2 → min при ограничениях  x1 ≤ 8  x ≤ 10  2  5 x1 + 3 x2 ≥ 45  x1 ≥ 0, x2 ≥ 0. 36 Задачи планирования производства При планировании производства продукции на промышленном предприятии необходимо учитывать его ресурсные ограничения, а именно: фонд машинного времени по каждому виду оборудования; фонд рабочего времени, определяемый численностью персонала; фонд материальных ресурсов, которые может получить в планируемый период предприятие от поставщиков по заключенным договорам. Модели многих задач планирования базируются на законах сохранения (балансовых соотношениях) и эмпирических закономерностях преобразования ресурсов в продукцию (производственных функциях). Математически подобные модели представляются в виде систем m линейных уравнений с n неизвестными, которые решаются с помощью известных методов линейной алгебры (например, методом Гаусса). Основное уравнение ресурсной модели производства отражает баланс необходимых ресурсов предприятия и имеет следующий вид [17]: m yi = xi − ∑ aij x j (i = 1,2,..., m) , (2.1) i= j где aij − норма расхода i -го вида вспомогательной продукции на производство единицы j -го вида основной (конечной) продукции; x j − количество производимой основной продукции j -го вида; yi − количество основной продукции i -го вида. Содержательный смысл этого уравнения заключается в следующем: количество основного i -го продукта yi должно равняться количеству xi вспомогательного продукта, используемого для производства этого основного продукта, минус общие расходы этого вспомогательного продукта на комплектацию других основных и вспомогательных продуктов предприятия. Основное уравнение ресурсной модели (2.1) может быть преобразовано к виду m ∑a i= j ij x j + yi = xi (i = 1, 2,..., m) (2.2) и решено методом Гаусса для получения планируемых объемов xi основной и вспомогательной продукции. 37 Требуемые для выполнения плана материальные ресурсы определяются как m ∑d j =1 rj x j = dr , (2.3) где d rj − норма расхода r -го вида материальных ресурсов на изготовление единицы j -го вида продукции, r − номер вида материалов, сырья, полуфабрикатов, комплектующих, деталей, узлов, топлива, электроэнергии. Требуемые для выполнения плана производственные фонды оборудования (в виде затрат машинного времени) определяются как m ∑f j =1 sj x j = fs , (2.4) где f sj − норма расхода s -го вида фондов на изготовление единицы j -го вида продукции, s − номер вида фондов оборудования. Требуемые для выполнения плана трудовые ресурсы (в виде затрат рабочего времени) определяются как m ∑t j =1 gj x j = tg , (2.5) где t gj − норма затрат (рабочего времени) g -го вида труда на изготовление единицы j -го вида продукции, g − номер вида труда (по профессиям). Если d r , f s , t g выходят за установленные для этого планового периода максимальные обеспеченные уровни, то необходимо пересмотреть (уменьшить) объем конечной продукции yi , определить новые значения или принять меры по увеличению ресурсов. Если какое-либо из соотношений (2.3)–(2.5) или же все они представлены неравенствами, то решить подобную задачу известными методами линейной алгебры не удастся. В этом случае для решения задачи должны использоваться модели и методы линейного программирования (см. ниже). Задача № 3. Производственному участку поручено выпускать мебель двух видов, на производство которых выделены необходимые сырьевые и производственные ресурсы (табл. 4). Найти такой план выпуска продукции, чтобы суммарная прибыль от ее реализации была наибольшей. 38 Виды продукции 1. Стол 2. Диван Объемы ресурсов Затраты ресурсов на единицу продукции Ткань оби- Пиломате- ДревесноОборудовочная, м2 риалы, м3 стружечвание, ная плита, станко2 м смен 0,032 1,6 11,4 4 0,06 3,8 1856 31,648 641,6 4807 Таблица 4 Прибыль на единицу продукции, р. 36,27 6,7 Решение. Составим экономико-математическую модель задачи. Обозначим через x1 и x2 − число единиц запланированных к производству столов и диванов соответственно. Cуммарная прибыль от реализации всей выпущенной продукции представляется целевой функцией, которая имеет вид Z ( X ) = 36,27 x1 + 6,7 x2 . Ограничение на запасы обивочной ткани можно представить следующим неравенством: 4 x2 ≤ 1856. На запасы пиломатериалов 0,032 x1 + 0,06 x2 ≤ 31,648. На запасы древесностружечной плиты (ДСтП) 1,6 x1 ≤ 641,6. На объем технологического оборудования 11,4 x1 + 3,8 x2 ≤ 4807. Кроме того, по смыслу задачи x1 ≥ 0 , x2 ≥ 0 . Таким образом, экономико-математическая модель задачи примет следующий вид: найти такой план выпуска столов и диванов X = ( x1 , x2 ) , при котором достигается максимум целевой функции Z ( X ) = 36,27 x1 + 6,7 x2 → max при ограничениях 39 4 x 2 ≤ 1856 0,032 x + 0,06 x ≤ 31,648 1 2  1,6 x1 ≤ 641,6 11,4 x + 3,8 x ≤ 4807 1 2   x1 ≥ 0, x2 ≥ 0. Задача № 4. Фирма выпускает три вида изделий. В процессе производства используются три технологические операции. На рис. 5 показана технологическая схема производства изделий 1-го, 2-го и 3-го видов. При изготовлении изделия 2-го вида технологическая операция 2 не выполняется, а при производстве изделия 3-го вида используются только технологические операции 1 и 2. В прямоугольниках, представляющих операции технологического маршрута, указаны длительности этих операций при изготовлении изделий каждого типа. Операция 1 Операция 2 Операция 3 1 мин./изд. 3 мин./изд. 1 мин./изд. Изделие 1 4 мин./изд. Изделие 2 2 мин./изд. 1 мин./изд. 2 мин./изд. Изделие 3 Рис. 5. Технологическая схема производства изделий 1-го, 2-го и 3-го видов Так как эти технологические операции используются фирмой и для других производственных целей, фонд рабочего времени, в течение которого операции 1, 2 и 3 могут быть применены для производства рассматриваемых изделий, ограничен следующими предельными значениями (в сутки): для операции 1 − 430 мин, для операции 2 − 460 мин, для операции 3 − 420 мин. 40 Прибыль от продажи одного изделия 1-го, 2-го и 3-го видов составляет 3, 2 и 5 рублей соответственно. Каков наиболее выгодный суточный объем производства каждого вида изделия? Решение. Построим экономико-математическую модель задачи. Обозначим x1 − количество производимых изделий 1-го вида, x2 − количество производимых изделий 2-го вида, x3 − количество производимых изделий 3-го вида. Тогда математическая формулировка задачи примет вид Z ( X ) = 3 x1 + 2 x2 + 5 x3 → max (величина прибыли за сутки) при следующих ограничениях на предельное время использования операций в течение суток: 1x1 + 2 x2 + 1x3 ≤ 430  3 x1 + 0 x2 + 2 x3 ≤ 460 1x + 4 x + 0 x ≤ 420 2 3  1 и при выполнении условий x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Общая постановка задачи планирования производства Рассмотренную выше задачу можно легко обобщить на случай выпуска n видов продукции с использованием m видов ресурсов [16]. Обозначим x j ( j = 1,2,..., n ) − число единиц продукции Pj , запланированной к производству; bi (i = 1,2,..., m) − запас ресурса S i ; aij − число единиц ресурса S i , затрачиваемого на единицу продукции Pj (числа aij часто называют технологическими коэффициентами); c j − прибыль от реализации единицы продукции Pj . Тогда экономико-математическая модель задачи планирования производства примет следующий вид: найти такой план X = ( x1 , x2 ,..., xn ) выпуска продукции, удовлетворяющий системе неравенств a11 x1 + a12 x2 + ... + a1n xn ≤ b1 a x + a x + ... + a x ≤ b  21 2 22 2 2n n 2  ........................................ am1 xm + a m 2 x2 + ... + a mn xn ≤ bm . (2.6) 41 и условию x1 ≥ 0 , x2 ≥ 0 , …, xm ≥ 0 , (2.7) при котором функция Z ( X ) принимает максимальное значение Z ( X ) = c1 x1 + c2 x2 + ... + cn xn → max . (2.8) Ограничения (2.6) и (2.7) могут быть представлены в сокращенной форме n ∑a x j =1 ij i ≤ bi , xi ≥ 0 (i = 1,2,..., m) . (2.9) Примечание 1. Неравенства, представленные в системе (2.6), называются функциональными ограничениями, в условии (2.7) − прямыми, или тривиальными. Примечание 2. Задачи линейного программирования могут быть условно разбиты на две группы: одноиндексные и двухиндексные − по количеству индексов у переменных решения ( xi и xij ) [18]. В этом смысле все приведенные выше задачи являются одноиндексными. Двухиндексные задачи рассмотрены ниже. Общая постановка задачи об использовании мощностей (загрузке оборудования) Предприятию задан план производства продукции по времени и номенклатуре: требуется за время T выпустить n1 , n2 ,..., nk единиц продукции P1 , P2 ,..., Pk . Продукция производится на станках S1 , S 2 ,..., S m , для каждого из которых известны производительность aij (т.е. число единиц продукции Pj , которое можно произвести на станке S i за единицу времени) и затраты bij на изготовление продукции Pj на станке S i в единицу времени. Необходимо составить такой план работы станков (т.е. распределить выпуск продукции между станками), чтобы затраты на производство всей продукции были минимальными. 42 Экономико-математическая модель задачи об использовании мощностей Составим экономико-математическую модель задачи [9]. Обозначим xij − время, в течение которого станок S i будет занят изготовлением продукции Pj (i = 1,2,..., m; j = 1,2,..., k ) . Так как время работы каждого станка ограничено и не превышает T , то справедливы следующие неравенства:  x11 + x12 + ... + x1k ≤ T  x + x + ... + x ≤ T  21 22 2k (2.10)  .......... .......... ..........   xm1 + xm 2 + ... + xmk ≤ T . Для выполнения плана выпуска по номенклатуре необходимо, чтобы выполнялись следующие равенства: a11 x11 + a21 x21 + ... + a m1 xm1 = n1 a x + a x + ... + a x = n  12 12 22 22 m2 m2 2 (2.11)  .......... .......... .......... .......... ....  a1k x1k + a 2 k x2 k + ... + a mk xmk = nk . Кроме того, по условию задачи xij ≥ 0 (i = 1,2,..., m; j = 1,2,..., k ). (2.12) Затраты на производство всей продукции должны быть минимальны: Z ( X ) = b11 x11 + b12 x12 + ... + bmk xmk → min . (2.13) Экономико-математическая модель задачи об использовании мощностей (загрузке оборудования) примет вид: найти такое решение X = ( x11 , x12 ,..., xmk ) , удовлетворяющее системам (2.10) и (2.11) и условию (2.12), при котором целевая функция (2.13) принимает минимальное значение. Задача № 5 . На двух автоматических линиях выпускают аппараты трех типов: А, B, C. Другие данные условия задачи приведены в табл. 5. Составить такой план загрузки станков, чтобы затраты были минимальными, а задание выполнено не более чем за 10 суток. 43 Таблица 5 Тип аппарата A B C Производительность работы линий, шт/сут 1 2 4 3 6 5 8 2 Затраты на работу линий, р/сут 1 2 400 300 100 200 300 400 План, шт. 20 40 50 Решение. Составим экономико-математическую модель задачи. Обозначим через x1a , x1b и x1c − время, в течение которого 1-я линия будет занята выпуском аппаратов A, B и C соответственно. Аналогично, обозначим через x2 a , x2 b и x2 c − время, в течение которого 2-я линия будет занята выпуском аппаратов A, B и C соответственно. Так как время работы каждой линии ограничено 10-ю сутками, то справедливы следующие неравенства:  x1a + x1b + x1c ≤ 10 (2.14)   x2 a + x2b + x2 c ≤ 10. Для выполнения плана по номенклатуре необходимо, чтобы выполнялись следующие равенства: 4 x1a + 3 x2 a ≥ 50  6 x1b + 5 x 2b ≥ 40 8 x + 2 x ≥ 50.  1c 2c Кроме того, по смыслу задачи x1a ≥ 0, x1b ≥ 0, x1c ≥ 0, x2 a ≥ 0, x2 b ≥ 0, x2c ≥ 0. (2.15) (2.16) Затраты на производство планового количества аппаратов A, B и C выражаются следующей целевой функцией: Z ( X ) = 400 x1a + 100 x1b + 300 x1c + 300 x2 a + 200 x2 b + 400 x2 c . (2.17) Таким образом, экономико-математическая модель задачи примет вид: найти такое решение X = ( x1a , x1b , x1c , x2 a , x2b , x2 c ) , удовлетворяющее системам (2.14) и (2.15) и условию (2.16), при котором целевая функция (2.17) принимает минимальное значение: Z ( X ) = 400 x1a + 100 x1b + 300 x1c + 300 x2 a + 200 x2 b + 400 x2 c → min . 44 Задача № 6. Промышленная фирма производит изделие, представляющее собой сборку из трех различных узлов. Эти узлы изготавливаются на двух заводах. Из-за различий в составе технологического оборудования производительность заводов по выпуску каждого из трех видов узлов неодинакова. В табл. 6 содержатся исходные данные, характеризующие как производительность заводов по выпуску каждого из узлов, так и максимальный суммарный ресурс времени, которым располагает каждый из заводов для производства этих узлов. Завод 1 2 Максимальный недельный фонд времени, час 100 80 Таблица 6 Производительность, узел/час Узел 1 Узел 2 Узел 3 8 5 10 6 12 4 Идеальной является такая ситуация, когда производственные мощности обоих заводов используются таким образом, что в итоге обеспечивается выпуск одинакового количества каждого из видов узлов. Однако этого трудно добиться из-за различий в производительности заводов. Более реальная цель состоит, повидимому, в том, чтобы максимизировать выпуск изделий, что фактически эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или двум видам узлов. Требуется определить еженедельные затраты времени (в часах) на производство каждого из трех видов узлов на каждом заводе, обеспечивающие максимальный выпуск изделий. Решение. Возможный объем выпуска каждого из трех видов узлов зависит от того, какой фонд времени выделяет каждый завод для их изготовления. Обозначим xij − недельный фонд времени (в часах), выделяемый на заводе i для производства узлов вида j . Тогда объемы производства каждого из трех комплектующих узлов равны: 8 x11 + 6 x21 (узел 1), 5 x12 + 12 x22 (узел 2), 10 x13 + 4 x23 (узел 3). Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделий должно быть равно количеству комплектующих узлов, объем производства которых минимален. Если, например, объем производства двух заводов составляет 100, 112 и 108 соответст- 45 вующих узлов, то количество конечных изделий будет равно min{100,112,108} = 100 . Поэтому количество конечных изделий можно выразить через число комплектующих узлов следующим образом: min{8 x11 + 6 x21 ,5 x12 + 12 x22 ,10 x13 + 4 x23 } . Условия рассматриваемой задачи устанавливают ограничения только на фонд времени, которым располагает каждый завод. Таким образом, математическую модель можно представить в следующем виде: Z ( X ) = min{8 x11 + 6 x21 , 5 x12 + 12 x22 ,10 x13 + 4 x 23 } → max при ограничениях  x11 + x12 + x13 ≤ 100   x21 + x22 + x 23 ≤ 80  x ≥ 0, (i = 1,2; j = 1,2,3).  ij ( завод 1), ( завод 2), Данная модель не является линейной (поскольку выражение для целевой функции представлено функцией отыскания минимума), но она может быть приведена к линейной форме с помощью простого преобразования. Пусть y = min{8 x11 + 6 x21 ,5 x12 + 12 x22 ,10 x13 + 4 x23 }. Тогда целевая функция запишется как Z ( X ) = y → max при ограничениях 8 x11 + 6 x21 ≥ y 5 x + 12 x ≥ y  12 22  10 x13 + 4 x23 ≥ y  y ≥ 0. Окончательно математическая модель задачи запишется в виде Z ( X ) = y → max при ограничениях 8 x11 + 6 x21 − y ≥ 0  5 x12 + 12 x22 − y ≥ 0 10 x13 + 4 x23 − y ≥ 0   x11 + x12 + x13 ≤ 100  x + x + x ≤ 80 22 23  21  xij ≥ 0, (i = 1,2; j = 1,2,3)   y ≥ 0. 46 Задачи о раскрое материала Задачи о раскрое материала являются частным случаем общей задачи планирования производства. Ниже рассмотрены две задачи, одна из которых посвящена распилу бревен [9], другая − раскрою ДСтП [10]. Третья задача, посвященная раскрою листов фанеры на комплектные заготовки, предназначена для самостоятельного решения [19]. Задача № 7. Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Решение. Прежде всего, определим возможные способы распила бревен, указав соответствующее число получаемых при этом брусьев (табл. 7). Таблица 7 Число получаемых брусьев длиной, м Способ распила i 1,2 3,0 5,0 1 5 − − 2 2 1 − 3 − 2 4 − − − 1 Обозначим xi − число бревен, распиленных i -м способом (i = 1, 2, 3, 4) и x − число комплектов брусьев. Учитывая, что все бревна должны быть распилены, а число брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид: найти такой план раскроя бревен X = ( x1 , x2 , x3 , x4 ) , при котором количество полученных комплектов будет максимальным Z ( X ) = x → max и выполняются ограничения  x1 + x2 + x3 + x4 = 195 5 x + 2 x = 2 x 2  1  x2 + 2 x3 = x  x = 3x  4  xi ≥ 0 (i = 1, 2, 3, 4). 47 Задача № 8 . ДСтП размером 350×175 см подлежат раскрою на прямоугольные заготовки двух типоразмеров: 200×70 см и 160×90 см1. Требуется получить не менее 300 заготовок первого и не менее 400 заготовок второго типоразмера. При этом суммарное (по площади) количество отходов должно быть минимально. Решение. Рассмотрим все возможные варианты раскроя плит на заготовки (рис. 6). 350 160 70 70 175 160 90 70 160 200 90 б) a) 90 160 90 90 200 в) Рис. 6. Варианты раскроя ДСтП на заготовки На рис. 6 (a) показан вариант раскроя плиты на две заготовки 1-го и одну заготовку 2-го типоразмера, обеспечивающий площадь отходов 350 ⋅ 175 − (2 ⋅ 200 ⋅ 70 + 160 ⋅ 90) = 61250 − 42400 = 18850 см2. 1 Типоразмеры плит и заготовок обычно указываются в миллиметрах, т.е. 3500×1750 мм, 2000×700 мм и 1600×900 мм. В задаче использованы более крупные единицы измерения − сантиметры, чтобы облегчить некоторые численные расчеты, которые придется выполнять «вручную». 48 Часть плиты, уходящей в отходы, закрашена серым цветом. Все другие варианты, содержащие эти же три заготовки, различаются только их расположением на плите и эквивалентны с точки зрения экономичности. По варианту раскроя, представленному на рис. 6 (б), можно получить одну заготовку 1-го и две заготовки 2-го типоразмера, площадь одходов равна 350 ⋅ 175 − (200 ⋅ 70 + 2 ⋅ 160 ⋅ 90) = 61250 − 42800 = 18450 см2. По варианту раскроя, представленному на рис. 6 (в), можно получить три заготовки 2-го типоразмера с площадью отходов 350 ⋅ 175 − 3 ⋅ 160 ⋅ 90 = 61250 − 43200 = 18050 см2. Для решения задачи следует выяснить, сколько плит надо раскроить по каждому из рассмотренных вариантов при выполнении предъявляемых требований. Обозначим через x1 количество плит, раскраиваемых по первому варианту, x2 − по второму варианту, x3 − по третьему варианту. Составим ограничение по выпуску заготовок 1-го типоразмера. Из одной плиты по первому варианту раскроя получаются две таких заготовки, из x1 плит 2x1 заготовок 1-го типоразмера. Кроме того, по одной такой заготовке получится при раскрое каждой плиты по второму варианту. Всего по этому варианту раскраивается x2 плит, из которых вырабатывается x2 заготовок 1-го типоразмера. Таким образом, общее количество заготовок 1-го типоразмера равно 2 x1 + x2 и по условию задачи оно не должно быть менее 300, т.е. имеем следующее ограничение: 2 x1 + x2 ≥ 300 . Аналогичным образом составляется ограничение по выработке заготовок 2-го типоразмера x1 + 2 x2 + 3 x3 ≥ 400 . Выражение для суммарного количества отходов при раскрое является целевой функцией, имеющей вид Z ( X ) = 18850 x1 + 18450 x2 + 18050 x3 . Наконец, следует учесть естественные ограничения на неотрицательность переменных x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Таким образом, экономико-математическая модель задачи оптимального раскроя ДСтП на заготовки имеет вид: найти такой план раскроя X = ( x1 , x2 , x3 ) , при котором целевая функция, определяющая суммарную площадь отходов, минимальна 49 Z ( X ) = 18850 x1 + 18450 x2 + 18050 x3 → min и выполняются следующие ограничения: 2 x1 + x2 ≥ 300   x1 + 2 x2 + 3 x3 ≥ 400  x ≥ 0, x ≥ 0, x ≥ 0.  1 2 3 Общая постановка задачи о раскрое одного материала На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных b1 , b2 ,..., bl (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i -го способа (i = 1, 2, ..., n) дает aik единиц k -го изделия (k = 1, 2, ..., l ). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов. Составим экономико-математическую модель задачи. Обозначим xi − число единиц материала, раскраиваемых i -м способом, и x − число изготавливаемых комплектов изделий. Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то n ∑x i =1 i = a. (2.18) Требование комплектности выразится уравнениями n ∑xa i =1 i ik = bk x (k = 1, 2, ..., l ). (2.19) Очевидно, что xi ≥ 0 (i = 1, 2, ..., n). (2.20) Экономико-математическая модель задачи: найти такое решение X = ( x1 , x2 ,..., xn ) , удовлетворяющее системе уравнений (2.18) и (2.19) и условию (2.20), при котором функция Z ( X ) = x принимает максимальное значение. 50 Общая постановка задачи о раскрое нескольких материалов Задачу о раскрое можно легко обобщить на случай m раскраиваемых материалов. Пусть каждая единица j -го материала ( j = 1, 2, ..., m) может быть раскроена n различными способами, причем использование i -го способа (i = 1, 2, ..., n) дает aijk единиц k -го изделия (k = 1, 2, ..., l ) , а запас j -го материала равен a j единиц. Обозначим xij − число единиц j -го материала, раскраиваемого i -м способом. Экономико-математическая модель задачи о раскрое в общей постановке примет вид: найти такое решение X = ( x11 , x12 ,..., xnm ) , удовлетворяющее системе ограничений  n ∑ xij ≤ a j  i=1  n m ∑∑ x a = b x k  i=1 j=1 ij ijk ( j = 1,2,..., m) (2.21) (k = 1,2,..., l ) и условию xij ≥ 0 , (2.22) при которых целевая функция Z ( X ) принимает максимальное значение: Z ( X ) = x → max . (2.23) 51 Способы решения задачи линейного программирования В данной главе на примере решения простой задачи производственного планирования рассмотрены следующие два способа решения ЗЛП: графический и симплекс-метод. Экономико-математическая модель задачи производственного планирования Пусть предприятие обладает i видами производственных ресурсов (i = 1, 2, ..., m) , объем каждого из которых обозначим через bi . Имеющиеся на предприятии ресурсы используются для производства j видов продукции ( j = 1, 2, ..., n) , причем известно количество i -го вида ресурсов, затрачиваемое на выпуск единицы j -го вида продукции, которое обозначим через aij . Кроме того, известна прибыль от реализации единицы каждого из j видов выпущенной продукции, которую обозначим через c j . С учетом введенных обозначений экономико-математическая модель задачи формирования производственного плана, обеспечивающего получение максимальной прибыли, может быть представлена следующим образом: найти план выпуска продукции X = ( x1 , x2 , ..., x j , ..., xn ) , удовлетворяющий системе ограничений a11 x1 + a12 x2 + ... + a1 j x j + ... + a1n x n ≤ b1  a21 x1 + a 22 x2 + ... + a 2 j x j + ... + a 2 n xn ≤ b2  ... ... ... ... ... ... (3.1)  ... a x + a x + ... + a x + ... + a x ≤ b m2 2 mj j mn n m  m1 1  x1 ≥ 0, x2 ≥ 0, ..., x j ≥ 0, ..., xn ≥ 0, при которых целевая функция задачи (прибыль от реализации произведенной продукции) принимает максимальное значение Z ( X ) = c1 x1 + c2 x2 + ... + c j x j + ... + cn xn → max . (3.2) Как отмечалось выше, данная задача относится к ЗЛП, поскольку и целевая функция, и ограничения являются линейными. 52 Выражения (3.1) и (3.2) можно записать в краткой форме n ∑a x j =1 ij j ≤ bi , x j ≥ 0, i =1, m; j = 1, n; (3.3) (3.4) n Z ( X ) = ∑ c j x j → max . (3.5) j =1 Другим кратким способом записи выражений (3.1) и (3.2) является следующая матричная форма [9]: AX ≤ B , (3.6) X ≥ 0, (3.7) CX → max , (3.8)  a11 a12 ... a1 j ... a1n     a21 a22 ... a2 j ... a2 n  где A =   − так называемая технологическая матрица; ... ... ... ... ... ...    a a ... a ... a  mj mn   m1 m 2  b1  b B= 2 ...  b  m  x1       x2   − вектор ресурсных ограничений; X =  ...  − вектор-план;     x    n   С = (с1 с2 ... cn ) − вектор стоимости. Разновидностью матричной формы записи математической модели задачи является векторная форма [20] P1 x1 + P2 x2 + ... + Pj x j + ... + Pn xn ≤ P , (3.9) X ≥ 0, (3.10) CX → max , (3.11) где CX − скалярное произведение векторов С = (с1 с2 ... cn ) и X = ( x1 x2 ... xn ) , т.е. число, равное сумме произведений соответствующих координат этих векторов: CX = c1 x1 + c2 x2 + ... + c j x j + ... + cn xn (по определению); векторы  a11    a  P1 =  21  , ...   a   m1   a12    a   P2 =  22  , ...   a   m2  …,  a1n   b1      a   b  Pn =  2 n  , P =  2  ... ...     b  a   mn   m 53 состоят соответственно из коэффициентов при переменных и свободных членов. Пример построения экономико-математической модели задачи производственного планирования Задача № 9. Предприятие производит два вида продукции P и P1 , ис-2 пользуя для этого три вида сырья: S1 , S 2 , S 3 . Нормы расхода сырья каждого вида приведены в табл. 8. Найти такой план выпуска продукции, при котором прибыль от ее реализации является максимальной. Таблица 8 Расход сырья на единицу продукции Продукция S1 S2 S3 Прибыль от реализации ед. продукции P1 1 2 1 3 P2 1 1 2 4 Кол-во сырья в наличии 5 9 7 Экономико-математическую модель данной задачи можно записать следующим образом: определить объемы производства продукции P1 и P2 , при которых достигается максимизация целевой функции Z ( X ) = 3 x1 + 4 x2 → max (3.12) при ограничениях  x1 + x2 ≤ 5 2 x + x ≤ 9 2  1  x1 + 2 x2 ≤ 7 x ≥ 0  1  x2 ≥ 0, (3.13) (3.14) (3.15) (3.16) (3.17) где x1 и x2 − количество единиц продукции P1 и P2 . Так как в математической модели задачи использованы только две переменные x1 и x2 , ее можно решить графически. 54 Графический способ решения ЗЛП Графический (геометрический) способ решения ЗЛП обычно предполагает последовательное выполнение следующих действий: 1. Запись математических выражений, представляющих целевую функцию и ограничения, в виде равенств (уравнений). 2. Построение на графике прямых для уравнений, соответствующих ограничениям. 3. Определение области допустимых решений (ОДР) для задачи. 4. Построение на графике прямой, соответствующей целевой функции. 5. Параллельный перенос (перемещение) прямой, построенной для целевой функции, в одну из крайних точек ОДР для получения оптимального решения. Пример решения задачи производственного планирования графическим методом Решим задачу производственного планирования, рассмотренную выше, графическим способом. Вначале определим ОДР, в которой одновременно выполняются все ограничения, представленные в модели задачи. Для этого представим каждое из ограничений (3.13)−(3.17) в виде равенства (уравнения) и получим для них по паре точек, через которые проведем на графике отрезки прямых. 1-е ограничение (3.13): x1 + x2 = 5 ; при x1 = 0 , x2 = 5 ; при x2 = 0 , x1 = 5 , т.е. получим пару точек с координатами (0; 5) и (5; 0). 2-е ограничение (3.14): 2 x1 + x2 = 9 ; при x1 = 0 , x2 = 9 ; при x2 = 0 , x1 = 4,5 , т.е. получим пару точек с координатами (0; 9) и (4,5; 0). 3-е ограничение (3.15): x1 + 2 x2 = 7 ; при x1 = 0 , x2 = 3,5 ; при x2 = 0 , x1 = 7 , т.е. получим пару 4-е ограничение (3.16): x1 = 0 ; точек с координатами (0; 3,5) и (7; 0). прямая, совпадающая с осью Ox2 . 5-е ограничение (3.17): x2 = 0 ; прямая, совпадающая с осью Ox1 . 55 Таким образом, ОДР задачи представляет собой выпуклый пятиугольник ABCDE, показанный на рис. 7. x2 9 8 7 6 5 4 ∇Z B 3 C 2 D 1 E A O 1 2 3 4 5 6 7 8 9 x1 Рис. 7. Графический способ решения ЗЛП В качестве уравнения для целевой функции можно использовать выражение 3 x1 + 4 x2 = 12 , правая часть которого равняется произведению коэффициентов при неизвестных. Полагая x1 = 0 , получим x2 = 3 . Аналогично, при x2 = 0 , получим x1 = 4 . Следовательно, прямая для целевой функции проходит через пару точек с координатами (0; 3) и (4; 0). На рисунке эта прямая обозначена пунктиром. Направление параллельного переноса прямой, представляющей целевую функцию, определяется вычислением градиента функции Z :  ∂F ∂F   = (3;4) , ∇Z ( X ) =  ; ∂ x ∂ x  1 2  показывающего направление наискорейшего возрастания функции. Вектор, начало которого совпадает с началом системы координат, а конец имеет коорди- 56 наты (3; 4), задает направление переноса. Имеется строгое математическое доказательство того, что оптимальное решение задачи находится в одной из угловых (крайних) точек ОДР (см., например, теорему 3.3 в [9]). Перемещая прямую для целевой функции параллельно самой себе в направлении, заданном вектором-градиентом, получим, что такой точкой является вершина пятиугольника C, имеющая координаты (3; 2). Таким образом, оптимальный план для данной задачи составит 3 единицы продукции P1 и 2 единицы продукции P2 , от реализации которых предприятие получит максимум прибыли, равный 17 денежным единицам. Анализ чувствительности модели задачи производственного планирования После того, как найдено оптимальное решение задачи производственного планирования, можно выполнить анализ его чувствительности к изменениям исходных данных модели. В частности, целесообразно выяснить следующее [16]: 1. На сколько можно увеличить запас некоторого вида сырья для улучшения полученного оптимального плана? 2. На сколько можно снизить запас некоторого вида сырья при сохранении полученного оптимального плана? 3. Увеличение запасов какого вида сырья наиболее выгодно? 4. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменение оптимального решения? Прежде всего выполним классификацию ограничений, разделив их на активные (или связывающие) и неактивные (или несвязывающие). Активные ограничения соответствуют прямым, проходящим через точку, представляющую оптимальное решение (на рис. 8 это вершина C пятиугольника ABCDE). Неактивные ограничения соответствуют прямым, которые ограничивают ОДР, но не проходят через точку оптимального решения. В данном случае активными являются 1-е и 3-е ограничения, поскольку соответствующие им прямые проходят через точку, координаты которой и дают оптимальный производственный план. Активные ограничения лимитируют запасы сырья S1 и S 3 , которые логично отнести к разряду дефицитных, тогда как 57 неактивное 2-е ограничение ассоциируется с видом сырья S 2 , запас которого имеется в некотором избытке, т.е. оно является недефицитным. x2 9 S2 8 7 6 L 5 4 A3 S1 B A1 3 C K 2 D 1 S3 E A O ∇Z ( X ) 1 2 3 4 5 6 7 8 9 x1 Рис. 8. Анализ чувствительности модели задачи Вначале рассмотрим влияние увеличения запасов сырья S1 (1-е ограничение) на улучшение полученного оптимального плана. Из рисунка видно, что при увеличении запаса этого вида сырья соответствующая прямая (в частности, отрезок СD) перемещается вверх параллельно самой себе, постепенно стягивая в точку треугольник CKD. В точке K, соответствующей оптимальному решению, активными являются 2-е и 3-е ограничения, а 1-е ограничение становится неактивным. Поэтому запас сырья S1 не следует увеличивать сверх того предела, когда ограничение становится неактивным. Это предельное значение рассчитывается путем подстановки координат точки K(11/3; 5/3) в левую часть 1-го ограничения: 11 5 16 1⋅ + 1⋅ = , 3 3 3 58 11 5 53 + 4⋅ = . 3 3 3 Аналогично рассматривается вопрос о целесообразности увеличения дефицитного сырья S 3 . Из рисунка видно, что при увеличении этого вида сырья Z (K ) = 3 ⋅ соответствующая прямая (в частности отрезок BC), перемещается вверх параллельно самой себе. В точке L 3-е ограничение становится неактивным, поэтому объем сырья S 3 не следует увеличивать сверх этого предела. Это предельное значение рассчитывается путем подстановки координат точки L(0; 5) в левую часть 3-го ограничения: 1 ⋅ 0 + 2 ⋅ 5 = 10 , Z ( L ) = 3 ⋅ 0 + 4 ⋅ 5 = 20 . Таким образом, предельные запасы для сырья S1 и S 3 составляют соот1 и 10 единиц соответственно. Дальнейшее повышение этих запа3 сов нецелесообразно, поскольку не приведет к улучшению оптимального решения задачи. Рассмотрим теперь вопрос об уменьшении запаса недефицитного сырья S 2 (2-е ограничение). Из рисунка видно, что, не изменяя оптимального реше- ветственно 5 ния, соответствующую прямую (в частности, отрезок KE) можно перемещать параллельно самой себе до пересечения с точкой C. Уменьшение запасов сырья S 2 до величины 2 ⋅ 3 + 1 ⋅ 2 = 8 никак не повлияет на оптимальность полученного ранее решения. Результаты проведенного анализа представлены в табл. 9 [16]. Таблица 9 Сырье Тип сырья Макс. изменение запаса, Макс. изменение прибыли, ∆S i ∆Z (X ) S1 Дефицитное 16 / 3 − 5 = 1 / 3 53 / 3 − 51 / 3 = 2 / 3 S2 Недефицитное 9 −8 =1 17 − 17 = 0 S3 Дефицитное 10 − 7 = 3 20 − 17 = 3 Для ответа на третий вопрос введем характеристики ценности каждой дополнительной единицы сырья. Обозначим ценность дополнительной единицы i -го вида сырья через Yi , где 59 Yi = ∆Z ( X ) , ∆S i i = 1, 2, 3. Подставляя в данную формулу значения, приведенные в таблице выше, получаем следующие величины для ценности каждой дополнительной единицы каждого типа сырья: Y1 = 2, Y2 = 0, Y3 = 1 . Полученные результаты свидетельствуют, что дополнительные вложения в первую очередь следует направлять на закупку сырья S1 и лишь затем − на закупку сырья S 3 . Для ответа на четвертый вопрос опять обратимся к рис. 8. Из него видно, что при небольшом изменении коэффициентов целевой функции с1 и с2 прямая Z ( X ) = 17 вращается вокруг точки C. Таким образом, точка C будет оставаться оптимальной до тех пор, пока прямая Z ( X ) не выйдет за пределы, определяемые 1-м и 3-м ограничениями, т.е. пока вектор-градиент ∇Z (X ) будет находиться между векторами-нормалями A1 и A3 к прямым, соответствующим 1-му и 3-му ограничениям. Определим сначала диапазон изменения коэффициента с1 при фиксированном коэффициенте с2 ( с2 =4). Тангенсы углов наклона для векторов ∇Z (X ) , A1 , A3 соответственно равны: tg (α ) = c2 / c1 , tg (α1 ) = 1 , tg (α 3 ) = 2 . Поэтому диапазон изменения коэффициента с1 в целевой функции определится из соотношения 1 ≤ с2 / c1 ≤ 2 , т.е. 2 ≤ c1 ≤ 4 . Диапазон изменения коэффициента с2 при фиксированном значении с1 ( с1 =3) определяется аналогично, т.е. 3 ≤ c2 ≤ 6 . Решение ЗЛП симплекс-методом Симплекс-метод − универсальный метод решения ЗЛП, разработанный в 1949 г. американским математиком Дж. Данцигом. В его основе лежит идея последовательного улучшения полученного решения, для реализации которого необходимы [9]: 1) способ определения какого-либо первоначального допустимого базисного решения задачи; 2) правило перехода к лучшему (по крайней мере, не худшему) решению; 3) критерий проверки оптимальности найденного решения. 60 Для использования симплекс-метода ЗЛП должна быть приведена к каноническому (стандартному) виду, т.е. система ограничений ее модели (за исключением тривиальных, или естественных ограничений) должна быть представлена в виде уравнений (равенств). Переход к канонической ЗЛП (КЗЛП) выполняется следующим образом [20]: − ограничения, представленные неравенствами, преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных xk (k = n, n + m) , которые одновременно входят в целевую функцию с коэффициентом 0, т.е. не оказывают влияния на ее значение; − переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных, т.е. x j = x j − x j , ( x j ≥ 0, x j ≥ 0) . Ниже рассмотрен пример использования симплекс-метода для решения задачи производственного планирования как частного случая общей задачи линейного программирования (ОЗЛП). Пример решения задачи производственного планирования симплекс-методом Решим симплекс-методом задачу, математическая модель которой представлена соотношениями (3.12) − (3.17). Прежде всего, преобразуем с помощью дополнительных переменных неравенства (3.13) − (3.15) в уравнения. В данном случае все дополнительные переменные (их число равно 3) вводятся со знаком «плюс», так как рассматриваемые неравенства представляют собой неравенства вида «меньше или равно». Получим систему ограничений в виде:  x1 + x2 + x3 = 5  (3.18) 2 x1 + x2 + x4 = 9  x + 2 x + x = 7. 2 5  1 Для нахождения первоначального базисного решения разобьем переменные на две группы − основные и не основные (вспомогательные). Для этого можно воспользоваться следующим простым правилом для определения основных переменных [20]: в качестве основных переменных на первом шаге следует выбрать (если это возможно) такие m переменных, каждая из которых вхо- 61 дит только в одно из m уравнений системы ограничений, при этом нет таких уравнений, в которые не входит ни одна из этих переменных. Введенные выше дополнительные переменные x3 , x4 и x5 удовлетворяют данному требованию. Кроме того, выбранные основные переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях уравнений, т.е. полученное на первом шаге базисное решение будет допустимым. I шаг. Основные переменные: x3 , x4 , x5 . Вспомогательные переменные: x1 , x2 . В системе уравнений (3.18) выразим основные переменные через вспомогательные, т.е. получим следующую систему уравнений:  x3 = 5 − x1 − x 2   x 4 = 9 − 2 x1 − x2 x = 7 − x − 2x . 1 2  5 (3.19) Приравняв вспомогательные переменные к нулю, т.е. положив x1 = 0 и x2 = 0 , получим допустимое базисное решение X 1 = (0; 0; 5; 9; 7) . Это решение соответствует совпадающей с началом системы координат O (0; 0) вершине A пятиугольника ABCDE, который представляет ОДР задачи (см. рис. 7 выше). Проверим, не является ли полученное допустимое базисное решение оптимальным. Для этого рассмотрим выражение для целевой функции Z ( X ) = 3 x1 + 4 x2 , которое для найденного решения X 1 равняется значению функции Z1 = Z ( X 1 ) = 0 . Очевидно, что значение функции Z ( X ) можно увеличить путем увеличения любой из вспомогательных переменных, входящих в выражение для Z с положительным коэффициентом. Это можно осуществить, перейдя к новому допустимому базисному решению, в котором эта переменная будет основной, т.е. сможет принимать не нулевое, а положительное значение (если новое решение окажется вырожденным, то целевая функция сохранит свое значение). При таком переходе одна из основных переменных становится вспомогательной, что в геометрической трактовке означает переход к соседней вершине пятиугольника ABCDE, в которой значение целевой функции «лучше» (по крайней мере «не хуже»). В данном случае для увеличения значения Z можно переводить в основные переменные либо x1 , либо x2 , так как обе эти переменные входят в выражение для Z со знаком «плюс». Выберем переменную x2 , так как ее коэффициент больший, чем у x1 . 62 Система уравнений (3.13) − (3.15) накладывает ограничения на рост переменной x2 . Поскольку все переменные должны оставаться неотрицательными, выполняются следующие неравенства (при этом x1 = 0 как вспомогательная переменная):   x2 ≤ 5  x3 = 5 − x 2 ≥ 0   откуда  x2 ≤ 9 (3.20)  x4 = 9 − x2 ≥ 0  x = 7 − 2x ≥ 0 7 2  5  x2 ≤ = 3,5.  2 Очевидно, что сохранение условия неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из границ, полученных для всех уравнений (3.20). В данном случае возможное наибольшее значение для переменной x2 определяется как x2 = min{5; 9; 3,5} = 3,5 . При x2 = 3,5 основная переменная x5 обращается в нуль и переходит во вспомогательные. Третье уравнение системы (3.19), где достигается наибольшее возможное значение переменной, переводимой в основные (т.е. где оценка минимальна), называется разрешающим (подчеркнуто). II шаг. Основные переменные: x2 , x3 , x4 . Вспомогательные переменные: x1 , x5 . Выразим новые основные переменные через новые вспомогательные переменные, начиная с разрешающего уравнения:  x2 = (7 − x1 − x5 ) / 2   x3 = 5 − x1 − (7 − x1 − x5 ) / 2  x = 9 − 2 x − (7 − x − x ) / 2  4 1 1 5 (3.21)  x2 = 3,5 − 0,5 x1 − 0,5 x5   x3 = 1,5 − 0,5 x1 + 0,5 x5   x4 = 5,5 − 1,5 x1 + 0,5 x5 . (3.22) или Второе базисное решение X 2 = {0; 3,5; 1,5; 5,5; 0} является допустимым и соответствует вершине B(0; 3,5) на рис. 7. Переход от решения X 1 к решению X 2 геометрически можно интерпретировать как переход от вершины А(0; 0) к вершине B(0; 3,5) пятиугольника ABCDE. 63 Проверим, не является ли оптимальным полученное решение. Запишем целевую функцию, выраженную через вспомогательные переменные, использующиеся на данном шаге: Z 2 = Z ( X 2 ) = 3 x1 + 4 x2 = 3 x1 + 4 (3,5 − 0,5 x1 − 0,5 x5 ) = (3.23) = 3 x1 + 14 − 2 x1 − 2 x5 = x1 − 2 x5 + 14 = 14. Убедимся, что полученное решение лучше, чем предыдущее (т.е. значение Z увеличилось): ∆Z1 = Z 2 − Z1 = 14 − 0 = 14 . Вычисленное значение Z ( X 2 ) не является максимальным, поскольку в выражении для целевой функции (3.23) имеется переменная x1 с положительным коэффициентом, равным 1. Система уравнений (3.22) накладывает ограничения на рост переменной x1 . Обеспечивая выполнение условия неотрицательности переменных, запишем следующие неравенства:  x2 = 3,5 − 0,5 x1 − 0,5 x5 ≥ 0   x3 = 1,5 − 0,5 x1 + 0,5 x5 ≥ 0  x = 5,5 − 1,5 x + 0,5 x ≥ 0, 1 5  4 откуда, полагая x5 = 0 , получим (3.24)   x1 ≤ 7  (3.25)  x1 ≤ 3  11  x1 ≤ .  3 Полученная система неравенств (3.25) определяет наибольшее значение для переменной x1 : x1 = min{ 7; 3; 11 / 3} = 3 . При x1 = 3 переменная x3 обращается в нуль, поэтому ее предполагается перевести во вспомогательные переменные. Второе уравнение системы (3.22) является разрешающим, переменная x3 переходит во вспомогательные переменные, x1 − в основные. III шаг. Основные переменные: x1 , x2 , x4 . Вспомогательные переменные: x3 , x5 . Как и на шаге II, выразим новые основные переменные через новые вспомогательные переменные, начиная с разрешающего уравнения. 0,5 x1 = 1,5 − x3 + 0,5 x5 , x1 = 3 − 2 x3 + x5 . Подставляем выражение для x1 в следующее уравнение: (3.26) 64 x2 = 3,5 − 0,5 x1 − 0,5 x5 = 3,5 − 0,5 (3 − 2 x3 + x5 ) − 0,5 x5 = = 3,5 − 1,5 + x3 − 0,5 x5 − 0,5 x5 = 2 + x3 − x5 , x2 = 2 + x3 − x5 . (3.27) Подставляем выражение для x1 в следующее уравнение: x4 = 5,5 − 1,5 x1 + 0,5 x5 = 5,5 − 1,5 (3 − 2 x3 + x5 ) + 0,5 x5 = = 5,5 − 4,5 + 3 x3 − 1,5 x5 + 0,5 x5 = 1 + 3 x3 − x5 , x4 = 1 + 3 x3 − x5 . (3.28) В результате преобразований (3.26) − (3.28) получаем следующую систему уравнений:  x1 = 3 − 2 x3 + x5   x 2 = 2 + x3 − x5  x = 1 + 3x − x .  4 3 5 (3.29) Базисное решение X 3 = (3; 2; 0; 1; 0) соответствует вершине C(3; 2) пятиугольника ABCDE, представляющего ОДР задачи (см. рис. 7 выше). Выражаем целевую функцию через вспомогательные переменные: Z 3 = Z ( X 3 ) = 3 x1 + 4 x2 = 3 (3 − 2 x3 + x5 ) + 4 (2 + x3 − x5 ) = (3.30) = 9 − 6 x3 + 3 x5 + 8 + 4 x3 − 4 x5 = 17 − 2 x3 − x5 . Полагая x3 = 0 и x5 = 0 , вычислим значение целевой функции Z 3 = Z ( X 3 ) = 17. Убедимся, что полученное решение лучше, чем предыдущее: ∆Z 2 = Z 3 − Z 2 = 17 − 14 = 3 , т.е. значение целевой функции возросло по сравнению со значением, вычисленным на шаге II. Кроме того, третье допустимое базисное решение является оптимальным, так как коэффициенты вспомогательных переменных в выражении для целевой функции (3.30) являются отрицательными, т.е. рост значений x3 и x5 не приведет к увеличению значения Z . Таким образом, оптимальным решением задачи является x1 = 3 и x2 = 2 , обеспечивающие оптимальное значение целевой функции Z ( x1 , x2 ) = 17 . С учетом экономического смысла рассмотренной задачи можно сделать следующий вывод: для получения максимальной прибыли, равной 17 денежным единицам, предприятие должно выпускать и реализовать 3 единицы продукта P1 и 2 единицы продукта P2 . При этом дополнительные переменные x3 , x4 и x5 показывают разницу между запасами сырья (ресурсов) каждого вида и их потреблением, т.е. остатки ресурсов. При выполнении оптимального плана производства 65 x3 = x5 = 0 , т.е. сырье S1 и S 3 расходуется полностью, а остаток сырья S 2 равен 1 единице. В заключение сформулируем критерий оптимальности решения при отыскании максимума линейной функции, а также определим возможные подходы к отысканию минимума линейной функции. Если при отыскании максимума линейной функции в ее выражении, содержащем вспомогательные переменные, отсутствуют положительные коэффициенты, полученное решение оптимально. При поиске минимума линейной функции F можно использовать следующие два пути [9]: 1) отыскать максимум функции Z , полагая Z = − F и учитывая, что Fmin = − Z max ; 2) модифицировать симплекс-метод: на каждом шаге уменьшать линейную функцию за счет той вспомогательной переменной, которая входит в выражение линейной функции с отрицательным коэффициентом. 66 Глава 3. Транспортная задача ПН B1 B2 B3 B4 B5 Запасы О A 1 2 3 4 2 4 140 A2 8 4 1 4 1 180 A3 9 7 3 7 2 160 Потребности 60 70 120 130 100 480 ПО О Потребность в товаре в пункте назначения B2 Рис. 9. Пример транспортной таблицы Запас товара в пункте отправления A3 Стоимость транспортировки одной единицы товара из пункта отправления A1 в пункт назначения B1 К ЗЛП транспортного типа (кратко: транспортной задаче − ТЗ) приходят при рассмотрении различных практических ситуаций, связанных с составлением наиболее экономичного плана перевозок продукции, управления запасами, назначением персонала на рабочие места, оборотом наличного капитала и многими другими. Цель ТЗ в изначальном виде − поиск самых низкозатратных схем транспортировки товарных запасов или поставок от многих поставщиков (пункты отправления) ко многим потребителям (пункты назначения). Поставщиками могут быть фабрики, склады, отделы или другие места, из которых отправляются товары. Потребителями также могут быть фабрики, склады, отделы или любые другие места, которые получают товары. Информация, необходимая для использования модели ТЗ, включает следующее [21]: 1. Список пунктов отправления (ПО) и пропускная способность каждого из них или количество поставок за определенный период. 2. Список пунктов назначения (ПН) и их показатели спроса за определенный период. 3. Стоимость транспортировки единицы товара из каждого пункта отправления в каждый пункт назначения. Эта информация представляется в виде так называемой транспортной таблицы (рис. 9). 67 Ниже рассмотрена общая постановка ТЗ и выполнено построение ее математической модели [16]. Экономико-математическая модель ТЗ Постановка задачи. Некоторый однородный товар (продукт, груз), находящийся у m поставщиков Ai в количестве ai единиц (i = 1,2,..., m) необходимо доставить n потребителям B j в количестве b j единиц ( j = 1,2,..., n). Известна стоимость cij перевозки единицы товара от i -го поставщика к j -му потребителю. Необходимо составить план перевозки, имеющий минимальную стоимость. Основное предположение, используемое при построении модели, состоит в том, что величина транспортных расходов на каждом маршруте прямо пропорциональна количеству единиц перевозимого товара. Построение математической модели. Обозначим через xij количество единиц товара, запланированных к перевозке от i -го поставщика к j -му потребителю. Тогда математическая модель ТЗ формулируется следующим образом: m n Z ( X ) = ∑∑ cij xij → min (4.1) i =1 j =1 при ограничениях n ∑x j =1 ij m ∑x i =1 ij ≤ ai , (i = 1,2,..., m) ; (4.2) ≥ b j , ( j = 1,2,..., n) ; (4.3) xij ≥ 0 , ( i = 1,2,..., m; j = 1,2,..., n ). (4.4) Ограничения (4.2) означают, что суммарный объем перевозок от i -го поставщика не может превышать имеющегося у него запаса товара. Ограничения (4.3) означают, что суммарные перевозки товара j -му потребителю должны полностью удовлетворить его потребности в товаре. Ограничения (4.4) исключают обратные перевозки. Из ограничений (4.2) и (4.3) следует, что m n ∑ a ≥ ∑b i =1 Если имеет место равенство i j =1 j . 68 m n ∑ a = ∑b i =1 i j =1 j , (4.5) то модель называется сбалансированной транспортной моделью. В сбалансированной модели ограничения (4.2) − (4.3) имеют вид равенств. В реальных условиях запас товара не всегда равен спросу (потребности), но транспортную модель всегда можно сбалансировать. В случае превышения запаса над спросом, т.е. если m n ∑ a > ∑b i =1 i j =1 j , вводится фиктивный (n + 1) -й потребитель со спросом m n i =1 j =1 bn+1 = ∑ ai − ∑ b j , а соответствующие стоимости ci , n +1 (i = 1,2,..., m) считаются равными нулю. Аналогично, при m n i =1 j =1 ∑ ai < ∑ b j вводится фиктивный (m + 1) -й поставщик с запасом товара n m j =1 i =1 am+1 = ∑ b j − ∑ ai , а соответствующие стоимости cm +1, j ( j = 1,2,..., n) считаются равными нулю. Таким образом, исходная задача сводится к сбалансированной ТЗ, из оптимального плана которой получается оптимальный план несбалансированной ТЗ. Примечание 1. Несбалансированную ТЗ называют также открытой ТЗ, тогда как сбалансированную ТЗ − закрытой ТЗ. Примечание 2. Стремление сбалансировать ТЗ обусловлено возможностью применить в этом случае эффективный вычислительный метод. Ниже приведен пример сбалансированной ТЗ и дано ее решение с подробными пояснениями [16]. Задача № 11. На трех базах (пунктах отправления) A1 , A2 , A3 находится однородный груз в количествах, соответственно равных 140, 180 и 160 единицам. Этот груз требуется перевести в пять пунктов назначения B1 , B2 , B3 , B4 , B5 соответственно в количествах 60, 70, 120, 130 и 100 единиц. Стоимости перевозки единицы груза из каждого пункта отправления в соответствующие пункты назначения указаны в табл. 10. 69 Таблица 10 ПН B1 B2 B3 B4 B5 Запасы ПО 3 2 2 4 4 140 A1 x11 x12 x14 x13 4 8 x15 4 1 1 180 A2 x21 x22 x24 x23 9 3 7 x25 2 7 160 A3 x31 Потребности x32 60 x33 70 120 x34 130 x35 100 480 Решение. Построим математическую модель данной ТЗ. Обозначим через xij количество единиц груза, которое планируется перевести из пункта отправления Ai (i = 1, 2, 3) в пункт назначения B j ( j = 1, 2, 3, 4, 5) . Тогда целевая функция для ТЗ запишется как 2 x11 + 3 x12 + 4 x13 + 2 x14 + 4 x15 + 8 x21 + 4 x22 + x23 + 4 x24 + x25 + 9 x31 + 7 x32 + 3 x33 + 7 x34 + 2 x35 → min при ограничениях  x11 + x12 + x13 + x14 + x15 = 140   x21 + x22 + x23 + x24 + x 25 = 180  x31 + x32 + x33 + x34 + x35 = 160   x11 + x21 + x31 = 60   x12 + x22 + x32 = 70  x + x + x = 120 23 33  13  x14 + x24 + x34 = 130   x15 + x25 + x35 = 100  xij ≥ 0 (i = 1, 2, 3; j = 1, 2, 3, 4, 5).  70 Число неизвестных переменных xij в ТЗ с m поставщиками и n потребителями равно m ⋅ n , а число уравнений в системе (4.2) − (4.3) равно m + n . Так как ТЗ является сбалансированной, т.е. выполняется условие (4.5), число линейно независимых уравнений равно m + n − 1 . Следовательно, опорный план ТЗ может иметь не более m + n − 1 отличных от нуля неизвестных. Существуют несколько схем построения первоначального опорного плана: метод «северо-западного угла» (СЗУ), метод наименьшей стоимости, метод Фогеля. Эффективность данных методов различается: в общем случае метод Фогеля дает наилучшее решение (в ряде случаев − оптимальное), а метод СЗУ − наихудшее. Все методы, используемые для нахождения первоначального опорного плана, отличаются только способом выбора клетки для заполнения, а само заполнение происходит одинаково независимо от используемого метода. Следует помнить, что перед нахождением опорного плана транспортная задача должна быть сбалансирована. Построение опорного плана ТЗ методом СЗУ В данной ТЗ m = 3 , n = 5 , следовательно, опорный план должен иметь не более m + n − 1 = 3 + 5 − 1 = 7 отличных от нуля переменных. Следуя методу СЗУ, начинают с того, что приписывают переменной x11 , расположенной в верхней левой клетке (СЗУ) таблицы, максимально возможное значение. После этого вычеркивают соответствующий столбец (строку), фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными 0. Если ограничения, представляемые столбцом и строкой, выполняются одновременно, то вычеркивают либо столбец, либо строку. Процесс продолжается до тех пор, пока не будут удовлетворены все потребители за счет запасов поставщиков. Применительно к данной ТЗ эта процедура приводит к виду, представленному в табл. 11. В результате получаем опорный план X 0 (семь занятых клеток таблицы):  60 70 10 0 0    X 0 =  0 0 110 70 0  . 0 0 0 60 100   Согласно полученному опорному плану общая стоимость перевозки груза составляет 71 Z ( X 0 ) = 2 ⋅ 60 + 3 ⋅ 70 + 4 ⋅ 10 + 1 ⋅ 110 + 4 ⋅ 70 + 7 ⋅ 60 + 2 ⋅ 100 = 1380. Примечание. Если одновременно и столбец, и строка удовлетворяют ограничениям, очередная переменная, включаемая в базисное решение, обязательно имеет нулевое значение. Таблица 11 ПН B1 B2 B3 B4 B5 Запасы ПО 3 2 A1 60 70 A2 − − A3 Потребности 110 4 − 4 1 7 9 − 10 4 8 2 4 1 − 70 7 3 − − − 60 (60) (70) (120) (110) (130) (60) 2 100 (140) (80) (10) (180) (70) (160) (100) (100) 480 Построение опорного плана ТЗ методом наименьшей стоимости Согласно данному методу, выбирается переменная xij , которой соответствует наименьшая стоимость перевозки во всей таблице, и ей придается возможно большее количество перевезенного груза. Вычеркивается соответствующий столбец или строка. Если ограничения по столбцу (потребности, спрос) и строке (запасы, предложение) выполняются одновременно, то вычеркивается либо столбец, либо строка. После вычисления новых значений потребностей и запасов для всех невычеркнутых строк и столбцов процесс повторяется при возможно большем значении той переменной xij , которой соответствует наименьшая стоимость перевозки среди невычеркнутых. Процедура завершается, когда остается одна строка или один столбец (табл. 12). В результате получаем опорный план X 0 (семь занятых клеток таблицы): 72 80 0   60 0 0   X 0 =  0 0 120 0 60  .  0 70 0 50 40   Согласно полученному опорному плану, общая стоимость перевозок груза составляет Z ( X 0 ) = 2 ⋅ 60 + 2 ⋅ 80 + 1 ⋅ 120 + 1 ⋅ 60 + 7 ⋅ 70 + 7 ⋅ 50 + 2 ⋅ 40 = 1380. Таблица 12 ПН B1 B2 B3 B4 B5 Запасы ПО 3 2 A1 − − 60 4 8 A2 − − A3 Потребности − (60) 70 (70) 4 − 120 (140) (80) 1 (180) (60) 2 (160) (120) (50) 60 7 3 4 − 80 1 7 9 2 4 − 50 40 (120) (130) (50) (100) (40) 480 Поиск опорного плана ТЗ методом Фогеля На каждом шаге метода Фогеля для каждой i -й строки вычисляются штрафы d i как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы d j для каждого j -го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем максимальному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальной стоимостью перевозки (табл. 13). Если в таблице существует несколько одинаковых по величине максимальных штрафов, то в соответствующих строках или столбцах выбирается одна невычеркнутая с минимальной стоимостью перевозки. 73 Если клеток с минимальной стоимостью также несколько, то из них выбирается клетка (i, j ) с максимальным суммарным штрафом, т.е. суммой штрафов по i -й строке и j -му столбцу. Если в таблице существует несколько клеток с минимальной стоимостью и соответствующими им одинаковыми максимальными суммарными штрафами, то выбирается клетка, обеспечивающая перевозку максимального количества груза из возможных вариантов. Таблица 13 ПН B1 B2 B3 B4 B5 ПО 2 3 4 2 4 A1 − 60 A2 − 8 4 10 9 A3 Потребности Штрафы для столбцов, dj − 120 7 − 60 (60) (70) (60) 3 − 4 1 − 50 − (140) (80) Штрафы для строк, di 1 1 1 1 − − 3 − 1 1 5 0 0 0 − − 80 1 Запасы 7 2 (180) (60) (10) (160) (60) 100 (120) (130) (100) (50) 6 1 2 2 1 − 1 2 2 1 − 1 − 2 1 − 1 − − − 1 − 2 2 − 3 − − − − − − − − − 480 Из двух столбцов с одинаковой величиной штрафа выбираем тот, у которого есть клетка с минимальной стоимостью перевозки В результате получается опорный план X 0 (семь занятых клеток таблицы): 74 80 0   60 0 0   X 0 =  0 10 120 50 0  .  0 60 0 0 100   Согласно полученному опорному плану, общая стоимость перевозок груза составляет Z ( X 0 ) = 2 ⋅ 60 + 4 ⋅10 + 7 ⋅ 60 + 1 ⋅120 + 2 ⋅ 80 + 4 ⋅ 50 + 2 ⋅ 100 = 1260. Определение оптимального плана ТЗ методом потенциалов Один из эффективных методов решения ТЗ, получивший название метода потенциалов, был предложен в 1949 г. советскими математиками Л.В. Канторовичем и М.К. Гавуриным. Позже аналогичный метод разработал Дж. Данциг, основываясь на общих идеях линейного программирования. Подобно тому, как ТЗ − частный случай ЗЛП, так и метод потенциалов является разновидностью симплекс-метода. Он представляет собой итеративный процесс, на каждом шаге которого рассматривается некоторый текущий базисный план, проверяется его оптимальность и, если необходимо, определяется переход к следующему − лучшему базисному плану [20]. Теорема. Если для некоторого опорного плана ТЗ X * = ( xij* ) mn существуют такие числа u1* , u2* , …, um* , v1* , v2* , …, vn* , что ui* + v*j = cij − для базисных переменных (занятых клеток), ui* + v*j ≤ cij − для остальных переменных (свободных клеток), то X * = ( xij* ) mn − оптимальный план ТЗ. Доказательство теоремы приведено в [9]. Числа ui* и ui* называются потенциалами поставщиков и потребителей соответственно. Данная теорема позволяет получить решение ТЗ. После нахождения опорного плана необходимо вычислить значения потенциалов ui* и ui* . Так как для базисных переменных имеет место система m + n − 1 уравнений с m + n неизвестными ∆*ij = ui* + v*j − cij = 0 , то одну из неизвестных переменных можно приравнять к нулю и затем последовательно найти значения остальных неизвестных. Далее вычисляют симплексные разности для всех остальных переменных по формуле 75 ∆ ij = ui + v j − cij . Если среди них нет положительных значений, то найденный опорный план является оптимальным. В противном случае выбирают ∆ lk = max{∆ ij } и переменную xlk включают в базис. Для определения переменной, исключаемой из базиса, строят замкнутый цикл и перераспределяют поставки. Определение. Циклом называется ломаная линия, вершины которой расположены в занятых клетках таблицы (рис. 10). x lk − + + − x pq − + Рис. 10. Примеры циклов Цикл начинается и заканчивается клеткой, соответствующей включаемой в базис переменной xlk . Перемещение поставок в цикле производится по следующему правилу: 1. Заполняемой клетке, соответствующей переменной xlk , приписывается знак «+», а всем остальным клеткам − поочередно знаки «−» и «+». 2. В заполняемую клетку переносят меньшее из чисел xij , стоящих в клетках со знаком «−». Одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком «+», и вычитают из чисел, стоящих в клетках со знаком «−». 3. Клетка со знаком «−», в которой стояло минимальное число, считается свободной, а соответствующая ей переменная x pq исключается из базиса. Примечание. Если минимальное число x pq достигается более чем в одной клетке, то освобождают лишь одну из них, а остальные оставляют занятыми нулевыми поставками. 76 Поиск оптимального плана ТЗ. Перейдем к определению оптимального плана перевозок для рассматриваемой ТЗ. Итерация 1. Пусть получен первоначальный опорный план, соответствующий табл. 11, т.е. опорный план, полученный методом СЗУ. В соответствии с количеством поставщиков и потребителей рассмотрим три переменные u1 , u2 , u3 − потенциалы поставщиков и пять переменных v1 , v2 , v3 , v4 , v5 − потенциалы потребителей. Для каждой занятой клетки в табл. 4.2 запишем уравнения вида ui + v j = cij , где cij − стоимость перевозки единицы груза для данной клетки; ui и v j − соответственно потенциалы поставщика и потребителя. u1 + v1 = 2 ; u 2 + v3 = 1 ; u1 + v2 = 3 ; u3 + v 4 = 7 ; u 2 + v4 = 4 ; u3 + v5 = 2 . u1 + v3 = 4 ; Полагая u1 = 0 (так как имеются 8 переменных и 7 уравнений), получаем v1 = 2 , v2 = 3 , v3 = 4 . Подставляем полученные значения в другие уравнения системы: u2 + 4 = 1 ; u 2 = −3 ; − 3 + v4 = 4 ; v4 = 7 ; u3 + 7 = 7 ; u3 = 0 ; 0 + v5 = 2 ; v5 = 2 . Таким образом, имеем следующие значения потенциалов поставщиков и потребителей: u1 = 0 ; u 2 = −3 ; u3 = 0 ; v1 = 2 ; v2 = 3 ; v3 = 4 ; v4 = 7 ; v5 = 2 . Далее вычисляем симплексные разности для остальных переменных по следующей формуле: ∆ ij = ui + v j − cij . ∆14 = 0 + 7 − 2 = 5; ∆15 = 0 + 2 − 4 = −2; ∆ 21 = −3 + 2 − 8 = −9; ∆ 22 = −3 + 3 − 4 = −4; ∆ 25 = −3 + 2 − 1 = −2; ∆ 31 = 0 + 2 − 9 = −7; ∆ 33 = 0 + 4 − 3 = 1. ∆ 32 = 0 + 3 − 7 = −4; 77 Таким образом, имеем следующие значения симплексных разностей: ∆ ij = {5, − 2, − 9, − 4, − 2, − 7, − 4,1}. ∆ lk = max{∆ ij } = ∆14 = 5 , xlk = x14 = 10 . Подставляем полученные значения в таблицу с опорным планом и получаем табл. 14 (на сером фоне представлены значения симплексных разностей для соответствующих значений потенциалов поставщиков и потребителей). Таблица 14 ПН ПО B1 B2 B3 B4 B5 v1 = 2 v2 = 3 v3 = 4 v4 = 7 v5 = 2 3 2 A1 60 70 − u 2 = −3 A3 u3 = 0 Потребности − -9 − -7 60 8 − 9 − -4 70 7 − 1 120 − − 4 140 -3 4 1 110 + -4 5 + 4 2 − 10 u1 = 0 A2 4 Запасы − 70 1 180 -2 7 3 60 130 2 100 100 160 480 Пометим заполняемую клетку (1, 4) знаком «+», а затем поочередно клетки (2, 4), (2, 3) и (1, 3) − соответственно знаками «+», «−» и «+». Среди клеток таблицы, образующих цикл и помеченных знаком «−», меньшее значение (10) содержится в клетке (1, 3). Прибавим это значение к соответствующим числам, стоящим в клетках цикла, помеченных знаком «+», и вычтем из чисел, стоящих в клетках, помеченных знаком «−». Освободим клетку (1, 3), в которой стояло минимальное число, а соответствующую ей переменную x13 исключим из базиса. Получаем новый опорный план ТЗ: 78 10 0   60 70 0   X 1 =  0 0 120 60 0  . 0 0 0 60 100   Z ( X 1 ) = 2 ⋅ 60 + 3 ⋅ 70 + 2 ⋅ 10 + 1 ⋅ 120 + 4 ⋅ 60 + 7 ⋅ 60 + 2 ⋅ 100 = 1330 . Среди полученных симплексных разностей для переменных в свободных клетках имеется положительное число: 1 в клетке (3, 3). Это означает, что найденный опорный план не является оптимальным. Итерация 2. Для каждой занятой клетки табл. 14 (с учетом сделанной перестановки) снова рассчитаем значения потенциалов поставщиков и потребителей. u1 + v1 = 2 ; u 2 + v3 = 1 ; u3 + v 4 = 7 ; u1 + v2 = 3 ; u 2 + v4 = 4 ; u3 + v5 = 2 . u1 + v4 = 2 ; Полагая u1 = 0 , получаем v1 = 2 , v2 = 3 , v4 = 2 . Подставляем полученные значения в другие уравнения системы: u2 + 2 = 4 ; u2 = 2 ; 2 + v3 = 1 ; v3 = −1 ; u3 + 2 = 7 ; u3 = 5 ; 5 + v5 = 2 ; v5 = −3 . Таким образом, имеем следующие значения потенциалов поставщиков и потребителей: u1 = 0 ; u2 = 2 ; u3 = 5 ; v1 = 2 ; v2 = 3 ; v3 = −1 ; v4 = 2 ; v5 = −3 . Вычислим симплексные разности для остальных переменных: ∆13 = 0 − 1 − 4 = −5; ∆15 = 0 − 3 − 4 = −7; ∆ 21 = 2 + 2 − 8 = −4; ∆ 22 = 2 + 3 − 4 = 1; ∆ 25 = 2 − 3 − 1 = −2; ∆ 31 = 5 + 2 − 9 = −2; ∆ 32 = 5 + 3 − 7 = 1; ∆ 33 = 5 − 1 − 3 = 1. Таким образом, имеем следующие значения симплексных разностей: ∆ ij = {−5, − 7, − 4,1, − 2, − 2,1,1} . ∆ lk = max{∆ ij } = ∆ 22 = 1 , xlk = x22 = 60 . 79 Подставляем полученные значения в таблицу с опорным планом X 1 и получаем табл. 15. Пометим заполняемую клетку (2, 2) знаком «+», а затем поочередно клетки (1, 2), (1, 4) и (2, 4) − соответственно знаками «−», «+» и «−». Среди клеток, образующих цикл и помеченных знаком «−», меньшее значение (60) содержится в клетке (2, 4). Прибавим это значение к соответствующим числам, стоящим в клетках цикла, помеченных знаком «+», и вычтем из чисел, стоящих в клетках, помеченных знаком «−». Таблица 15 ПН ПО B1 B2 B3 B4 B5 v1 = 2 v2 = 3 v3 = −1 v4 = 2 v5 = −3 3 2 A1 60 − A2 u2 = 2 A3 u3 = 5 Потребности − -4 − -2 60 10 + 70 u1 = 0 8 -5 + 9 4 − 2 4 4 1 120 − 70 7 − 1 120 − 60 1 − 1 − -7 Запасы 4 140 1 180 -2 7 3 60 130 2 100 100 160 480 Освободим клетку (2, 4), в которой стояло минимальное число, а соответствующую ей переменную x24 исключим из базиса. Получаем новый опорный план ТЗ:  60 10 0 70 0    X 2 =  0 60 120 0 0  .  0 0 0 60 100    Z ( X 2 ) = 2 ⋅ 60 + 3 ⋅ 10 + 2 ⋅ 70 + 4 ⋅ 60 + 1 ⋅ 120 + 7 ⋅ 60 + 2 ⋅ 100 = 1270 . 80 Среди полученных значений симплексных разностей для переменных в свободных клетках имеются положительные числа: 1 в клетках (3, 2) и (3, 3). Это означает, что найденный опорный план не является оптимальным. Итерация 3. Для каждой занятой клетки табл. 15 (с учетом сделанной перестановки) снова рассчитаем значения потенциалов поставщиков и потребителей: u1 + v1 = 2 ; u 2 + v2 = 4 ; u3 + v 4 = 7 ; u1 + v2 = 3 ; u 2 + v3 = 1 ; u3 + v5 = 2 . u1 + v4 = 2 ; Полагая u1 = 0 , получаем v1 = 2 , v2 = 3 , v4 = 2 . Подставляем полученные значения в другие уравнения системы: u2 + 3 = 4 ; u2 = 1 ; 1 + v3 = 1 ; v3 = 0 ; u3 + 2 = 7 ; u3 = 5 ; 5 + v5 = 2 ; v5 = −3 . Таким образом, имеем следующие значения потенциалов поставщиков и потребителей: u1 = 0 ; u2 = 1 ; u3 = 5 ; v1 = 2 ; v2 = 3 ; v3 = 0 ; v4 = 2 ; v5 = −3 . Вычислим симплексные разности для остальных переменных: ∆13 = 0 + 0 − 4 = −4; ∆15 = 0 − 3 − 4 = −7; ∆ 21 = 1 + 2 − 8 = −5; ∆ 24 = 1 + 2 − 4 = −1; ∆ 25 = 1 − 3 − 1 = −3; ∆ 31 = 5 + 2 − 9 = −2; ∆ 32 = 5 + 3 − 7 = 1; ∆ 33 = 5 + 0 − 3 = 2. Таким образом, имеем следующие значения симплексных разностей: ∆ ij = {−2, − 7, − 5, − 1, − 3, − 2,1, 2}. ∆ lk = max{∆ ij } = ∆ 33 = 2 , xlk = x33 = 10 . Подставляем полученные значения в таблицу с опорным планом X 2 и получаем табл. 16. 81 Таблица 16 ПН ПО B1 B2 B3 B4 B5 v1 = 2 v2 = 3 v3 = 0 v4 = 2 v5 = −3 3 2 A1 60 − A2 u2 = 1 A3 u3 = 5 Потребности − -5 − -2 60 70 + 10 u1 = 0 8 -4 60 4 9 − 1 70 7 60 -1 120 − 60 4 140 1 180 -3 7 3 + 2 − -7 4 1 120 − + 2 4 Запасы 2 100 − 130 100 160 480 Пометим заполняемую клетку (3, 3) знаком «+», а затем поочередно клетки (2, 3), (2, 2), (1, 2), (1, 4) и (3, 4) − соответственно знаками «−», «+», «−», «+» и «−». Среди клеток, образующих цикл и помеченных знаком «−», меньшее значение (10) содержится в клетке (1, 2). Прибавим это значение к соответствующим числам, стоящим в клетках цикла, помеченных знаком «+», и вычтем из чисел, стоящих в клетках, помеченных знаком «−». Освободим клетку (1, 2), в которой стояло минимальное число, а соответствующую ей переменную x12 исключим из базиса. Получаем новый опорный план ТЗ:  60 0 0 80 0    X 3 =  0 70 110 0 0  .  0 0 10 50 100    Z ( X 3 ) = 2 ⋅ 60 + 2 ⋅ 80 + 4 ⋅ 70 + 1 ⋅ 110 + 3 ⋅ 10 + 7 ⋅ 50 + 2 ⋅ 100 = 1250 . Среди полученных значений симплексных разностей для переменных в свободных клетках имеются положительные числа: 1 в клетке (3, 2) и 2 в клетке (3, 3). Это означает, что найденный опорный план не является оптимальным. 82 Итерация 4. Для каждой занятой клетки табл. 16 (с учетом сделанной перестановки) снова рассчитаем значения потенциалов поставщиков и потребителей: u1 + v1 = 2 ; u 2 + v2 = 4 ; u3 + v3 = 3 ; u1 + v4 = 2 ; u 2 + v3 = 1 ; u3 + v 4 = 7 ; u3 + v5 = 2 . Полагая u1 = 0 , получаем v1 = 2 , v4 = 2 . Подставляем полученные значения в другие уравнения системы: u3 + 2 = 7 ; u3 = 5 ; 3 + v2 = 4 ; v2 = 1 ; 5 + v3 = 3 ; v3 = −2 ; 5 + v5 = 2 ; v5 = −3 . u2 − 2 = 1 ; u2 = 3 ; Таким образом, имеем следующие значения потенциалов поставщиков и потребителей: u1 = 0 ; u2 = 3 ; u3 = 5 ; v1 = 2 ; v2 = 1 ; v3 = −2 ; v4 = 2 ; v5 = −3 . Вычислим симплексные разности для остальных переменных: ∆12 = u1 + v2 − c12 = 0 + 1 − 3 = −2; ∆13 = u1 + v3 − c13 = 0 − 2 − 4 = −6; ∆15 = u1 + v3 − c15 = 0 − 3 − 4 = −7; ∆ 21 = u2 + v1 − c21 = 3 + 2 − 8 = −3; ∆ 24 = u 2 + v4 − c24 = 3 + 2 − 4 = 1; ∆ 25 = u 2 + v5 − c25 = 3 − 3 − 1 = −1; ∆ 31 = u3 + v1 − c31 = 5 + 2 − 9 = −2; ∆ 32 = u3 + v2 − c32 = 5 + 1 − 7 = −1. Таким образом, имеем следующие значения симплексных разностей: ∆ ij = {−2, − 6, − 7, − 3,1, − 1, − 2, − 1} . ∆ lk = max{∆ ij } = ∆ 24 = 1 , xlk = x24 = 50 . Подставляем полученные значения в таблицу с опорным планом X 3 и получаем табл. 17. Пометим заполняемую клетку (2, 4) знаком «+», а затем поочередно клетки (3, 4), (3, 3), (2, 3) − соответственно знаками «−», «+», «−». Среди клеток, образующих цикл и помеченных знаком «−», меньшее значение (50) содержится в клетке (3, 4). Прибавим это значение к числам, стоящим в клетках, помеченных знаком «+», и вычтем из чисел, стоящих в клетках, помеченных знаком «−». 83 Таблица 17 ПН B2 B1 v1 = 2 ПО A1 u1 = 0 A2 u2 = 3 A3 u3 = 5 Потребности B3 v2 = 1 2 − 60 v3 = −2 3 − -2 8 − -3 9 − -2 60 B4 B5 v4 = 2 v5 = −3 2 4 − -7 80 -6 70 − -1 4 1 110 − 7 10 − 140 1 180 -1 7 3 2 50 100 160 − + 70 4 − +1 4 Запасы 120 130 100 480 Освободим клетку (2, 4), в которой стояло минимальное число, а соответствующую ей переменную x24 исключим из базиса. Получаем новый опорный план ТЗ:  60 0 0 80 0    X 4 =  0 70 60 50 0  .  0 0 60 0 100    Z ( X 4 ) = 2 ⋅ 60 + 2 ⋅ 80 + 4 ⋅ 70 + 1 ⋅ 60 + 4 ⋅ 50 + 3 ⋅ 60 + 2 ⋅ 100 = 1200. Среди полученных значений симплексных разностей для переменных в свободных клетках имеется положительное число: 1 в клетке (2, 4). Итерация 5. Для каждой занятой клетки табл. 17 (с учетом сделанной перестановки) снова рассчитаем значения потенциалов поставщиков и потребителей: u1 + v1 = 2 ; u 2 + v2 = 4 ; u3 + v3 = 3 ; u1 + v4 = 2 ; u 2 + v3 = 1 ; u3 + v5 = 2 . u 2 + v4 = 4 ; Полагая u1 = 0 , получаем v1 = 2 , v4 = 2 . Подставляем полученные значения в другие уравнения системы: u 2 + v4 = u 2 + 2 = 4 ; u2 = 2 ; u 2 + v2 = 2 + v2 = 4 ; v2 = 2 ; 84 u2 + v3 = 2 + v3 = 1 ; v3 = −1 ; u3 + v3 = u3 − 1 = 3 ; u3 = 4 ; u3 + v5 = 4 + v5 = 2 ; v5 = −2 . Таким образом, имеем следующие значения потенциалов поставщиков и потребителей: u1 = 0 ; u2 = 2 ; u3 = 4 ; v1 = 2 ; v2 = 2 ; v3 = −1 ; v4 = 2 ; v5 = −2 . Вычислим симплексные разности для остальных переменных: ∆12 = u1 + v2 − c12 = 0 + 2 − 3 = −1; ∆13 = u1 + v3 − c13 = 0 − 1 − 4 = −5; ∆15 = u1 + v5 − c15 = 0 − 2 − 4 = −6; ∆ 21 = u 2 + v1 − c21 = 2 + 2 − 8 = −4; ∆ 25 = u2 + v5 − c25 = 2 − 2 − 1 = −1; ∆ 31 = u3 + v1 − c31 = 4 + 2 − 9 = −3; ∆ 32 = u3 + v2 − c32 = 4 + 2 − 7 = −1; ∆ 34 = u3 + v4 − c34 = 4 + 2 − 7 = −1. Таким образом, имеем следующие значения симплексных разностей: ∆ ij = {−1, − 5, − 6, − 4, − 1, − 3, − 1, − 1} . Поскольку среди найденных симплексных разностей нет положительных значений, то найденный в итерации 4 опорный план является оптимальным. Таким образом, оптимальный план перевозок груза от поставщиков к потребителям имеет следующий вид:  60 0 0 80 0    70 60 50  .  0 0 60 0 100    Изменение суммарной стоимости перевозок по мере приближения к оптимальному плану показано в табл. 18. Таблица 18 Целевая функция Z ( X1 ) Z (X 2) Z (X3) Z (X 4) Стоимость перевозки 1330 1270 1250 1200 85 Решение ТЗ, имеющих некоторые особенности в постановке 1. В некоторых реальных условиях перевозки груза из определенного пункта отправления Ai в пункт назначения B j не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Ai в пункт B j является сколь угодно большой величиной M , и при этом условии известными методами находят решение ТЗ. Такой подход к нахождению решения ТЗ называется запрещением перевозок. 2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Например, из пункта Ai в пункт B j требуется обязательно перевести aij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении i -й строки j -го столбца, записывают указанное число aij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки M . Для полученной таким образом новой ТЗ находят оптимальный план, который определяет оптимальный план исходной ТЗ. 3. Иногда требуется найти решение ТЗ, при котором из пункта Ai в пункт B j должно быть перевезено не менее aij единиц груза. Для определения оптимального плана такой задачи считают, что запасы Ai и потребности B j меньше фактических aij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи. Примечание. При целых ai (i = 1, 2, ..., m) и b j ( j = 1, 2, ..., n) из-за специфики ограничений ТЗ любое базисное допустимое решение является целочисленным. 86 Глава 4. Задача о назначениях Задача о назначениях − одна из разновидностей задач распределительного типа (ЗРТ), в которой для выполнения каждой работы требуется один и только один ресурс (один работник, один станок, одна автомашина и т.д.). Другими словами, ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем ТЗ, рассматривающая назначение сотрудников на должности или работы, автомашин на маршруты, водителей на автомашины и т.п. Экономико-математическая модель задачи о назначениях Пусть на предприятии (или в подразделении предприятия) имеются n сотрудников S1 , S 2 , …, S i , …, S n (i = 1,2,..., n) , которых необходимо назначить (распределить) по n работам R1 , R2 , …, R j , …, Rn ( j = 1,2,..., n) . Каждую из указанных работ может выполнять любой из сотрудников, однако производительность их труда по видам работ различается. В результате проведенных наблюдений и экспериментов зафиксирована производительность труда сотрудников по различным видам работ. Обозначим aij − производительность i -го сотрудника по j -й работе, а xij − назначение i -го сотрудника на j -ю работу: 1, если сотрудник S i назначен на работу R j ; xij =  0, в противном случае. Условие задачи о назначениях можно представить в табличном виде (табл. 19). Из табл. 19 следует, что если сотрудник S i назначен на работу R j , то xij = 1 , а остальные элементы этой строки будут равны 0. Таким образом, сумма переменных xij для любой строки или столбца равна 1, т.е. можно записать следующие условия: 87  n ∑ xij = 1, (i = 1, 2, ..., n)  i=1  n (5.1) ∑ xij = 1, ( j = 1, 2, ..., n)  j =1  x ≥ 0.  ij  В качестве целевой функции (критерия оптимальности) принимаем суммарную производительность сотрудников: n n Z = ∑∑ aij xij → max . (5.2) i =1 j =1 Таким образом, сущность задачи о назначениях состоит в отыскании таких неотрицательных значений xij , чтобы целевая функция (общая производительность) была максимальной. Таблица 19 Сотрудники Работы R1 R2 x11 x12 a11 a12 x21 x22 S2 a21 a22 … … … … … xi1 xi 2 Si ai1 ai 2 … … Sn … … … xn1 xn 2 an1 an 2 S1 … Ri … x1n x1 j … a1 j … … … a2 n … … xin xij aij … … ain … … xnn xnj … anj a1n x2 n x2 j a2 j Rn … ann Рассмотренную выше задачу можно классифицировать как комбинаторную (переборную) задачу. Пример решения подобной задачи представлен ниже [17]. Задача. На малом предприятии имеются три работника, которых необходимо распределить по трем различным работам. Предварительно была опреде- 88 лена производительность aij каждого работника по каждой из трех работ (см. табл. 20). Таблица 20 Работы Работники R1 R2 R3 S1 x11 x12 x13 a11 = 10 a12 = 15 a13 = 25 x21 x22 x23 a21 = 20 a22 = 10 a23 = 5 x31 x32 x33 a31 = 15 a32 = 10 a33 = 10 S2 S3 Запишем все возможные распределения 3 работников по 3 видам работ в виде следующих триад: 1) ( x11 , x22 , x33 ) ; 2) ( x11 , x23 , x32 ) ; 3) ( x12 , x21 , x33 ) ; 4) ( x12 , x23 , x31 ) ; 5) ( x13 , x22 , x31 ) ; 6) ( x13 , x21 , x32 ) . Для каждой из триад рассчитаем суммарную производительность: y1 = 1 ⋅ 10 + 1 ⋅ 10 + 1 ⋅ 10 = 30 ; y2 = 1 ⋅ 10 + 1 ⋅ 5 + 1 ⋅ 10 = 25 ; y3 = 1 ⋅ 15 + 1 ⋅ 20 + 1 ⋅ 10 = 45 ; y4 = 1 ⋅15 + 1 ⋅ 5 + 1 ⋅ 15 = 35 ; y5 = 1 ⋅ 25 + 1 ⋅ 10 + 1 ⋅ 15 = 45 ; y6 = 1 ⋅ 25 + 1 ⋅ 20 + 1 ⋅ 10 = 55 . Сравнивая полученные суммарные производительности, соответствующие каждой из триад, видим, что наибольшая производительность соответствует 6-й триаде: y6 = 55 . Следовательно, оптимальное распределение работников по видам работ представлено триадой ( x13 , x21 , x32 ) , т.е. 1-й работник назначается на 3-ю работу, 2-й − на 1-ю, 3-й − на 2-ю. Как отмечалось выше, задача о назначениях является частным случаем ТЗ. Применение симплекс-метода к задаче о назначениях неэффективно, так как любое ее допустимое базисное решение является вырожденным. Специфические особенности задачи о назначениях позволили разработать эффективный метод ее решения, известный как венгерский метод [22]. 89 Решение задачи о назначениях венгерским методом Специальный метод решения задачи о назначениях был впервые предложен американским математиком Г. Куном. Он назвал свой алгоритм венгерским методом, поскольку в нем используется теория паросочетаний, разработанная венгерскими учеными Д. Кенигом и Э. Эгервари. Основная идея венгерского метода заключается в переходе от исходной матрицы стоимости С к эквивалентной ей матрице стоимости С0 с неотрицательными элементами и системой n независимых нулей, т.е. с такой совокупностью нулевых элементов матрицы, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Очевидно, что квадратная матрица порядка n не может иметь систему более чем n независимых нулей. Две прямоугольные матрицы С и D называются эквивалентными (обозначается С∼D), если cij = d ij + α i + β j для всех i, j . Нулевые элементы матрицы С называются независимыми нулями в строке и столбце, на пересечении которых расположено нулевое значение и не содержатся другие нулевые элементы. Алгоритм венгерского метода решения задачи о назначениях состоит из подготовительного этапа и не более чем n − 2 последовательно повторяющихся итераций. На подготовительном этапе получают матрицу стоимости С0, эквивалентную матрице стоимости рассматриваемой задачи о назначениях и содержащую первоначальную систему независимых нулей. На каждой итерации число независимых нулей в преобразованной эквивалентной матрице стоимости увеличивается не менее чем на единицу. Через конечное число итераций система независимых нулей в преобразованной эквивалентной матрице стоимости С0 будет состоять из n элементов, что означает завершение процесса решения рассматриваемой задачи. Подготовительный этап заключается в последовательном выполнении следующих трех шагов: 1. Для каждого столбца матрицы стоимости С задачи о назначениях находят минимальный элемент l j = min cij , i =1, n j = 1, n , и формируют эквивалентную матрицу стоимости C ′ = (cij′ ) , в которой 90 cij′ = cij − l j ≥ 0 i, j = 1, n . В результате выполнения этого шага получается эквивалентная матрица стоимости C ′ , в каждом столбце которой имеется, по крайней мере, один нулевой элемент. 2. Для каждой строки матрицы стоимости C ′ находят минимальный элемент d i = min cij′ , i = 1, n , j =1, n и формируют эквивалентную матрицу стоимости C0 = (c ij ) , в которой c 0ij = cij′ − di ≥ 0 i, j = 1, n . В итоге образуется эквивалентная матрица стоимости С0 с неотрицательными элементами, в каждой строке и каждом столбце которой имеется по крайней мере один нулевой элемент. 3. В первом столбце матрицы С0 выбирают любой нулевой элемент и обозначают его как 0*. Далее во втором столбце выбирают нулевой элемент, не лежащий в одной строке с 0* первого столбца и тоже обозначают его как 0*. Эту процедуру повторяют для всех последующих столбцов матрицы стоимости С0 и, таким образом, получается первоначальная система независимых нулей, которая состоит из элементов, обозначенных как 0*. Эта система не может содержать менее двух элементов. Рассмотрим пример проведения подготовительного этапа алгоритма венгерского метода для следующей матрицы стоимости:  5 6 7 1   10 4 6 7   C = . 8 5 3 5   12 5 9 8  С учетом описанной выше процедуры подготовительного этапа выполним следующие шаги: 1. Найдем минимальные элементы в столбцах матрицы С. В первом столбце минимальным элементом является l1=c11=5, во втором – l2 = c22 = 4, в третьем – l3 = c33 = 3, в четвертом – l4 = c14 = 1. При вычитании этих значений из соответствующих столбцов получается матрица 91  0 2 4 0   5 3 6   C′ =  . 3 1 0 4   7 1 6 7   2. Находим минимальные элементы в строках матрицы C ′ . В первой ′ = 0, во второй – d2 = c ′22 = 0, в строке минимальным элементом является d1 = c11 ′ = 0, в четвертой – d4 = c ′42 = 1. При вычитании этих значений третьей – d3 = c33 из соответствующих строк получается матрица  0 2 4 0    5 0 3 6 C0 =  . 3 1 0 4   6 5 6   3. Отмечаем систему независимых нулей:  0* 2  * 5 0 C0 =  3 1  6 0  4 3 0* 5 0  6 4  6  или  0*  5 C0 =  3 6  2 4 0 3 1 0* 0* 5 0  6 . 4  6  После выполнения подготовительного этапа перейдем к описанию итерации алгоритма венгерского метода решения задачи о назначениях. Итерация алгоритма включает в себя следующие шаги (или пункты): 1. В матрице С0 подсчитывают число элементов в системе независимых нулей и обозначают его как k. Если k = n, то выполняется пункт 2. Если k < n, то выполняется пункт 3. 2. В соответствии с системой n независимых нулей эквивалентной матрицы стоимости С = С0 в матрице вместо переменных 0* записываются 1, а остальные элементы заменяются нулями. Решение завершено. 92 3. Столбцы матрицы C0, содержащие 0*, выделяются знаком «+», их элементы называют выделенными (при этом остальные элементы матрицы называются невыделенными). Осуществляется переход к пункту 4. 4. Если среди невыделенных элементов матрицы имеется хотя бы один нуль, то выполняется пункт 5, в противном случае выполняется пункт 9. 5. Если строка, содержащая невыделенный нуль, содержит еще и 0*, то выполняется пункт 6, иначе осуществляется переход к пункту 7. 6. Обнаруженный невыделенный нуль обозначается через 0′, а содержащая его строка отмечается знаком «+» и все ее элементы становятся выделенными. При этом одновременно снимается знак «+» со столбца, в котором расположен 0* из выделенной строки. Осуществляется возврат к пункту 4. 7. Найденный невыделенный нуль обозначается через 0′ и, начиная с него, строится так называемая L-цепочка по следующему правилу: берется исходный 0′; далее выделяется 0*, расположенный в том же столбце; затем 0′, расположенный в строке с 0*; далее – 0*, расположенный в столбце с предыдущим 0′ и т.д. Затем выполняется пункт 8. Ниже приведены три правила формирования L-цепочки. Правило 1. Построение L-цепочки осуществляется однозначно, так как в каждом столбце не может быть более одного 0*, а в каждой строке не может быть более одного 0′. Правило 2. L-цепочка всегда начинается с 0′ и заканчивается 0′. Ее можно представить в виде следующей схемы: по столбцу по строке 0′  → 0*  → 0′ ... Правило 3. Число элементов L-цепочки является нечетным числом. Причем L-цепочка может состоять из одного элемента, если в одном столбце с рассматриваемым 0′ нет 0*. 8. В L-цепочке все 0* заменяются нулями, а все 0′ – символами 0*, в результате чего в эквивалентной матрице стоимости получается новая система независимых нулей, число элементов которой на единицу больше числа элементов в предыдущей системе независимых нулей. Вне L-цепочки все 0′ заменяются нулями, а также отменяются выделения строк и столбцов матрицы, после чего происходит возврат к пункту 1. 9. Среди невыделенных элементов матрицы С0 находится минимальный элемент h (h > 0). Значение h вычитается из элементов невыделенных строк и 93 прибавляется к элементам выделенных столбцов. Вновь получается эквивалентная матрица стоимости с неотрицательными элементами, в которой по меньшей мере один из невыделенных элементов является нулем. Затем выполняется пункт 5. Рассмотрим пример решения задачи о назначениях венгерским методом. Возьмем эквивалентную матрицу стоимости, полученную выше, и выполним следующие итерации алгоритма: Итерация 1 Шаг 1. Имеется эквивалентная матрица стоимости, полученная на подготовительном этапе:  0* 2 4 0    * 3 6 5 0 . C0 =  3 1 0* 4     6 0 5 6   Число k элементов в системе независимых нулей матрицы равно трем. А так как n = 4 и k < n, то переходим к шагу 3. Шаг 3. Согласно алгоритму, выделяем первый, второй и третий столбцы матрицы, содержащие 0*, и переходим к действиям, описанным в шаге 4: + + +  0* 2 4 0    * 5 3 6   C0 =  . * 3 1 4    6 0 5 6   Шаг 4. Проверяем, есть ли среди невыделенных элементов хотя бы один нуль. Нулевой элемент имеется в невыделенном четвертом столбце (в первой строке). Переходим к шагу 5. Шаг 5. Так как в первой строке матрицы C0 наряду с невыделенным нулем (с14 = 0), есть элемент с11, выделенный как 0*, то переходим к шагу 6. Шаг 6. Согласно этому пункту найденный невыделенный нуль обозначается через 0′ и выделяется содержащая его строка. При этом снимается выделение с первого столбца, в котором расположен 0* из первой строки: 94 + + +  0 * 2 4 0′    * 3 6 5 0 C0 =  . * 3 1 4    6 0 5 6   После чего вновь выполняем шаг 4 алгоритма решения задачи. Шаг 4. Проверяем, есть ли среди невыделенных элементов матрицы нулевые значения. Поскольку таких значений нет, то выполняется шаг 9. Шаг 9. Среди невыделенных элементов матрицы C0 находим минимальный элемент h = min{5, 3, 6, 6, 4, 6}=3. Значение h = 3 вычитаем из элементов невыделенных строк (строка 2, строка 3 и строка 4) и прибавляем к элементам выделенных столбцов с номерами 2, 3. Получаем новую эквивалентную матрицу стоимости: + + * +0 5 7 0′    * 2 3 3   C0 =  . * 1 1    3 0 5 3   После чего, согласно алгоритму, переходим к шагу 5. Шаг 5. В третьей строке, содержится и невыделенный нуль (с31 = 0), и выделенный нуль – с33, значит переходим к шагу 6. Шаг 6. Невыделенный нуль обозначается через 0′ и выделяется содержащая его строка. Одновременно снимается знак выделения с третьего столбца, в котором расположен 0* из третьей строки. В итоге получаем: + * +0 5 7 0′    * 3 3 2 0 C0 =  . + 0 ′ 1 0* 1     3 0 5 3   Вновь возвращаемся к шагу 4. Шаг 4. Среди невыделенных элементов матрицы C0 нет нулей. Переходим к шагу 9. Шаг 9. Снова среди невыделенных элементов матрицы находим минимальный элемент h = min{2, 3, 3, 3, 5, 3} = 2. Значение h = 2 вычитаем из эле- 95 ментов невыделенных строк (строки 2 и 4) и прибавляем к элементам выделенного второго столбца. Получаем новую эквивалентную матрицу стоимости: + +  0* 7 7 0′    *  0 0 1 1 C0 =  . + 0 ′ 3 0* 1     1 0 3 1   Переходим к шагу 5. Шаг 5. Во второй строке, содержащей невыделенный нуль (с21=0), есть выделенный нуль – с22, значит переходим к шагу 6. Шаг 6. Найденный невыделенный нуль обозначается через 0′ и выделяется содержащая его строка. Снимается знак выделения со второго столбца, в котором расположен 0* из второй строки. Получается +  0* 7  +  0′ 0* C0 =  + 0′ 3  1 0  7 1 0* 3 0′   1 . 1  1  Переходим к шагу 4. Шаг 4. Среди невыделенных элементов матрицы C0 есть нуль (с42 = 0), поэтому переходим к шагу 5. Шаг 5. Так как четвертая строка, содержащая невыделенный нуль, не содержит 0*, то переходим к шагу 7. Шаг 7. Найденный невыделенный нуль обозначаем символом 0′ и строим L-цепочку (с42→ с22→ с21→ с11→ с14): +  0* 7  +  0′ 0* C0 =  + 0′ 3   1 0′  7 1 0* 3 0′  1 . 1 1  Переходим к шагу 8. Шаг 8. В L-цепочке все символы 0* заменяем нулями, а символы 0′ заменяем символами 0*. Вне цепочки все 0′ заменяем нулями и снимаем все выделе- 96 ния строк и столбцов. Получаем новую эквивалентную матрицу с новой системой независимых нулей: 0  * 0 C0 =  0 1  7 7 1 3 0* 0* 3 0*   1 . 1  1  Переходим к шагу 1. Итерация 2 Шаг 1. Число k элементов в системе независимых нулей матрицы С0 равно четырем. А так как n = 4 и k = n, то переходим к шагу 2. Шаг 2. В соответствии с эквивалентной матрицей стоимости выписываем оптимальное решение рассматриваемой задачи, которое получается заменой всех 0* единицами, а всех остальных значений нулями:  0 0 0 1   1   X0 =  . 0 0 1 0    0 1 0 0 На практике встречаются задачи, для которых параметр сij имеет смысл эффективности выполнения i-й работы j-м исполнителем i, j = 1, n . В таких случаях суммарная эффективность выполнения всех работ должна быть максимальной. В этом случае следует изменить первое действие подготовительного этапа венгерского метода, которое принимает следующий вид. Для каждого столбца матрицы стоимости С задачи о назначениях находят максимальный элемент l j = max cij , j = 1, n , i =1, n и формируют эквивалентную матрицу стоимости C ′ = (cij′ ) , в которой cij′ = l j − cij ≥ 0 i, j = 1, n . Последующие шаги подготовительного этапа и итерации венгерского метода не изменятся. 97 Пример. Дана матрица эффективностей 10 7 6  5 9 7 C = 7 8 10  3 8 4 В этом случае 9  3 . 5  2  l1 = max{10, 5, 7, 3}=10, l2 = max{7, 9, 8, 8}=9, l3 = max{6, 7, 10, 4}=10, l4 = max{9, 3, 5, 2}=9. и эквивалентная матрица стоимости получит вид 0  5 C′ =  3  7 2 4 0  0 3 6 . 1 0 4  1 6 7  98 Библиографический список 1. Советов, Б. Я. Моделирование систем [Текст] : учеб. пособие для вузов / Б. Я. Советов, С. А. Яковлев. − М. : Высш. шк., 1999. − 320 с. 2. Таха А.Х. Введение в исследование операций, 7-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2005. – 912 с. 3. Лотов, А. В. Введение в экономико-математическое моделирование [Текст] / А. В. Лотов. − М. : Наука. Гл. ред. физ.-мат. лит., 1984. − 392 с. 4. Хазанова, Л. Э. Математические методы в экономике [Текст] : учеб. пособие / Л. Э. Хазанова. − 2-е изд., испр. и перераб. − М. : Изд-во БЕК, 2002. − 144 с. 5. Бахвалов, Л. А. Компьютерное моделирование: долгий путь к сияющим вершинам? [Текст] / Л. А. Бахвалов // Компьютерра. − № 40, 1997. 6. Марка, Д. А. Методология структурного анализа и проектирования SADT [Текст] : [пер. с англ.] / Д. А. Марка, К. МакГоуэн. − М. : МетаТехнология, 1993. − 240 с. 7. Кобелев, Н. Б. Основы имитационного моделирования сложных экономических систем [Текст] : учеб. пособие / Н. Б. Кобелев. − М. : Дело, 2003. − 336 с. 8. Форрестер, Дж. Основы кибернетики предприятия (индустриальная динамика) [Текст] : [пер. с англ.] / Дж. Форрестер. − М. : Прогресс, 1971. − 340 с. 9. Исследование операций в экономике [Текст] : учеб. пособие для вузов [Текст] / Н. Ш. Кремер [и др.]. − М. : ЮНИТИ, 2001. − 407 с. 10. Сливина Н.А., Петрушко М.И. Математические модели и методы исследования операций: учеб. пособие. – М.: Издательский дом МЭИ, 2007. – 112 с. 11. Кремер Н.Ш. Исследование операций в экономике, 3-е издание.: - М.: Юрайт, 2013. – 438 с. 12. Венцель, Е. С. Исследование операций. Задачи, принципы, методология [Текст] : учеб. пособие для вузов / Е. С. Венцель. − 3-е изд., стереотип. − М. : Дрофа, 2004. − 208 с. 13. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от арифметики до эконометрики: учебно-справочное пособие, 2-е издание.: М.: Юрайт, 2011. – 646 с. 99 14. Попов А.М., Сотников В.Н. Экономико-математические методы и модели: учебник для прикладного бакалавриата, 3-е издание.: - М.: Юрайт, 2015. – 345 с. 15. Шикин, Е. В. Математические методы и модели в управлении [Текст] : учеб. пособие / Е. В. Шикин, Г. А. Чхартишвили. − М. : Дело, 2000. − 440 с. 16. Производственный менеджмент [Текст] : учеб. для вузов / С. Д. Ильенкова [и др.]. − М. : ЮНИТИ-ДАНА, 2000. − 583 с. 17. Черняк А.А., Новиков В.А., Мельников О.И., Кузнецов А.В. Математика для экономистов на базе MathCAD. – СПб.: БХВ-Петербург, 2014. – 496 с. 18. Алесинская, Т. В. Учебное пособие по решению задач по курсу «Экономико-математические методы и модели» [Текст] / Т. В. Алесинская. − Таганрог : Изд-во ТРТУ, 2002. − 153 с. 19. Excel для экономистов и менеджеров [Текст] / А. Г. Дубина [и др.]. − СПб. : Питер, 2004. − 285 с. 20. Конюховский, П. В. Математические методы исследования операций в экономике [Текст] : учеб. пособие / П. В. Конюховский. − СПб. : Питер, 2000. − 208 с. 21. Стивенсон, В. Дж. Управление производством [Текст] : [пер. с англ.] / В. Дж. Стивенсон. − М. : ООО «Изд-во «Лаборатория Базовых Знаний», ЗАО «Изд-во БИНОМ», 1999. − 928 с. 22. Волков, И. К. Исследование операций [Текст] : учеб. для вузов / И. К. Волков, Е. А. Загоруйко ; под ред. В. С. Зарубина, А. П. Крищенко. − 3-е изд., стереотип. − М. : Изд-во МГТУ им. Н. Э. Баумана, 2004. − 440 с. 23. Стариков А.В. Экономико-математическое и компьютерное моделирование: учеб. пособие. – Воронеж: Фед. агентство по образованию, ГОУ ВПО «ВГЛТА», 2008. – 132 с.