Реализация оптимизационных алгоритмов в линейных моделях многоагентных систем

Реализация оптимизационных алгоритмов в линейных моделях многоагентных систем

Актуальность темы

.

Искусство управления знаниями является необходимой составляющей конкурентоспособности и развития общества в современных условиях глобализации, тесно связанных с высокотехнологичным производством и передовым менеджментом, передачей знаний и развитием телекоммуникационных и информационных технологий. Растущие требования к повышению интерактивности в автоматизированных системах поддержки учебного процесса приводят к тому, что на первое место выходят такие характеристики как информативность и коммуникативность. Административная часть таких систем также не может оставаться статичным дополнением к базам данных. Для нее тоже необходимы персонифицированные интеллектуальные интерфейсы, электронный обмен данными, сценарии исполнения рутинных дел, интеллектуальная поддержка принятия решений, а также новые эффективные процедуры поиска, создания отчетов и анализа тенденций развития учебного заведения. В последнее время такие компьютерные системы начали называть системами поддержки дистанционного обучения. Дистанционное обучение прошло стремительный путь развития. В восьмидесятые годы оно перешло в асинхронный режим обучения с использованием компьютера, начали развиваться новейшие формы обучения, такие как электронное обучение и непрерывное обучение. На данном этапе, традиционным стало использование интерактивных веб-сайтов. Разработку мультимедийных систем и баз данных, соединенных гиперлинками, доступных через универсальные веб-браузеры, принято считать основой асинхронного дистанционного обучения. Современные информационные сетевые технологии дают возможность не просто перевести учебный процесс в цифровой режим, или заменить учебную аудиторию, преподавателя и учебник компьютером — они позволяют изменить философию учебного процесса, создать новую образовательную культуру. Дистанционное обучение перешло от традиционной системы передачи знаний, построенной вокруг преподавателя, к виртуальной учебной среде и учебному сообществу, ориентированных на студента. В последние годы сделан еще один шаг к улучшению систем компьютерной поддержки дистанционного обучения (КСПДО) — реализовано множество моделей дистанционного обучения с учетом новейших тенденций создания распределенных систем и использования агентных технологий. Последние придают этим системам признаки онтологических систем и переводят пользователей этих систем из ранга пассивного получателя знаний в активных участников процесса обучения. Этот уровень достигается за счет использования таких нестандартных свойств агентов, как: реактивность — агенты реагируют на изменения среды в реальном времени (обычная их деятельность описывается таким образом «WHEN event ІF condіtіon THEN actіon»); проактивность — способность решать задачи и достигать цели (агенты не только реагируют на изменения среды, но и сами ее опрашивают); способность существовать в постоянно активном состоянии, точнее, иметь собственный поток управления; гибкость — действия агентов не фиксированы жестко; интеллектуальность (способность обучаться) — умение находить новые решения; агенты могут изменять свое поведение, используя как свой опыт, так и опыт других агентов. Становится достаточно ощутимой свобода действий такого программного комплекса и даже некоторое «сознание». Учитывая, что одной из базовых идей агентной технологии является исполнение задач (администрирования, поиска данных и т. п.) непосредственно на локальной машине, это снижает до минимума взаимодействие между администратором и узлами системы, а также минимизирует трафик. Понятно, что дальнейший прогресс компьютерных систем поддержки дистанционного обучения состоит в оптимизации сетевой структуры логического взаимодействия субъектов и объектов образовательного процесса, что отображает гибкую по логическим связям и информационному наполнению образовательную среду. В данной работе разрабатывается концепция адаптивного использования интерактивных средств программной поддержки систем дистанционного обучения на принципах построения онтологических систем и эволюционной адаптации агентной технологии в рамках построения проекта дистанционного обучения.

Цель курсовой работы: реализовать линейные модели многоагентных систем при помощи программы Ecsel

Задачи:

1.Изучение литературы по данной теме.

2.Описание оптимизационных алгоритмов

3.Реализация оптимизационных алгоритмов в линейных моделях многоагентных систем.

1. ОСНОВНЫЕ ПОНЯТИЯ АГЕНТОВ

1.1ОСНОВНЫЕ ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ

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

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

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

Мультиагентная система — сложная система, в которой функционируют два или более интеллектуальных агентов.

Процесс самоорганизации в мультиагентных системах — внутренняя упорядоченность, согласованность, взаимодействие более или менее дифференцированных и автономных агентов агентной системы, обусловленной ее строением.

1.2 ОПРЕДЕЛЕНИЯ АГЕНТОВ

Общепринятого определения «агента» еще не существует. Рассматриваемый в какой-либо системе мультиагент — это аппаратная или программная сущность, способная действовать в интересах достижения целей, поставленных перед ним владельцем и/или пользователем. Таким образом, в рамках мультиагентных систем мы рассматриваем агенты, как автономные компоненты, действующие по определенному сценарию. Классифицируются агенты на четыре основных типа: простые, умные (smart), интеллектуальные (intelligent) и действительно интеллектуальные (truly intelligent).

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

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

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

1.3 СВОЙСТВА АГЕНТОВ

1.Автономность: агенты функционируют без прямого вмешательства людей или кого-либо другого и владеют определенной способностью контролировать свои действия и внутреннее состояние.

2.Общественное поведение (social ability):агенты взаимодействуют с другими агентами средствами некоторого коммуникационного языка.

3.Реактивность: агенты способны воспринимать окружающую среду (которая может быть физическим миром, пользователем, взаимодействующим через графический интерфейс, коллекцией других агентов, Іnternet-ом, или, возможно, всем вместе взятым) и адекватно реагировать в определенных временных рамках на изменения, которые происходят.

3.Целенаправленная активность: агенты не просто реагируют на изменения среды, но и обладают целенаправленным поведением и способностью проявлять инициативу.

5.Индивидуальная картина мира: каждый агент имеет собственную модель окружающего его мира (среды), которая описывает то, как агент видит мир. Агент строит свою модель мира на основе информации, которую получает из внешней среды.

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

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

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

Классификацию агентов можно провести в двух направлениях — по их инструментальной реализации (языку программирования агентов) и по основным приметам, которыми они владеют.

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

Следовательно, система разработки, которая бы полностью соответствовала требованиям построения агентов, должна была бы соответствовать таким требованиям: обеспечение перенесения кода на различные платформы, доступность на многих платформах, поддержка сетевого взаимодействия, многопотоковая обработка и некоторые другие. Чаще всего в агентных технологиях используются: универсальные языки программирования (Java); языки, «ориентированы на знания», такие, как языки представления знаний (KIF), языки переговоров и обмена знаниями (KQML, AgentSpeak, April), языки спецификаций агентов; специализированные языки программирования агентов (TeleScript); языки сценариев и scripting languages (Tcl/Tk); символьные языки и языки логического программирования (Oz).

Одно из самых главных свойств агента — это интеллектуальность. Интеллектуальный агент владеет определенными знаниями о себе и об окружающей среде, и на основе этих знаний он способен определять свое поведение. Интеллектуальные агенты являются основной областью интересов агентной технологии. Важна также среда существования агента: это может быть как реальный мир, так и виртуальный (компьютерный), что является важным в связи со всеобщим распространением сети Internet. От агентов требуют способности к обучению и даже самообучению. Поскольку обучение обуславливает наличие знаний у обучаемого, то обучаемым или самообучаемым может быть только интеллектуальный агент.

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

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

1.4 КЛАССИФИКАЦИИ АГЕНТОВ

Можно предложить немало различных оснований для построения классификаций агентов. Наиболее очевидными являются критерии классификации, связанные с полярными шкалами «естественное-искусственное» и «материальное-идеальное». По первому критерию, выделяются натуральные агенты (животные, люди, группы организмов, коллективы людей) и искусственные агенты (роботы, коллективы автоматов, сложные компьютерные программы). В данной работе описываются только искусственные агенты. По второму критерию, все искусственные агенты подразделяются на: 1) материальных, физически существующих и работающих в реальном пространстве, например, интегральные роботы) и 2) виртуальных, существующих лишь в программной среде (виртуальном пространстве); нередко такие «программные роботы» (software robots) называют сокращенно софтботами (softbots) [17, 77,113].

Еще одна пара взаимосвязанных критериев классификации опирается на дихотомии «сосредоточенное-распределенное» и «неподвижное-подвижное» [6,71,72,83,129]. Примером неподвижного агента служит стационарный манипуляционный робот, а примером мобильногопоисковый агент, мигрирующий по сети в целях отыскания нужной информации. Подчас мобильные софтботы (моботы) могут трактоваться как распределенные, чисто коммуникативные агенты, которые не имеют собственных средств восприятия и действий (поэтому они не манипулируют никакими объектами), а лишь используют располагаемые ресурсы для коммуникации с другими агентами и миграции по сети в поисках релевантных данных и процедур. Наоборот, четко локализованные агенты в определенном смысле противоположны коммуникативным: они не могут двигаться по сети и обычно не обладают способностью к представлению среды, а их общение с другими агентами происходит не напрямую, а косвенно, через механизмы восприятия и действия.

Важным основанием для классификации служит наличие (отсутствие) у агентов характеристик обучаемости или адаптивности. У обучаемых агентов поведение основано на предыдущем опыте.

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

С уровнем «свободы воли» и характером взаимодействия связаны, в частности, представления о благонамеренных (benevolent) и злонамеренных, эгоистических (self-interested) и альтруистических агентах .

Еще одним важнейшим основанием для классификации искусственных агентов служит принятие либо психологической, либо биологической метафоры при рассмотрении природы их действий (дихотомия «психологическое — биологическое»). В одном случае, речь идет о трактовке агентов как квазисубъектов, самостоятельно решающих встающие перед ними задачи, а в другом они уподобляются простейшим организмам, непосредственно реагирующим на изменения среды в интересах выживания и адаптации [60,61,72,77]. В частности, исходя из биологической метафоры, строятся «аниматы», т. е. искусственные животные, которые в процессе выживения должны приспособливаться к все более сложным и враждебным средам. Аниматы могут быть реализованы и как виртуальные агенты (имитация на компьютере), и как роботы, действующие в реальном физическом мире .

В целом, данная типология агентов тесно связана с классической проблемой взаимодействия «субъект — объект». Уровень субъектности агента непосредственно зависит от того, наделен ли он символьными представлениями, требующимися для организации рассуждений, или в противоположность этому он работает только на уровне образов (субсимвольном), связанных с сенсомоторной регуляцией. Соответствующую классификацию агентов (рис.2) можно построить по следующим двум признакам: а) степень развития внутреннего представления внешнего мира и б) способ поведения.

По первому признаку, выделяются интеллектуальные (когнитивные, рассудочные) и реактивные агенты. Когнитивные агенты [53,71,75,103,138]обладают более богатым представлением внешней среды, чем реактивные. Это достигается за счет наличия у них базы знаний и механизма решения. Близкий термин «рассудочный (deliberative) агент» служит для обозначения агента, который обладает символьной моделью внешнего мира, а также возможностью принимать решения на основе символьных рассуждений, например, метода сравнения по образцу [82,138]

Отсюда вытекает еще одно существенное различие между интеллектуальными и реактивными агентами, связанное с возможностями прогнозирования изменений внешней среды и, как следствие, своего будущего. Реактивные агенты [37,46,47,73,100,111], имеющие довольно бедное внутреннее представление внешней среды (или не имеющие его вовсе), обладают очень ограниченным диапазоном предвидения. Они практически не способны планировать свои действия, поскольку реактивность в чистом виде означает такую структуру обратной связи, которая не содержит механизмов прогноза. В то же время когнитивные агенты, благодаря развитым внутренним представлениям внешней среды и возможностям рассуждений, могут запоминать и анализировать различные ситуации, предвидеть возможные реакции на свои действия, делать из этого выводы, полезные для дальнейших действий и, в результате, планировать свое поведение.

Рис. 2. Классификация агентов

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

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

По типу поведения интеллектуальные агенты делятся на интенциональных и рефлекторных, а реактивные — на побуждаемых и трофических. Большинство интеллектуальных (когнитивных) агентов можно отнести к числу интенциональных [61,82,114,124]. Подобные агенты наделены собственными механизмами мотивации. Это означает, что в них так или иначе моделируются внутренние убеждения, желания, намерения и мотивы, порождающие цели, которые определяют их действия. В свою очередь, модульные или рефлекторные агенты не имеют внутренних источников мотивации и собственных целей, а их поведение характеризуется простейшими (одношаговыми) выводами или автоматизмами. Таким образом, они представляют собой граничный случай понятия когнитивного агента и могут использоваться как «вспомогательные агенты». Данные агенты близки к акторам: они способны отвечать на вопросы и выполнять задания, которые ставят перед ними другие агенты, но решение этих задач не приводит к появлению у них собственных целей. Типичными примерами таких вырожденных агентов являются системы поиска в базах данных и простейшие логические регуляторы.

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

Табл.1. Сравнительный анализ свойств когнитивных и реактивных агентов

Между тем, реактивные агенты также могут иметь примитивный механизм мотивации, толкающий их на выполнение задачи, например, удовлетворение набора жизненных потребностей. В частности, здесь речь может идти о поддержании требуемого энергетического баланса или, в более широком плане, условиях выживания агента как сохранения гомеостазиса (что связано со способностями определения и увеличения расстояния от границ гомеостазиса) [9,13,106]. Например, используя интегральную формулировку гомеостазиса по Г. А. Голицыну, можно утверждать, что побуждаемый агент стремится минимизировать функционал

I=

где y_i — отклонение некоторой жизненно важной переменной от нормы (потребность), a_i — вес (субъективная важность) этой потребности, t — время, а произведение M_i = a_iy_i естественно трактовать как побуждение (влечение).

Итак, когнитивные агенты, благодаря их сложности, наличию знаний и способностей к рассуждениям о своем поведении и внешней среде могут быть более автономными и работать относительно независимо, демонстрируя достаточно гибкое поведение. Но та же сложность автономных агентов, выливающаяся в способность противиться внешним воздействиям, вызывает определенные трудности при организации их эффективного взаимодействия. Поэтому в составе МАС, построенной из интеллектуальных агентов, как правило, присутствует не более 7+2 автономных единиц (магическое число Миллера).

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

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

Наконец, еще один тип классификации, где дополнительно к биологическому и психологическому уровням агентообразования вводится социальный и используются аналогии с триадой «растение — животное — человек», описан П. Браспеннингом. По его мнению, реактивных, интенциональных и социальных агентов можно уподобить компонентам этой триады. Агенты, подобные растениям, характеризуются реактивностью, выполнением стереотипных программ и посылкой сообщений другим агентам и в среду. Агенты, подобные животным, интенциональны, способны выбирать цели, строить планы действий и обеспечивать их выполнение. Они координируют свои действия, обмениваясь информацией об индивидуальных предпочтениях или задачах. Наконец, гуманоидные агенты, обладая внутренними моделями других агентов (и способностью к рефлексии), характеризуются социальным (ролевым) поведением. Сложность внутренних моделей зависит от уровня знаний и опыта гуманоидного агента.

2. ЛИНЕЙНЫЕ МОДЕЛИ МНОГОАГЕНТНЫХ СИСТЕМ

2.1 ОСНОВНЫЕ ПОНЯТИЯ

Линейное программирование — это раздел методов оптимизации. К числу задач линейного программирования можно отнести задачи: рационального использования сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования.

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

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

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

Линейное программирование — один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова"programming" - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а"линейное планирование", что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т. д. в нашей литературе стали общепринятыми.

Линейное программирование возникло после Второй МировойВойны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».

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

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

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

Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском Союзе исследования в этой области начались ранее. Первые постановки задач линейного программирования были сформулированы известным советским математиком Л. В. Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

2.2 ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И СВОЙСТВА ЕЕ РЕШЕНИЙ

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

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

Формы записи задачи линейного программирования:

Общей задачей линейного программирования называют задачу при ограничениях

— произвольные

где

— заданные действительные числа; (2.1) — целевая функция; (2.1) — (2.6) -ограничения;

— план задачи.

Пусть ЗЛП представлена в следующей записи:

Чтобы задача (2.7) — (2.8) имела решение, системе её ограничений (2.8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r=n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r

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

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

2.3 ГРАФИЧЕСКИЙ СПОСОБ РЕШЕНИЯ ЗЛП

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

Пусть дана задача Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.12), (2.13) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.11) — (2.13) есть выпуклое множество.

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник .

Выберем произвольное значение целевой функции. Получим. Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение. Считая в равенстве (2.11) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные целевой функции по x1 и x2:

Частная производная (2.14) (так же как и (2.15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, c1 и c2 — скорости возрастания Z соответственно вдоль осей и. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

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

Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.

1. С учетом системы ограничений строим область допустимых решений .

2. Строим вектор наискорейшего возрастания целевой функции — вектор градиентного направления.

3. Проводим произвольную линию уровня .

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

5. Определяем оптимальный план и экстремальное значение целевой функции .

2.4 СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЕ ЗЛП

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного плана;

3) умение переходить к нехудшему опорному плану.

Пусть ЗЛП представлена системой ограничений в каноническом виде:

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

которая имеет предпочтительный вид .

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .

Пусть далее система ограничений имеет вид

.

Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть (при) с коэффициентами, равными -1. Поэтому, вообще говоря, базисный план не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные. В целевую функцию переменные, вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом — М для задачи на максимум, где М — большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.

Пусть исходная ЗЛП имеет вид причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

,

Задача (2.19) — (2.21) имеет предпочтительный план. Её начальный опорный план имеет вид Если некоторые из уравнений (2.17) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане

(2.22)

М-задачи (2.19) — (2.21) все искусственные переменные, то план

является оптимальным планом исходной задачи (2.16) — (2.18).

Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М — задачу, которая имеет начальный опорный план

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

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

Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Признаки оптимальности.

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

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

3. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL

линейный программирование симплексный графический

Пример 1: Требуется составить такой рацион кормления животных тремя видами корма, при котором они получат необходимое количество питательных веществ A и B и себестоимость кормов будет минимальна.

Цены кормов, требуемое количество питательных веществ и их содержание в каждом корме показаны в таблице.

Если обозначить X=(x1, x2, x3) — искомое количество кормов, то задача ЛП формулируется так: Найти решение X системы:

при котором целевая функция принимает минимальное значение.

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

Внешний вид условия в программе Excel.

Ячейки таблицы имеют следующий смысл:

диапазон A1: C2 — содержит матрицу A;

диапазон D1: D2 — содержит вектор ресурсов В;

диапазон A6: C6 — содержит вектор цен С;

диапазон A4: C4 — содержит вектор решений X, начальные значения которого заданы нулю и который будет оптимизирован программой;

диапазон E1: E2 — содержит выражения, вычисляющие произведение AX;

ячейка E6 — содержит выражение, вычисляющее f=CX.

Вызов программы поиска решения выполняется через меню «СервисПоиск решения…». В открывшемся окне «Поиск решения» необходимо установить следующие параметры:

" Установить целевую ячейку" — E6;

установить переключатель «Равной минимальному значению» ;

в поле «изменяя ячейки» указать диапазон A4: C4;

в области «Ограничения» нажать кнопку «Добавить» и в окне «Добавление ограничений» ввести ограничения: E1>=D1 и E2>=D2;

Окно для ввода исходных данных задачи ЛП в программе Excel

нажать кнопку «Параметры…» и в открывшемся окне установить флажки «Линейная модель», «Неотрицательные значения» и выбрать переключатель «Оценка» — «Линейная» .

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

Внешний вид условия и полученного решения в программе Excel

Таким образом, животных следует кормить:

первым кормом в количестве 0,38 кг,

третьим — 3,85 кг, второй корм — не использовать вообще.

При таком рационе затраты на кормление одного животного составят 11,88 руб.

Пример 2

X1 + 2X2? 14

X1 + 3X2? 15

2X1 + X2? 10

X1, X2? 0

3X1 + 7 X2 > min

Пример 3

9X1 + 14X2 + 15 X3 + 10X4 > max

X1 + X2 + X3 + 2X4? 3

X1 + 2X2 + 3X3 + X4? 7

X1, X2, X3, X4? 0

Графический метод.

Пример 1

Найдем наибольшее значение линейной функции графическим методом.

L=x1-x2

при следующих ограничениях:

Решение В первую очередь, найдем область допустимых значений, т. е. точки x₁ и x₂, которые удовлетворяют системе ограничений. По условию задачи x₁ 0, x₂ 0, т. е. мы рассматриваем только те точки, которые принадлежат первой четверти.

Шаг 1.

Рассмотрим неравенство 1 системы ограничений.

x₁ + x₂ 3 _.

· Построим прямую. Заменим знак неравенства на знак равенства .

x₁ + x₂ = 3

Преобразуем уравнение следующим образом .

Каждый член уравнения разделим на 3 .

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

На оси X₁ рисуем точку с координатой 3. На оси X₂ рисуем точку с координатой 3. Соединяем полученные точки и получаем необходимую прямую. Какие точки нас интересуют?

x1+x2?3

x2?-x1+3

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

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

A (3,0)

В (0,3)

Шаг 2.

Рассмотрим неравенство 2 системы ограничений.

x₁ + x₂ 7

· Построим прямую. Заменим знак неравенства на знак равенства .

x₁ + x₂ = 7

Преобразуем уравнение следующим образом .

Каждый член уравнения разделим на 7 .

Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси X₁ рисуем точку с координатой 7. На оси X₂ рисуем точку с координатой 7. Соединяем полученные точки и получаем необходимую прямую.

· Какие точки нас интересуют?

x1+x2?7

x2?-x1+7

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

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

A (3,0)

C (7,0)

B (0,3)

D (0,7)

Шаг 2

Рассмотрим неравенство 2 системы ограничений.

x1+x2?7

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

x1+x2=7

Преобразуем уравнение следующим образом:

Каждый член уравнения разделим на 7

Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси X₁ рисуем точку с координатой 7. На оси X₂ рисуем точку с координатой 7. Соединяем полученные точки и получаем необходимую прямую.

· Какие точки нас интересуют?

x1+x2?7

x2? -x1+7

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

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

A (3, 0)

C (7, 0)

B (0, 3)

D (0, 7)

Шаг 3

Рассмотрим неравенство 3 системы ограничений.

x₂ 2

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

x₂ = 2

Прямая проходит параллельно оси X₁.

· Какие точки нас интересуют?

x₂ 2

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

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

B (0, 3)

D (0, 7)

E (1, 2)

E (1, 2)

Шаг 4

Рассмотрим неравенство 4 системы ограничений.

x₂ 5

· Построим прямую. Заменим знак неравенства на знак равенства .

x₂ = 5

Прямая проходит параллельно оси X₁.

· Какие точки нас интересуют?

x₂ 5

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой

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

B (0, 3)

G (0, 5)

E (1, 2)

F (5, 2)

H (2, 5)

Шаг 5

Рассмотрим неравенство 5 системы ограничений.

x₁ 4

· Построим прямую. Заменим знак неравенства на знак равенства .

x₁ = 4

Прямая проходит параллельно оси X₂.

· Какие точки нас интересуют?

x₁ 4

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие левее построенной нами прямой.

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

B (0, 3)

G (0, 5)

E (1, 2)

H (2, 5)

M (4, 3)

N (4, 2)

Шаг 6

Вернемся к нашей исходной функции L .

L = x₁ — x₂

Допустим значение функции L равно 1 (абсолютно произвольно выбранное число), тогда

1= x₁ — x₂

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