Экономико-математические модели. Применение элементов линейной алгебры в экономике. Линейное программирование

Часть 1. Экономико-математические модели Введение Принятие решения в реальных задачах экономики и управления – проблема многосложная, отягощенная к тому же неохватным разнообразием объективно существующих альтернатив и ограниченными возможностями взявшегося за его поиск. Успехи использования математических методов и стиля мышления в естественных науках привели к мысли о том, чтобы включить в сферу математического влияния проблемы экономики и управления. Основным методом исследования экономических систем становится метод математического моделирования, т. е. способ теоретического анализа и практического действия, направленный на разработку и использование моделей. При этом под моделью будем понимать образ реального объекта (процесса) в идеальной форме (т. е. описанный знаковыми математическими средствами), отражающий существенные свойства моделируемого объекта (процесса) и заменяющий его в ходе исследования и управления. Специалисты разных направлений, связанных с приложением математики, ясно представляют, что математическое моделирование – это в некоторой степени искусство применения математики и системного анализа. Очевидно, что в полной мере искусством построения моделей можно овладеть только в результате собственной практики. Настоящее учебное пособие дает лишь основы математического моделирования, т. е. минимум тех знаний, которые необходимы начинающим исследователям. Практическими задачами экономико-математического моделирования являются: • анализ экономических объектов и процессов; • экономическое прогнозирование, предвидение развития экономических процессов; • выработка управленческих решений на всех уровнях хозяйственной иерархии. Следует, однако, иметь в виду, что далеко не во всех случаях данные, полученные в результате моделирования, могут использоваться непосредственно как готовые управленческие решения. Они скорее могут быть рассмотрены как «консультирующие» средства. Принятие управленческих решений остается за человеком. Таким образом, математическое моделирование является лишь одним из компонентов (пусть очень важным) в человеко-машинных системах планирования и управления экономическими системами. Важнейшим фактором успешного применения методов математического моделирования является знание основных законов экономической теории и их практического приложения к реальным объектам и системам. Одним из основных понятий при экономико-математическом моделировании является понятие адекватности модели, т. е. соответствия модели моделируемому объекту или процессу. Адекватность модели – в какой-то мере условное понятие, так как полного соответствия модели реальному объекту быть не может. При моделировании имеется в виду не просто адекватность, но соответствие по тем свойствам, которые считаются существенными для исследования. Проверка адекватности моделей является весьма серьёзной проблемой, тем более что ее осложняет трудность измерения экономических величин. Однако без такой проверки применение результатов моделирования в управленческих решениях может не только оказаться малополезным, но и принести существенный вред. Социально-экономические системы относятся, как правило, к так называемым сложным системам. Сложные системы в экономике обладают рядом свойств, которые необходимо учитывать при их моделировании, иначе невозможно говорить об адекватности построенной экономической модели. Важнейшие из этих свойств: • эмерджентность как проявление в наиболее яркой форме свойства целостности системы, т. е. наличие у экономической системы таких свойств, которые не присущи ни одному из составляющих систему элементов, взятому в отдельности, вне системы. Эмерджентность есть результат возникновения между элементами системы так называемых синергических связей, которые обеспечивают увеличение общего эффекта до величины большей, чем сумма эффектов элементов системы, действующих независимо. Поэтому экономические системы необходимо исследовать и моделировать в целом; • массовый характер экономических явлений и процессов. Закономерности экономических процессов не обнаруживаются на основании небольшого числа наблюдений. Поэтому моделирование в экономике должно опираться на массовые наблюдения; • динамичность экономических процессов, заключающаяся в изменении параметров и структуры экономических систем под влиянием среды (внешних факторов); • случайность и неопределённость в развитии экономических явлений. Поэтому экономические явления и процессы носят в основном вероятностный характер, и для их изучения необходимо применение экономико-математических моделей на базе теории вероятностей и математической статистики; • невозможность изолировать протекающие в экономических системах явления и процессы от окружающей среды, чтобы наблюдать и исследовать их в чистом виде; • активная реакция на появляющиеся новые факторы, способность социально-экономических систем к активным, не всегда предсказуемым действиям в зависимости от отношения системы к этим факторам, способам и методам их воздействия. Выделенные свойства социально-экономических систем, естественно, осложняют процесс их моделирования, однако эти свойства следует постоянно иметь в виду при рассмотрении различных аспектов в экономико-математическом моделировании, начиная с выбора типа модели и заканчивая вопросами практического использования результатов моделирования. 1.1 Основные принципы и этапы математического моделирования Метод моделирования основывается на принципах аналогии, т. е. возможности изучения реального объекта (системы, процесса) не непосредственно, а через рассмотрение подобного ему и более доступного объекта, его модели. В дальнейшем мы будем говорить только об экономико-математическом моделировании, т. е. об описании знаковыми математическими средствами экономических систем. Однако сразу отметим, что независимо от содержания исследуемого вопроса, области деятельности и личных склонностей исследователя процесс научного исследования всегда проходит определенные этапы. В этом смысле можно говорить об алгоритме (этапах) не только экономико-математического моделирования, но и об алгоритме научного исследования вообще. Он наглядно представлен на рис. 1.1. Рассмотрим сущность каждого этапа и пути его осуществления в процессе исследования. Объект. Объект исследования (предприятие, фирма, система и исследуемый процесс) может быть задан (целевой заказ) исследователю заказчиком или выбран самостоятельно (например, при написании выпускной квалификационной работы, диссертационной работы и т. д.). Выбор проблемы (задачи). Сформулировать проблему и выбрать задачу – это весьма существенный и нетривиальный шаг даже в том случае, когда формулировка проблемы звучит совсем просто. Определение реальной проблемы, а не описание ее симптомов требует понимания и интуиции, некоторого воображения и времени. Число различных задач, которые можно выделить даже на уже избранном объекте исследования, практически не ограничено. Однако полезно понимать, что существует четыре типа фундаментальных задач. В этом нетрудно убедиться, если обратить внимание на то, что любой объект исследования что-либо потребляет и что-либо вырабатывает. Этим «что-либо» могут быть вещество, продукция, финансы, энергия, информация и т. д. Объект, который ничего не потребляет и ничего не вырабатывает, просто не будет нами обнаружен. Выработка без потребления противоречит закону сохранения. Потребление без выработки является очевидно бессмысленным, если не сказать невозможным. Таким образом, любой объект исследования (рис. 1.2) имеет «входы» (X1, X2, …, Xn), выходы (Y1, Y2 ,…, Ym), внешние воздействия (T1, T2, …, Tk), которые не подвластны экспериментатору, и, наконец, правило F преобразования входных величин в выходные. Рис. 1.1. Этапы математического моделирования (научного исследования) Рис. 1.2. Представление объекта исследования Обозначив соответствующие совокупности через , работу любого объекта можно записать в виде . Основные задачи при исследовании любого объекта: 1. Задача анализа: даны входные воздействия и правило их переработки F (устройство объекта). Необходимо найти выходной результат . 2. Задача синтеза: необходимо определить и структуру объекта. 3. Задача коррекции: даны и требуемые «выходы» . Необходимо определить требующиеся входные воздействия (обычно требуется определить только некоторые поправки к , отсюда и название задачи). 4. Задача устойчивости состоит в определении работоспособности системы в реальных условиях с учетом изменения внешних неконтролируемых факторов , которые в первых трех задачах считаются постоянными. Однако их практическое изменение может внести существенные поправки в результат работы объекта. Одним из источников задач является оптимизация по критерию. Оптимизация здесь понимается как поиск пути достижения максимума (или минимума) определенного показателя (затрат, стоимости, прибыли, надежности и т. д.). Показатель оптимизации называют критерием или целевой функцией. Следует различать два типа оптимизации: по параметрам и по структуре. Возможна и комбинированная задача. В первом случае структура (устройство, организация, процедура, алгоритм и т. д.) объекта задана предысторией, сложившейся практикой или другими обстоятельствами. Необходимо лишь установить оптимальные значения определенных внутренних параметров системы, при которых критерий оптимизации достигает экстремума. Во втором случае необходимо определить алгоритм работы объекта и его структуру, при которой критерий достигает экстремума. Как правило, задачи оптимизации по структуре сложнее задач оптимизации по параметрам. Это следует из того, что оптимизация по параметрам по своему существу является задачей анализа, в то время как оптимизация по структуре является задачей синтеза искомой структуры. Важным этапом решения задач оптимизации является выбор критерия. Он может быть найден лишь путем содержательного анализа работы исследуемого объекта. При этом могут быть совершены ошибки, основанные на смешении целей и средств. Принято, что хороший критерий должен удовлетворять трем основным требованиям: • отражать интуитивное или логически осознанное представление потребителя о качестве работы систем; • поддаваться математической обработке в целях анализа и синтеза; • указывать пути построения оптимальной системы. По отношению к сложным объектам (например, предприятиям, учреждениям) возникает весьма трудная задача многокритериальной оптимизации. При этом желательно найти параметры или структуру, при которой достигают экстремума одновременно нескольких показателей, например надежность и стоимость. Такие задачи в точном смысле, как правило, неразрешимы. Однако современная теория оптимизации предлагает ряд путей «обходного» и условного решения задачи. Так, можно стремиться к экстремуму одного показателя при заданных границах других. Можно максимизировать (или минимизировать) линейную или нелинейную комбинацию частных показателей. При этом возникает задача «сложения» разноразмерных параметров, имеющих, к тому же, различную психологическую ценность. Имеется несколько способов «обхода» этих трудностей, в частности способ введения шкалы предпочтений и построение обобщенной функции желательности. Модель. Этап формирования модели начинается со словесно-смыслового (логико-лингвистического) описания системы, объекта или явления. На этом этапе важно осознать, что модель всегда есть избранный нами способ «замены» объекта исследования. Иногда эта замена состоит в переходе к аналитическому упрощенному представлению и описанию объекта, т. е. к замене объекта некоторой информацией о нем. Помимо сведений общего характера о природе системы (объекта) и целях исследования данный этап должен содержать некоторые предположения, например линейность характеристик, при этом отбрасываются все факторы и эффекты, которые представляются не самыми существенными для оценки поведения системы. Например, при составлении уравнения запасов рассматривается только основное производство. Идеализирующие предположения по возможности записываются в математической форме, чтобы их справедливость поддавалась количественному контролю. Выбор модели – одна из фундаментальных трудностей научного исследования. Ясно, что модель должна быть адекватна задаче, которая поставлена на объекте. Адекватность означает в данном случае необходимость удержать в модели качества объекта, существенные для поставленной задачи. Однако откуда мы можем заранее знать, какие качества объекта существенны? Можно утверждать, что если модель ясна заранее, то исследование не даст существенно новых результатов, хотя, возможно, приведет к уточнению знаний об объекте. Модель – это всегда гипотеза, предположение. Однако если проблема сформулирована корректно, то появляется возможность выбора готовой модели (из банка моделей, описывающих стандартные ситуации), разработка которой поможет в решении рассматриваемой проблемы. Познавательные возможности модели определяются тем, что модель отображает лишь некоторые существенные черты исходного объекта, поэтому любая модель замещает оригинал в строго ограниченном смысле. Из этого следует, что для одного объекта может быть построено несколько моделей, отражающих определенные стороны исследуемого объекта или характеризующих его с разной степенью детализации. Модели могут быть очень разными: словесные (вербальные), графические, математические. Мы в основном будем использовать математические модели, которые однозначно описывают избранные свойства объекта в терминах математики. По общему целевому назначению экономико-математические модели делятся на теоретико-аналитические, используемые при изучении общих свойств и закономерностей экономических процессов, и прикладные, применяемые в решении конкретных экономических задач анализа, прогнозирования и управления. По степени агрегирования объектов моделирования модели разделяются на макроэкономические и микроэкономические. Хотя между ними и нет четкого разграничения, к первым из них относятся модели, отражающие функционирование экономики как единого целого, в то время как микроэкономические модели связаны, как правило, с такими звеньями экономики, как предприятия и фирмы. По конкретному предназначению, т. е. по цели создания и применения, выделяют балансовые модели, выражающие требования соответствия наличных ресурсов и их использования; трендовые модели, в которых развитие моделируемой экономической системы отражается через тренд (длительную тенденцию) ее основных показателей; оптимизационные модели, предназначенные для выбора наилучшего варианта из определенного числа вариантов производства, распределения или потребления; имитационные модели, предназначенные для использования в процессе машинной имитации изучаемых систем или процессов и др. По учету факторов времени модели подразделяются на статические, в которых все зависимости отнесены к одному моменту времени, и динамические, описывающие экономические системы в развитии. По учету фактора неопределенности модели распадаются на детерминированные, если в них результаты на выходе однозначно определяются управляющими воздействиями, и стохастические (вероятностные), если при задании на входе модели определенной совокупности значений на ее выходе могут получаться различные результаты в зависимости от действия случайного фактора. Экономико-математические модели могут классифицироваться также по характеристике математических объектов, включенных в модель, иными словами, по типу математического аппарата, используемого в модели. По этому признаку могут быть выделены матричные модели, модели линейного и нелинейного программирования, корреляционно-регрессивные модели, модели теории массового обслуживания, модели сетевого планирования и управления, модели теории игр и т. д. Формулировка (постановка) задачи. Постановку или формулировку задачи не следует смешивать с ее выбором или словесной дискуссией по поводу задачи. Сформулировать или поставить задачу – значит строго определить систему количественных взаимосвязей между заданными и искомыми переменными. При этом некоторые взаимосвязи, вид которых не ясен, допустимо обозначать условными знаками в виде функций и функционалов. Правильно и строго сформулированная задача не допускает двусмысленности в толковании того, что задано или считается известным, что требуется отыскать, в чем состоят ограничения, которые на практике всегда существуют. Постановка задачи относится поэтому в определенном смысле к самым сложным этапам алгоритма математического моделирования (научного исследования), ибо она требует глубоких знаний в изучаемой области. Формулировка задачи состоит в нахождении совокупности уравнений и (или) неравенств, описывающих объект. Этот этап тесно связан с предыдущим – выбором модели – и последующим – решением. Однако в целях уяснения существа дела постановку задачи следует условно рассмотреть отдельно. Постановку (формализацию) задачи целесообразно представить из трех шагов или этапов: параметризации, поиска меры и подготовки исходных данных и поиска взаимосвязей. Параметризация состоит в однозначном введении в рассмотрение всех описывающих задачу переменных (параметров). Ясно, что параметризация фактически начата на этапе выбора модели. В дальнейшем целесообразно все переменные разделить на аргументы (переменные, которые будут изменяться в определенных пределах, устанавливаемых исследователем), ограничения (переменные, которым будут заданы несколько дискретных значений) и искомые функции (однако на данном этапе в этом нет необходимости). Параметризацию, в свою очередь, целесообразно провести в три «подэтапа». Сначала все переменные следует перечислить словами. Затем ввести для них сокращенные (буквенные) обозначения и установить характер изменения каждого параметра (закономерное, случайное со средним, равным нулю, относительно медленное, принимающее только положительные значения и т. д.) В сложной задаче, содержащей много переменных, обозначениям целесообразно придавать мнемонический характер путем выбора букв или индексов. Параметризация, по существу, возвращает исследователя к уточнению модели объекта. Поиск меры и подготовка исходных данных состоит в установлении возможности измерить введенные переменные (параметры) и подготовить исходные данные. В экономических задачах это, как правило, наиболее трудоемкий этап моделирования, так как дело не сводится к пассивному сбору данных. Математическое моделирование предъявляет жесткие требования к системе информации; при этом надо принимать во внимание не только принципиальную возможность подготовки информации требуемого качества, но и затраты на подготовку информационных массивов. В процессе подготовки информации используются методы теории вероятностей, теоретической и математической статистики для организации выборочных обследований, оценки достоверности данных и т. д. При системном экономико-математическом моделировании результаты функционирования одних моделей служат исходной информацией для других. Некоторые переменные, если не все, можно непосредственно измерить (определить). Некоторые переменные могут быть определены косвенно, т. е. путем определения других величин, с которыми они однозначно и приемлемо для исследования связаны. Часть переменных нельзя измерить (определить), но их можно упорядочить, т. е. расположить по мере увеличения или уменьшения качества, которое они описывают. В процессе упорядочивания возможны затруднения, однако при введении некоторых условностей их можно преодолеть. Упорядоченную последовательность можно пронумеровать и таким образом каждому состоянию сопоставить число, т. е. в определенном смысле измерить (определить). Наконец, некоторое, обычно небольшое, число переменных нет возможности измерить (определить). Так, например, нет возможности измерить (определить) настроение сотрудников предприятия или состояние их здоровья, от которых явно зависит, например, производительность труда изучаемого предприятия. Подобная ситуация складывается часто именно в больших человеко-машинных системах, вовлекающих обе компоненты в процесс тесного взаимодействия. Для измерения (определения) неизмеримых переменных используется метод экспертных оценок, который состоит в том, чтобы в качестве меры принять определенным образом усредненное мнение группы экспертов в данной области исследования. В частном случае метод экспертных оценок может дать лишь упорядочение по параметру, рассмотренное выше. Поиск взаимосвязей. На этом, заключительном, этапе постановки задачи находятся системы уравнений и неравенств, связывающие переменные. На этом этапе постановки (но не решения) задачи неизвестные взаимосвязи могут быть обозначены символически (F, f, J, x, y, A, B, … ,V и т. д.). В этом случае фактический поиск зависимостей перейдет на этап решения задачи. Совершенно очевидно, что поиск взаимосвязей не может быть осуществлен умозрительно, без обращения к закономерностям, действующим на объекте исследования. В этом смысле этап поиска взаимосвязей не может быть формализован. Закономерность на объекте, например связь некоторой переменной X с переменной Y, в принципе может быть определена лишь путем эксперимента на объекте. Однако это верно лишь по отношению к объектам, с которыми исследователь сталкивается впервые. Подобная ситуация в чистом виде может встретиться крайне редко. Обычно же исследователь сталкивается с частично (или полностью) известным объектом, для которого связь некоторых (а может быть, и всех) переменных друг с другом известна. Таким образом, задача поиска взаимосвязей достаточно четко разделяется на ситуацию поиска одних связей через другие и ситуацию поиска неизвестных первичных связей, которые не удается выразить через другие, известные. Именно этот, второй, случай фактически следует отнести к этапу решения задачи, а не ее постановки. Решение задачи. Решение задачи состоит в раскрытии взаимосвязей переменных, которые на этапе постановки задачи были обозначены неопределенными зависимостями (F, f, Y и т. д.), а также фактическом решении систем уравнений, неравенств и других соотношений, полученных на этапе постановки. Общим принципом является утверждение о том, что решение, если оно существует, всегда возможно. Однако эта «возможность» качественно может быть различной. Здесь встречаются следующие основные ситуации. а) полученная система уравнений (или одно уравнение) была изучена математикой на протяжении ее многовекового развития. Задача исследователя состоит при этом в строгом сопоставлении своих уравнений с уравнениями математики и в последующем решении по установленным правилам; б) полученная система уравнений ранее не встречалась и математиками не изучалась. Вероятность этого весьма мала; в) возможно решить полученную систему уравнений для нескольких частных случаев, сделав какие-либо упрощения (отбрасывание малых членов, пренебрежение нелинейностью и др.). Этот путь опасен, так как подобное «отбрасывание» может сделать задачу тривиальной, потеряв вместе с «малыми» членами важные физические, технические и экономические эффекты; г) полученную систему уравнений можно решить численно на ЭВМ. Подобное решение в виде таблиц или графиков менее полноценно, чем аналитическое, но оно часто может быть единственно возможным. Этот случай включает разработку алгоритмов численного решения задачи, подготовку программ на ЭВМ и непосредственное проведение расчетов; при этом значительные трудности могут возникать из-за большой размерности экономических задач. Обычно расчеты на основе экономико-математической модели носят многовариантный характер. Многочисленные модельные эксперименты, изучение поведения модели при различных условиях возможно проводить благодаря высокому быстродействию современных ЭВМ. Численное решение существенно дополняет результаты аналитического исследования (если оно возможно), а для многих моделей является единственно возможным. Анализ результатов и экспериментальная проверка. Никакое научное исследование не может считаться завершенным без анализа полученных результатов и их экспериментальной проверки. Основными причинами этого являются: • отсутствие уверенности в достаточной полноте (адекватности) принятой модели объекта (системы); • отсутствие уверенности в допустимости пренебрежений, сделанных на этапе постановки задачи и ее решения; • возможность появления ошибок при выполнении этапа решения. Необходимость экспериментальной проверки результатов теоретического исследования вытекает из основного положения, согласно которому критерием истины является общественная практика. Необходимость ее тем больше, чем новее решаемая задача, чем более трудоемкой она является (по объему затрат ресурсов) и чем опаснее последствия от неверного решения задачи. Трудоемкость и ответственность экспериментальной проверки или самостоятельных исследований привели в настоящее время к созданию отдельного научного направления – теории эксперимента. Методы экспериментальной проверки можно разделить на прямые и косвенные. Прямой метод состоит в физическом построении или использовании уже имеющегося объекта исследования и в проверке на нем теоретических соотношений и результатов математического моделирования. Прямая проверка является наиболее достоверным и убедительным путем, однако и наиболее дорогостоящим. Кроме того, очевидно, что не все объекты допускают прямое экспериментирование с ними. Косвенная проверка результатов теории производится на уменьшенных («масштабных») физических или цифровых моделях исследуемых объектов. Хотя «практика есть критерий истины», расхождение данных эксперимента с теорией не всегда является доказательством ошибочности последней. В этой связи важным понятием является чистота эксперимента. Исследователь должен многократно и многими независимыми средствами убедиться, что он измеряет или наблюдает (фиксирует) именно то, что предполагает измерять или наблюдать. Это может быть достигнуто лишь в результате общественной, многократно повторенной практики в разных условиях. Если чистота эксперимента сомнений не вызывает, то экспериментальная проверка может дать два принципиально различных результата. В первом случае результаты эксперимента подтверждают теорию с достаточной для практики точностью. Исследование при этом может считаться законченным, а результаты – передаваться для использования. Во втором случае может иметь место неприемлемое расхождение. В этом случае необходимо уточнить модель, постановку и решение задачи. Эта ситуация отражена циклом на алгоритме исследования (см. рис 1.1). Перечисленные в алгоритме этапы экономико-математического моделирования находятся в тесной взаимосвязи, в частности, могут иметь место возвратные связи этапов, не отраженные в алгоритме. Так, на этапе построения модели может выясниться, что выбранная задача или противоречива, или приводит к слишком сложной математической модели; в этом случае исходная задача (проблема) должна быть скорректирована. Наиболее часто необходимость возврата к предшествующим этапам моделирования возникает на этапе подготовки исходной информации. Если необходимая информация отсутствует или затраты на ее подготовку слишком велики, приходится возвращаться к этапам постановки задачи и ее формализации, чтобы приспособиться к доступной исследователю информации. Недостатки, которые не удается исправить на тех или иных этапах моделирования, устраняются в последующих циклах. Однако результаты каждого цикла имеют и вполне самостоятельное значение. Начав исследование с построения простой модели, можно получить полезные результаты, на основании которых перейти к созданию более сложной и более совершенной модели, включающей в себя новые условия и более точные математические зависимости. Важно осознать, что наличие цикла (который иногда придется пройти несколько раз) является не результатом недостаточных возможностей науки, но следует из ее существа. Наука проверяет гипотезы, т. е. предположения, которые заранее не ясны. Часть 2. Применение элементов линейной алгебры в экономике 2.1 Использование алгебры матриц Использование элементов алгебры матриц является одним из основных методов решения многих экономических задач. Особенно этот вопрос стал актуальным при разработке и использовании баз данных: при работе с ними почти вся информация хранится и обрабатывается в матричной форме. Рассмотрим задачи, использующие понятия n-мерного вектора, матрицы и действия над ними. Пример 1. Пусть затраты четырех видов сырья на выпуск четырех видов продукции характеризуются матрицей A, приведенной в предыдущем примере. Требуется найти: а) общие затраты на сырье для каждого вида продукции и его перевозку; б) общие затраты на сырье и его транспортировку при условии заданного вектора-плана предыдущего примера, если известны себестоимость каждого вида сырья (4, 6, 5, 8) и его доставки (2, 1, 3, 2) в ден. ед. Решение. Составим матрицу себестоимости сырья и его доставки (соответственно 1-я и 2-я строки): . Тогда ответ на первый вопрос задачи дается в виде произведения матрицы A на транспонированную матрицу : . Суммарные затраты на сырье и его доставку (в денежных единицах) при векторе-плане выпуска продукции = (60; 50; 35; 40) определяются произведением вектора на матрицу . . Пример 4. В табл. 2.2 приведены данные о дневной производительности пяти предприятий, выпускающих четыре вида продукции с потреблением трех видов сырья, а также продолжительность работы каждого предприятия в году, затраты видов сырья и цена каждого вида сырья. Таблица 2.2 Вид изделия № п/п Производительность предприятий, изд./день Затраты видов сырья, кг/изд. 1 2 3 4 5 1 2 3 1 4 5 3 6 7 2 3 4 2 2 4 3 3 5 6 3 8 15 4 6 4 4 5 4 3 10 7 5 4 5 8 6 Количество рабочих дней в году Цена видов сырья 1 2 3 4 5 1 2 3 200 150 170 120 140 40 50 60 Требуется определить: • годовую производительность каждого предприятия по каждому виду изделий; • годовую потребность каждого предприятия по каждому виду сырья; • годовую сумму кредитования каждого предприятия для закупки сырья, необходимого для выпуска продукции указанных видов и количеств. Решение. Нужно составить матрицы, характеризующие весь интересующий нас экономический спектр производства, а затем при помощи соответствующих операций над ними получить решение данной задачи. Прежде всего построим матрицу производительности предприятий по всем видам продукции. Каждый столбец этой матрицы соответствует дневной производительности отдельного предприятия по каждому виду продукции. Следовательно, годовая производительность j-го предприятия по каждому виду продукции получается умножением j-го столбца матрицы A на количество рабочих дней в году для этого предприятия (j = 1, 2, 3, 4, 5). Таким образом, годовая производительность каждого предприятия по каждому из изделий описывается матрицей . Матрица затрат сырья на единицу изделия (эти показатели по условию одинаковы для всех предприятий) имеет вид вид сырья Дневной расход по типам сырья на предприятиях описывается произведением матрицы В на матрицу А: , где i-я строка соответствует номеру типа сырья, а j-й столбец – номеру предприятия согласно табл. 2.2 (i = 1, 2, 3, 4; j = 1, 2, 3, 4, 5). Ответ на второй вопрос задачи получим по аналогии с матрицей Aгод умножением столбцов матрицы B·A на соответствующие количества рабочих дней в году для предприятий – это годовая потребность каждого предприятия в каждом виде сырья: . Введем вектор стоимости сырья: = (40; 50; 60). Тогда стоимость общего годового запаса сырья для каждого предприятия получается умножением вектора на матрицу : Следовательно, суммы кредитования предприятий для закупки сырья определяются соответствующими компонентами вектора . Пример 2. Отрасль состоит из n предприятий, выпускающих по одному виду продукции каждое; обозначим объем продукции i-го предприятия через . Каждое из предприятий отрасли для обеспечения своего производства потребляет часть продукции, выпускаемой им самим и другими предприятиями. Например, в отрасли электротехнического оборудования часть продукции предприятий, выпускающих электродвигатели, силовые кабели, выключатели, электрические лампочки и т. д., употребляется практически всей отраслью. Пусть – доля i-го предприятия, потребляемая j-м предприятием для обеспечения выпуска своей продукции объема . Возникает естественный вопрос о величине – количестве продукции i-го предприятия, предназначенной для реализации вне данной отрасли (объем конечного продукта). Эта величина легко может быть подсчитана по формуле , i = 1, 2, …, n. Введем в рассмотрение матрицу порядка n, описывающую внутреннее потребление отрасли: i, j = 1, 2, …, n. Тогда вектор конечного продукта является решением матричного уравнения . Используя единичную матрицу , получаем . (2.1) Например, отрасль состоит из трех предприятий, вектор выпуска продукции отрасли и матрица внутреннего потребления имеют соответственно вид , . Используя формулу (2.1), получаем вектор объемов конечного продукта, предназначенного для реализации вне отрасли: . 2.2. Модель Леонтьева многоотраслевой экономики (балансовый анализ) Макроэкономика функционирования многоотраслевого хозяйства требует баланса между отдельными отраслями. Каждая отрасль с одной стороны является производителем, а с другой – потребителем продукции, выпускаемой другими отраслями. Возникает задача расчета связи между отраслями через выпуск и потребление продукции разного вида. Впервые эта проблема была сформулирована в виде математической модели в 1936 году в трудах известного американского экономиста В. В. Леонтьева, который попытался проанализировать причины экономической депрессии США в 1929–1932 годах. Эта модель основана на алгебре матриц и использует аппарат матричного анализа. Предположим, что рассматривается n отраслей производства, каждая из которых производит свою продукцию. Часть продукции идет на внутрипроизводственное потребление данной отраслью и другими отраслями, а другая часть предназначена для целей конечного (вне сферы материального производства) личного и общественного потребления. Обычно процесс производства рассматривается за некоторый период времени, в ряде случаев такой единицей служит год. Введем следующие обозначения: – общий (валовый) объем продукции i-й отрасли; – объем продукции i-й отрасли, потребляемой j-й отраслью в процессе производства (i, j = 1, 2, …,n); () – матрица потоков средств производства; – объем конечной продукции i-й отрасли, предназначенный для реализации (потребления) в непроизводственной сфере. Так как валовый объем продукции любой i-й отрасли равен суммарному объему продукции, потребляемой n отраслями, и конечного продукта, то , (i = 1, 2, …, n). (2.2) Уравнения (2.2) называются соотношениями баланса. Поскольку продукция разных отраслей имеет разные измерения, будем в дальнейшем иметь в виду стоимостный межотраслевой баланс, когда все величины, входящие в (2.2), имеют стоимостное выражение. Введем коэффициенты прямых затрат , (i, j = 1, 2, …,n), (2.3) показывающие затраты продукции i-й отрасли на производство единицы продукции j-й отрасли. Коэффициенты в течение длительного времени меняются очень слабо и могут рассматриваться как постоянные числа. Это явление становится понятным в свете того, что технология производства остается на одном и том же уровне довольно длительное время, и, следовательно, объем потребления j-й отраслью продукции i-й отрасли при производстве своей продукции объема есть технологическая константа. При таком допущении технология производства принимается линейной, а само допущение называется гипотезой линейности. Согласно гипотезе линейности, имеем , (i, j = 1, 2, …,n). (2.4) С учетом (2.4) соотношения баланса (2.2) примут вид: , (i = 1, 2, …, n)., (2.5) или . (2.6) Введем в рассмотрение векторы-столбцы объемов произведенной продукции (вектор валового выпуска), объемов продукции конечного потребления (вектор конечного потребления) и матрицу коэффициентов прямых затрат: . (2.7) Тогда систему (2.5) можно записать в матричном виде: . (2.8) Обычно это соотношение называют уравнением линейного межотраслевого баланса. Вместе с описанием матричного представления (2.7) это уравнение носит название модели Леонтьева. Уравнение межотраслевого баланса можно использовать в двух целях. В первом, наиболее простом случае, когда известен вектор валового выпуска , требуется рассчитать вектор конечного потребления . Однако в большинстве случаев для целей планирования основная задача состоит в отыскании такого вектора валового выпуска , который при известной матрице прямых затрат A обеспечивает заданный вектор конечного продукта . Перепишем систему (2.8) с использованием единичной матрицы E в виде . (2.9) Если матрица (E – A) невырожденная, т. е. |E – A| 0, то существует обратная матрица и единственное решение уравнения (2.9): . (2.10) Матрица называется матрицей полных затрат. Чтобы выяснить экономический смысл элементов матрицы , будем задаваться единичными векторами конечного продукта , , …, . Тогда по (2.6) соответствующие векторы валового выпуска будут , , …, . Следовательно, каждый элемент матрицы есть величина валового выпуска продукции i-й отрасли, необходимого для обеспечения выпуска единицы конечного продукта j-й отрасли: = 1, (j = 1, 2, …, n). В соответствии с экономическим смыслом задачи значения должны быть неотрицательными при неотрицательных значениях и , где i, j =1, 2, …, n. Матрица называется продуктивной, если для любого вектора существует решение уравнения (2.16). В этом случае и модель Леонтьева называется продуктивной. С другой стороны, для того, чтобы при модель Леонтьева была продуктивной, необходимо и достаточно, чтобы элементы матрицы были неотрицательными (). Если это условие будет выполняться, то и произведение, стоящее в правой части (2.10), будет также неотрицательным при . при заданной матрице потребления A с наибольшим собственным значением основной математический результат формулируется следующим образом: матрица неотрицательна тогда и только тогда, когда < 1. В этом случае экономическая система может производить продукцию в любом сочетании: при таких собственных значениях (< 1) производство всегда превосходит потребление. Можно показать, что матрица A будет продуктивной (< 1), если максимум сумм элементов ее столбцов не превосходит единицы, причем хотя бы для одного из столбцов сумма элементов строго меньше единицы, т. е. матрица A продуктивна (и модель Леонтьева продуктивна), если для любых i, j = 1, 2, …, n, и существует номер j такой, что . Рассмотрим применение модели Леонтьева на примерах. Пример 1. В таблице 2.4 взаимодействие двух отраслей – энергетики и машиностроения – определяется матрицей прямых затрат (процесс производства рассматривается за определенный период) Таблица 2.4 Отрасль Прямые затраты Конечный продукт, усл. ден. ед. Энергетика Машиностроение Энергетика 0,07 0,21 72 Машиностроение 0,12 0,15 63 Известны также объемы продуктов конечного потребления. Вычислить: 1) необходимый объем валового выпуска каждой отрасли, если конечное потребление энергетической отрасли увеличится вдвое, а машиностроения сохранится на прежнем уровне; 2) составить матрицу потоков средств производства . Решение. 1. Матрица A имеет неотрицательные элементы и удовлетворяет критерию продуктивности (при любом j сумма элементов столбца ), т. е. . Поэтому для любого вектора конечного продукта можно найти необходимый вектор валового выпуска по формуле (2.10): . Найдем матрицу полных затрат : . Определитель матрицы равен . Следовательно,. По условию вектор конечного продукта . Тогда по формуле (2.10) получаем вектор валового выпуска: , т. е. валовый выпуск в энергетической отрасли надо увеличить до 169,8 у. е., а в машиностроительной – до 116,1 у. е. 2. Элементы матрицы потоков средств производства вычислим по формуле : = 0,07∙169,8 ≈ 11,9 (у. е.), = 0,21∙116,1 ≈ 24,4 (у. е.), = 0,12∙169,8 ≈ 20,4 (у. е.), = 0,15∙116,1 ≈ 17,4 (у. е.). Матрица потоков средств производства: . Пример 2. В табл. 2.5 приведены данные баланса трех отраслей промышленности за некоторый период времени. Требуется найти объем валового выпуска каждого вида продукции, если конечное потребление по отраслям увеличить соответственно на 20, 10 и 20 условных денежных единиц. Таблица 2.5 Отрасль Потребление Конечный продукт Валовый продукт 1 2 3 Производство 1 Добыча и переработка углеводородов 5 35 20 40 100 2 Энергетика 10 10 20 60 100 3 Машиностроение 20 10 10 10 50 Решение. Имеем = 100, = 100, =50; = 5, =35, = 20, 10, 10, 20, 20, 10, 10; 40, 60, 10. По формуле (2.3) находим коэффициенты прямых затрат: , , , , , , , , . Следовательно, матрица прямых затрат равна . Матрица A удовлетворяет всем критериям продуктивности: , и существует номер j (j = 1, 2) такой, что < 1. Выпишем векторы валового выпуска и конечного потребления: и . В случае заданного увеличения конечного потребления новый вектор конечного продукта будет иметь вид . Требуется найти новый вектор валового выпуска , удовлетворяющий соотношениям баланса в предположении, что матрица A не изменится. По формуле (2.9) имеем , (2.11) где матрица имеет вид . Подставляя в (2.11) найденную матрицу и значения нового вектора конечного продукта , получим: . Решение полученной системы линейных уравнений можно осуществить любым методом, в том числе и методом Гаусса. В результате решения получим . Таким образом, для того, чтобы обеспечить заданное увеличение компонент вектора конечного продукта, необходимо увеличить соответствующие валовые выпуски: добычу и переработку углеводородов – на 52,2 %, уровень энергетики – на 35,8 % и выпуск продукции машиностроения – на 85 % (т. к. ∙100 % = 185 %) по сравнению с исходными величинами, указанными в табл. 2.5. В заключение отметим, что основная цель, которую поставил Леонтьев, состояла в том, чтобы найти модель, использующую данные реальной экономики. Официальная американская статистика в 1958 году содержала в матричной таблице межотраслевых связей данные по 83 отраслям производства. Построенная экономическая теория Леонтьева выходит за рамки простого исследования матрицы и позволяет решать вопросы о естественных ценах рынка и об оптимизации. Трудовые ресурсы при этом рассматриваются отдельно как наиболее важный товар, количество которого ограничено и должно быть минимизировано. Часть 3. Линейное программирование 3.1. Введение в линейное программирование Линейное программирование (ЛП) – наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений. В общем виде математическая модель задачи линейного программирования (ЗЛП) записывается как при ограничениях: где – неизвестные; – заданные постоянные величины. Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств. Чтобы составить математическую модель задачи ЛП, необходимо: • ввести обозначения переменных; • учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений; • исходя из цели экономических исследований, составить целевую функцию. 3.2. Формулировка основных типов задач ЛП, построение их математических моделей Задачи, решаемые методами ЛП, очень разнообразны по содержанию. Но их математические модели схожи и условно объединяются в три большие группы задач: • транспортные задачи; • задачи о составлении плана; • задачи о смеси (о диете). Транспортная задача Задача 1. На двух торговых базах А и В имеется 30 гарнитуров мебели, по 15 на каждой. Всю мебель требуется доставить в два мебельных магазина, С и Д причем в С надо доставить 10 гарнитуров, а в Д – 20. Известно, что доставка одного гарнитура с базы А в магазин С обходится в одну денежную единицу, в магазин Д – в три денежных единицы. Соответственно с базы В в магазины С и Д: две и пять денежных единиц. Составить план перевозок так, чтобы стоимость всех перевозок была наименьшей. Данные задачи для удобства разметим в таблице. На пересечении строк и столбцов стоят числа, характеризующие стоимость соответствующих перевозок (табл. 3.1). Таблица 3.1 магазины базы С Д отправлено гарнитуров А 1 3 15 В 2 5 15 получено гарнитуров 10 20 30 30 Составим математическую модель задачи. Необходимо ввести переменные. В формулировке вопроса говорится, что необходимо составить план перевозок. Обозначим через х1, х2 количество гарнитуров, перевозимых с базы А в магазины С и Д соответственно, а через у1, у2 – количество гарнитуров, перевозимых с базы В в магазины С и Д соответственно. Тогда количество мебели, вывозимое со склада А, равно (х1 + х2), а со склада В – (у1  +  у2). Потребность магазина С равна 10 гарнитурам, и в него привезли (х1  +  у1) штук, т. е. х1  +  у1  =  10. Аналогично, для магазина Д имеем х2  +  у2  =  20. Заметим, что потребности магазинов в точности равны количеству гарнитуров, имеющихся на складах, поэтому х1 + у2  =  15 и у1  + у2  =  15. Если бы со складов вы увезли меньше, чем по 15 комплектов, то магазинам не хватило бы мебели для удовлетворения их потребностей. Итак, переменные х1, х2, у1, у2 по смыслу задачи неотрицательны и удовлетворяют системе ограничений: (3.1) Обозначив через F транспортные расходы, посчитаем их. на перевозку одного комплекта мебели из А в С тратится одна ден. ед., на перевозку x1 комплектов – x1 ден. ед. Аналогично, на перевозку x2 комплектов из А в Д затратится 3x2 ден. ед.; из В в С – 2y1 ден. ед., из В в Д – 5y2 ден. ед.: F = 1x1 + 3x2 + 2y1 + 5y2 → min (3.2) На множестве решений системы ограничений (3.1) найти такое решение, которое обращает в минимум целевую функцию F (3.2), или найти оптимальный план (x1, x2, y1, y2), определяемый системой ограничений (3.1) и целевой функцией (3.2). В рассмотренной задаче наличие груза у поставщиков (15 + 15) равно общей потребности потребителей (10 + 20). Такая модель называется закрытой, а соответствующая задача – сбалансированной транспортной задачей. В экономических расчетах встречаются открытые модели, в которых указанное равенство не соблюдается. Либо запас у поставщиков больше потребности у потребителей, либо спрос превышает наличие товара. заметим, что тогда в систему ограничений несбалансированной транспортной задачи наряду с уравнениями будут входить и неравенства. Задача 2. В пунктах А и В расположены кирпичные заводы, а в С и Д – карьеры, снабжающие их песком. потребность заводов в песке меньше, чем производительность карьеров. Известно, сколько песка нужно каждому из заводов и сколько добывается в каждом карьере. Также известна стоимость перевозки 1 т песка из каждого карьера к заводам (числа на стрелочках). Нужно так спланировать снабжение заводов песком, чтобы затраты на перевозку были наименьшими. Данные задачи на схеме. Постоим математическую модель задачи. Введем переменные: x11 – количество тонн песка, перевозимого с карьера С на завод А; x12 – с карьера С на завод А; x21 – количество тонн песка в А с карьера Д; x22 – количество тонн песка с карьера Д на завод В. На завод А должно быть доставлено 40 т с обоих карьеров, значит x11 + x21 = 40, на завод В должно быть доставлено 50 т, значит x12 + x22 = 50. Из карьера С вывезено не более 70 т, т. е. x11 + x12 ≤ 70, аналогично x21 + x22 ≤ 30. Имеем систему ограничений: (3.3) Целевая функция F, выражающая стоимость перевозок, имеет вид F = 2x11 + 6x12 + 5x21 + 3x22→min. (3.4) Задача о составлении плана. Задача 3. Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. – за изделие II вида. Составить план выпуска этих изделий так, чтобы от реализации их завод получил наибольшую прибыль. В таблице указано время, необходимое для обработки каждого из двух видов изделий на оборудовании всех четырех видов (табл. 3.2). Таблица 3.2 Изделия Виды машин 1 2 3 4 I 1 0,5 1 II 1 1 1 Возможное время работы машин 18 12 12 9 В задаче необходимо определить план выпуска изделий, обозначим за x количество изделий I вида, за y – количество изделий II вида. Тогда посчитаем, сколько времени затратит первая машина на обработку всех производственных изделий. Она тратит одну единицу времени на одного изделие I вида, значит на x штук изделий потратит 1x ед. времени, на обработку y изделий II вида затратится 1y ед. времени. Всего резерв времени работы первой машины – 18 единиц времени. Значит, x + y ≤ 18. Аналогичные рассуждения со второй машиной, третьей и четвертой дадут систему ограничений: (3.5) Общая прибыль будет выражена в целевой функции: F = 4x + 6y → max. (3.6) Задача состоит в нахождении на множестве решений системы (3.5) такого решения, при котором значение целевой функции (3.6) было бы максимальным. Задача составления смеси. Примером таких задач может быть задача о составлении таких смесей нефтепродуктов, которые бы удовлетворяли определенным техническим требованиям и были наиболее дешевыми по стоимости. Либо задачи о рационе, когда известна потребность в определенных веществах и содержание этих веществ в различных продуктах. Необходимо составить рацион так, чтобы удовлетворить потребности в необходимых веществах и при этом продуктовая корзина имела бы минимальную стоимость при заданных ценах на продукты. Задача 4. Для откорма цыплят на птицефабрике в их рацион необходимо включать не менее 33 единиц вещества А, 23 единиц питательного вещества В, 12 единиц С. Для откорма используются три вида корма. Данные о содержании питательных веществ в каждом виде корма заданы таблицей. Также известна стоимость кормов. Необходимо составить наиболее дешевый рацион (табл. 3.3). Таблица 3.3 Корма-продукты Вещества Стоимость 1 ед. корма А В С I 4 3 1 20 II 3 2 1 20 III 2 1 2 10 Вещества А, В, С – это жиры, белки, углеводы, а продукты I, II, III –корм цыплят, например пшено, комбикорм, витаминные добавки. Тогда первая строка таблицы показывает содержание в одной единице пшена: 4 ед. белка, 3 ед. жиров, одной ед. углеводов. Вторая строка – содержание белков, жиров, углеводов в 1 ед. II продукта и т. д. В качестве ответа на поставленную задачу необходимо разработать рацион, т. е. указать сколько и каких кормов взять, чтобы необходимое количество питательных веществ было соблюдено и при этом он стоил как можно дешевле. Обозначим за x1 количество кормов типа I в рационе, за x2 – количество кормов типа II и, соответственно, x3 – количество корма III в рационе. Тогда, вещества А при употреблении такого рациона цыплята получат 4x1 – при потреблении продуктов типа I, 3x2 – при потреблении II продукта, 2x3 – при потреблении III. Всего вещества А необходимо употребить по условию задачи не менее 33 единиц, следовательно 4x1 + 3x2 + 2x3 ≥ 33. Аналогично с веществами В и С: 3x1 + 2x2 + 1x3 ≥ 23 и x1 + x2 + 2x3 ≥ 12. Таким образом, получим систему ограничений: (3.7) Переменные неотрицательны по смыслу задачи. При этом стоимость рациона выражается функцией: F = 20x1 + 20x2 + 10x3 → min, (3.8) т. к. 20, 20, 10 – стоимость одной ед. продуктов I, II, III типов соответственно, а в рационе их содержится x1, x2, x3 единиц. 3.3. Графический способ решения задач ЛП Решение систем линейных неравенств графически. Если в задаче ЛП неизвестных всего два, как, к примеру, в задаче 3, то ее можно решить графически. Система ограничений такой задачи состоит из неравенств от двух переменных: и целевая функция имеет вид F = C1x + C2y, которую необходимо максимизировать. Рассмотрим два неравенства: ax + by ≤  c, ax + by ≥  c. Прямая ax  + by = c делит плоскость на две полуплоскости так, что координаты точек одной из них удовлетворяют неравенству ax + by > c, а другой неравенству ax + + by < c. Пусть для определенности a < 0, b > 0, c > 0. Все точки с абсциссой x0, лежащие выше P (например, точка М), имеют yM > y0, а все точки, лежащие ниже точки P, с абсциссой x0, имеют yN < y0. Поскольку x0 – произвольная точка, то всегда с одной стороны от прямой будут находиться точки, для которых ax + by > c, образующие полуплоскость, а с другой стороны – точки, для которых ax + by < c. Знак неравенства в полуплоскости зависит от чисел a, b, c. Для решения графического системы линейных неравенств от двух переменных необходимо: 1. Для каждого неравенства выписать уравнение, соответствующее данному неравенству. 2. Построить прямые, являющиеся графиками функций, задаваемых уравнениями. 3. Для каждой прямой определить полуплоскость, которая задается неравенством. Для этого взять произвольную точку, не лежащую на прямой, подставить ее координаты в неравенство. если неравенство верное, то полуплоскость, содержащая выбранную точку, и является решением исходного неравенства. Если неравенство неверное, то полуплоскость по другую сторону прямой является множеством решений данного неравенства. 4. Чтобы решить систему неравенств, необходимо найти область пересечения всех полуплоскостей, являющихся решением каждого неравенства системы. Эта область может оказаться пустой (рис. 3.2) тогда система неравенств не имеет решений, несовместна. В противном случае говорят, что система совместна. Решений может быть конечное число, если область представляет собой замкнутый многоугольник (рис. 3.3), и бесконечное множество, если область неограниченна (рис. 3.4). Рис.3.2. Рис. 3.3. Рис. 3.4. Решение задачи ЛП графически Задача ЛП состоит из ограничений, являющихся системой неравенств, и целевой функции. Определение. Любое решение системы ограничений называется допустимым решением ЗЛП. Определение. Допустимое решение, в котором целевая функция достигает максимального или минимального значения, называется оптимальным решением. В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с1x + с2y. Переменные x, y в ЗЛП принимают, как правило, неотрицательные значения (x ≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости. Рассмотрим линейную функцию F = с1x + с2y и зафиксируем ее значение F. пусть, к примеру, F  = 0, т. е. с1x + с2y = 0. графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис. 3.5). Рис. 3.5 При изменении фиксированного значения F = d, прямая с1x + с2y = d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с1x + с2y = d, при некотором значении d = d1 достигнет многоугольника D, назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении d = d2 будем иметь с ним последнюю общую точку В, назовем В «точкой выхода». Наименьшего и наибольшего значения целевая функция F = с1x + с2y достигнет в точках «входа» А и «выхода» В. Оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D. Таким образом, план решения ЗЛП: • построить область решений системы ограничений; • построить прямую, соответствующую целевой функции, и параллельным переносом этой прямой найти точку «входа» или «выхода» (в зависимости от требования минимизировать или максимизировать целевую функцию); • определить координаты этой точки, вычислить в них значение целевой функции. Вектор (с1, с2), перпендикулярный прямой, показывает направление роста целевой функции. При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения. Случай 1. При перемещении прямой с1x + + с2y = d «вход» или «выход» (рис. 3.6) произойдет по стороне многоугольника. В этом случае точек «выхода» («входа») бесчисленное множество, а именно – любая точка отрезка АВ, т.е. целевая функция принимает максимальное (минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D. Случай 2 Если область допустимых значений неограниченна (рис. 3.7), то целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена. Рис. 3.6 Рис. 3.7 3.4. Каноническая форма задач ЛП Одним из универсальных методов решения ЗЛП является симплексный метод, который используется, если задача ЛП имеет каноническую форму. Определение. Задача ЛП имеет каноническую форму, если все ограничения системы состоят только из уравнений (кроме неравенств, выражающих неотрицательность переменных) и целевую функцию необходимо минимизировать. В большинстве экономических задач чаще всего в систему ограничений первоначально входят не только уравнения, а и неравенства. Приведение общей задачи ЛП к канонической форме достигается путем введения новых (дополнительных) переменных. Система ограничений (3.3) состоит из четырех неравенств. Введя дополнительные переменные y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, перейдем к системе ограничений: (3.9) Дополнительные переменные yi имеют экономический смысл, а именно означают величину неиспользованного ресурса. Рассмотрим задачу о смеси. Система ограничений (3.7) имела вид: Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y1, y2, y3 ≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме: Переменные yi также будут иметь экономический смысл, переменная y1 будет означать количество излишнего вещества А в смеси, y2 – количество излишков вещества В в смеси, y3 – излишки С в смеси. Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (–F). Вывод. Для представления задачи ЛП в канонической форме необходимо: • неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных; • если целевая функция F →max (максимизируется), она заменяется на функцию –F → min (которая минимизируется). 3.5. Симплексный метод решения задач линейного программирования При графическом методе решения задач ЛП из множества вершин, принадлежащих границе множества решений системы неравенств, необходимо выбрать такую вершину, в которой значение целевой функции достигало максимума (минимума). В случае двух переменных этот метод совершенно нагляден и позволяет быстро находить решение задачи. Если в задаче три и более переменных, то трудно представить наглядно область решений системы ограничений. Такие задачи решаются с помощью симплекс-метода или методом последовательных улучшений. По определенному правилу находится первоначальный опорный план (некоторая вершина области ограничений). Проверяется, является ли план оптимальным. Если да, то задача решена. Если нет, то переходим к другому улучшенному плану – к другой вершине. значение целевой функции на этом плане (в этой вершине) заведомо лучше, чем в предыдущей. Алгоритм перехода осуществляется с помощью вычислительного шага, который удобно записывать в виде таблиц, называемых симплекс-таблицами. Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению. Рассмотрим симплексный метод на конкретном примере задачи о составлении плана. Задача. Для изготовления изделий А и В склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А расходуется две единицы, а изделия В – одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А требуется изготовить не более 50 шт., а изделий В – не более 40 шт. Причем, прибыль от реализации одного изделия А – 5 руб., а от В – 3 руб. Построим математическую модель, обозначив за х1 количество изделий А в плане, за х2 – количество изделий В. тогда система ограничений будет выглядеть следующим образом: Приведем задачу к каноническому виду, введя дополнительные переменные: (3.10) . Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом. I этап. Запись задачи в симплекс-таблицу. Между системой ограничений задачи (3.10) и симплекс-таблицей взаимно-однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений, а столбцов – столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные – верхнюю строку таблицы. Нижняя строка называется индексной, в ней записываются коэффициенты при переменных в целевой функции. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена; если есть, то записываем его с противоположным знаком. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблицы к другой должно увеличиваться по модулю. Итак, нашей системе ограничений соответствует таблица 3.4, и можно переходить ко II этапу решения. Таблица 3.4 базисные –х1 –х2 свободные х3 х4 х5 1 2 1 1 50 40 80 –F –5 –3 II этап. Проверка опорного плана на оптимальность. Таблице 3.4 соответствует опорный план: (х1, х2, х3, х4, х5) = (0, 0, 50, 40, 80). Свободные переменные х1, х2 равны 0; х1 = 0, х2 = 0. А базисные переменные х3, х4, х5 принимают значения х3 = 50, х4 = 40, х5 = 80 – из столбца свободных членов. Значение целевой функции: –F = – 5х1 – 3х2 = –5 · 0 – 3 · 0 = 0. Проверяем является ли данный опорный план оптимальным. для этого необходимо просмотреть индексную строку – строку целевой функции F. Возможны различные ситуации. 1. В индексной F-строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятому с противоположным знаком. Переходим к IV этапу. 2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция F→∞ неограниченно убывает. 3. В индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к следующему III этапу. пересчитываем таблицу, улучшая опорный план. III этап. Улучшение опорного плана. Из отрицательных элементов индексной F-строки выберем наибольший по модулю, назовем соответствующий ему столбец разрешающим и пометим «↑». Чтобы выбрать разрешающую строку, необходимо вычислить отношения элементов столбца свободных членов только к положительным элементам разрешающего столбца. Выбрать из полученных отношений минимальное. Соответствующий элемент, на котором достигается минимум, называется разрешающим. Будем выделять его квадратом. В примере, , элемент 2 – разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5). Таблица 3.5 базисные –х1 –х2 свободные х3 х4 х5 1 2 1 1 50 40 80 -F –5 –3 Выбрав разрешающий элемент, делаем перечет таблицы по правилам: 1. В новой таблице таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В нашем примере: х1 входит в базис, вместо х5, которая выходит из базиса и теперь свободная (табл. 3.6). Таблица 3.6 базисные -х5 -х2 свободные х3 х4 х1 40 –F 2. На месте разрешающего элемента 2 записываем обратное ему число . 3. Элементы разрешающей строки делим на разрешающий элемент. 4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком. 5. Чтобы заполнить оставшиеся элементы таблицы 3.6, осуществляем пересчет по правилу прямоугольника. Пусть мы хотим посчитать элемент, стоящий на месте 50. Соединяем этот элемент мысленно с разрешающим, находим произведение, вычитаем произведение элементов, находящихся на другой диагонали получившегося прямоугольника. Разность делим на разрешающий элемент. Итак, . Записываем 10 на место, где было 50. Аналогично: , , , . Таблица 3.7 базисные –х5 –х2 свободные х3 10 х4 1 40 х1 40 –F 200 В таблице 3.7 базисными переменными являются переменные . Значение целевой функции уменьшилось и равно –200. Проверяем базисное решение на оптимальность, т.е.переходим ко II этапу. Процесс конечен, критерием остановки являются пункт 1 и 2 II этапа. Проверим индексную строку и, увидев в ней отрицательный элемент , назовем соответствующий ему столбец разрешающим и, согласно III этапу, пересчитаем таблицу. Составив отношения и выбрав среди них минимальное  = 40, определили разрешающий элемент 1. Пересчет осуществляем согласно правилам 2–5. Таблица 3.8 базисные –х5 –х4 свободные х3 30 х2 1 40 х1 20 –F 220 Поскольку в индексной строке нет отрицательных элементов, то задача решена, базисный план оптимален. IVэтап. Выписывание оптимального решения. Если симплекс-метод остановился согласно пункту 1 II этапа, то решение задачи выписывается следующим образом. Базисные переменные принимают значения столбца свободных членов соответственно. В нашем примере х3 = 30, х2  = 40, х1 = 20. Свободные переменные равны 0, х5 = 0, х4 = 0. Целевая функция принимает значение последнего элемента столбца свободных членов с противоположным знаком: –F = –220 F = 220, в нашем примере функция исследовалась на min, и первоначально F max, поэтому фактически знак поменялся дважды. Итак, х* = (20, 40, 30, 0, 0), F* = 220. Ответ: необходимо в план выпуска включить 20 изделий типа А, 40 изделий типа В, при этом прибыль будет максимальной и будет равна 220 руб. 3.6. Поиск первоначального опорного плана Предположим, что каноническая задача ЛП имеет отрицательные правые части уравнений системы ограничений, как например в задаче о рационе. F = 20х1 + 20х2 + 10х3 min. Запишем задачу в симплекс-таблицу (табл. 3.9). Таблица 3.9 базисные –х1 –х2 –х3 свободные х4 –4 –3 –2 –33 х5 –3 –2 –1 –23 х6 –1 –1 –2 –12 F 20 20 10 Базисное решение, соответствующее базису и равное (0; 0; 0; –33; 23; –12), не является допустимым ввиду отрицательности х4 < 0, x5 < 0, x6 < 0. Правило нахождения допустимого опорного плана: если в столбце свободных членов есть отрицательные элементы, выберите из них наибольший по модулю, а в его строке – любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитайте таблицу по прежним правилам 2–5. Если в полученной таблице все элементы столбца свободных членов стали положительны либо 0, то данное базисное решение можно взять в качестве первоначального опорного плана. Далее симплекс-методом решаем задачу. Если в столбце свободных членов не все элементы неотрицательны, то еще раз воспользоваться этим правилом. В задаче о рационе в качестве разрешающей строки табл. 3.9 выбраем первую. А разрешающим элементом выберем, к примеру, элемент –4. Таблица 3.10 базисные –х4 –х2 –х3 свободные х1 х5 х6 F 5 5 165 Переменная х1 вошла в базис вместо х4, все вычисления осуществлялись по правилу 2–5. В правом столбце еще остался отрицательный элемент, воспользуемся правилом еще раз. Строка переменной х6 – разрешающая, а в качестве разрешающего элемента возьмем, к примеру, , здесь есть некоторая возможность выбора. Таблица 3.11 базисные –х4 –х2 –х6 свободные х1 7 х5 х3 F 5 5 165 Полученный базисный план х* = (х1, х2, х3, х4, х5, х6) = (7, 0, , 0, , 0) является допустимым и, к тому же, оказывается оптимальным, т. к. в индексной строке нет отрицательных элементов. Оптимальное значение целевой функции равно F* = 165. Действительно, F = 20х1 + 20х2 + 10х3 = 20 · 7 + 0 + 10· = 140 + 25 = 165. 3.7. Решение задачи о плане симплекс-методом Задача. Предприятие располагает тремя видами сырья и намеревается выпускать четыре вида продукции. Коэффициенты в таблице 3.12 указывают затраты соответствующего вида сырья на единицу определенного вида продукции, а также прибыль от реализации единицы продукции и общие запасы ресурсов. Задача: найти оптимальный план производства продукции, при котором будет обеспечена максимальная прибыль. Таблица 3.12 Виды продукции Виды сырья I II III IV Запасы ресурсов 1 5 0,4 2 0,5 400 2 5 1 1 300 3 1 1 1 600 Прибыль 3 5 4 5 Математическую модель: х1, х2, х3, х4 – количество продукции I, II, III, IV вида соответственно в плане. Количество используемого сырья и его запасы выразятся в неравенствах: F = 3x1 + 5x2 + 4x3 + 5x4 max. Целевая функция выражает собой общую суммарную прибыль, полученную от реализации всей плановой продукции, а каждое из неравенств выражает затраты определенного вида продукции. Затраты не должны превышать запасов сырья. Приведем задачу к канонической форме и к специальному виду, введя дополнительные переменные х5, х6, х7 в каждое из неравенств. Если первого ресурса необходимо для производства плановой продукции 5х1 + 0,4х2 + 2х3 + 0,5х4, то х5 обозначает просто излишки первого ресурса как разность между имеющимся запасом и требуемым для производства. Аналогично х6 и х7. Итак, дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. Запишем задачу в таблицу 3.13, предварительно выписав ее каноническую форму: I этап. Это задача специального вида, базис составляют переменные , правые части уравнений неотрицательны, план х = (0, 0, 0, 0, 400, 300, 100) – опорный. Он соответствует симплекс-таблице. Таблица 3.13 II этап. Проверим план на оптимальность. Так как в индексной F-строке есть отрицательные элементы, то план неоптимален, переходим к III этапу. III этап. Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, но могли бы выбрать и второй, т. к. в обоих (–5). Остановившись на четвертом, выберем в качестве разрешающего элемента 1, т. к. именно на нем достигается минимум соотношений . С разрешающим элементом 1 проводим преобразование таблицы по правилам 2–5 (табл. 3.14). Таблица 3.14 Полученный план опять неоптимален, т. к. в F-строке есть отрицательный элемент –5. этот столбец разрешающий. В качестве разрешающего элемента выбираем 5, т. к. . Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т. к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять «внутренность» таблицы (табл. 3.15). Таблица 3.15 базисные –х1 –х6 –х3 –х7 свободные х5 334 х2 40 х4 100 –F 1 1 1 4 700 План оптимален, т. к. в индексной строке нет отрицательных элементов, выписываем его. IV этап. Базисные переменные принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план х*=(0,40,0,100,334,0,0) и F*=700. Действительно, F  =3х1 +4х3 +5х2 +5х4 =5·40+5·100=700. Т. е. для получения максимальной прибыли в 700 руб. предприятие должно выпускать изделия II вида в количестве 40 штук, IV – вида в количестве 100 штук, изделия I и III вида производить невыгодно. При этом сырье второго и третьего вида будет израсходовано полностью, а сырья первого вида останется 334 единицы (х5  =  334, х6 = 0, х7 = 0). 3.8. Двойственность в линейном программировании Основные определения теории двойственности. Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования. При решении одной из них автоматически решается и другая задача. Такие задачи называют взаимодвойственными. Рассмотрим задачу о планируемом выпуске продукции. F = 3х1 + 5х2 + 4х3 + 5х4 → max. Построим двойственную ей задачу по следующим правилам. 1. Количество переменных в двойственной задаче равно количеству неравенств в исходной. 2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной. 3. Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется. 4. Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной. Исходная задача I. Двойственная задача II. F = 3x1 + 5x2 + 4x3 + 5x4 → max. G = 400y1 + 300y2 + 100y3 → min. Заметим, что строки матрицы задачи I являются столбцами матрицы задачи II. Поэтому коэффициенты при переменных yi в задаче II – это, соответственно, коэффициенты i-го неравенства в задаче I. Неравенства, соединенные стрелочками, будем называть сопряженными. Теоремы двойственности. Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности. Теорема 1 (первая теорема двойственности). Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*) = G(y*), где х*, у* – оптимальные решения задач I и II Теорема 2 (вторая теорема двойственности). Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство. Доказательства теорем опускаем, а на конкретном примере посмотрим связь в паре двойственных задач. Итак, имеем исходную задачу I, которую мы решили в п. 3.8, и ее оптимальное решение х* = (0, 40, 0, 100) и F(х*) = 700. Найдем решение двойственной задачи II у* = (у1, у2, у3), воспользовавшись второй теоремой двойственности и известным оптимальным планом х*. Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений. <, т. к. 5 · 0 + 0,4 · 40 + 2 · 0 + 0,5 · 100 = 66 < 400; =, т. к. 5 · 40 + 1 · 0 + 100 = 300; =, т. к. 0 + 0 + 100 = 100; =, т. к. х1 = 0; >, т. к. х2 = 40 > 0; =, т. к. х3 = 0; >, т. к. х4 = 100 > 0. Поскольку 1, 5, 7 неравенства строгие (имеют знак «<» или «>»), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем: или т. е. у* = (0, 1, 4) – оптимальное решение. Заметим, что G(y*) = 400y1 + 300y2 + 100y3 = 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*). В силу второй теоремы двойственности оптимальное решение задачи II найдено с использованием условия обращения в равенство хотя бы одного из пары сопряженных неравенств в системах ограничений двойственных задач. Между переменными исходной задачи и переменными двойственной существует связь. А именно: после приведения обеих задач I и II к каноническому виду основные и дополнительные переменные задач соответствуют друг другу следующим образом: Установив такую связь и решив задачу I симплекс-методом, т.е. получив последнюю симплекс-таблицу (табл. 3.15), фактически решаем задачу II. Запишем таблицу 3.15, учитывая соответствие между переменными хi и yj (табл. 3.16). Таблица 3.16 у4 у2 у6 у3 базисные –х1 –х6 –х3 –х7 свободные у1 х5 334 у5 х2 40 у7 х4 100 –F 1 1 1 4 700 В силу соответствия и II теоремы двойственности переменные у1, у5, у7 обязаны равняться 0, т. к. х5, х2, х4>0 строго. А переменные у4, у2, у6, у3 принимают значения из индексной строки 1, 1, 1, 4 соответственно, т. к. им соответствующие переменные х1, х6, х3, х7 = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных: у* = (у1*, у2*, у3*, у4*, у5*, у6*, у7*) = (0, 1, 4, 1, 0, 1, 0). Экономическая интерпретация двойственной задачи и теории двойственности Исходная задача I имела экономический смысл: основные переменные хi обозначали количество произведенной продукции i-го вида, дополнительные переменные обозначали количество излишков соответствующего вида ресурсов, каждое из неравенств выражало собой расход определенного вида сырья в сравнении с запасом этого сырья. Целевая функция определяла прибыль при реализации всей продукции. Предположим теперь, что предприятие имеет возможность реализовывать сырье на сторону. Какую минимальную цену надо установить за единицу каждого вида сырья при условии, чтобы доход от реализации всех его запасов был не меньше дохода от реализации продукции, которая может быть выпущена из этого сырья. Переменные у1, у2, у3 будут обозначать условную предполагаемую цену за ресурс 1, 2, 3 вида соответственно. Тогда доход от продажи видов сырья, расходуемых на производство одной единицы продукции I, равен: 5у1 + 1· у3. Т. к. цена продукции I типа равна 3 ед., то 5у1 + у3 3, в силу того, что интересы предприятия требуют, чтобы доход от продажи сырья был не меньше, чем от реализации продукции. Именно в силу такого экономического толкования система ограничений двойственной задачи принимает вид: Целевая функция G = 400y1 + 300y2 + 100y3 подсчитывает условную суммарную стоимость всего имеющегося сырья. В силу I теоремы двойственности F(x*) = G(y*) равенство означает, что максимальная прибыль от продажи всей готовой продукции совпадает с минимальной условной ценой ресурсов. Условные оптимальные цены уi показывают наименьшую стоимость ресурсов, при которой выгодно обращать эти ресурсы в продукцию, производить. Переменные уi – это условные, а не реальные цены на сырье. Случай у1* = 0 означает лишь, что этот ресурс не израсходован полностью, имеется в излишке, недефицитен. Первое неравенство в системе ограничений задачи I, в котором подсчитывается расход первого ресурса: 5х1* + 0,4х2* + 2х3* + 0,5х4* = 66 < 400. его избыток составляет х5 = 334 ед. при данном оптимальном плане производства. Этот ресурс имеется в избытке, и поэтому для производителя он недефицитен, его условная цена равна 0, его не надо закупать. Наоборот, ресурс 2 и 3 используются полностью, причем у3 = 4 а у2 = 1, т. е. сырье третьего вида более дефицитно, чем второго, его условная цена больше. Если производитель продукции имел бы возможность приобретать дополнительно сырье к уже имеющемуся, с целью получения максимального дохода от производства, то увеличив сырье второго вида на единицу, он бы получил дополнительно доход в у2 денежных единиц, с увеличением на единицу сырья третьего вида, значение целевой функции увеличилось бы еще на у3 единицы. Если перед производителем стоит вопрос, «выгодно ли производить какую-либо продукцию при условии, что затраты на единицу продукции составят 3, 1, 4 единиц 1, 2, 3-го видов сырья соответственно, а прибыль от реализации равна 23 единицам», то в силу экономического истолкования задачи ответом на этот вопрос будет «Если затраты равны 3, 1, 4, а цены у1* = 0, у2* = 1, у3* = 4, то суммарная условная стоимость ресурсов, необходимых для производства этой новой продукции: 3 · 0 + 1 · 1 + 4 · 4 = 17 < 23. Следовательно продукцию производить выгодно, т. к. прибыль от реализации превышает затраты на ресурсы, в противном случае ответ бы на этот вопрос был отрицательным».