Трудно найти иголку в
стоге сена, но еще труднее
найти конкретную соломинку
в этом стоге.
Аж-Гриндер
Хорошие указания приносят
не меньшую пользу,
чем хорошие примеры.
Сенека
Решение - задачи принятия решений - управленческое решение - факторы процесса принятия решений - допустимое решение - оптимальное решение - структурированные проблемы - слабо структурированные проблемы - неструктурирован- ■ ные проблемы - «новая» парадигма - операционально замкнутая система - собственное поведение системы - регулярное управление - управление изменениями - самоорганизация - экологич-ность управления
Проблемы, связанные с отысканием способов достижения поставленных целей с учетом имеющихся возможностей, т.е. проблемы принятия решений, пронизывают всю человеческую практику (и общественную, и личную) и поэтому отличаются большим разнообразием. Исходя из этого, рассмотрим некоторые общие теоретические вопросы, которые могут быть взяты в качестве современной методологической основы не только для принятия государственных управленческих решений. Они также оказываются полезными при принятии управленческих решений в различных сферах бизнеса, в так называемом третьем секторе, представляющем собой все общественные организации, в каждой отдельно взятой организации как со сложной структурой (транснациональные корпорации, холдинги, финансово-промышленные группы и другие объединения), так и с традиционными структурами (функциональной, линейно-функциональной и т.п.).
В специальной литературе можно встретить различные трактовки термина «решение». Решение понимается и как результат выбора, и как процесс, и как акт выбора. Эти трактовки самого понятия «решение» не противоречат, а только дополняют друг друга, расставляя по-разному акценты в зависимости от контекста исследований и конкретной управленческой деятельности. Так, рассматривая решение как процесс, протекающий во времени, можно говорить о его этапах. Решение как результат выбора - это уже предписание к действию, а как акт выбора - творческая составляющая управленческой деятельности, которая рассматривает решение неотделимо от такого понятия, как «властная воля». Таким образом, под решением понимаются одновременно и процесс, и результат, и акт выбора цели и способ ее достижения.
В зависимости от основания классификации выделяют следующие задачи принятия решений:
Структурированные, слабо структурированные и неструктурированные;
Уникальные и повторяющиеся;
Статические и динамические;
В условиях определенности и в условиях неопределенности (в частности, при риске, при противодействии);
С фиксированным набором альтернатив (вариантов решений, стратегий) и с формируемым в процессе принятия решений;
С одним критерием (целевой функцией, показателем качества или эффективности) и со многими (несколькими) критериями;
а также рассматривают:
Задачи выбора одной наилучшей (оптимальной) альтернативы или же выделение нескольких лучших альтернатив, ранжирование (разбивку на упорядоченные классы) всех или только выделяемых лучших альтернатив;
Индивидуальные и коллективные решения;
Волевые, интеллектуальные и эмоциональные решения;
Технические, технологические и т.п.;
Оперативные, тактические и стратегические;
Рутинные и уникальные;
Интуитивные и рациональные;
Сложные и простые, и т.д.
Процессы принятия управленческих решений занимают в управленческой деятельности центральное место. Заметим, что не всякое решение является управленческим, а только такое, которое, во-первых, является результатом выбора между несколькими альтернативами, в большинстве случаев приблизительно равноценными с точки зрения принимающего решение, а во-вторых, когда результат выбора как социальное явление влияет на других людей и воспринимается ими в качестве обязательного к исполнению. Если не выполняется первое условие, то принимаемое решение или продиктовано другими людьми, или обстоятельствами, не зависящими от лица, принимающего решение. В этом случае имеем дело с так называемым ритуальным
управлением. В случае невыполнения второго условия имеет место управленческая утопия, а нереальное управление.
Процесс принятия решения как неотъемлемая составляющая каждой из функций управления предполагает наличие следующих факторов:
1. Лицо, принимающее решение (ЛПР) - человек или группа людей, наделенных необходимыми полномочиями для принятия решения и несущих за него ответственность.
2. Управляемые переменные, охватываемые проблемой ситуации, т.е. совокупность факторов и условий, вызывающих появление той или иной проблемы, которыми может управлять ЛПР.
3. Неуправляемые переменные - охватываемые проблемой ситуации, которыми не может управлять ЛПР, но которыми могут управлять другие лица. В совокупности с управляемыми переменными неуправляемые переменные могут влиять на результат выбора, образуя фон проблемы или ее окружающую среду.
4. Ограничения (внутренние и внешние) на значения управляемых и неуправляемых переменных, которые в совокупности определяют область допустимых решений.
5. Критерий (или критерии) для оценки альтернативных вариантов решения. Критерий может быть задан количественной моделью или качественно (в терминах индивидуальных предпочтений или в терминах нечеткой логики).
6. Решающее правило (или система решающих правил) - принципы и методы выбора решения, в результате применения которых получают рекомендации или рекомендуемое решение (хотя окончательный выбор остается за ЛПР).
7. Альтернативы (возможные исходы), зависящие как от значений качественных или количественных управляемых и неуправляемых переменных, так и от самого выбора.
8. Решение, предполагающее существование по крайней мере двух альтернатив поведения (исходов); в противном случае проблемы принятия решения не возникает ввиду отсутствия выбора.
9. Возможности реализации выбранного или принятого решения. Функцию принятия решений можно рассматривать как задачу, которую
(хотя и с разным содержанием) постоянно приходится решать в процессе управленческой деятельности и которая имеет следующую постановку: определить наилучший способ действий для достижения поставленных целей. Здесь под целью понимаются как видение желаемого состояния управляемой системы, так и результат правильной (в определенном смысле) управленческой деятельности. При этом имеется проблема, если желаемое состояние системы не соответствует фактическому. Проблема на своем фоне (совокупность проблемы и ситуации) представляет собой проблемную ситуацию. Для разрешения проблемной ситуации ЛПР стремится выбрать «самое хорошее», оптимальное в определенном смысле решение, надеясь, что оно сохранит это свойство и в перспективе. Если же решение принимается в условиях неопределенности (имеется избыток или недостаток информации, несколько критериев оценки альтернатив и т.п.), то имеет смысл говорить о решениях, оптимальных, по В. Парето (итальянский экономист), которые следует искать среди неулучшаемых альтернатив.
Решение задачи называют допустимым, если оно удовлетворяет огра-ничениям, связывающим как управляемые, так и неуправляемые переменные. Допустимое решение называют оптимальным, если оно обеспечивает желаемый экстремум критерия выбора.
Проблемы, для которых зависимости между переменными выявлены так, что могут быть представлены числами или формализованы таким образом, что также допускают в конце концов численные оценки, определяются как структурированные (или количественно сформулированные). Проблемы, содержащие лишь название важнейших характеристик, ресурсов и при-" знаков, количественные зависимости между которыми не определены, называют неструктурированными (качественно выраженными). Проблемы, которые содержат как качественные, так и количественные элементы, причем качественные и неопределенные аспекты проблемы имеют тенденцию усиливаться, называют слабо структурированными. Модель (описание) слабо-! структурированных проблем может быть построена только на основании дополнительной информации, получаемой от человека или группы лиц, участвующих в решении такой проблемы, для компонентов которой характерньи нечеткость, многовариантность и приближенный (хотя и с сохранением структуры) вид описания.
Если описание (или модель) проблемной ситуации содержит динамическую систему взаимозависимостей между большим количеством переменных: большой размерности с наличием нелинейных связей между ними, а также случайных факторов, то такая проблемная ситуация определяется как слож-, нал. Если же задача статическая, небольшой размерности, с отсутствием нелинейностей и случайных факторов, то такую задачу классифицируют как, простую задачу. Заметим, что термин «сложность» относится именно к описанию проблемной ситуации, а не к природе решаемой проблемы.
Хотя задачи принятия решений сопровождают человечество с момента его зарождения, систематическое их изучение началось лишь в XX в. В последние десятилетия было ясно осознано, что проблема принятия решений междисциплинарна и требует системного подхода. Поэтому в настоящее: время интенсивно разрабатываются тесно связанные между собой математическая, психологическая, организационная, информационная и другие теорий
принятия решений. Проблема принятия решений в управлении социальными процессами представляется настолько сложной, что наряду с использованием системного подхода требует для своего решения установления связей между идеями различных научных дисциплин, философских традиций, часто выходя за пределы науки в ее традиционном понимании и порождая элементы нового видения реальности. Следовательно, речь идет о проникновении «новой» парадигмы в управленческую теорию и практику.
Известно, что в первые десятилетия нашего века физические исследования, по словам физика, лауреата Нобелевской премии Ф. Капры, «привели в соприкосновение со странной и неожиданной реальностью, поколебавшей у физиков основания их мировоззрения и заставившей их мыслить совершенно по-новому. Мир, который они наблюдали, не представлялся более машиной, состоящей из множества отдельных объектов, он был неделимым целым: сетью отношений, которые необходимым образом включали наблюдателя. Стремясь постичь природу явлений, ученые не могли не обнаружить, что их основные понятия, язык, весь способ мышления не годятся для описания открывшейся реальности». В течение последних 30 лет стали говорить о парадигмах и об их смене даже вне науки. Например, так называемая новая (или «третья») парадигма считается, порожденной первой и второй парадигмами. Охарактеризуем очень кратко каждую из них.
В основе первой парадигмы мышления лежит проектирование внешнего мира человека на его внутренний мир которое иррационально, интуитивно, бессознательно. Особую роль играют умения, навыки, ритуалы. Это мифологический образ мышления. В основе второй парадигмы - рациональный подход с линейными причинно-следственными связями. Здесь появляются изобретательство, конструирование. Сформировано представление о Мире как о часовом механизме - механистическое представление мира. В процессах анализа и моделирования сложных систем появилось понятие обратной связи с акцентом на отрицательные обратные связи. В рамках второй парадигмы возникает техногенное производство («механическая жизнь»). Синтаксисом этой парадигмы является математический анализ. Моделирование процессов основывается на понятии «непрерывность», приводящем к так называемой дурной бесконечности и ряду логических парадоксов. Третья, или новая парадигма представляет собой коммуникацию первой и второй парадигм, где в основе лежит принцип равновесия между рациональным и иррациональным, сознательным и бессознательным, научным знанием и интуицией. В рамках третьей парадигмы осуществляется как бы возврат проекции внешнего мира на внутренний мир человека, а сама парадигма понимается как совокупность мыслей, восприятий и ценностей, которые создают определенное видение реальности, оказывающееся основой самоорганизации общества. В третьей парадигме используется синтаксис квантовой механики с собственными значениями и собственными функциями. Механистическая модель мира уступает место биологической с описанием сложных систем как живых. Таким образом, освоение новой («третьей») парадигмы является одной из возможностей формирования современной методологии деятельности, включающей принятие компетентных решений при интегрировании имеющегося опыта, интуиции с достижениями современной науки, накопленными за последние 40-50 лет.
При современном рациональном подходе рекомендации (или изменения типа «сверху - вниз»), казалось бы, оптимальные с рациональной точки зрения, если априори и не обречены на неудачу, то со временем превращаются в разбухшие, искаженные версии первоначальных планов, а отсутствие ясности преобразует бюрократические организации в механизмы для ухода от ответственности. Инструментами новой управленческой парадигмы могут служить «мягкие» аналитические методы, а также «мягкие» технологии принятия решений и «мягкие» управленческие технологии.
Системы управления организацией могут быть описаны по-разному. Описание системы как хорошо отлаженного механизма достаточно эффективно, но имеет ряд недостатков. При этом функционирование организации ориентировано на достижение конечной цели, а сам процесс достижения рассматривается как инструмент или как одна из возможных альтернатив. При отсутствии ясно сформулированной цели такой подход к ее достижению представляется весьма затруднительным и туманным.
Социальная система является сложной системой. Эта сложность усиливается еще и тем, что субъект управления такой системой сам включен в управляемую систему, привнося тем самым в нее еще большую непредсказуемость, неопределенность своими субъективными, эмоциональными реакциями, своими описаниями-и представлениями о самой этой системе, также являющимися атрибутами управляемой системы. Другими словами, принципиальным для таких систем является наличие включенного в систему наблю-" дателя. Встать в позицию внешнего наблюдателя по отношению к социальной системе представляется (даже из чисто теоретических рассуждений) проблематичным. На языке «управляющий - система» это означает, что управляющий включен в систему и, управляя системой, управляет самим собой. Более того, говорить, что управляющий управляет системой, также верно, как и то, что система управляет управляющим.
Одним из наиболее важных результатов такого описания является понимание того, что управление неотделимо от системы и никакая группа-управляющих не составляет изолированного блока. Каждый управляющий находится внутри системы, связан с ней сложной сетью взаимодействий и,; можно сказать, что он управляет собой в структуре системы. Эта замкнутая ситуация лежит в основе многих парадоксов, включая один из древнейших
парадоксов Эпименида о брадобрее, которому было приказано брить тех, кто не бреет себя сам. Проблемы не существует до тех пор, пока не возникает вопрос о том, что делать самому брадобрею. Тогда имеем неразрешимую проблему: если брадобрей будет брить себя сам, то он не должен себя брить, если же он не будет себя брить, то должен себя брить, т.е. из любой из этих посылок следует ее отрицание и, следовательно, утверждение совпадает со своим отрицанием. Аналогичен этому парадокс лжеца: житель острова говорит, что каждый, живущий на острове, - лжец. В математике известен парадокс Рассела: множество всех множеств, не содержащих себя в качестве своего элемента. Математика объясняет возникновение парадоксов непредикативностью определений, когда то, что определяется, принимает участие в собственном определений. Если наблюдатель является частью наблюдаемой им системы, а управляющий управляет собой в составе организации, то можно увидеть непредикативность и парадоксальность такой ситуации. В этом случае говорят, что имеется семантическая петля, а систему называют операционально замкнутой (или живой). Из этого тупика намечается выход: появляются новые подходы к структурированию ситуаций такого рода на основе современных математических подходов, использующих многозначные логики, нечеткие множества, фрактальные структуры, современные (формальные и неформальные) методы анализа данных и т.п. Операционально замкнутые системы занимают как бы промежуточное положение между открытыми и замкнутыми системами. С одной стороны, они могут реагировать на входной сигнал, что делает их похожими на открытые системы, с другой стороны, они - «непослушные» системы, системы с «характером», с «настроением» или, как говорят, обладают внутренним состоянием. Уместно вспомнить известный из психологии пример, когда, глядя на один и тот же рисунок, одни люди видят профили двух человеческих лиц, расположенных друг против друга, а другие -контур вазы для цветов. Простейшими формальными моделями таких систем являются нетривиальная машина У. Эшби и биологические автоматы известного советского математика М. Цетлина.
Живые системы реагируют на входящий сигнал в зависимости от своего внутреннего состояния. При этом воздействие среды на систему может порождать континуум реакций (т.е. столько реакций, сколько существует точек на прямой), так что с позиций теоретического внешнего наблюдателя такая ситуация может рассматриваться как отсутствие реакции на входящий сигнал (свойство автономии). Считается, что окружающая среда влияет на систему только как источник модуляций, вызывающих спонтанные изменения структуры внутренних связей в ограничениях, налагаемых организацией системы. Поэтому реакции системы на одинаковые, с точки зрения внешнего наблюдателя, воздействия среды могут быть совершенно различными и, вообще говоря, не являться реакциями. Это происходит не только потому, что поведение системы определяется в основном текущим состоянием структуры, невидимой внешнему наблюдателю, но и от того, что некоторый входящий сигнал, зафиксированный наблюдателем, может не восприниматься системой как входящий, и наоборот.
Операционально замкнутая система функционирует согласно двум принципам самоорганизации:
Операционально замкнутая система обладает собственным поведением;
Операционально замкнутая система изменяется путем естественного дрейфа.
Собственное поведение системы - это такое особое состояние системы, которое в процессе функционирования становится результатом стабилизации последовательности ее состояний. Так, если в качестве примера рассматривать процесс обсуждения государственными служащими некоторой проблемы, то собственное поведение системы можно интерпретировать как ситуацию «договоренности» или «разрешения» этой проблемы. Если рассматривать совокупность состояний системы в процессе ее функционирования как бесконечную последовательность, то можно показать, что в качестве своего предела она имеет собственное поведение системы, которое, оказывается, в соответствии с полученным математическим соотношением совпадает с самим процессом, т.е. в смысле математического равенства результат и процесс неразличимы.
Следовательно, возможен двоякий подход к процессам управления и принятия решений: акцент можно делать на формулировании и достижении конечной цели, а можно акцентировать внимание на разумной, правильной в определенном смысле организации самого процесса управления или процесса принятия решения. Первый подход, ориентированный на конечное целе-полагание, находится в концепции регулярного управления, задающего основные стандарты, процедуры и правила управления. Этот подход является достаточно традиционным в теории и практике управления. Второй подход, ориентированный на правильную организацию самого процесса принятия решения и управления, больше соответствует контексту управления изменениями, или управлению в режиме реального времени. Один подход не исключает другой, они только дополняют друг друга, подобно тому, как в физике рассматривается свет и как волна, и как частица.
Эффективность использования на практике того или иного подхода зависит от содержания конкретной проблемы, которую необходимо разрешить. В различных технологиях принятия решений на разных этапах указанные подходы могут применяться как автономно друг от друга, так и переплетаться в разных комбинациях. При этом эволюция процесса представляется как дрейф от одного собственного состояния к другому собственному состоянию
системы. Под естественным дрейфом понимают неустойчивое движение системы в окрестностях ее собственного поведения. Следовательно, эволюционное развитие системы можно рассматривать как движение системы по ее собственным поведениям (значениям). При этом известно, что операционально замкнутая система имеет конечное или счетное число собственных поведений. Таким образом, множество собственных поведений операционально замкнутой системы дискретно, и функционирование системы с позиции теоретического внешнего наблюдателя представляет собой последовательный дискретный переход системы из одного собственного состояния в другое собственное состояние. Такой процесс называют квантованием социальных систем.
Описание функционирования операционально замкнутой системы по своему синтаксису напоминает описание движения электрона в модели атома Н. Бора, где нахождение электрона на орбите соответствует собственному поведению системы, «скачки» с одной орбиты на другую - переходу системы из одного собственного состояния в другое собственное состояние.
Если представить среду как живую систему с самоорганизующимся поведением, становится понятным, что сама система может фактически наделять внешнее окружение собственными значениями. Это также следует из существования прогностического свойства живой системы, связанного с тем, что любое описание, если его рассматривать как реальное, имеет последствия. Или, как утверждает Дж. Сорос, «описание формирует будущее». В связи с этим на основе формирования эффективных прагматических карт участников процесса принятия решений возникает необходимость в генерации «карты будущего», в процессе которой важно не только понять настоящую и желаемую ситуацию, но и пережить некоторый опыт. Это связано с формированием ситуации и созданием условий для возможной самоорганизации системы. Суть самоорганизации заключается в том, что имеются самопорождающиеся структуры, которые порождают карты будущего так, что осуществляют взаимодействие с картой будущего
В качестве иллюстрации того, что такое самоорганизация, можно привести следующий пример. Имеется аудитория с несколькими тысячами человек, каждый из которых держит в руках палку, одна половина которой зеленого, а другая - красного цвета. На зеленом экране изображен круг, а на нем - зеленая «пятерка» - цифра пять зеленого цвета. Лидеры предлагают сидящим в зале посмотреть на экран, а затем, подняв палку зеленым или красным концом вверх, восстановить изображение на экране (после того, как оно было с него убрано). Зал сканируют. Сначала на экране появляются красные и зеленые пятна случайных и неопределенных конфигураций, но менее чем через четыре минуты картина становится устойчивой: изображение на экране восстановлено. На этом примере видно, что хотя никто не мог
даже предположить, каким образом прийти к результату и что задача в принципе решаема, но, представив будущее визуально и задав совершенно конкретно, синтаксически правильно ситуацию, люди в аудитории просто ДАЛИ правильно ответ на вызов лидеров. Они это сделали без всяких инструкций, только за счет ВИДЕНИЯ желаемого результата. Это пример того, как живая система с правильно заданным синтаксисом и «сформированным» желаемым результатом может породить этот результат. Порождают эти системы сначала собственные описания, которые затем становятся собственными значениями (собственными поведениями). Таким образом, результат может быть получен в ответ на вызов с видением результата, с верой и желанием его достичь, с обращением на него внимания других: нужна ясная структура, чтобы выйти на прагматические собственные значения.
Суть «новой парадигмы» состоит в определенном отходе от управленческого рационализма, от изначального убеждения, что успех организации определяется прежде всего рационализацией процессов в ней. Организации необходимо заботиться об адаптивности своих внутренних систем, извлекать максимум выгоды из имеющихся возможностей. В этом случае организационные механизмы приспосабливаются к выявлению новых проблем и выработке новых решений больше, чем к контролю уже принятых ранее. Маневр в распределении ресурсов ценится выше, чем пунктуальность в их расходовании. Организация, агрессивно действующая в своей среде, новаторская в научно-техническом отношении, ориентированная на качество, а не на количество, адаптивная по внутреннему строению своих систем, все в большей степени зависит от человеческого фактора, который неотделим от компетенции, эффекта команды, развертывания систем стратегического управления.
Как отмечено выше, автономная система реагирует на управляющие толчки непредсказуемым образом. Известно также, что результат человеческого действия лишь частично соответствует намерениям и расчету. Типичными примерами ограниченной управляемости социальных систем служат переговоры, обсуждение проблемы, поиск решений группой экспертов. Здесь никто не контролирует ситуацию целиком, скорее сам процесс управляет участниками.
Как говорил всемирно известный английский ученый Cm Бир: «Управление системой есть способность общаться с ней, понимать ее внутренний язык и уметь пользоваться им, будучи компетентным собеседником». Другими словами, надо стремиться, чтобы синтаксис анализа, описания системы и управления ею соответствовали синтаксису функционирования самой системы. Именно это имеют в виду, говоря об экологичности управления. В связи с последним замечанием в рамках современных аналитических технологий, технологий принятия решений и управления социальными системами,
связанными со сменой парадигмы, появляется так называемый экологичный подход к проблеме: от экологии мышления к экологии управления с требованием экологичности каждого описания.
Заметим, что описание системы как открытой или операционально замкнутой порождено наблюдателем. Эти описания не противоречат и не исключают друг друга: каждое из них имеет свою область эффективности. Однако ясно, что такие системы, как экологическая, социальная, геополитическая и другие, могут быть в соответствии с их организацией представлены как операционально замкнутые.
Инструментами анализа и принятия решений в рамках новой парадигмы могут служить методология «мягких» систем, мета-модель, модели «точности», системной технологии вмешательства, организационного развития и другие, а также новые технологии анализа информации, работающие в «мягком» контексте. Это означает, что наряду с применением современного формального (математического) аппарата в управленческих и аналитических исследованиях, а также в самом процессе принятия управленческих решений целесообразно использовать как ресурс профессиональный опыт и интуицию субъектов управления.
Способность получать качественную информацию, представлять ее в полезном виде и эффективно действовать на этой основе - один из самых ценных навыков в управлении социальными процессами. Это особенно важно в условиях динамичного хаотического формирования общественных отношений, когда проведение анализа социальных систем только с помощью формального аппарата не представляется целесообразным и даже возможным. В этих условиях имеет место отход от рациональных методов анализа и механистического описания системы и переход к описанию организации как живой, с «мягкими» и неформальными подходами к ее анализу, принятию решений и управлению такой системой.
Литература
Вир Ст. Мозг фирмы. - М., 1993.
Диев B.C. Управленческие решения: неопределенность, модели, интуиция. -Новосибирск, 1998.
Зотов В. Б. Территориальное управление (методология, теория, практика). -М., 1998.
Капра Ф. Уроки мудрости. - М., 1996.
Купряшин Г.Л., Соловьев A.M. Государственное управление: Учебное пособие. -М., 1996.
Сорос Дж. Алхимия финансов. - М., 1997.
Управление организацией: Учебник / Под ред. А.Г. Поршнева, З.П. Румянцевой, Н.А. Соломатина. - М, 1998.
Фатхутдинов Р.А. Разработка управленческого решения: Учебное пособие. -М., 1997.
Хайек Ф.А. Пагубная самонадеянность. - М., 1992. Юкаева B.C. Управленческие решения: Учебное пособие. - М., 1999.
Выпуклые множества и их свойства. Для того, чтобы изучить свойства ЗЛП, необходимо дать строгое определение выпуклого множества. Ранее выпуклое множество определялось как множество, которое вместе с любыми двумя своими точками содержит отрезок, их соединяющий.
Обобщением понятия отрезка для нескольких точек является их выпуклая линейная комбинация.
Точка Х называетсявыпуклой линейной комбинацией точек , если выполняются условия
Множество точек являетсявыпуклым, если оно вместе с любыми своими двумя точками содержит их произвольную выпуклую, линейную комбинацию.
Можно доказать следующую теорему о представлении выпуклого многогранника.
Теорема 1.1. Выпуклый п-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.
Из теоремы 1.1 следует, что выпуклый многогранник порождается своими угловыми точками или вершинами: отрезок – двумя точками, треугольник – тремя, тетраэдр – четырьмя точками и т.д. В то же время выпуклая многогранная область, являясь неограниченным множеством, не определяется однозначно своими угловыми точками: любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.
Свойства задачи линейного программирования. Ранее были рассмотрены различные формы задачи линейного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей или канонической задачи.
Для обоснования свойств задачи линейного программирования и методов ее решения целесообразно рассмотреть еще два вида записи канонической задачи.
Матричная форма записи:
Здесь С – матрица-строка, А – матрица системы, Х – матрица-столбец переменных, В – матрица-столбец свободных членов:
Векторная форма записи:
где векторы соответствуют столбцам коэффициентов при неизвестных.
Выше была сформулирована, но не доказана в общем виде следующая теорема.
Теорема 1.2. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
Доказательство: Пусть - два допустимых решения ЗЛП, заданной в матричной форме. Тогда и . Рассмотрим выпуклую линейную комбинацию решений , т.е.
и покажем, что она также является допустимым решением системы (1.3). В самом деле
т.e. решение X удовлетворяет системе (1.3). Но так как , то и Х >0, т.е. решение удовлетворяет условию неотрицательности.
Итак, доказано, что множество всех допустимых решений задачи линейного программирования является выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которые в дальнейшем будем называть одним термином – многогранником решений.
Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение задачи линейного программирования, дается в следующей фундаментальной теореме.
Теорема 1.3. Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек.
Доказательство: Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через , а оптимальное решение - через X* . Тогда F(X*) ³ F(X) для всех точек Х многогранника решений. Если X* – угловая точка, то первая часть теоремы доказана.
Предположим, что X* не является угловой точкой, тогда на основании теоремы 1.1 X* можно представить как выпуклую линейную комбинацию угловых точек многогранника решений, т.е.
Так как F(X) – линейная функция, получаем
В этом разложении среди значений выберем максимальное. Пусть оно соответствует угловой точке X k (1 £ k £ р) ; обозначим его через М, т.е. . Заменим в выражении (1.5) каждое значение этим максимальным значением М. Тогда
По предположению Х
* – оптимальное решение, поэтому, с одной стороны, ,но, с другой стороны, доказано, что
F(X*)
£ М,
следовательно, , где X k
– угловая точка. Итак, существует угловая точка X k
, в которой линейная функция принимает максимальное значение.
Для доказательства второй части теоремы допустим, что целевая функция принимает максимальное значение более чем в одной угловой точке, например, в точках , где , тогда
Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е.
В этом случае, учитывая, что функция F(X) – линейная, получим
т.е. линейная функция F принимает максимальное значение в произвольной точкеХ , являющейся выпуклой линейной комбинацией угловых точек.
Замечание. Требование ограниченности многогранника решений в теореме является существенным, так как в случае неограниченной многогранной области, как отмечалось в теореме 1.1, не каждую точку такой области можно представить выпуклой линейной комбинацией ее угловых точек.
Доказанная теорема является фундаментальной, так как она указывает принципиальный путь решения задач линейного программирования. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необходимо исследовать лишь конечное число угловых точек многогранника решений.
Следующая теорема посвящена аналитическому методу нахождения угловых точек.
Теорема 1.4. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.
Доказательство: Пусть – допустимое базисное решение системы ограничений ЗЛП (1.4), в котором первые т компонент - основные переменные, а остальные п - т компонент – неосновные переменные, равные нулю в базисном решении (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что Х
Предположим противное, т.е. что Х не является угловой точкой. Тогда точку Х можно представить внутренней точкой отрезка, соединяющего две различные, не совпадающие с X, точки
другими словами, – выпуклой линейной комбинацией точек многогранника решений, т.е.
где (полагаем, что , ибо в противном случае точка Х совпадает с точкой Х 1 или Х 2).
Запишем векторное равенство (1.6) в координатной форме:
Т.к. все переменные и коэффициенты неотрицательны, то из последних п-т равенств следует, что , т.е. в решениях Х 1 , Х 2 и Х системы уравнений (1.4) значения п - т компонент равны в данном случае нулю. Эти компоненты можно считать значениями неосновных переменных. Но значения неосновных переменных однозначно определяют значения основных, следовательно,
Таким образом, все п компонент в решениях Х 1 , Х 2 и Х совпадают, и значит, точки Х 1 и Х 2 сливаются, что противоречит допущению. Следовательно, X – угловая точка многогранника решений.
Докажем обратное утверждение. Пусть – угловая точка многогранника решений и первые ее т координат положительны. Покажем, что Х – допустимое базисное решение. не является угловой точкой, что противоречит условию. Следовательно, наше допущение неверно, т.е. векторы линейно независимы и Х – допустимое базисное решение задачи (1.4).
Из теорем 1.3 и 1.4 непосредственно вытекает важное следствие: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.
Итак, оптимум линейной функции задачи линейного программирования следует искать среди конечного числа ее допустимых базисных решений.
Общая задача линейного программирования (ОЗЛП) формулируется следующим образом – найти переменные задачи x 1 , x 2 , ..., x n , которые обеспечивают экстремум целевой функции
Допустимым решением (планом) задачи линейного программирования (ЗЛП) называется любой n -мерный вектор X =(x 1 , x 2 , ..., x n), удовлетворяющий системе ограничений равенств и неравенств. Множество допустимых решений задачи образует область допустимых решений D .
Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение, при котором целевая функция Z (X ) достигает экстремума.
Каноническая задача линейного программирования (КЗЛП) имеет вид
(1.2)
Она отличается от ОЗЛП тем, что её система ограничений является системой только уравнений и все переменные неотрицательные.
Приведение ОЗЛП к каноническому виду ЗЛП:
Чтобы заменить исходную задачу минимизации на задачу максимизации (или наоборот задачу максимизации на задачу минимизации) достаточно целевую функцию умножить на «-1» и искать максимум (минимум) полученной функции;
Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных x n +1 ≥ 0 они преобразуются в равенства:
неравенство a i 1 x 1 +…+a in x n ≥ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ,
неравенство a i 1 x 1 +…+a in x n ≤ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ;
Если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательны-ми переменными: x k = x " k – x ” k , где x " k ≥ 0. x ” k ≥ 0.
Графический метод решения ЗЛП с двумя неизвестными
ЗЛП с двумя неизвестными имеет вид:
Метод основан на возможности графического изображения области допустимых решений и нахождении среди них оптимального решения.
Область допустимых решений (ОДР) задачи является выпуклым многоугольником и строится как пересечение (общая часть) областей решений каждого из неравенств ограничений задачи.
Областью решения неравенства a i 1 x 1 +a i 2 x 2 ≤ b i является одна из двух полуплоскостей, на которые прямая a i 1 x 1 +a i 2 x 2 = b i , соответствующая этому неравенству, делит координатную плоскость. Чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на разделяющей прямой подставить в неравенство:
Если неравенство справедливо, то областью решений является полуплоскость, содержащая эту точку;
Если неравенство не справедливо, то областью решений является полуплоскость, не содержащая эту точку.
Для нахождения среди допустимых решений оптимального используются линии уровня.
Линией уровня называется прямая с 1 x 1 +с 2 x 2 = l , где l = const, на которой целевая функция задачи принимает постоянное значение. Все линии уровня параллельны между собой.
Градиент целевой функции grad Z (X ) задает вектор нормали C = (c 1 , c 2) линий уровня. Целевая функция на линиях уровня возрастает, если линии уровня перемещать в направлении их нормали, и убывает – в противоположном направлении.
Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с ОДР и по отношению к которой ОДР находится в одной из полуплоскостей. ОДР задачи имеет не более двух опорных прямых.
Оптимальное решение ЗЛП лежит на опорной прямой в угловой точке многоугольника ОДР. ЗЛП имеет единственное решение, если опорная прямая проходит через одну угловую точку ОДР, бесконечное множество решений, если опорная прямая проходит через ребро многоугольника ОДР. ЗЛП не имеет решения, если ОДР является пустым множеством (когда система ограничений несовместна) и если ОДР неограниченна в направлении экстремума (целевая функция неограниченна).
Алгоритм графического метода решения ЗЛП с двумя неизвестными:
Построить ОДР.
Построить вектор нормали C = (c 1 , c 2) и линию уровня с 1 x 1 +с 2 x 2 = 0, проходящую через начало координат и перпендикулярную вектору С .
Передвигать линию уровня до опорной прямой в направлении вектора С в задаче на max, или в противоположном направлении – в задаче на min.
Если при перемещении линии уровня в направлении экстремума ОДР уходит в бесконечность, то ЗЛП не имеет решения ввиду неограниченности целевой функции.
Если ЗЛП имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих ОДР и имеющих общие точки с опорной прямой. Если экстремум достигается в двух угловых точках, то ЗЛП имеет бесконечное множество решений, принадлежащих ребру ОДР, ограниченному этими угловыми точками. В данном случае вычисляются координаты обеих угловых точек.
Вычислить значение целевой функции в точке экстремума.
Симплекс-метод решения ЗЛП
Симплекс-метод основывается на следующих положениях:
ОДР задачи линейного программирования является выпуклым множеством с конечным числом угловых точек;
Оптимальным решением ЗЛП является одна из угловых точек ОДР. Угловые точки ОДР алгебраически представляют некоторые базисные (опорные) решения системы ограничений ЗЛП.
Базисным (опорным) решением ЗЛП называется такое допустимое решение X 0 =( x 10 , x 20 , ..., x m 0 , 0,…0), для которого векторы условий (столбцы коэффициентов при неизвестных в системе ограничений) линейно независимы.
Ненулевые координаты x 10 , x 20 , ..., x m 0 решения X 0 называются базисными переменными, оставшиеся координаты решения X 0 - свободными переменными. Число отличных от нуля координат опорного решения не может быть больше ранга r системы ограничений ЗЛП (числа линейно независимых уравнений в системе ограничений ЗЛП). Далее считаем, что система ограничений ЗЛП состоит из линейно независимых уравнений, т.е. r = m .
Смысл симплекс-метода заключается в целенаправленном переходе от одного опорного решения ЗЛП к другому (т.е. от одной угловой точки ОДР к другой) в направлении экстремума и состоит в последовательности этапов:
Найти начальное опорное решение;
Осуществить переход от одного опорного решения к другому;
Определить критерий достижения оптимального решения или сделать заключение об отсутствии решения.
Алгоритм выполнения Симплекс-метода ЗЛП
Алгоритм симплекс-метода осуществляет переход от одного опорного решения ЗЛП к другому в направлении экстремума целевой функции.
Пусть ЗЛП задана в каноническом виде (1.2) и выполнено условие
b i ≥ 0, i =1,2,…,m , (1.3)
соотношение (1.3) всегда можно выполнить, домножив соответствующее уравнение на «-1» в случае отрицательности b i . Также считаем, что система уравнений в ограничениях задачи (1.2) линейно независима и имеет ранг r = m . При этом вектор опорного решения имеет m ненулевых координат.
Пусть исходная задача (1.2), (1.3) приведена к виду, где базисные переменные x 1 , x 2 , ..., x m выражены через свободные переменные x m + 1 , x m + 2 , ..., x n
(1.4)
На основе этих соотношений построим таблицу 1
Таблица 1.
Таблица 1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменениями содержания этой таблицы.
Алгоритм с имплекс-метода :
1. В последней строке Z симплекс-таблицы в задаче на min находят наименьший положительный элемент (в задаче на max - наименьший отрицательный элемент), не считая свободного члена. Столбец, ответствующий этому элементу, называется разрешающим.
2. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс - отношений, оно соответствует разрешающей строке.
3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.
4. Если имеется несколько одинаковых по величине симплекс - отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симлекс - таблицы.
5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс - таблица преобразуется следующим образом (таблица 2):
Таблица 2
6. Элемент таблицы 2, соответствующий разрешающему элементу таблицы 1, равен обратной величине разрешающего элемента.
7. Элементы строки таблицы 2, соответствующие элементам разрешающей строки таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент.
8. Элементы столбца таблицы 2, соответствующие элементам разрешающего столбца таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент и берутся с противоположным знаком.
9. Остальные элементы вычисляются по правилу прямоугольника : мысленно вычерчиваем прямоугольник в таблице 1, одна вершина которого совпадает с разрешающим элементом (Рэ), а другая – с элементом, который мы ищем; обозначим элемент в новой таблице 2 через (Нэ), а элемент, стоящий на этом же месте в старой таблице 1 – через (Сэ). Остальные две вершины А и В дополняют фигуру до прямоугольника. Тогда искомый элемент Нэ из таблицы 2 равен Нэ = Сэ – А*В/Рэ.
10. Критерий оптимальности. Как только получится таблица, у которой в последней строке в задаче на min все элементы отрицательны (в задаче на max все элементы положительны), считается, что экстремум найден. Оптимальное значение целевой функции равно свободному члену в строке Z, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные полагаются равными нулю.
11.Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).
Метод искусственного базиса решения ЗЛП
Алгоритм симплекс-метода применим, если выделено какое-либо опорное решение ЗЛП, т. е, исходная ЗЛП (1.2) приведена к виду (1.4). Метод искусственного базиса предлагает процедуру построения такого опорного решения.
Метод искусственного базисаоснован на введении искусственных базисных переменных y 1 , y 2 ,…, y m , с помощью которых система ограничений ЗЛП (2.2)
(1.5)
может быть преобразована к виду
(1.6)
Системы (1.5) и (1.6) будут эквивалентны в том случае, если все y i будут равны нулю. Как и раньше мы считаем, что все b i ≥ 0. Для того чтобы у i были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные базисные переменные y i перешли в свободные переменные. Такой переход можно сделать алгоритмом симплекс метода относительно дополнительной целевой функции
F (y ) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)
Исходная симплекс таблица для данного метода имеет вид
Сначала симплекс таблица преобразуется относительно целевой функции F (y ) до получения опорного решения. Опорное решение найдено, когда выполнен следующий критерий: F (y ) = 0 и все искусственные переменные у i переведены в свободные переменные. Затем из симплекс таблицы вычеркивается строка для F (y ) и столбцы для у i и решают задачу для исходной целевой функции Z (x ) до получения оптимального решения.
Оптимизация линейных моделей в MS Excel производится симплекс-методом - целенаправленным перебором опорных решений задачи линейного программирования. Алгоритм симплекс-метода сводится к построению выпуклого многогранника в многомерном пространстве, а затем к перебору его вершин с целью поиска экстремального значения целевой функции .Эффективные средства линейного программирования лежат в основе и целочисленного и нелинейного программирования для решения более сложных задач оптимизации. Эти методы, однако, требуют более длительного времени для вычислений.
В последующих лекциях будут подробно разобраны примеры решения типичных задач оптимизации и принятия управленческих решений с помощью надстройки MS Excel " Поиск решения". Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:
- имеется единственная цель, функционально связанная с другими параметрами системы, которую нужно оптимизировать (найти ее максимум, минимум или определенное числовое значение);
- имеются ограничения, выражающиеся, как правило, в виде неравенств (например, объем используемого сырья не может превышать запасов сырья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);
- имеется набор входных значений-переменных, влияющих на оптимизируемые величины и на ограничения.
Параметры задач ограничиваются такими предельными показателями:
- количество неизвестных – 200;
- количество формульных ограничений на неизвестные – 100;
- количество предельных условий на неизвестные – 400.
Алгоритм поиска оптимальных решений включает в себя несколько этапов:
- подготовительные работы;
- отладка решения;
- анализ решения .
Последовательность необходимых подготовительных работ , выполняемых при решении задач экономико-математического моделирования с помощью MS Excel , приведена на блок-схеме рисунка 1.6 .
Рис.
1.6.
Из приведенных пяти пунктов плана подготовительных работ только пятый пункт является формализуемым. Остальные работы требуют творчества - и разными людьми они могут быть выполнены по -разному. Кратко поясним сущность формулировок пунктов плана.
При постановке задачи известны целевые коэффициенты
и нормированные коэффициенты
.
В предыдущем примере коэффициентами, формирующими целевую функцию, служили значения нормированной прибыли на одну полку типа
(
) и одну полку типа (
). Нормированными коэффициентами
служили нормы расхода
материала и машинного времени на одну полку каждого типа. Матрица
имела следующий вид:
Кроме того, всегда известны значения ресурсов
. В предыдущем примере это был
недельный запас досок и возможности использовать
машинное время: 
, 
. Часто в задачах значения переменных
требуется
ограничить. Поэтому нужно определить нижний и верхний пределы области их изменений.
Таким образом, в диалоговом окне оптимизационной программы " Поиск решения" мы должны задать следующий целевой алгоритм :
Целевая функция равна произведению вектора искомых значений переменных на вектор целевых коэффициентов
Нормированных коэффициентов на вектор искомых значений переменных не должен превышать значения заданного вектора ресурсов
Значения переменной должны находиться в заданных пределах число исходных элементов системы
Число исходных элементов системы
Число заданных видов ресурсов
Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):
Рис. 1.7.
- если не получено допустимое решение, то выполнить корректировку модели исходных данных;
- если не получено оптимальное решение , то ввести дополнительные ограничения.
Программа выдает оптимальное решение только для модели реальной проблемы, а не решение самой проблемы. При построении модели были сделаны различные упрощающие допущения реальной ситуации. Это позволило формализовать процесс, приближенно отобразив реальные количественные зависимости между параметрами системы и целью. А если реальные параметры будут отличаться от тех, которые заложены в модели, то как изменится решение? Чтобы узнать это, перед принятием управленческого решения проводят анализ решения модели.
Анализ оптимального решения , встроенный в программу, представляет собой заключительный этап математического моделирования экономических процессов. Он позволяет осуществить более глубокую проверку соответствия модели процессу, а также надежности оптимального решения. Он основывается на данных оптимального решения и отчетов, которые выдаются в "Поиске решения". Но он не исключает и не заменяет традиционного анализа плана с экономических позиций перед принятием управленческого решения.
Экономический анализ ставит перед собой следующие цели :
- определение возможных последствий в системе в целом и ее элементах при изменении параметра модели;
- оценка устойчивости оптимального плана к изменению отдельных параметров задачи: если он не устойчив к изменению большинства параметров, снижается гарантия его выполнения и достижения рассчитанного оптимума;
- проведение вариантных расчетов и получение новых вариантов плана без повторного решения задачи от исходного базиса с помощью корректировки.
Возможные методы анализа представлены в схеме на рисунке 1.8 .
После получения оптимального решения проводится его анализ по полученным отчетам. Анализ устойчивости - изучение влияния изменений отдельно взятых параметров модели на показатели оптимального решения. Анализ пределов - анализ допустимых изменений в оптимальном плане, при котором план остается оптимальным.
Учитывая ответственность принятия экономического управленческого решения , руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:
- "что будет, если…"
- "что надо, чтобы…"
Анализ с целью ответа на первый вопрос называется вариантным анализом ; анализ с целью ответа на второй вопрос называется решениями по заказу.
Вариантный анализ бывает следующих видов:
- Параметрический - анализ, который заключается в решении задачи при различных значениях некоторого параметра.
- Структурный анализ - когда решение задачи оптимизации ищется при различной структуре ограничений.
- Многокритериальный анализ - это решение задачи по разным целевым функциям.
- Анализ при условных исходных данных - когда исходные данные, используемые при решении задачи, зависят от соблюдения дополнительных условий.
После проведения анализа следует представить результаты в графической форме и составить отчет с рекомендациями о принятии решения с учетом конкретной экономической ситуации.
Тест по дисциплине «Исследование операций»
(верные ответы - первые)
1. Термин "исследование операций” появился …
в годы второй мировой войны
в 50-ые годы XX века
в 60-ые годы XX века
в 70-ые годы XX века
в 90-ые годы XX века
в начале XXI века
2. Под исследованием операций понимают (выберите наиболее подходящий вариант) …
комплекс научных методов для решения задач эффективного управления организационными системами
комплекс мер, предпринимаемых для реализации определенных операций
комплекс методов реализации задуманного плана
научные методы распределения ресурсов при организации производства
3. Упорядочьте этапы, через которые, как правило, проходит любое операционное исследование:
постановка задачи
построение содержательной (вербальной) модели рассматриваемого объекта (процесса)
построение математической модели
решение задач, сформулированных на базе построенной математической модели
проверка полученных результатов на адекватность природе изучаемой системы
реализация полученного решения на практике
4. В исследовании операций под операцией понимают…
всякое мероприятие (систему действий), объединенное единым замыслом и направленное на достижение какой-либо цели
всякое неуправляемое мероприятие
комплекс технических мероприятий, обеспечивающих производство продуктов потребления
5. Решение называют оптимальным, …
если оно по тем или иным признакам предпочтительнее других
если оно рационально
если оно согласовано с начальством
если оно утверждено общим собранием
6. Математическое программирование …
занимается изучением экстремальных задач и разработкой методов их решения
представляет собой процесс создания программ для компьютера под руководством математиков
занимается решением математических задач на компьютере
7. Задача линейного программирования состоит в …
отыскании наибольшего (наименьшего) значения линейной функции при наличии линейных ограничений
создании линейной программы на избранном языке программирования, предназначенной для решения поставленной задачи
описании линейного алгоритма решения заданной задачи
8. В задаче квадратичного программирования…
целевая функция является квадратичной
область допустимых решения является квадратом
ограничения содержат квадратичные функции
9. В задачах целочисленного программирования…
неизвестные могут принимать только целочисленные значения
целевая функция должна обязательно принять целое значение, а неизвестные могут быть любыми
целевой функцией является числовая константа
10. В задачах параметрического программирования…
целевая функция и/или система ограничений содержит параметр(ы)
область допустимых решения является параллелограммом или параллелепипедом
количество переменных может быть только четным
11. В задачах динамического программирования…
процесс нахождения решения является многоэтапным
необходимо рационализировать производство динамита
требуется оптимизировать использование динамиков
12. Поставлена следующая задача линейного программирования:
F (х 1, х 2) = 5х 1 + 6х 2→ mах
0.2х 1 + 0.3х 2 ≤ 1.8,
0.2х 1 + 0.1х 2 ≤ 1.2,
0.3х 1 + 0.3х 2 ≤ 2.4,
х 1 ≥ 0, х 2 ≥ 0.
Выберите задачу, которая эквивалентна этой задаче.
F (х 1, х 2)= 5х 1 + 6х 2 → mах ,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
х 1 + х 2 ≤ 8,
х 1 ≥ 0,
х 2 ≥ 0.
F (х 1, х 2)= 6х 1 + 5х 2 → min,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
х 1 + х 2 ≤ 8,
х 1 ≥ 0,
х 2 ≥ 0.
F (х 1, х 2)= 50х 1 + 60х 2 → mах ,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
х 1 + х 2 ≤ 8,
х 1 ≥ 0,
х 2 ≥ 0.
F (х 1, х 2)= 5х 12 + 6х 22 → mах ,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
3х 1 + х 2 ≤ 2.4,
х 1 ≥ 0,
х 2 ≥ 0.
13. Целевой функцией задачи линейного программирования может являться функция:
F =12x1 +20x2–3 0x3 →min
F = →min
F
=
→max
F =→max.
14. Системой ограничений задачи линейного программирования может являться система:
15. Симплекс-метод - это:
аналитический метод решения основной задачи линейного программирования
метод отыскания области допустимых решений задачи линейного программирования;
графический метод решения основной задачи линейного программирования;
метод приведения общей задачи линейного программирования к каноническому виду.
16. Задача линейного программирования состоит в:
отыскании наибольшего или наименьшего значения линейной функции при наличии линейных ограничений
разработке линейного алгоритма и реализации его на компьютере
составлении и решении системы линейных уравнений
поиске линейной траектории развития процесса, описываемого заданной системой ограничений.
17. Область допустимых решений задачи линейного программирования не может выглядеть так:
18. Целевой функцией задачи линейного программирования может являться функция:
F =12x1 +20x2–3 0x3 →min
F = →min
F
=→max
F =→max.
19.Системой ограничений задачи линейного программирования может являться система:
20. Область допустимых решений задачи линейного программирования имеет вид:
F (х 1, х 2)= 3х 1 + 5х 2 равно…
21. Область допустимых решений задачи линейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= 5х 1 + 3х 2 равно…
22. Область допустимых решений задачи линейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= 2х 1 - 2х 2 равно…
23. Область допустимых решений задачи линейного программирования имеет вид:
F (х 1, х 2)= 2х 1 - 2х 2 равно…
24. Область допустимых решений задачи нелинейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= х 2 – х 12 равно…
25. Максимальное значение целевой функции F
(х
1, х
2)= 5х
1 + 2х
2 при ограничениях
х
1 + х
2 ≤ 6,
х 1 ≤ 4,
х 1 ≥ 0, х 2 ≥ 0, равно …
26. Малое предприятие производит изделия двух видов. На изготовление одного изделия вида А расходуется 2 кг сырья, на изготовление одного изделия вида В – 1 кг. Всего имеется 60 кг сырья. Требуется составить план производства, обеспечивающий получение наибольшей выручки, если отпускная стоимость одного изделия вида А 3 д. е., вида В - 1 у. е., причем изделий вида А требуется изготовить не более 25, а вида В – не более 30.
Данная задача является …
задачей линейного программирования
задачей, решаемой методом динамического программирования
задачей сетевого планирования.
27. Малое предприятие производит изделия двух видов. На изготовление одного изделия вида А расходуется 2 кг сырья, на изготовление одного изделия вида В – 1 кг. Всего имеется 60 кг сырья. Требуется составить план производства, обеспечивающий получение наибольшей выручки, если отпускная стоимость одного изделия вида А 3 д. е., вида В - 1 у. е., причем изделий вида А требуется изготовить не более 25, а вида В – не более 30.
Целевой функцией данной задачи является функция …
F (x1,x2 )=3x1 +x2 →max
F (x1,x2 )=25x1 +30x2 →max
F (x1,x2 )=2x1 +x2 →max
F (x1,x2 )=60 -2x1 - x2 →min
28. Малое предприятие производит изделия двух видов. На изготовление одного изделия вида А расходуется 2 кг сырья, на изготовление одного изделия вида В – 1 кг. Всего имеется 60 кг сырья. Требуется составить план производства, обеспечивающий получение наибольшей выручки, если отпускная стоимость одного изделия вида А 3 д. е., вида В - 1 у. е., причем изделий вида А требуется изготовить не более 25, а вида В – не более 30
Допустимым планом данной задачи является план:
X= (20, 20)
X= (25, 15)
X= (20, 25)
X= (30, 10)
29. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной.
Данная задача является …
транспортной задачей
задачей нелинейного программирования
задачей коммивояжера
задачей о назначениях
30. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной
Опорным планом данной задачи является план:
;
31. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной.
Целевой функцией данной задачи является функция:
F =4x11 +6x12+ 8x13 +5x21 +8x22 +7x23 →min
F = →min
F =60x1 +160x2+ 80x3 +70x4 +705 →max
F =60x1 +160x2– 80x3– 70x4– 705 →min
32. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной.
Оптимальным планом данной задачи является план:
;
.
;
;
33. Транспортная задача
будет закрытой, если…
34. Транспортная задача
является…
открытой
закрытой
неразрешимой
35. Транспортная задача
является…
закрытой
открытой
неразрешимой
36. Для решения следующей транспортной задачи
необходимо ввести…
фиктивного потребителя
фиктивного поставщика;
эффективный тариф
37. Для решения следующей транспортной задачи
необходимо ввести…
фиктивного поставщика;
фиктивного потребителя
эффективный тариф
эффективную процентную ставку.
38. Среди данных транспортных задач
закрытыми являются…
39. Исходный опорный план транспортной задачи можно составить…
всеми перечисленными методами
методом северо-западного угла
методом минимального тарифа
методом двойного предпочтения
методом аппроксимации Фогеля
40. Если целевая функция задачи линейного программирования задана на максимум, то… целевая функция двойственной задачи задается на минимум
целевая функция в двойственной задаче отсутствует
двойственная задача не имеет решений
двойственная задача имеет бесконечно много решений
41. Дана задача линейного программирования:
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 ≥ 0, х 2 ≥ 0.
Двойственной для этой задачи будет следующая…
F* (y1, y2)= 14y1 + 8y2 → min ,
3y 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
F* (y1, y2)= 2y1 + 7y2 → min ,
2y1 + 3y2 ³ 14,
y 1 + y2 ³ 8,
y 1 £ 0, y2 £ 0.
F* (y1, y2)= 2y1 + 7y2 → min ,
3 y 1 + y2 ³ 7,
y 1 £ 0, y2 £ 0.
F* (y1, y2)= 14y1 + 8y2 → min ,
y 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
42. Если одна из пары двойственных задач имеет оптимальный план, то…
и другая имеет оптимальный план
другая не имеет оптимального плана
другая не имеет допустимых решений
43. Если одна из пары двойственных задач имеет оптимальный план, то…
и другая имеет оптимальный план и значения целевых функций при их оптимальных планах равны между собой
и другая имеет оптимальный план, но значения целевых функций при их оптимальных планах не равны между собой
другая задача может не иметь оптимального плана, но иметь допустимые решения
44. Если целевая функция одной из пары двойственных задач не ограничена (для задачи на максимум – сверху, для задачи на минимум - снизу), то
другая задача не имеет допустимых планов
другая задача имеет допустимые планы, но не имеет оптимального плана
целевая функция другой задачи также не ограничена
45. При решении некоторых задач нелинейного программирования применяется …
метод множителей Лагранжа
метод Гаусса
метод аппроксимации Фогеля
метод Гомори
46. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → mах ,
х 1 + х 2 =6,
х 1 ≥ 0, х 2 ≥ 0.
F (х 1, х 2) …
не достижимо (+ ¥)
47. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → m in ,
х 1 + х 2 =6,
х 1 ≥ 0, х 2 ≥ 0.
F (х 1, х 2) …
48. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → mах ,
х 1 + х 2 =6,
х 1, х 2 - любые.
Наибольшее значение целевой функции F (х 1, х 2) …
не достижимо (+ ¥)
49. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → m in ,
х 1 + х 2 =6,
х 1, х 2 - любые.
Наименьшее значение целевой функции F (х 1, х 2) …
не достижимо (- ¥)
50. Область допустимых решений задачи нелинейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= х 12 +х 22 равно…
51. Область допустимых решений задачи нелинейного программирования имеет вид:
Тогда минимальное значение функции F (х 1, х 2)= х 12 +х 22 равно…
52. Для решения транспортной задачи может применяться…
метод потенциалов
метод множителей Лагранжа
метод Гаусса
метод дезориентации
53. В системе ограничений общей задачи линейного программирования …
54. В системе ограничений стандартной (симметричной) задачи линейного программирования …
могут присутствовать только неравенства
могут присутствовать и уравнения, и неравенства
могут присутствовать только уравнения
55. В системе ограничений канонической (основной) задачи линейного программирования …
могут присутствовать только уравнения (при условии неотрицательности переменных)
могут присутствовать только неравенства (при условии неотрицательности переменных)
могут присутствовать и уравнения, и неравенства (при условии неотрицательности переменных)
56. Задача линейного программирования
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 ≥ 0, х 2 ≥ 0.
записана в …
стандартной (симметричной) форме
канонической (основной) форме
словесной форме
57. Для записи задачи
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 ≥ 0, х 2 ≥ 0.
в канонической форме …
58. Для записи задачи
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 + 4х 2 ≥ 10,
х 1 ≥ 0, х 2 ≥ 0.
в канонической форме …
необходимо ввести три дополнительных неотрицательных переменных
необходимо ввести две дополнительных неотрицательных переменных
необходимо ввести четыре дополнительных неотрицательных переменных
59. Для записи задачи
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 = 14,
х 1 + х 2 ≤ 8,
х 1 + 4х 2 ≥ 10,
х 1 ≥ 0, х 2 ≥ 0.
в канонической форме …
необходимо ввести две дополнительных неотрицательных переменных
необходимо ввести три дополнительных неотрицательных переменных
необходимо ввести четыре дополнительных неотрицательных переменных
необходимо ввести пять дополнительных неотрицательных переменных
60. При решении задач целочисленного программирования может применяться …
метод Гомори
метод множителей Лагранжа
метод Гаусса
метод аппроксимации Фогеля
61. В основе решения задач методом динамического программирования лежит…
принцип «бритва Оккама»
принцип «зуб - за зуб, око - за око»
принцип Гейзенберга
62 . Ситуация, в которой участвуют стороны, интересы которых полностью или частично противоположны, называется …
(конфликтной, конфликтная, конфликт, конфликтом)
63. Действительный или формальный конфликт, в котором имеется по крайней мере два участника (игрока), каждый из которых стремится к достижению собственных целей, называется …
(игра, игрой)
64. Допустимые действия каждого из игроков, направленные на достижение некоторой цели, называются …
(правила игры, правилами игры)
65. Количественная оценка результатов игры называется …
(платежом, платеж, платёж)
66. Если в игре участвует только две стороны (два лица), то игра называется…
(парной, парная, парной игрой, парная игра)
67. Если в парной игре сумма платежей равна нулю, то есть проигрыш одного игрока равен выигрышу другого, то игра называется игрой…
(с нулевой суммой)
68. Однозначное описание выбора игрока в каждой из возможных ситуаций, при которой он должен сделать личный ход, называется..
(стратегией игрока, стратегия игрока, стратегией, стратегия)
69. Если при многократном повторении игры стратегия обеспечивает игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш), то такая стратегия называется…
(оптимальной, оптимальная, оптимальной стратегией, оптимальная стратегия)
70. Пусть a - нижняя цена, а b - верхняя цена парной игры с нулевой суммой. Тогда верно утверждение…
71. Пусть a - нижняя цена, а b - верхняя цена парной игры с нулевой суммой. Если a = b = v, то число v называется …
ценой игры
точкой равновесия
оптимальной стратегией
смешанной стратегией
72. Пусть a - нижняя цена, а b - верхняя цена парной игры с нулевой суммой. Если a = b, то игра называется…
игрой с седловой точкой
неразрешимым конфликтом
игрой без правил
73. Вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии, называется…
смешенной стратегией
направляющим вектором
вектором нормали
градиентом
74. Нижняя цена матричной игры, заданной платежной матрицей , равна…
Больше нижней цены
равна нижней цене
не существует
81. Матричная игра, заданная платежной матрицей , …
имеет седловую точку
не имеет седловой точки
не является парной
82. Цена игры, заданной платежной матрицей , равна…
83. Матричная игра, заданная платежной матрицей , …
является парной
имеет седловую точку
не является парной
84. Парная игра с нулевой суммой, заданная своей платежной матрицей, может быть сведена к …
задаче линейного программирования
задаче нелинейного программирования
целочисленной задаче линейного программирования
классической задаче оптимизации
85. Нижняя цена матричной игры, заданной платежной матрицей , равна…
Больше нижней цены
равна нижней цене
не существует
92. Матричная игра, заданная платежной матрицей , …
не имеет седловой точки
имеет седловую точку
не является парной
93. Цена игры, заданной платежной матрицей , заключена в пределах…
94. Если в потоке событий события следуют одно за другим через заранее заданные и строго определенные промежутки времени, то такой поток называется …
регулярным
организованным
95. Если вероятность попадания любого числа событий на промежуток времени зависит только от длины этого промежутка и не зависит от того, как далеко расположен этот промежуток от начала отсчета времени, то соответствующий поток событий называется:
стационарным
потоком без последствий
простейшим
пуассоновским
96. Если число событий, попадающих на один из произвольно выбранных промежутков времени, не зависит от числа событий, попавших на другой, также произвольно выбранный промежуток времени при условии, что эти промежутки не пересекаются, то соответствующий поток событий называется …
потоком без последствий
регулярным
показательным
нормальным
97. Если вероятность попадания на очень малый отрезок времени сразу двух или более событий пренебрежимо мала по сравнению с вероятностью попадания только одного события, то соответствующий поток событий называется…
ординарным
неординарным
нормальным
пуассоновским
98. Если поток событий одновременно обладает свойствами стационарности, ординарности и отсутствием последствия, то он называется:
простейшим (пуассоновским)
нормальным
99. Одноканальная СМО с отказами представляет собой пост ежедневного обслуживания для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей λ=1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслуживания являются простейшими. Тогда в установившемся режиме относительная пропускная способность q равна…
100. Одноканальная СМО с отказами представляет собой пост ежедневного обслуживания для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей λ=1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслуживания являются простейшими. Тогда в установившемся режиме процент автомобилей, получающих отказ в обслуживании, равен…