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

С уровнем «свободы воли» и характером взаимодействия связаны, в частности, представления о благонамеренных(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]. Подобные агенты наделены собственными механизмами мотивации. Это означает, что в них так или иначе моделируются внутренние убеждения, желания, намерения и мотивы, порождающие цели, которые определяют их действия. В свою очередь, модульные или рефлекторные агенты не имеют внутренних источников мотивации и собственных целей, а их поведение характеризуется простейшими (одношаговыми) выводами или автоматизмами. Таким образом, они представляют собой граничный случай понятия когнитивного агента и могут использоваться как «вспомогательные агенты». Данные агенты близки к акторам: они способны отвечать на вопросы и выполнять задания, которые ставят перед ними другие агенты, но решение этих задач не приводит к появлению у них собственных целей. Типичными примерами таких вырожденных агентов являются системы поиска в базах данных и простейшие логические регуляторы.

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

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

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

=

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при ограничениях 

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

где

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

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

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

Чтобы задача (2.7) - (2.8) имела решение, системе её ограничений (2.8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r=n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов  содержит базис - максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более  Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n - r переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов. Этому базису соответствуют базисные переменные, а свободными будут переменные

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).

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

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

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

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

Пусть дана задача

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть (при) с коэффициентами, равными -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+ 2X2 ≥ 14+ 3X2 ≥ 15

X1 + X2 ≥ 10, X2 ≥ 0

X1 + 7 X2 → min

Пример 3

X1 + 14X2 + 15 X3 + 10X4 → max+ X2 + X3 + 2X4 ≤ 3+ 2X2 + 3X3 + X4 ≤ 7, X2, X3, X4 ≥ 0

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

Пример 1

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

=x1-x2

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

Решение

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

Шаг 1.

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

₁ + x₂ 3 _.

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

₁ + x₂ = 3

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

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

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

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

x1+x2≥3≥-x1+3

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

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

(3,0)

В(0,3)

Шаг 2.

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

₁ + x₂ 7

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

₁ + x₂ = 7

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

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

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

+x2≤7≤-x1+7

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

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

A(3,0)(7,0)(0,3)(0,7)

Шаг 2

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

+x2≤7

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

+x2=7

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

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

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

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

+x2≤7≤ -x1+7

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

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

D(0 , 7)

Шаг 3

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

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

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

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

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

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

Шаг 4

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

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

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

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

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

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

Шаг 5

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

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

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

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

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

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

Шаг 6

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

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

= x₁ - x₂

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

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

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

Причем очевидно, что значение функции будет возрастать при перемещении прямой в направлении вектора  _. Диапазон перемещения прямой НЕ от точки O до точки N, а именно, в направлении от точки O к точке N. Будем перемещать прямую, перпендикулярную вектору ,до тех пор, пока она полностью не пройдет область допустимых решений. В нашем случае, касание прямой, перед выходом из области допустимых решений, произойдет в точке N (4 , 2). В данной точке значение функции будет наибольшим.

Ответ : Наибольшее значение функция достигает при x₁ = 4, x₂ = 2.

Значение функции : L = 2.

ЗАКЛЮЧЕНИЕ

В работе были рассмотрены два метода решения задач линейного программирования с помощью EXCEL и графический метод. Решена задача с подробным описанием. На наш взгляд, при изучении темы «Линейное программирование» необходимо уделять больше внимания современным методам решения задач линейного программирования. Например, с помощью EXCEL . По-нашему, это не вызовет у студентов больших трудностей, т.к. с основными принципами решения задач линейного программирования они познакомятся при изучении геометрического и симплекс-метода, а с языками программирования (pascal, basic), с работой в среде EXCEL на предмете «Информатика». В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.

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

СПИСОК ЛИТЕРАТУРЫ

1.Ашманов С.А.Линейное программирование М.: 1961

.Банди, Б. Основы линейного программирования.- М.: Радио и связь, 1989 - 176с.

3.Васильев Ф.П., Иваницкий А.Ю. Линейное программирование.- М.: Факториал Пресс, 2003 - 352 с.

. Глибовец Н.Н., 2002 Глибовец Н.Н. Использование агентных технологий в системах дистанционного образования

5. Дмитренко П.В., Пасичник Ю.А., 1999 Дмитренко П.В., Пасичник Ю.А. // Дистанцийна освіта. - К.: НПУ.

6.Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. 

. Кононов В.А. - Исследование операций. Для продвинутых математиков

8.Лорен Абдулезер, Джон Уолкенбах. Как эффективно работать и избежать неприятностей в Microsoft Excel, НТ Пресс, 2007.

9.Лунгу К.Н. Линейное программирование: Руководство к решению задач.-М.: Физматлит, 2005 - 127 с.

10.Минько А.А.Принятие решений с помощью Excel. Просто как дважды два, ЭКСМО, 2007.

12 . Смирнов А.В., Шереметов Л.Б., 1998 Смирнов А.В., Шереметов Л.Б., Многоагентная технология проектирования сложных систем. // Автоиметьзация проектирования, №№ 3 - 1998.

. Смородинский С.С., Батин Н. В. Оптимизация решений на основе методов и моделей математического программирования. Мн.: БГУИР, 2003.

.Тарасов В.Б-“Науки об искусственном”

15.Юнов С. Я могу работать с Microsoft Excel, Бином. Лаборатория знаний , 2007.