Методы оптимальных решений

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Тульский государственный университет» Института права и управления Кафедра «Финансы и менеджмент» Н.Е. Гучек доцент, кандидат технических наук КОНСПЕКТ ЛЕКЦИЙ по дисциплине МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ СЕМЕСТР 1 Направление подготовки: 38.03.01- «Экономика» Профили подготовки: «Финансы и кредит», «Бухгалтерский учет, анализ и аудит», «Налоги и налогообложение», «Мировая экономика» Форма обучения: заочная Тула 2017 г. Конспект лекций подготовлен доцентом Н.Е. Гучек и обсужден на заседании кафедры «Финансы и менеджмент» института права и управления, протокол № 8 от 22 марта 2017 г. Зав. кафедрой __________________________А.Л. Сабинина 2 Содержание Лекция 1. Введение в теорию принятия решений ...................................................................4 1.1. Основные понятия теории принятия решений............................................................. 4 1.2. Математическая формализация ................................................................................... 7 1.3. Современный этап развития теории принятия решений .......................................... 11 Лекция 2. Математическое моделирование .......................................................................... 15 2.1. Этапы построения математической модели ............................................................ 15 2.2. Понятия устойчивости, оптимизации и адекватности модели............................... 18 2.3. Постановка и технология решения оптимизационных задач управления ................ 21 Лекция 3. Линейное программирование ................................................................................. 24 3.1. Линейное программирование как инструмент математического моделирования экономики ............................................................................................................................ 24 3.2. Примеры моделей линейного программирования ........................................................ 28 Лекция 4. Задачи линейное программирование ...................................................................... 31 4.1. Формы задач линейного программирования и их эквивалентные преобразования ... 31 4.2. Геометрическая интерпретация задачи линейного программирования ................... 35 Лекция 5. Симплексный метод решения задачи линейного программирования................... 38 5.1. Симплекс-метод ........................................................................................................... 38 5.2. Симплексные таблицы и алгоритм решения задач .................................................... 39 5.3. Применение симплексного метода в экономических задачах .................................... 41 Лекция 6. Метод искусственного базиса решения задачи линейного программирования .. 44 6.1. Метод искусственного базиса .................................................................................... 44 6.2. Применение метода искусственного базиса .............................................................. 45 Лекция 7. Двойственные задачи линейного программирования............................................................ 47 7.1. Двойственная задача для стандартной задачи ..................................................................... 51 7.2. Основные теоремы двойственности ................................................................................... 54 7.3. Метод одновременного решения пары двойственных задач.............................................. …..58 Библиографический список ...................................................................................................... 60 3 Лекция 1. Введение в теорию принятия решений План. 1.1. Основные понятия теории принятия решений. 1.2. Математическая формализация. 1.3. Современный этап развития теории принятия решений. 1.1. Основные понятия теории принятия решений Математические модели и методы – необходимый элемент экономической теории на микро- и макроуровне. Использование математики в экономике позволяет: во-первых, выделить и формально описать наиболее важные, существенные связи экономических переменных и объектов; во-вторых, из четко сформулированных исходных данных и соотношений методами дедукции можно получать выводы, адекватные изучаемому объекту в той же мере, что и сделанные предпосылки; в-третьих, методы математики и статистики позволяют индуктивным путем получать новые знания об объекте: оценивать форму и параметры зависимостей его переменных, в наибольшей степени соответствующие имеющимся наблюдениям; в-четвертых, использование языка математики позволяет точно и компактно излагать положения экономической теории, формулировать ее понятия и выводы. Математическое моделирование экономических явлений и процессов с целью обеспечения принятия решений – область научно-практической деятельности, получившая мощный стимул к развитию во время и сразу после Второй мировой войны. Это направление развивалось вместе с развитием кибернетики, исследования операций, системного анализа и информатики. При построении, изучении и применении экономико-математических моделей принятия решений используются различные экономико-математические методы. Их можно разделить на несколько групп: - методы оптимизации; 4 - вероятностно-статистические методы; - методы построения и анализа имитационных моделей; - методы анализа конфликтных ситуаций (теории игр). Во всех этих группах можно выделить статическую и динамическую постановки. При наличии фактора времени используют дифференциальные уравнения и разностные схемы. Методы оптимальных решений опираются на теорию оптимальных решений. Рассмотрим основные понятия теории принятия решений1. Кто принимает решения? В теории принятия решений есть специальный термин – лицо, принимающее решение, сокращенно ЛПР. Это тот, на ком лежит ответственность за принятое решение, тот, кто подписывает приказ или иной документ, в котором выражено решение. Обычно это генеральный директор или председатель правления, командир воинской части, мэр города и т.п. Но иногда действует коллективный ЛПР, например, совет директоров, Государственная Дума Российской Федерации. Проект решения готовят специалисты или, как говорят, «аппарат ЛПР». Однако ответственность лежит на ЛПР, а не на тех, кто участвовал в подготовке решения. В практической работе важно четко отделять этап дискуссии, когда рассматриваются различные варианты решения, от этапа принятия решения, после которого надо решение выполнять, а не обсуждать. Порядок подготовки решения (регламент). Регламенты, определяющие порядок работы, очень важны. От них зависит принятое решение. Цели. Каждое решение направлено на достижение одной или нескольких целей. Возможны случаи, когда несколько целей можно достичь одновременно. Но чаще бывает по-другому. Например, часто встречающаяся формулировка «максимум прибыли при минимуме затрат» внутренне противоречива. Минимум затрат равен 0, когда работа не проводится, то и прибыль тогда тоже равна 0. если же прибыль вели1 Орлов А.И. Теория принятия решений: учебник / А.И. Орлов. – М.: Издательство «Экзамен», 2006. – С. 15 -18. 5 ка, то и затраты велики, поскольку и то, и другое связано с объемом производства. Можно либо максимизировать прибыль при фиксированных затратах, либо минимизировать затраты при заданной прибыли, но невозможно добиться «максимума прибыли при минимуме затрат». Часто одной и той же цели можно добиться различными способами. Ресурсы. Каждое решение предполагает использование тех или иных ресурсов. В практической работе над проектом решения важно отвечать на вопросы: «Чего мы хотим достичь? Какие ресурсы мы готовы использовать для этого?» Риски и неопределенности. Многие решения принимаются в условиях риска, т.е. при возможной опасности потерь. Связано это с разнообразными неопределенностями, окружающими нас. Неопределенность – это недостаточность информации о тех или иных факторах. Кроме отрицательных неожиданностей, бывают положительные – удачи. При принятии решений следует застраховаться от потерь и не пропустить удачу. Формулировка «Максимум прибыли и минимум риска» - внутренне противоречива. Обычно при возрастании прибыли возрастает и риск – возможность многое или все потерять. Неопределенность значений показателей, на основе которых принимаются решения, описывается интервальными значениями этих показателей, например (60  3) % или 1000  200 руб. Поэтому необходимо изучить устойчивость выводов по отношению к допустимым отклонениям исходных данных, а также по отношению к малым изменениям предпосылок используемой математической модели. Любое измерение проводится с некоторой погрешностью, и эту погрешность необходимо указывать. Критерии оценки решения. Критерии оценки решения могут самыми разнообразными. Можно исходить из наихудшего случая или наилучшего случая (пессимистический подход и оптимистический подход), средней выгоды (интегрального критерия, объединяющего оптимистический и пессимистический подходы), упущенной выгоды. 6 Критерии могут противоречить друг другу. Поэтому ЛПР приходится решать, какой из критериев для него важнее. В этом ему может помочь теория полезности, хорошо разработанная в экономике (в частности, так называемая маржинальная полезность в теории поведения потребителей и др.) и имеющая развитый математический аппарат. 1.2. Математическая формализация Для исследования характеристик процесса функционирования любой системы математическими методами, включая и компьютерное моделирование, должна быть проведена формализация этого процесса, то есть построена математическая модель. Под математическим моделированием будем понимать процесс установления соответствия данному реальному объекту некоторого математического объекта, называемого математической моделью, и исследование этой модели, позволяющее устанавливать ее свойства, характеризующие, в конечном счете, свойства моделируемого объекта. Вид математической модели зависит от природы реального объекта, задач исследования, требуемой достоверности и точности решения этих задач, наконец, от вкуса и квалификации исследователя. Модель – это условный образ исследуемого объекта, который приближенно воссоздает этот объект с помощь некоторого языка. В экономикоматематических моделях таким объектом является экономический процесс (например, планирование производства, использование мощностей и др.), а языком – математические методы. Экономико-математическая модель – это математическое описание исследуемого экономического процесса или объекта. Примерами экономико-математических моделей являются модели потребительского выбора, модели фирмы, модели экономического роста, модели равновесия на товарных, факторных и финансовых рынках и другие. При построении моделей экономисты выявляют существенные факторы, которые определяют исследуемое явление, и отбрасывают детали, несущественные для 7 решения поставленной проблемы. Формализация основных особенностей функционирования экономических объектов позволяет оценить возможные последствия воздействия на них и использовать такие оценки в управлении. Применение математического моделирования при принятии решений предполагает последовательное осуществление трех этапов исследования. Первый – от исходной практической проблемы до теоретической чисто математической задачи. Второй – математическое изучение и решение этой задачи. Третий – переход от математических выводов обратно к практической проблеме. В области моделирования задач принятия решений, как и в иных областях применения математики, выделяют четверку проблем: задача – модель – метод – условия применимости. Задача, как правило, порождена потребностями той или иной прикладной области. При этом происходит одна из возможных математических формализаций реальной ситуации. Например, при изучении предпочтений потребителей у маркетологов возникает вопрос: различаются ли мнения двух групп потребителей? При математической формализации мнения потребителей в каждой группе обычно моделируются как независимые случайные выборки, т.е. как совокупности независимых одинаково распределенных случайных величин. Вопрос маркетологов в рамках этой модели переформулируется в вопрос о проверке той или иной статистической гипотезы однородности, например, о проверке равенства математических ожиданий или о совпадении функций распределения двух совокупностей. Задача может возникнуть при обобщении потребностей ряда прикладных областей. Необходимости проверки упомянутой гипотезы однородности возникает и в медицине при сравнении двух групп пациентов, в технике при сопоставлении результатов обработки деталей двумя способами и в других областях. 8 Следовательно, одна и та же математическая модель может применяться для решения разных по прикладной сущности задач. Другими словами, следует различать математическую структуру модели и ее экономическое содержание. Рассмотрим два простых примера2. Пример 1. Пусть требуется определить, какую сумму следует положить в банк при заданной ставке процента (20 % годовых), чтобы через год получить 12000долл.? Введем формальные обозначения для величин рассматриваемой задачи: М0 – начальная сумма денег; М1 – конечная сумма денег; r – ставка процента. Запишем соотношение между ними (математическую модель): М1 = М0 (1+r/100). Найдем требуемую величину из решения основного уравнения модели: M0  M1 12000   10000äîëë . 1  r / 100 1,2 Пример 2. Пусть требуется определить, каков был объем выпуска продукции предприятия, если в результате технического перевооружения средняя производительность труда увеличилась на 20 %, и предприятие стало выпускать 12000 единиц продукции. Введем формальные обозначения для величин рассматриваемой задачи: Q0 – начальный выпуск; Q1 – конечный выпуск; r – процент прироста производительности. Запишем соотношение между ними (математическую модель): Q1 = Q0 (1+r/100). Найдем требуемую величину из решения основного уравнения модели: Q0  Q1 12000   10000åä. 1  r / 100 1,2 2 Замков. О.О. Математические методы в экономике: учебник / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. – М. : МГУ им. М.В. Ломоносова, Издательство «ДИС», 1997. – С. 13 – 14. 9 Сравнивая полученные модели и результаты, можно заметить, что математическая форма модели имеет вид: Х1 = Х0 (1+r/100), который является одинаковым для обоих примеров, как и числовые значения входящих в нее величин и результатов. Однако экономическая ситуация, описываемая моделью и экономическое содержание модели и результатов расчета совершенно различны. Таким образом, одни и те же математические модели и методы могут быть использованы для решения совершенно разных экономических задач. Метод, используемый в рамках определенной математической модели – это дело математиков. Для решения задачи в рамках одной и той же принятой исследователем модели может быть предложено много методов. Например, центральная предельная теорема теории вероятностей была получена такими разными методами, как: теорема Муавра – Лапласа, метод моментов Чебышева, метод характеристических функций Ляпунова, метод Линдеберга и метод Феллера. Для проверки гипотезы однородности могут использоваться методы Смирнова, Лемана – Розенблата, Вилкоксона и др. Условия применимости – полностью математический элемент четверки. С точки зрения математика замена условия дифференцируемости некоторой функции на условие ее непрерывности представляет существенное научное достижение, в то время как для прикладного исследователя, как и во времена Ньютона и Лейбница, непрерывные функции мало отличаются от дифференцируемых. Точнее, они одинаково могут быть использованы для описания реальной действительности. Экономические модели позволяют выявить особенности функционирования экономического объекта и на основе этого предсказывать будущее поведение объекта при изменении каких-либо параметров. Предсказания будущих изменений, например, повышение обменного курса, ухудшения экономической конъюнктуры, падение прибыли может опираться только на интуицию. Но при этом могут быть упущены, неправильно определены или неверно оценены важ10 ные взаимосвязи экономических показателей, влияющих на рассматриваемую ситуацию. В модели все взаимосвязи переменных могут быть оценены количественно, что позволяет получить более качественный и надежный прогноз. По своему определению любая экономическая модель абстрактна и, следовательно, неполна, поскольку она включает наиболее существенные факторы, определяющие закономерности функционирования рассматриваемого экономического объекта, она абстрагируется от других факторов, которые, несмотря на свою относительную малость, все же в совокупности могут определять не только отклонения в поведении объекта, но и само его поведение. Так, в простейшей модели спроса считается, что величина спроса на товар определяется его ценой и доходом потребителя. На самом же деле на величину спроса оказывает также влияние ряд других факторов: вкусы и ожидания потребителей, цены на другие товары, воздействие рекламы, моды и т.п. Обычно предполагают, что все факторы, не учтенные явно в экономической модели, оказывают на объект относительно малое результирующее воздействие в интересующем исследователя аспекте. Состав учтенных в модели факторов и ее структура могут быть уточнены в ходе совершенствования модели. 1.3. Современный этап развития теории принятия решений Теория принятия решений – быстроразвивающаяся наука. Задачи, которыми она занимается, порождены практикой управленческих решений на различных уровнях управления – от подразделения или предприятия до государств и международных организаций. На современном этапе развития теории принятия решений активно исследуются три проблемы: 1) системный подход при принятии решений; 2) современные методы принятия решений; 3) проблема горизонта планирования. Системный подход при принятии решений. При обсуждении проблем принятия решений часто говорят о системном подходе, системе, системном 11 анализе. Другими словами, проблема должна рассматриваться в целом, а не какая-то ее одна черта, хотя и важная. Например, при массовом жилищном строительстве можно рассмотреть только одну черту – стоимость квадратного метра в доме. Тогда наиболее дешевые дома – пятиэтажки. Если же рассмотреть проблему системно, учесть стоимость транспортных и инженерных коммуникаций (подводящих электроэнергию, воду, тепло и др.), то оптимальное решение уже другое – девятиэтажные дома. Еще пример, менеджер банка, отвечающий за распространение пластиковых карт, может сосредоточиться на рекламе. Между тем ему лучше перейти от системы «банк – владельцы карт» к системе «банк – руководители организаций – владельцы карт». Договоренность с руководителем организации о приказе выплачивать заработную плату с помощью пластиковых карт, дает менеджеру гораздо больший прирост численности владельцев карт, чем постоянная дорогая реклама. Его ошибка – в неправильном выделении системы, с которой он должен работать. Будет не прав и менеджер банка, оценивающий работу подразделения в текущих рублях. Обязательно следует учитывать инфляцию. В противном случае реальная ставка платы за кредит отрицательна; или рублевый оборот растет, банк процветает, а после перехода к сопоставимым ценам путем деления на индекс инфляции оказывается, что дела банка не столь безоблачны. Существует много определений понятия системы. Общим для них является то, что о системе говорят как о множестве, между элементами которого имеются связи. Целостность системы и ее «отделенность» от окружающего мира обеспечиваются тем, что взаимосвязи внутри системы существенно сильнее, чем связь какого-либо ее элемента с любым элементом, лежащим вне системы. По определению действительного члена Российской академии наук Н.Н. Моисеева: «Системный анализ – это дисциплина, занимающаяся проблемами принятия решений в условиях, когда выбор альтернативы требует анализа сложной информации различной физической природы»3. 3 Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, 1981. 488 с. 12 Современные методы принятия решений. При принятии решений широко применяют весь арсенал методов современной прикладной математики. Они используются для оценки ситуации и прогнозирования при выборе целей, для генерирования множества возможных вариантов решений и выбора из них наилучшего. Наиболее разработанной и многочисленной является группа всевозможных методов оптимизации (математического программирования). В многокритериальных задачах используют методы свертки критериев и интерактивные компьютерные системы, позволяющие вырабатывать решение в процессе диалога человека и ЭВМ. Также используется имитационное моделирование, базирующееся на компьютерных системах, отвечающих на вопрос: «Что будет, если...?», метод статистических испытаний (Монте-Карло), модели надежности и массового обслуживания. Часто являются необходимыми статистические (эконометрические) методы, в частности методы выборочных обследований. При принятии решений применяют вероятностно-статистические модели и методы анализа данных. Весьма полезны и различные простые приемы принятия решений – экспертные оценки. Проблема горизонта планирования. Во многих ситуациях не определена продолжительность проекта или горизонт планирования инвестора не охватывает всю продолжительность реализации проекта до этапа утилизации. В таких случаях важно изучить влияние горизонта планирования на принимаемые решения. Например, если горизонт планирования владельца предприятия – 1 месяц, то наибольший денежный доход принесет продажа предприятия. Если планирование осуществляется владельцем на год, то сначала владелец будет нести затраты, закупив сырье, оплатив труд рабочих, и только затем, продав продукцию, владелец получит прибыль. Если планирование осуществляется на 10 лет, то владелец предприятия должен пойти на крупные затраты, закупив лицензии и новое оборудование с целью увеличения дохода в дальнейшие го- 13 ды. При планировании на 30 лет имеет смысл вложить средства в создание и развитие собственного научно-исследовательского центра. Таким образом, популярное утверждение «фирма работает ради максимизации прибыли» не имеет точного смысла. За какой период максимизировать прибыль – за месяц, год, 10 лет или 30 лет? Следовательно, принимаемые решения зависят от горизонта планирования. 14 4 Лекция 2. Математическое моделирование План. 2.1. Этапы построения математической модели. 2.2. Понятия устойчивости, оптимизации и адекватности модели. 2.3. Постановка и технология решения оптимизационных задач управления. 2.1. Этапы построения математической модели Общей методологией исследования (моделирования) сложных систем является системный подход и сложившийся на его базе системный анализ. Действительно, объект системного анализа – абстрактная система – фактически является моделью, предметом системного анализа является процесс моделирования. Методологической базой моделирования являются следующие системные принципы: - всеобщая полнота описания системы принципиально невозможна; - любое описание является упрощенным образом реальности, однако, даже самые сильные упрощения могут принести плодотворные результаты, если они отвечают цели исследования; - корректность и продуктивность описания системы определяется степенью достижения цели исследования – получением частичного конкретного знания; допустимы различные (в том числе и несопоставимые) субъективные модели одной и той же объективной системы; - личность исследователя включается в модель системы и, таким образом, в процессе исследования возникает новая система, включающая в себя наряду с изучаемой системой также ее исследователя с его научным аппаратом и субъективными качествами5. В соответствии с системным подходом можно построить «базовую» метамодель любой системы в виде открытого кортежа ее «базовых» признаков и свойств, упорядоченных в соответствии с эмпирически обоснованным нараста4 Материал лекции подготовлен на основе учебного пособия: Воронин А.А., Губко М.В., Мишин С.П , Новиков Д.А. Математические модели организаций: Учебное пособие. — М.: ЛЕНАНД, 2008. — 360 с. 5 Моисеев Н.Н. Прощание с простотой. – М.: АГРАФ, 1998. 15 нием системной (модельной) сложности: (1) «Базовая» модель системы: {Элементы:{…}, структура:{…}, функции:{…}, динамические свойства:{…}, взаимодействие с внешней средой:{…}, управление:{…}, целеполагание:{…}, самоуправление:{…}, поведение:{…}, гомеостазис:{…}, самоорганизация:{…}, развитие:{…}, эволюция:{…},……, цель исследования:{…}, исследова- тель:{…}}. К моделям предъявляют следующие требования 6: - ингерентность модели, то есть достаточная степень согласованности создаваемой модели со средой, чтобы создаваемая модель была согласована со средой, в которой ей предстоит функционировать, входила бы в эту среду не как чужеродный элемент, а как естественная составная часть7. - простота модели. Простота модели – ее неизбежное свойство: в модели невозможно зафиксировать все многообразие реальных ситуаций. - адекватность модели – означает возможность с ее помощью достичь поставленной цели моделирования в соответствии со сформулированными критериями. Адекватность модели означает, в частности, что она достаточно полна, точна и устойчива. Достаточно не вообще, а именно в той мере, которая позволяет достичь поставленной цели. Иногда удается (и это желательно) ввести некоторую меру адекватности модели, то есть определить способ сравнения разных моделей по степени успешности достижения цели с их помощью. Можно выделить следующие этапы построения математической модели (рис. 1.1). 1. Определение предмета и цели моделирования, включая границы исследуемой системы и те основные свойства, которые должны быть отражены. На этом этапе определяется предельный уровень сложности модели и во многом предопределяются результаты следующих этапов. 2. Выбор языка (аппарата) моделирования. Существует несколько сотен 6 7 Новиков А.М., Новиков Д.А. Методология. – М.: Синтег, 2007. Волкова В.Н., Денисов А.А. Основы теории систем и системного анализа. Изд. 2-е. – СПб.: СПб.ГТУ, 1999. 16 «аппаратов» моделирования, каждый из которых представляет собой разветвленный раздел прикладной математики. Наблюдаемое поведение Объект Р е а л и з а ц и я Класс моделей Множество частных моделей Идентификация и анализ адекватности Конкретная модель Ожидаемое поведение Решение задачи выбора Анализ устойчивости Оптимальное решение Рис. 1.1. Этапы построения и исследования математической модели 3. Выбор переменных, описывающих состояние системы и существенные параметры внешней среды, а также шкал их измерения и критериев оценки. 4. Выбор ограничений, то есть множеств возможных значений переменных и параметров, и (в динамических моделях) начальных условий. 5. Определение связей между переменными с учетом всей имеющейся информации о моделируемой системе, а также известных законов, закономерностей и т.п., описывающих данную систему. Именно этот этап иногда называют «построение модели» (в узком смысле). 6. Исследование модели – решение прямой и обратной задач моделирования. Именно этот этап иногда называют «моделированием» (в узком смысле). 7. Изучение устойчивости и адекватности модели. Последующие этапы связаны с практической реализацией модели и/или внедрением результатов моделирования. Приведенные этапы математического моделирования иногда приходится повторять, возвращаясь к более ранним этапам при уточнении цели моделирования, обеспечении точности, устойчивости, адекватности и т.д. 17 2.2. Понятия устойчивости, оптимизации и адекватности модели Важным свойством или требованием, предъявляемым к моделям, является требование их устойчивости. Можно различить несколько аспектов понятия «устойчивость». Устойчивость модели по отношению к изменениям ее параметров означает сохранение аппарата моделирования, основных связей между переменными, типов ограничений в некотором интервале ее параметров. Другим аспектом устойчивости является устойчивость решения задачи (результатов) моделирования (обнаруженных свойств, сценариев, траекторий, состояний) по отношению к изменениям параметров модели или начальных условий. Если зависимость от параметров и начальных условий является регулярной, то малые ошибки в исходных данных приведут к небольшим изменениям результата. Тогда, решая, например, задачу выбора по приближенным данным, можно обоснованно говорить о нахождении приближенного решения. Иногда устойчивость является целью практического моделирования. В частности – поиск алгоритмов деятельности человека без разрушения природной экосистемы. Оптимизация заключается в том, чтобы среди множества объектов (возможных решений, сценариев, вариантов проектируемой системы) найти наилучшие в заданных условиях, при заданных ограничениях, то есть оптимальные альтернативы. В этой фразе значение имеет каждое слово. Слово «наилучшие» предполагает, что у исследователя имеется критерий (или ряд критериев), способ (способы) сравнения вариантов. При этом важно учесть имеющиеся условия, ограничения, так как их изменение может привести к тому, что при одном и том же критерии (критериях) наилучшими окажутся другие варианты. Понятие оптимальности получило строгое и точное представление в различных математических теориях, прочно вошло в практику проектирования и эксплуатации технических систем, сыграло важную роль в формировании современных системных представлений, широко используется в административной и общественной практике, стало понятием, известным практически каждо18 му человеку, поскольку стремление к повышению эффективности труда, любой целенаправленной деятельности нашло свое выражение, свою понятную форму в идее оптимизации. Устойчивость результатов моделирования по отношению к изменениям реальности достигается сочетанием свойств устойчивости и адекватности модели. Адекватность тесно связана со свойством ингерентности и означает соответствие основных предположений, научного аппарата, методов, и, как следствие, результатов моделирования с одной стороны, моделируемой реальности, с другой – близким к ней моделям, теориям, парадигмам. Это, в частности, подразумевает корректное использование научного аппарата, методов компьютерного моделирования. Для понимания проблемы адекватности следует рассмотреть возможные ошибки моделирования в процессе построения математической модели некоторой реальной системы. Первым шагом является выбор «языка», на котором формулируется модель, то есть того математического аппарата, который будет использоваться (горизонтальная пунктирная линия на рис. 1.1 является условной границей между реальностью и моделями). Следующим этапом по уровню детализации является построение множества частных моделей, при переходе к которым вводятся те или иные предположения относительно параметров модели. Возникающие здесь ошибки могут быть вызваны неправильными представлениями о свойствах элементов моделируемой системы и их взаимодействии. После задания структуры модели посредством выбора определенных значений параметров (в том числе – числовых) происходит переход к некоторой конкретной модели, которая считается аналогом моделируемого объекта. На этом этапе появляются ошибки измерения. Кроме того, оптимальное решение, полученное в рамках конкретной модели, является оптимальным в том смысле, что при его использовании поведение модели соответствует предъявляемым требованиям. 19 Наблюдаемое поведение модели является с точки зрения субъекта, осуществляющего моделирование (например, полагающего, что модель адекватна), предполагаемым поведением реальной системы, которое в отсутствии ошибок моделирования будет оптимально в смысле выбранного критерия эффективности. Однако в общем случае наблюдаемое поведение реальной системы и ее ожидаемое поведение могут различаться достаточно сильно. Следовательно, необходимо исследование адекватности модели, то есть – устойчивости поведения реальной системы относительно ошибок моделирования (рис. 1.1). Например, пусть построена модель и найдено оптимальное в ее рамках решение. А что будет, если параметры модели «немного» отличаются от параметров реальной системы? Получается, что задача выбора решалась «не для той» системы. Отрицать такую возможность нельзя. Поэтому необходимо получить ответы на следующие вопросы: - насколько оптимальное решение чувствительно к ошибкам описания модели, то есть, будут ли малые возмущения модели приводить к столь же малым изменениям оптимального решения (задача анализа устойчивости); - будут ли решения, обладающие определенными свойствами в рамках модели (например, оптимальность, эффективность не ниже заданной и т.д.), обладать этими же свойствами и в реальной системе, и насколько широк класс реальных систем, в которых данное решение еще обладает этими свойствами (задача анализа адекватности). Приведенные качественные рассуждения свидетельствуют, что существует определенный дуализм между эффективностью решения и областью его применимости (областью его устойчивости и/или областью адекватности). Отобранные и проверенные на устойчивость и адекватность модели становятся основой для последнего, решающего этапа стадии прагматического моделирования – выбора модели для дальнейшей реализации. 20 2.3. Постановка и технология решения оптимизационных задач управления Пусть имеется управляющий орган (субъект управления) и управляемая система (объект управления). Состояние управляемой системы зависит от внешних воздействий, воздействий со стороны управляющего органа (управления) и, быть может (если объект управления активен, то есть также является субъектом), действий самой управляемой системы (рис. 1.2). Задача управляющего органа заключается в том, чтобы осуществить такие управляющие воздействия (жирная линия на рис. 1.2), чтобы с учетом информации о внешних воздействиях (пунктирная линия на рис. 1.2) обеспечить требуемое с его точки зрения состояние управляемой системы. Управляющий орган (субъект управления) Состояние управляемой системы Управление Управляемая система (объект управления) Внешние воздействия Рис. 1.2. Структура системы управления Иерархичность целей организационных систем приводит к иерархичности задач управления: если главная цель может достигаться различными управляющими воздействиями, то среди них можно выбрать наилучшие в каком-то смысле (достигающие второй по значимости цели) и т.д. Предпочтения управляющего органа описываются критерием эффективности функционирования управляемой системы и зависят от состояния управляемой системы и, быть может, от самих управляющих воздействий. Если известна зависимость состояния управляемой системы от управления, то получаем зависимость эффективности функционирования управляемой системы от управляющих воздействий. Этот критерий называется критерием эффективности управления. Следовательно, задача управления формально может быть сформулирована следующим образом: найти допустимые управляющие воздей21 ствия, имеющие максимальную эффективность (такое управление называется оптимальным управлением). Для этого нужно решить задачу оптимизации – осуществить выбор оптимального управления (оптимальных управляющих воздействий). В общем случае технология постановки и решения задачи управления включает следующие этапы (рис. 1.3, на котором в целях наглядности опущены обратные связи между этапами). Реальная система Описание системы и построение модели Анализ модели Задача синтеза управления (оптимизация) Теоретическое исследование Исследование устойчивости решений Идентификация Имитационные эксперименты Обучение персонала, внедрение, анализ эффективности практического использования и т.д. Настройка модели Внедрение Рис. 1.3. Технология постановки и решения задач управления Первый этап – построение модели – заключается в описании моделируемой системы в формальных терминах. Второй этап – анализ модели (исследование поведения управляемой системы при различных управляющих воздействиях). Третий этап – решение, во-первых, прямой задачи управления, то есть задачи синтеза оптимальных управляющих воздействий, заключающейся в поиске допустимых управлений, имеющих максимальную эффективность, и, вовторых, обратной задачи управления – поиска множества допустимых управляющих воздействий, переводящих управляемую систему в заданное состоя22 ние. Этот этап решения задачи управления вызывает наибольшие теоретические трудности и наиболее трудоемок с точки зрения исследователя. Четвертый этап – исследование устойчивости решений. Исследование устойчивости подразумевает решение, как минимум, двух задач. Первая задача заключается в изучении зависимости оптимальных решений от параметров модели, то есть является задачей анализа устойчивости решений. Вторая задача специфична для математического моделирования. Она заключается в теоретическом исследовании адекватности модели реальной системе, которое, в частности, подразумевает изучение эффективности решений, оптимальных в модели, которые при их использовании в реальных системах могут в силу ошибок моделирования отличаться от модели. Перечисленные четыре этапа заключаются в теоретическом изучении модели. Для того чтобы использовать результаты теоретического исследования при управлении реальной системой, необходимо произвести настройку модели, то есть идентифицировать моделируемую систему и провести серию имитационных экспериментов – соответственно пятый и шестой этапы. Этап имитационного моделирования во многих случаях необходим по нескольким причинам. Во-первых, имитационное моделирование может служить инструментом получения и оценки решений. Во-вторых, имитационное моделирование позволяет проверить справедливость гипотез, принятых при построении и анализе модели, то есть дает дополнительную информацию об адекватности модели без проведения натурного эксперимента. И, наконец, в-третьих, использование деловых игр и имитационных моделей в учебных целях позволяет участникам системы освоить и апробировать предлагаемые механизмы управления. Завершающим является седьмой этап – этап внедрения, на котором производится обучение, внедрение результатов в реальной системе с последующей оценкой эффективности их практического использования и коррекцией модели. На сегодняшний день накоплен значительный опыт разработки и использования самых разных методов моделирования, но все равно в этом процессе решающую роль играет творчество, интуитивное искусство создания модели. 23 Лекция 3. Линейное программирование План. 3.1.Линейное программирование как инструмент математического моделирования экономики. 3.2. Примеры моделей линейного программирования. 3.1. Линейное программирование как инструмент математического моделирования экономики Линейное программирование сформировалось как отдельный раздел прикладной математики в 40 – 50-х гг. ХХ в. благодаря работам советского ученого, лауреата Нобелевской премии Л.В. Канторовича. В 1939 году им была опубликована работа «Математические методы организации и планирования производства», в которой он с использованием математики решил экономические задачи о наилучшей загрузке машин, раскрое материалов с наименьшими расходами, распределении грузов по нескольким видам транспорта и другие, предложив метод разрешающих множителей8. Л.В. Канторович впервые сформулировал такие широко используемые экономико-математические понятия, как оптимальный план, оптимальное распределение ресурсов, объективно обусловленные оценки, указав многочисленные области экономики, где они могут быть применены. Понятие линейного программирования было введено американским математиком Д. Данцигом, который в 1949 г. предложил алгоритм решения задачи линейного программирования, получивший название «симплексный метод». Математическое программирование, в которое входит линейное программирование, в настоящее время является одним из направлений исследования операций. В зависимости от вида решаемых задач в нем выделяют такие области, как линейное, нелинейное, дискретное, динамическое программирование и др. Термин «программирование» введен в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определя8 Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: учеб. пособие. 2-е изд., доп. – СПб.: Питер, 2010. – С. 16–17. 24 ют программу или план работы некоторого экономического объекта. В классическом математическом анализе исследуются общая постановка задачи определения условного экстремума. Однако в связи с развитием промышленного производства, транспорта, агропромышленного комплекса, банковского сектора традиционных результатов математического анализа оказалось недостаточно. Потребности практики и развитие вычислительной техники привели к необходимости определения оптимальных решений при анализе сложных экономических систем. Главным инструментом для решения таких задач является математическое моделирование. При этом сначала строится простая модель, затем проводится ее исследование, позволяющее понять, какие из интегрирующих свойств объекта не улавливаются формальной схемой, после чего за счет усложнения модели обеспечивается большая ее адекватность реальности. Во многих случаях первым приближением к действительности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, являются линейными. Практика показывает, что достаточное количество экономических процессов достаточно полно описывается линейными моделями. Следовательно, линейное программирование как аппарат, позволяющий отыскивать условный экстремум на множестве, заданном линейными уравнениями и неравенствами, играет важную роль при анализе этих процессов. Линейное программирование получило широкое развитие в связи с тем, что было установлено: ряд задач сферы планирования и управления может быть сформулирован в виде задач линейного программирования, для решения которых имеются эффективные методы. По оценкам специалистов примерно 80– 85 % всех решаемых на практике задач оптимизации относится к задачам линейного программирования. Созданный математический аппарат в сочетании с компьютерными программами, производящими трудоемкие расчеты, позволяет широко использовать модели линейного программирования в экономической науке и практике. 25 Определение 19. Линейное программирование (ЛП) – это область математического программирования, являющегося разделом математики и изучающего методы поиска экстремальных (наибольших и наименьших) значений линейной функции конечного числа переменных, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой, а ограничения, которые представляют количественные соотношения между переменными, выражающие условия и требования экономической задачи и математически записываются в виде уравнений или неравенств, называются системой ограничений. К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения. Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции, называемой целевой10: f ( X )  c1 x1  c 2 x 2    c j x j    c n x n  max (min) (3.1) от n переменных x1, x2, …, хn при наложенных функциональных ограничениях: a11 x1  a12 x 2    a1 j x j    a1n x n  (, ) b1 , a x  a x    a x    a x  (, )b , 22 2 21 j j 2n n 2  21 1   ai x1  a i 2 x 2    aij x j    a in x n  (, )bi ,   a m1 x1  a m 2 x 2    a mj x j    a mn x n  (, )bm (3.2) и прямых ограничениях (требовании неотрицательности переменных) x j  0; j  1, n , (3.3) где aij, bi, cj – заданные постоянные величины. В системе ограничений (3.2) знаки «меньше или равно», «равно», «больше или равно» могут встречаться одновременно. 9 Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: учеб. пособие. 2-е изд., доп. – СПб.: Питер, 2010. – С. 17 – 18. 10 Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование: Учеб. пособие. – М.: Вузовские учебник, 2009. – С. 54 – 55. 26 ЗЛП в более краткой записи имеет вид: n f ( X )   c j x j  max (min) , j 1 при ограничениях: n a ij x j  (, ) bi , i  1, m ; j 1 x j  0; j  1, n . Вектор Х = (x1, x2, …, хn) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением) ЗЛП. Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f(X), называется оптимальным планом задачи и обозначается f(X*), где Х*=(x1*, x2*, …, хn*). Еще одна форма записи ЗЛП:   f ( X * )  max min [ f (C , x )] x X x X  Ax  (,  ) B, X  x , x0   где f(X*) есть максимальное (минимальное) значение f(С, х), взятое по всем решениям, входящим в множество возможных решений Х. Определение 211. Математическое выражение целевой функции и ее ограничений называются математической моделью экономической задачи. Для составления математической модели необходимо: 1) обозначить переменные; 2) составить целевую функцию исходя из цели задачи; 3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности. 11 Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: учеб. пособие. 2е изд., доп. – СПб.: Питер, 2010. – С. 18. 27 3.2. Примеры моделей линейного программирования 3.2.1. Задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии (задача об ассортименте)12. Предположим, что предприятие выпускает n различных изделий. Для их производства требуются m различных видов ресурсов (сырья, вспомогательных материалов, рабочего и машинного времени). Эти ресурсы ограничены и составляют в планируемый период b1, b2, , bm условных единиц. Известны также технологические коэффициенты aij, которые указывают, сколько единиц i-го ресурса требуется для производства изделия j-го вида ( i  1, m ; j  1, n ). Пусть прибыль, получаемая предприятием при реализации единицы изделия j-го вида, равна cj. В планируемый период все показатели aij, bi, cj предполагаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей. Другими словами требуется составить оптимальный план работы предприятия Х = (x1, x2, …, хn), т.е. найти такие значения переменных x1, x2, …, хn (объем выпуска продукции каждого вида), чтобы обеспечить предприятию получение максимальной прибыли от реализации всей продукции и чтобы на ее производство хватило имеющихся в распоряжении ресурсов. Экономико-математическая модель задачи n f ( X )   c j x j  max , j 1 n a ij x j  bi , i  1, m ; j 1 x j  0; j  1, n . Целевая функция представляет собой суммарную прибыль от реализации объема выпускаемой продукции всех видов. В данной модели оптимизация плана возможна за счет выбора наиболее выгодных видов продукции. Ограничения означают, что для любого из ресурсов его суммарный рас12 Там же. С. 57 – 58. 28 ход на производство всех видов продукции не превосходит его запасы. При составлении плана производства приходится учитывать не только ограниченность ресурсов, но и директивные задания по выпуску продукции Тj (госзаказы или уже заключенные договоры по отдельным видам продукции). В таком случае модель дополнится ограничением вида x j  T j . В этом случае свобода выбора значительно снижается. 3.2.2. Задача о смесях (рационе, диете)13 К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Получаемые смеси должны иметь в своем составе n различных компонентов в определенных количествах, а сами компоненты являются составными частями m исходных материалов. Введем следующие обозначения: xj – количество материала j-го вида, входящего в смесь; cj – цена материала j-го вида; bi – минимально необходимое содержание i-го компонента в смеси. Коэффициенты aij показывают удельный вес j-го компонента в единице j-го материала. Экономико-математическая модель задачи n f ( X )   c j x j  min , j 1 n a ij x j  bi , i  1, m ; j 1 x j  0; j  1, n . Целевая функция представляет собой суммарную стоимость смеси. Функциональные ограничения являются ограничениями по содержанию компонентов в смеси: смесь должна содержать компоненты в объемах, не менее указанных. 3.2.3. Транспортная задача14 Пусть некоторый однородный продукт, сосредоточенный у m поставщи- 13 14 Там же. С. 59. Там же. С. 59 – 60. 29 ков Аi в количестве ai единиц ( i  1, m ), необходимо доставить n потребителям Вj в количестве bj единиц ( j  1, n ). Известна стоимость сij перевозки единицы груза от поставщика Аi к потребителю Вj. Требуется составить план перевозок, позволяющий с минимальными затратами вывезти все грузы и полностью удовлетворить всех потребителей. Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от поставщика Аi к потребителю Вj запланировано перевести xij единиц груза, то стоимость перевозки составит сij xij. Экономико-математическая модель задачи m Z  i 1 n c ij xij  min , j 1 n x ij  ai , i  1, m , ij  b j , j  1, n , j 1 m x i 1 x j  0; i  1, m; j  1, n . Целевая функция представляет собой стоимость всего плана перевозок. Первое функциональное ограничение отражает требование, что все грузы должны быть перевезены, второе – все потребности должны быть удовлетворены. Транспортная задача имеет n + m уравнений с неизвестными. Матрица перевозок X = (xij)mn , удовлетворяющая всем ограничениям, называется планом перевозок транспортной задачи, а xij – перевозками. План Х*, при котором целевая функция обращается в минимум, называется оптимальным планом перевозок. 30 Лекция 4. Задачи линейного программирования (ЗЛП) План. 4.1. Формы задач линейного программирования. 4.2. Геометрический смысл задачи линейного программирования. 4.1. Формы задач линейного программирования и их эквивалентные преобразования15 На основе примеров задач линейного программирования можно представить три формы задач линейного программирования в зависимости от наличия ограничений разного типа. 1. Стандартная задача линейного программирования n f ( X )   c j x j  max , n или f ( X )   c j x j  min j 1 j 1 n n  aij x j  bi , i  1, m ; a x j  0; j  1, n . x j  0; j  1, n . j 1 ij x j  bi , i  1, m j 1 Стандартная задача линейного программирования – это задача, в которой система функциональных и прямых ограничений состоит из одних неравенств, переменные x j  0, ãäå j  1, n являются неотрицательными, а целевая функция может стремиться как к максимуму, так и к минимуму. Причем, в стандартной ЗЛП на максимум все функциональные ограничения имеют форму «меньше или равно». В стандартной ЗЛП на минимум все ограничения имеют форму «больше или равно». Стандартная задача линейного программирования имеет важное значение ввиду того, что большое число прикладных моделей сводится к этому классу задач линейного программирования. 2. Каноническая задача линейного программирования 15 Косоруков О.А., Мищенко А.В. Исследование операций: учебник / О.А. Косоруков, А.В. Мищенко; под общ. ред. д. э. н., проф. Н.П. Тихомирова. – М.: Изд-во «Экзамен», 2003. – С. 19–20. 31 n f ( X )   c j x j  max j 1 n a ij x j  bi , i  1, m ; j 1 x j  0; j  1, n . Каноническая задача линейного программирования – это задача, в которой все переменные xi неотрицательны, система функциональных ограничений представляет собой систему уравнений, а целевая функция стремиться к максимуму. Основные вычислительные методы (симплекс-метод и его модификации) решения задач линейного программирования разработаны именно для канонической задачи. 3. Общая задача линейного программирования. Необходимо максимизировать (или минимизировать) линейную функцию от n переменных x1, , xn вида n f ( X )   c j x j  max (min) j 1 при ограничениях n a ij x j  () bi , i  1, k , ij x j  bi , i  k  1, m , j 1 n a j 1 x j  0; j  1, l; l  n . Стандартная задача получается как частный случай общей при k = m, l = n; каноническая задача получается как частный случай общей при k = 0, l = n. Все три задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных, в том числе задачу на минимум свести к задаче на максимум и наоборот. Поэтому если имеется способ решения одной из этих трех задач, то тем самым может быть решена и любая другая из двух оставшихся. 32 Эквивалентными называются такие преобразования задач линейного программирования, которые не изменяют оптимального решения задачи. Эквивалентными преобразованиями являются: - переход от задачи на минимум к задаче на максимум и обратно; - переход от ограничения в виде неравенства «больше или равно» к ограничению в виде неравенства «меньше или равно»; - переход от ограничения в виде неравенства к ограничению в виде равенства; - переход от переменных любого знака к неотрицательным переменным. Переход от задачи на минимум функции g(X) к задаче на максимум заключается в рассмотрении задачи на максимум функции  g(X): g ( X * )  min [ g (C , x)]  max [ g (C , x )] . xX xX И наоборот переход от задачи на максимум функции f(X) к задаче на минимум заключается в рассмотрении задачи на минимум функции  f(X): f ( X * )  max [ f (C , x)]  min [ f (C , x)] . xX x X Если система ограничений какой-либо задачи включает неравенства разного вида, то необходимо привести исходную ЗЛП к стандартной форме записи, т.е. для ЗЛП на максимум привести все неравенства функциональных ограничений к виду «меньше или равно», а для ЗЛП на минимум – к виду «больше или равно». Для этого используются следующие эквивалентные преобразования: В задаче на максимум все члены слева и справа от неравенства умножают на (1), а знак неравенства меняют на противоположный: n исходные неравенства: a ij x j  bi , i  1, m ; j 1 n получаемые в результате преобразования неравенства:  a ij x j  bi , i  1, m . j 1 Аналогичным образом поступают и в задаче на минимум: n исходные неравенства: a ij x j  bi , i  1, m ; j 1 33 n получаемые в результате преобразования неравенства:  a ij x j  bi , i  1, m . j 1 Для решения ЗЛП в стандартной форме записи необходимо перейти к эквивалентной ЗЛП в канонической форме записи. Переход от неканонической модели (хотя бы одно ограничение является неравенством) к канонической осуществляется введением в каждое неравенство балансовой переменной xn+k. При знаке неравенства  балансовая переменная вводится в неравенство со знаком плюс, т.к. левая часть неравенства меньше правой. Если знак неравенства , то балансовая переменная вводится в неравенство со знаком минус, т.к. левая часть неравенства больше правой. При этом для всех балансовых переменных вводится условие неотрицательности. В целевую функцию балансовые переменные не вводятся. n Если сходные неравенства имеют вид a ij x j  bi , i  1, m , тогда в результа- j 1 n те преобразования получают равенства a ij x j  x n  k  bi , i  1, m, k  1, n и нера- j 1 венства x n k  0, k  1, n , отражающие условие неотрицательности балансовых переменных. n Если сходные неравенства имеют вид a ij x j  bi , i  1, m , тогда в результа- j 1 n те преобразования получают равенства a ij x j  x n  k  bi , i  1, m, k  1, n и нера- j 1 венства x n k  0, k  1, n , отражающие условие неотрицательности балансовых переменных. Если на переменную xj общей задачи не накладывается ограничение неотрицательности, то для того, чтобы общую задачу свести к стандартной, необходимо ввести новые переменные u j  0 и v j  0 и положить x j  u j  v j . Таким образом неотрицательное значение – 5 можно заменить двумя положительными значениями 10 и 15: – 5 = 10 – 15. 34 Задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии, задача на максимум выпуска продукции в заданном ассортименте, задача о смесях являются стандартными задачами линейного программирования, транспортная задача – каноническая задача линейного программирования. 4.2. Геометрическая интерпретация задачи линейного программирования Рассмотрим следующую задачу линейного программирования16: f ( X )  30 x1  40 x 2  max  x1  x 2  1500  x  600  1 5 x1  2 x 2  10000  2 x1  5 x 2  10000   x 2  1750  x1  2250   x1  2 x 2  4000 x , x  0  1 2 (1) (2) (3) (4) (5) (6) (7 ) (8, 9) На рис. 4.1 представлено множество допустимых точек, удовлетворяющих всем ограничениям задачи и представляющее собой пересечение полуплоскостей, отражающих ограничения задачи линейного программирования. Рис. 4.1. Геометрическая интерпретация решения задачи 16 Михайлова Э.А., Смирнов А.О. Методы нахождения оптимального управления экономическими системами: пособие для практических занятий / РГАТА. Кафедра экономики. - Рыбинск, 1998. - 42 с. 35 Геометрическую интерпретацию имеют ЗЛП с двумя переменными. Исследуем целевую функцию 30х1 + 40х2. Данной целевой функции соответствует семейство прямых 30х1 + 40х2 = L, представляющих собой множество параллельных прямых, каждая из которых соответствует определенному значению параметра L. Тогда задачу линейного программирования можно сформулировать следующим образом. Найти такое максимальное значение L, при котором прямая 30х1 + 40х2 = L пересекает допустимое множество. В общем случае с геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на которой достигается самая верхняя (нижняя) линия уровня (прямая, отражающая целевую функцию), расположенная дальше (ближе) остальных в направлении наискорейшего роста. Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент целевой функции f(X) на плоскости Х1ОХ2. Этот вектор показывает направление наискорейшего изменения целевой функции, он равен f ( X )  f ( X ) f ( X ) e1  e2 , x1 x 2 где e1 и e2  единичные векторы по осям ОХ1 и ОХ2 соответственно. Таким образом, f(X) = (f/x1, (f/x2). Координатами вектора-градиента целевой функции f(X) являются коэффициенты целевой функции f(X). В рассматриваемом примере, если двигать прямую 30х1 + 40х2 = L из начала координат по направлению вектора-градиента целевой функции, то точкой, в которой достигается самая верхняя линия уровня является точка М пересечения прямых 5x1 + 2x2 = 10000 и x1 + 2x2 = 4000 с координатами x1 = 1500 и x2 = 1250. Таким образом, оптимальное решение достигается в точке М (1500; 1250). При этом значение целевой функции составит f(X*) =30 * 1500 + 40 * 1250 = 95000. На этом примере можно увидеть основные свойства задач линейного программирования: допустимое множество точек представляет собой выпуклый 36 многоугольник, получившийся в результате пересечения полуплоскостей и наибольшее значение целевой функции достигается в его вершине – крайней точке. Решение задачи линейного программирования может быть не единственным, а состоять из бесконечного числа точек. Таким образом, решение задачи линейного программирования состоит в следующем: необходимо построить многоугольник допустимых точек, найти его вершины и выбрать из них те, координаты которых придают максимальное значение целевой функции. 37 Лекция 5. Симплексный метод решения задачи линейного программирования План. 5.1. Симплекс-метод. 5.2.Симплексные таблицы и алгоритм решения задач. 5.3. Применение симплексного метода в экономических задачах. 5.1. Симплекс-метод Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, заданную в каноническом виде. Идея симплекс метода была разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американский ученый Д. Данцинг в 1949 г. разработал симплекс-метод, позволяющий решать любую задачу линейного программирования. В настоящее время на основе этого метода разработан пакет программ для решения задач линейного программирования. Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. При этом перемещении значение целевой функции для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение. Симплексный метод состоит из трех основных элементов: 1) определения какого-либо первоначального допустимого базисного решения задачи; 2) правила перехода к лучшему решению; 3) проверки оптимальности допустимого решения. Симплекс-метод состоит из двух вычислительных процедур: - симплекс-метод с естественным базисом; - симплекс-метод с искусственным базисом. 38 Выбор конкретной вычислительной процедуры осуществляется после приведения исходной задачи линейного программирования к каноническому виду. Для применения симплекс-метода с естественным базисом ЗЛП в каноническом виде должна содержать единичную подматрицу порядка m, в этом случае очевиден первоначальный опорный план (неотрицательное базисное решение системы ограничений). Симплексный метод с искусственным базисом применяется при отсутствии первоначального опорного плана исходной ЗЛП в каноническом виде. Такая ситуация возникает при наличии в исходном ограничении знаков «равно» либо «больше или равно». 5.2. Симплексные таблицы и алгоритм решения задач Рассмотрим алгоритм решения задач симплексным методом17. 1. Математическая модель задачи должна бать канонической. Если она неканоническая, то ее надо привести к каноническому виду. 2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплекс-таблицу. Все строки таблицы 1-го шага, за исключением строки j (индексная строка), заполняем по данным системы ограничений и целевой функции. Симплексная таблица имеет следующий вид: сi Базисная переменная (БП) с1 с2  сm сm+1  сn f(X) x1 x2  xm xm+1  xn b1 c1 x1 1  h1, m+1  h1n l1 c2 x2 1  h2, m+1  h2n l2           cm xm  1 hm, m+1  hmn lm j  m+1  n f(X1) 17 Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: учеб. пособие. 2е изд., доп. – СПб.: Питер, 2010. – С. 30-32. 39 Индексная строка (j) для переменных находится по формуле m  j   ci hij  c j , j  1, n i 1 и для свободного члена по формуле m  j   ci li . i 1 При этом возможны следующие случаи решения задачи на максимум: - если все оценки j  0, то найденное решение оптимальное; - если хотя бы одна оценка j  0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f(X)  , т.е. целевая функция не ограничена в области допустимых решений; - если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению; - если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка. Пусть одна оценка k  0 или наибольшая по абсолютной величине k  0, тогда k-й столбец принимают за ключевой (разрешающий). За ключевую (разрешающую) строку принимают ту, которой соответствует минимальное отношение свободных членов (bi) к положительным коэффициентам k-го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевым (разрешающим) элементом. 3. Заполнение симплексной таблицы 2-го шага: - переписывается ключевая строка, разделив ее элементы на ключевой элемент; - заполняют базисные столбцы; - остальные коэффициенты таблицы находят по правилу «прямоугольника». Оценки можно считать по приведенным выше формулам или по правилу 40 «прямоугольника». Получается новое опорное решение, которое проверяется на оптимальность и т.д. Примечание. Если целевая функция f(X) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок j при всех j  1, n . Правило «прямоугольника» состоит в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h1, m+1. Тогда элемент i-й строки (m+2)-го столбца 2-го шага, который обозначим hi,m  2 , по правилу «прямоугольника» определяется по формуле hi,m  2  h1,m 1  hi , m  2  hi ,m 1  h1, m 2 h1,m 1 , где h1, m+1, hi, m+1, hi, m+2 – элементы 1-го шага. 5.3. Применение симплексного метода в экономических задачах Рассмотрим применение симплексного метода на примерах экономических задач18. Пример. Предприятие располагает тремя производственными ресурсами (сырьем, оборудование, электроэнергией) и может организовать производство продукции двумя различными способами. Расход ресурсов и амортизация оборудования за один месяц и общий ресурс при каждом способе производства заданы в таблице (в ден. ед.). Производственный ресурс Расход ресурсов за 1 месяц при работе Общий ресурс по 1 способу по 2 способу Сырье 1 2 4 Оборудование 1 1 3 Электроэнергия 2 1 8 18 Там же. С. 33 – 35. 41 При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором – 4 тыс. изделий. Сколько месяцев должно работать предприятие по каждому из этих способов, чтобы при наличных ресурсах обеспечить максимальный выпуск продукции? Решение. Обозначим: х1 – время работы предприятия по первому способу; х2 – время работы предприятия по второму способу. Экономикоматематическая модель задачи: f ( X )  3 x1  4 x 2  max при ограничениях:  x1  2 x 2  4,  x  x  3,  1 2   2 x1  x 2  8,  x1  0, x 2  0. Приведем задачу к каноническому виду: f ( X )  3 x1  4 x 2  max при ограничениях:  x1  2 x 2  x 3  4,  x  x  x  3,  1 2 4  2 x1  x 2  x5  8,  x j  0, j  1, 5. Составляем симплексную таблицу 1-го шага: сi БП 3 4 f (X ) х1 х2 х3 х4 х5 bi x3 1 2 1 4 x4 1 1 1 3 x5 2 1 1 8 -3 -4 j X 1 = (0, 0, 4, 3, 8), f ( X 1 ) = 0. 42 В индексной строке j имеются две отрицательные оценки, значит найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следует принять столбец базисной переменной х2, а за ключевую строку – строку переменной х3, где min (4/2, 3/1, 8/1) = min (2, 1, 8) = 2. Ключевым элементом является «2». Вводим в столбец БП переменную х2, выводим х3. Составляем симплексную таблицу 2-го шага: сi БП 3 4 f (X ) х1 х2 х3 х4 х5 bi 4 x2 1/2 1 1/2 2 x4 1/2 -1/2 1 1 x5 3/2 -1/2 1 6 -1 2 8 j X 2 = (0, 2, 0, 1, 6), f ( X 2 ) = 8. В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является «1/2». Составим симплексную таблицу 3-го шага: сi БП 3 4 f (X ) х1 х2 х3 х4 х5 bi 4 x2 1 1 -1 1 3 x1 1 -1 2 2 x5 1 -3 1 3 1 2 10 j Все оценки свободных переменных j  0, следовательно, найденное опорное решение является оптимальным: X * = (2, 1, 0, 0, 3), f ( X * ) = 10. Ответ: максимальный выпуск продукции составит 10 тыс. ед., при этом по первому способу предприятие должно работать два месяца, по второму – один месяц. 43 Лекция 6. Метод искусственного базиса решения задачи линейного программирования План. 6.1. Метод искусственного базиса. 6.2. Применение метода искусственного базиса. 6.1. Метод искусственного базиса При решении задач симплексным методом необходимо, чтобы модель задачи была канонической и система ограничений была приведена к единичному неотрицательному базису. Встречаются случаи, когда эти преобразования оказываются громоздкими19. Метод искусственного базиса дает возможность решать задачи, приведенные к каноническому виду, без предварительного нахождения опорного решения. Дана задача линейного программирования: n f ( X )   c j x j  max j 1 n a ij x j  bi , i  1, m , j 1 x j  0; j  1, n . Из этой задачи составим вспомогательную задачу следующим образом: 1) систему ограничений вспомогательной задачи получаем из системы ограничений исходной, добавляя в каждое ограничение, не содержащее базисную переменную, искусственную базисную переменную; 2) целевая функция равна алгебраической сумме искусственных переменных, взятых с коэффициентом (-1); 3) условие не отрицательности распространяется на все переменные, в том числе и искусственные. Математическая модель вспомогательной задачи: 19 Там же. С. 35- 36. 44 ~ f ( X )  m  ( x j )  max j  n 1 n a ij x j  x n i  bi , i  1, m , j 1 x j  0; j  1, n . Система ограничений вспомогательной задачи приведена к единичному базису, поэтому она имеет решение: X  = (0, 0, , 0, b1, b2, , bn), при этом f ( X )  0. Между оптимальным решением вспомогательной задачи и опорным решением исходной задачи существует зависимость: ~ 1) если f ( X ) = 0 достигается при X  = (l1, l2, , ln, 0, 0, , 0), то X = (l1, l2, , ln) является исходным опорным решением; ~ 2) если max f ( X )  0, то ограничения исходной задачи несовместны. 6.2. Применение метода искусственного базиса Применение метода искусственного базиса рассмотрим на следующем примере20: f ( X )  4 x1  4 x 2  2 x3  max при ограничениях:  2 x1  x 2  x 3  1,  2 x1  x 2  2 x3  2,  x  0, j  1, 3.  j Решение. Составим вспомогательную задачу: ~ f ( X )   x 4  x5  max при ограничениях:  2 x1  x 2  x3  x 4  1,  2 x1  x 2  2 x3  x5  2,  x j  0, j  1, 5.  20 Там же. С. 36- 37. 45 Решим вспомогательную задачу симплексным методом: сi БП -1 -1 ~ f ( X ) х1 х2 х3 х4 х5 bi -1 х4 2 1 1 1 1 -1 х5 2 -1 2 1 2 -4 -3 -3 j х1 1 ½ ½ ½ ½ -1 х5 -2 1 -1 1 1 2 -1 2 -1 j х1 1 3/2 1 ½ х3 -2 1 -1 1 1 1 1 j Решение вспомогательной задачи: ~ * X  = (0, 0, 1, 0, 0), f ( X * ) = 0, Исходное опорное решение данной задачи: X * = (0, 0, 1). Проверим это решение на оптимальность: сi БП 4 -4 2 f (X ) х1 х2 х3 bi 4 х1 1 3/2 2 х3 -2 1 1 6 2 j Ответ: X * = (0, 0, 1), f ( X * ) = 2. 46 Лекция 7. Двойственные задачи линейного программирования План. 7.1. Двойственная задача для стандартной задачи. 7.2. Основные теоремы двойственности. 7.3. Метод одновременного решения пары двойственных задач. 7.1. Двойственная задача для стандартной задачи Каждой задаче линейного программирования можно поставить в соответствие так называемую двойственную или сопряженную задачу по отношению к исходной задаче. Аппарат теории двойственности может быть эффективно использован для проведения качественных исследований свойств задачи линейного программирования. Рассмотрим задачу выбора оптимальной производственной программы. Пусть предприятие № 1 имеет запасы материально-сырьевых ресурсов в объемах bi ( i  1, m ), где m – число видов ресурсов. Как и раньше будем считать, что aij – это объем материально-сырьевых ресурсов вида i, необходимых для производства одной единицы продукции вида j, cj – прибыль от выпуска и реализации единицы продукции вида j ( j  1, n ). Далее будем считать, что предприятие № 2 решило купить все материально-сырьевые ресурсы у предприятия № 1 по некоторым оптимальным ценам на эти ресурсы, которые обозначим как y1, , ym. Естественно, что предприятие № 2 заинтересовано в том, чтобы затраты на приобретение материальносырьевых ресурсов были минимальными, т.е. g (Y )  b1 y1  b2 y 2    bm y m  min . С другой стороны, предприятие № 1, которое продает материальносырьевые ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при использовании ресурсов на производство готовой продукции. Для изготовления единицы продукции вида 1 расходуется a11 ресурсов первого вида, a21 ресурсов второго вида, , ai1 ресурсов i-го вида. Поэтому для 47 того чтобы удовлетворить требованиям продавца (предприятие № 1), затраты на ресурсы, используемые для изготовления одной единицы продукции первого вида, должны быть не менее ее цены с1. Иными словами, необходимо выполнение неравенства следующего вида: a11 y1  a 21 y 2    a m1 y m  c1 . Аналогично можно представить ограничения по всем остальным видам продукции 2, 3, , n. Экономико-математическая модель и содержательная интерпретация получаемой таким образом задачи представлена в правой части табл. 7.1. Таблица 7.1 Исходная (прямая) задача (I) f ( X )  c1 x1  c 2 x 2    c n x n  max (7.1) Двойственная задача (II) g (Y )  b1 y1  b2 y 2    bm y m  min (7.4) при ограничениях: при ограничениях:  a11 x1  a12 x 2    a1n x n  b1  a x  a x  a x  b  21 1 22 2 2n n 2    a m1 x1  a m 2 x 2    a mn x n  bm  a11 y1  a 21 y 2    a m1 y m  c1 a y  a y    a y  c  12 1 22 2 m2 m 2    a1n y1  a 2n y 2    a mn y m  c n (7.2) и условие неотрицательности и условие неотрицательности x1  0, x 2  0,  , x n  0 (7.5) (7.3) y1  0, y 2  0,  , y m  0 найти составить такой план выпуска продукции X  ( x1, x 2 , , x n ) , при котором прибыль такой набор (7.6) цен ресурсов Y  ( y1, y 2 , , y m ) , при котором общие затраты на ресурсы будут минимальными (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации продукции Цены ресурсов y1, , ym в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл их названий состоит в том, 48 что в отличие от цен на полученную продукцию, которые достаточно точно могут прогнозироваться, цены ресурсов y1, , ym являются внутренними, так как они задаются не извне, а определяются в результате решения задачи, поэтому их часто называют оценками ресурсов. Исходная и двойственная задачи обладают следующими характеристиками. 1. В первой задаче определяется максимум линейной целевой функции, во второй – минимум. 2. Коэффициенты при переменных в целевой функции первой задачи являются правыми частями в системе ограничений во второй задаче. 3. Каждая из задач задана в стандартной форме, при этом в задаче максимизации все неравенства вида «меньше или равно», а в задаче минимизации все неравенства вида «больше или равно». 4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.  a11 a12  a a Для задачи I A   21 22    a  m1 a m 2  a11  a Для задачи II A   12   a  1n a 21 a 22  a 2n     a1n   a 2n  .    a mn      a m1   am 2  .    a mn  5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче. 6. Условие не отрицательности переменных имеются в обеих задачах. Задачи (I и II) линейного программирования, обладающие указанными характеристиками, называются симметричными взаимодвойственными задачами. Далее будем называть их двойственными задачами. Задачу (I) еще называют исходной или прямой паре двойственных задач. Исходя из описанных 49 характеристик двойственных задач, можно сформулировать следующее правило формирования двойственной задачи. 1. Привести все неравенства системы к одному виду: если в исходной задаче ищется максимум целевой функции, то все неравенства системы ограничений приводятся к виду «меньше или равно», а если минимум – к виду «больше или равно». Для этого неравенства, не удовлетворяющие требованиям, умножают на (1). 2. Составить расширенную матрицу А1, в которую включить матрицу коэффициентов при переменных А, столбец правых частей исходной системы ограничений и строку коэффициентов при переменных в целевой функции. 3. Сформировать матрицу А1, транспонированную к матрице А1. 4. Сформировать двойственную задачу на основании полученной матрицы А1 и условия не отрицательности переменных. Пример формирования двойственной задачи. Пусть исходная или прямая задача линейного программирования (ПЗЛП) состоит в определении максимума целевой функции f ( X )   x1  3 x 2  max при ограничениях: 2 x1  3x 2  1  x  4 x  14  1 2   x1  x 2  3  x1  x 2  15 x1  0, x2  0 . Решение. 1. Так как исходная задача на максимум, то обе части первого и четвертого неравенства умножим на (1). Получим:  2 x1  3 x 2  1  x  4 x  14  1 2 .   x1  x 2  3  x1  x 2  15 2. Составим расширенную матрицу системы: 50 3  1  2   14   1 4 A1   1  1 3 .     1  1  15   1 3 f   3. Найдем матрицу А1, транспонированную к матрице А1:   2  1 1  1  1   A1   3 4  1  1 3  .   1 14 3  15 g   4. Сформулируем двойственную задачу g (Y )   y1  14 y 2  3 y 3  15 y 4  min при ограничениях:  2 y1  y 2  y 3  y 4  1   3 y1  4 y 2  y 3  y 4  3 y1  0, y 2  0, y 3  0, y 4  0 . 7.2. Основные теоремы двойственности Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности. Основное неравенство теории двойственности. Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений X  ( x1, x 2 , , x n ) и Y  ( y1, y 2 , , y m ) прямой и двойственной задач справедливо неравенство n f ( X )  g (Y ) или m c x j j 1 j   bi y i . (7.7) i 1 Доказательство. Умножив неравенства системы ограничений (7.2) прямой n задачи a ij x j  bi , i  1, m соответственно на переменные y1, , ym и сложив пра- j 1 вые и левые части полученных неравенств, имеем m n m  yi  aij x j   bi yi . i 1 j 1 (7.8) i 1 51 Аналогично преобразовав систему ограничений (7.5) двойственной задаm чи a ij y i  c j , j  1, n путем умножения обеих частей неравенства на перемен- i 1 ные х1, , хn и последующего их сложения, получим n m  x a j j 1 i 1 n ij yi   c j x j . (7.9) j 1 Так как левые и правые части неравенств (7.8) и (7.9) представляют одно m и то же выражение n  a i 1 ij x j y i , то в силу свойства транзитивности неравенств j 1 получим доказываемое неравенство (7.7). Теперь можно перейти к признакам оптимальности решений. Достаточный признак оптимальности. Сформулируем теорему. Теорема 1. Если X  ( x1, x2 ,, xn ) и Y  ( y1, y2 ,, y m )  допустимые решения взаимодвойственных задач, для которых выполняется равенство f ( X * )  g (Y * ) , (7.10) то X *  оптимальное решение прямой задачи I, а Y *  двойственной задачи II. Доказательство. Пусть X 1  любое допустимое решение прямой задачи I. Тогда на основании основного неравенства (7.7) получим f ( X 1 )  g (Y * ) . Однако X 1 - произвольное решение задачи I, отсюда в силу равенства (7.10) следует, что f ( X 1 )  f ( X * ) , т.е. X *  оптимальное решение прямой задачи I. Аналогично доказывается, что решение оптимально для задачи II. Кроме достаточного признака оптимальности взаимодвойственных задач существуют и другие важные соотношения между их решениями. Прежде всего возникают вопросы: всегда ли для каждой пары двойственных задач есть одновременно оптимальные решения; возможна ли ситуация, когда одна из двойственных задач имеет решение, а другая нет. Ответ на эти вопросы дает следующая теорема. Первая (основная) теорема двойственности. Если одна из взаимодвойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: 52 f ( X * )  g (Y * ) , fmax = gmin. (7.11) Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы и она не имеет решения. Из первой части утверждения теоремы (которую принимаем без доказательства) следует, что условие (7.10) является не только достаточным признаком оптимальности решений (доказанным выше), но и необходимым признаком оптимальности решений взаимодвойственных задач. Утверждение второй части легко доказывается методом от противного. Предположим, что в прямой задаче линейная функция не ограничена, т.е. f ( X * )   , а условия двойственной задачи не являются противоречивыми, т.е. существует хотя бы одно допустимое решение Y  ( y1, y2 ,, y m ) . Тогда, в силу основного неравенства теории двойственности (5.7) f ( X * )  g (Y * ) , что противоречит условию неограниченности f ( X ) . Следовательно, при f (X )   в прямой задаче допустимых решений в двойственной задаче быть не может. Экономический смысл первой (основной) теоремы двойственности. План производства * * * * * X *  ( x1 , x 2 , , x n ) и набор цен (оценок) ресурсов * Y *  ( y1 , y 2 , , y m ) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (известных заранее) ценах с1, с2, , сn, равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам y1, , ym. Для всех же других планов X и Y обеих задач в соответствии с основным неравенством (7.7) теории двой- ственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы. Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану X *  ( x1* , x2 * ,, xn * ) и получить максимальную прибыль (выручку) fmax либо продавать ресурсы по оптимальным ценам Y *  ( y1* , y 2 * ,, y m * ) и возместить от продажи равные ей минимальные затраты на ресурсы gmin. 53 Замечание. Утверждение, обратное по отношению ко второй части основной теоремы двойственности, в общем случае неверно, т.е. из того, что условия исходной задачи противоречивы, не следует, что линейная функция двойственной задачи не ограничена. Тесная связь между двумя взаимодвойственными задачами проявляется не только в равенстве оптимальных значений их линейных функций, о чем утверждалось в первой (основной) теореме двойственности. При приведении каждой из взаимодвойственных задач к каноническому виду в систему ограничений прямой задачи I (7.2) вводят m неотрицательных переменных xn+1, xn+2,  xn+m, а в систему ограничений двойственной задачи II – n неотрицательных переменных ym+1, ym+2,  ym+n. Системы ограничений каждой из взаимодвойственных задач примут вид: n a ij x j  x n k  bi , i  1, m (7.12) ij y i  y m  j  c j , j  1, n (7.13) j 1 m a i 1 Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи (табл. 7.2). Таблица 7.2 Переменные прямой задачи I Первоначальные x1  y m 1 x2   xj  y m2  y m j  Дополнительные xn  x n 1   y mn y1 Дополнительные x n  2  x n i   y2  yj  x n m  (7.14)  ym Первоначальные Переменные двойственной задачи II Теорема 2 (примем без доказательства). Положительным (ненулевым) компонентам оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2, , m и j = 1, 2, , n: если x *j > 0, то y m*  j = 0; 54 если x n*i > 0, то y i* = 0, и аналогично, если y i* > 0, то x n*i = 0; если y m*  j > 0, то x *j = 0. Из рассмотренной теоремы следует важный вывод о том, что введенное ранее соответствие (7.14) между переменными взаимодвойственных задач при достижении оптимума (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения. Рассмотренная теорема является следствием следующей теоремы. Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции прямой задачи, выраженной через неосновные переменные ее оптимального решения. Замечание. Если в одной из взаимодвойственных задач нарушается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное. Это связано с тем, что при нарушении единственности оптимального решения прямой задачи в выражении линейной функции ее оптимального решения через неосновные переменные отсутствует хотя бы одна из основных переменных. Третья теорема двойственности. Компоненты оптимального решения двойственной задачи равны значениям частных производных линейной функции fmax(b1, b2, , bm) по соответствующим аргументам, т.е. f max  y i* , i  1, m . bi (7.15) Из данной теоремы следует, что объективно обусловленные оценки показывают, насколько денежных единиц изменится максимальная выручка от реа- 55 лизации продукции при изменении запасов соответствующего i-го ресурса на одну единицу. 7.3. Метод одновременного решения пары двойственных задач Используя теоремы двойственности, можно, решив симплексным методом прямую задачу, найти оптимальное решение двойственной задачи. Метод одновременного решения пары взаимодвойственных задач заключается в следующем. 1. Обе задачи приводят к каноническому виду и устанавливают соответствие между переменными обеих задач. 2. Решают с помощью симплекс-метода ту из двух задач, где свободные члены в выражениях для базисных переменных неотрицательны (предполагается, что одна из задач таким свойством обладает). 3. На основании первой теоремы двойственности определяют оптимальное значение целевой функции второй задачи: f ( X * )  g (Y * ) или fmax = gmin. 4. На основании второй теоремы двойственности выписывают оптимальное решение второй задачи. Для этого целевую функцию первой задачи выражают через свободные, или неосновные, переменные. Тогда компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции прямой задачи, выраженной через неосновные переменные ее оптимального решения. При использовании симплекс-таблиц из последней симплекс-таблицы выделяют последнюю строку, в которой числа, соответствующие переменным прямой задачи, присваивают компонентам оптимального решения двойственной задачи на основе соответствия переменных прямой и двойственной задачи. Вернемся к примеру п. 4.3. Прямая ЗЛП: Двойственная ЗЛП: f ( X )  3 x1  4 x 2  max g (Y )  4 y1  3 y 2  8 y 3  min 56  x1  2 x 2  4,  x  x  3,  1 2   2 x1  x 2  8,  x1  0, x 2  0.  y1  y 2  2 y 3  3 2 y  y  y  4 2 3  1  y1  0, y 2  0, y 3  0 Канонический вид: f ( X )  3 x1  4 x 2  max g (Y )  4 y1  3 y 2  8 y 3  min  x1  2 x 2  x 3  4,  x  x  x  3,  1 2 4  2 x1  x 2  x5  8,  x j  0, j  1, 5.  y1  y 2  2 y 3  y 4  3 2 y  y  y  y  4 2 3 5  1  y  0, i  1, 5  i Установим соответствие между переменными двух задач: Переменные прямой задачи I Первоначальные Дополнительные х1 х2 х3 х4 х5      y4 y5 y1 y2 y3 Дополнительные Первоначальные Переменные двойственной задачи II Первой решается прямая задача, поскольку для нее свободные члены в выражениях для базисных переменных неотрицательны: х3 = 4 – х1 – 2х2, х4 = 3 – х1 – х2, х5 = 8 – 2х1 – х2. Итоговая симплекс-таблица решения прямой задачи имеет вид: сi БП x2 x1 x5 4 3 j 3 х1 1 4 х2 1 х3 1 -1 1 1 х4 -1 2 -3 2 х5 1 f (X ) y4 y5 y1 y2 y3 G(Y) 57 bi 1 2 3 10 Значение целевой функции двойственной задачи равно значению целевой функции прямой задачи: g (Y * ) = f ( X * ) = 10. Оптимальное решение прямой задачи: X * = (2, 1, 0, 0, 3). Оптимальное решение двойственной задачи: Y * = (1, 2, 0, 0, 0), поскольку y1  x3, y2  x4, y3  x5, y4  x1, y5  x2. Последней симплекс-таблице соответствуют следующие уравнения для базисных переменных, входящих в целевую функцию: х1 – х3 + 2х4 = 2, х2 + х3 – х4 = 1. Откуда х1 = 2 + х3 – 2х4, х2 = 1 – х3 + х4. Выразим целевую функцию через свободные переменные: f ( X * ) = 3(2 + х3 – 2х4) + 4(1 – х3 + х4) = 10 – х3 – 2х4. Таким образом, в соответствии со второй теоремой двойственности y1 = 1, y2 = 2, значения остальных переменных оптимального решения двойственной задачи y3, y4, y5 равны нулю, поскольку они не входят в выражение целевой функции. Следует отметить, что положительным (ненулевым) компонентам оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи: Переменные прямой задачи I Первоначальные Дополнительные x1*  2 x 2*  1 x3*  0 x 4*  0 x5*  3  y 0  y 0  * y1  1  y 2  y 0 * 4 * 5 Дополнительные * 2 * 3 Первоначальные Переменные двойственной задачи II Такое соответствие было отмечено в рассмотренной ранее теореме. 58 Библиографический список 1.Кочетыгов, А.А. Моделирование экономических систем: учебное пособие/ А.А. Кочетыгов; ТулГУ. — Тула: Изд-во ТулГУ, 2012. — 292 с. 2. Минько Э.В. Методы прогнозирования и исследования операций [Электронный ресурс]: учебное пособие / Минько Э.В., Минько А.Э. — Электрон. текстовые данные.— М.: Финансы и статистика, 2012. — 480 с. — ЭБС «IPRbooks», по паролю 3. Мастяева И.Н. Методы оптимизации. Линейные и нелинейные методы и модели в экономике [Электронный ресурс]: учебное пособие / Мастяева И.Н., Семенихина О.Н. — Электрон. текстовые данные.— М.: Евразийский открытый институт, 2011. — 424 с. — Режим доступа: http// www.iprbookshop.ru /10783. — ЭБС «IPRbooks», по паролю 4.Аттетков А.В. Введение в методы оптимизации [Электронный ресурс]: учебное пособие / Аттетков А.В.,Зарубин В.С., Канатников А.Н. — Электрон. текстовые данные.— М.: Финансы и статистика, 2014. — 272 с. — Режим доступа: http// www.iprbookshop.ru /18794. — ЭБС «IPRbooks», по паролю 5. Теория игр в экономике (практикум с решениями задач): учебное пособие / Л.Г. Лабскер, Н.А. Ященко; под ред. Л.Г. Лабскера — 3-е изд., перераб. — М.:КНОРУС., 2014. — 264 с. — (бакалавриат) — [Электронный ресурс] — URL: http// www. book.ru /view/915104/2 6. Шапкин, А.С. Математические методы и модели исследования операций: учебник для вузов/А.С. Шапкин, В.А. Шапкин. — М.: Дашков и К0, 2011. — 397 с. 7. Воробьев, С.А. Теория игр и исследование операций: учебное пособие / С.А.Воробьев: ТулГУ, Каф. прикладной математики и информатики. — Тула: Изд-во ТулГУ, 2012. — 103 с. 8. Вентцель Е.С. Исследование операций : задачи, принципы, методология : учеб. пособие / Е.С. Вентцель.— 5-е изд., стер. — М.: Высш. шк., 2010 .— 191 с. 9. Солодовников А.С. Математика в экономике: учебник для вузов. Ч.1 / А.С. Солодовников [и др.] .— 2-е изд., перераб. и доп. — М.: Финансы и статистика, 2007 .— 384с. 59