Указания методические по изучению дисциплины и выполнению контрольной работы ЭКОНОМИКО – МАТЕМАТИЧЕСКИЕ МЕТОДЫ Методические указания по изучению дисциплины и выполнению контрольной работы Методические указания по изучению дисциплины подготовил к.т.н., проф. кафедры математических методов обработки информации, зав. каф. ММОИ Клетин В.А. Москва, 2007 Экономико-математические методы Введение Экономические проблемы, возникающие перед специалистами, в большинстве своем сложные. Они зависят от множества различных, иногда противоречащих друг другу факторов, изменяются с течением времени и влияют на другие проблемы и процессы. Вследствие этого исследование экономической проблемы целесообразно проводить на адекватной математической модели. Математическая модель отражает проблему в абстрактной форме и позволяет учесть большое число разнообразных характеристик, от которых эта проблема зависит. Анализ и расчет математической модели позволяют выбрать оптимальные решения поставленной задачи и обосновать этот выбор. Впервые математические модели были использованы для решения практической задачи в 30-х годах в Великобритании при создании системы противовоздушной обороны. Для разработки данной системы были привлечены ученые различных специальностей. Система создавалась в условиях неопределенности относительно возможных действий противника, поэтому исследования проводились на адекватных математических моделях. В это время впервые был применен термин: «операционное исследование», подразумевающий исследования военной операции. В последующие годы операционные исследования или исследования операций развиваются как наука, результаты которой применяются для выбора оптимальных решений при управлении реальными процессами и системами. Математические модели, созданные для целей экономики, изучаются специальной научной дисциплиной, получившей название «экономико-математические методы». ЭММ представляют собой своеобразный инструментальный набор, с помощью которого экономисты, бизнесмены, менеджеры, стремясь добиться наилучшего эффекта «обрабатывают» свой материал. Научной основой ЭММ стали методы исследования операций. 1. Основные понятия и определения исследования операций 1.1. Цель и задачи исследования операций Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами (система - это совокупность взаимосвязанных, взаимодействующих элементов (людей, машин ...), выполняющих определенную задачу). Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Т. о., цель исследования - количественное обоснование принимаемых решений по организации управления. При решении конкретной задачи управления применение методов ИО предполагает: - построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности; - изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия. Операция - любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, организации, иначе - от выбора некоторых параметров. Всякий определенный выбор параметров называется решением. Оптимальными считают те решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений. Для применения количественных методов исследования требуется построить математическую модель операции. Составление модели операции требует понимания сущности описываемого явления и знания математического аппарата. 1.2. Модели и моделирование. Одним из основных методов научного познания является эксперимент, а самой распространенной его разновидностью - метод моделирования систем. В процессе создания систем приходится проводить многочисленные исследования, эксперименты и расчеты, связанные с оценкой качества функционирования систем, с выбором лучшего варианта для ее создания. Выполнять их непосредственно на реальной системе очень сложно, иногда занимает много времени и экономически невыгодно. Существуют системы (экономика страны), на которых просто невозможно ставить эксперименты с познавательной целью. Значительно проще и дешевле создать модель системы и проводить на ней эксперименты. Под моделью принято понимать систему, способную замещать оригинал так, что ее изучение дает новую информацию об оригинале. Модель должна частично или полностью воспроизводить структуру моделируемой системы, ее функции. Под моделированием понимается процесс построения и исследования модели, способной заменить реальную систему и дать о ней новую информацию. Модели, используемые на практике, условно можно разделить на два типа: физические и символические. Символические модели описывают структуру и функции оригинала с помощью символов и соотношений между ними, выражающих определенные зависимости, присущие оригиналу. Большое место среди символических моделей занимают математические модели (уравнения, неравенства, функции, алгоритмы и т.д.), отражающие математические или логические зависимости. Математическая модель представляет собой систему математических и логических соотношений, описывающих структуру и функции реальной системы. Математическая модель отличается по своей физической природе от оригинала. Исследование свойств оригинала с помощью математической модели значительно удобнее, дешевле и занимает меньше времени по сравнению с физическим моделированием. Многие математические модели являются универсальными, т.е. могут использоваться для исследования различных систем. Целый ряд систем, в том числе экономических, либо трудно, либо вообще невозможно представить с помощью физических моделей. Существенную роль в развитии математического моделирования сыграли ЭВМ, способные выполнять различные по сложности вычисления и логические операции с большой скоростью. Среди математических моделей важное место занимают ЭММ, представляющие собой математическое описание экономических процессов и явлений. Большинство ЭММ включает в себя систему уравнений и неравенств, состоящих из набора переменных и параметров. Переменные величины характеризуют, например, объем производимой продукции, капитальных вложений, перевозок и т.п., а параметры - нормы расхода сырья, материалов, времени на производство определенной продукции. Практически в каждой модели можно выделить две группы переменных: 1) внешние переменные - их значения определяются вне данной модели и считаются в данной модели заданными; 2) внутренние переменные, значения которых определяются в результате исследования данной модели. ЭММ используются преимущественно для планирования или прогнозирования состояния системы на будущее. Наряду с использованием в предсказательных целях ЭММ применяются для описания реально существовавших или существующих экономических процессов. Выделяют описательные и оптимизационные ЭММ, которые используются на любых уровнях народнохозяйственной иерархии. Описательные модели экономических систем представляют собой формализованную с помощью математического аппарата экономическую задачу и используются для более глубокого изучения состояния системы и взаимосвязи ее элементов. К ним относятся матричные модели межотраслевых балансов народного хозяйства и экономического района, производственные функции и др. При определении исходных данных задачи модели данного типа позволяют получить единственное решение. Основной недостаток этих моделей - отсутствие условия нахождения оптимального решения. Оптимизационные модели отражают в математической форме смысл экономической задачи. Отличительной особенностью этих моделей является наличие условия нахождения оптимального решения (критерия оптимальности), которое записывается в виде функционала. Эти модели при определенных исходных данных задачи позволяют получать множество решений, удовлетворяющих условиям задачи, и обеспечивают выбор оптимального решения, отвечающего критерию оптимальности: модели определения оптимальной производственной программы, модели оптимального смешивания компонентов, оптимального раскроя, оптимального размещения предприятий некоторой отрасли на определенной территории, модели транспортной задачи. Большинство существующих оптимизационных моделей являются моделями планирования и имеют один критерий оптимальности. 1.3. Процесс экономико-математического моделирования. Этот процесс состоит из нескольких взаимосвязанных этапов. Разбиение на этапы и выделение на каждом этапе присущих ему процессов условно: на одном из выделенных этапов возможно совмещение процессов, относящихся к разным этапам. Первый этап - постановка задачи. Данный этап начинается с выработки цели исследования. Для конкретной экономической системы цели исследования могут быть различными, например, для предприятия можно задаться целью составить оптимальный план выпуска продукции или перевозок грузов, либо найти оптимальный вариант раскроя исходных материалов и т.д. Исходя из цели исследования необходимо провести подробный анализ системы, выявить ее структуру и функции, изучить особенности. В процессе постановки задачи необходимо помнить, что модель должна, во-первых, правильно воспроизводить действительность, во-вторых, быть доступной для исследования. Эти два обстоятельства оказывают существенное влияние на выбор исходных предпосылок. При моделировании экономических систем, исходя из цели исследования, с одной стороны, необходимо выбрать самые важные в условиях данной задачи факторы и ввести в модель только те, которые самым существенным образом влияют на результат решения, на достижение поставленной цели. Учет в модели несущественных факторов приводит к тому, что модель становится сложной для понимания моделируемой системы и для решения. С другой стороны, игнорирование многих факторов может привести к чрезмерному упрощению модели, нарушению соответствия ее действительности. Компромисс между этими двумя требованиями достигается методом проб и ошибок. Эйнштейн утверждал, что правильная постановка задачи более важна, чем ее решение. Второй этап - построение математической модели На этом этапе проводится формализация задачи - построение математических зависимостей в виде уравнений, неравенств, функций и т.п. Формализованную с помощью математического аппарата запись экономической задачи называют моделью задачи. Приступая к формализации экономического процесса, необходимо проанализировать, подходит ли для его описания одна из ранее созданных ЭММ. К настоящему моменту создано несколько десятков так называемых универсальных, или типовых, моделей (модель транспортной задачи, модели задачи о ранце, диете, раскрое и т.п.), которые используются на практике для описания различных экономических процессов. Самой универсальной моделью считается модель транспортной задачи, с помощью которой формализуется не только процесс перевозки грузов, но и процесс размещения предприятий отрасли на определенной территории, процесс назначения работников на работы и др. Третий этап - получение решения с помощью построенной модели. Основные задачи данного этапа. Первая задача - сбор и обработка необходимой для модели достоверной исходной информации, определение числовых значений параметров и внешних переменных. На практике не всегда удается собрать требуемую информацию, что приводит к невозможности использования модели в полученном виде. Тогда приходится возвращаться к постановке задачи и приспосабливать ее к имеющимся исходным данным. Вторая задача - выбор метода получения решения: используются аналитические (формульные) и численные экономико-математические методы: симплекс-метод, метод потенциалов и др. Экономико-математические методы в определенной степени универсальны и используются для решения различных экономических задач. Однако не любая задача укладывается в рамки модели, для которой уже разработаны эффективные аналитические или численные методы решения. В этом случае пользуются другими методами получения решения, в частности эвристическими и имитационными методами исследования систем. Эвристика (в переводе с греческого - нахожу, придумываю, открываю) - это совокупность неформальных методов решения задач (эвристических методов), основанных на прошлом опыте, интуиции решающего. Эвристические методы в общем случае не гарантируют получение наилучшего решения, поскольку они опираются не на доказательства, а на так называемые правдоподобные рассуждения. Имитационное моделирование следует рассматривать как новую методологию, новое направление в моделировании, позволяющее расширить его возможности. Под имитационным моделированием понимается экспериментирование с моделью реальной системы, в частности, вычислительный эксперимент, проводимый с помощью математической модели путем изменения различных исходных предпосылок. Поскольку вручную такие эксперименты просто невозможны, ИМ получило развитие только с появлением ЭВМ. Имитация (в переводе с латинского - подражание) - это воспроизведение чего-либо искусственными средствами, что позволяет постичь суть явления, не прибегая к экспериментам на реальном объекте. Имитационные модели служат для анализа поведения системы в условиях, определяемых экспериментатором. Четвертый этап - применение полученных с помощью модели результатов на практике. Сложность экономических процессов и явлений, другие особенности экономических систем затрудняют не только построение моделей, но и проверку их адекватности - соответствия ЭММ рассматриваемой экономической системе, цели ее исследования. Любая модель любой системы предполагает абстрагирование от некоторых реальных свойств объекта и отражает лишь основные его свойства. На данном этапе проверяется, насколько принятые допущения правомерны и, следовательно, применима ли построенная модель для исследования моделируемой системы. В случае необходимости модель корректируется. С целью обоснования пригодности модели для конкретных исследований проводится так называемый анализ модели на чувствительность. Полученное с помощью ЭММ решение анализируется на чувствительность путем изменения исходной информации в определенных пределах. Важность данной задачи состоит в том, что исходная информация со временем может меняться и необходимо знать, как будут влиять эти изменения на получаемое решение. 1.4. Общая постановка задачи исследования операций. Все факторы, входящие в описание операции, можно разделить на две группы: - постоянные факторы (условия проведения операции), на которые мы влиять не можем. Обозначим их через ; - зависимые факторы (элементы решения) x1 ,x2 ,..., которые в известных пределах мы можем выбирать по своему усмотрению. Критерий эффективности, выражаемый некоторой функцией, называемой целевой , зависит от факторов обеих групп, поэтому целевую функцию Z можно записать в виде Z = f(x1 ,x2,..., Все модели исследования операций могут быть классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов. Следует отметить прежде всего большой класс оптимизационных моделей. Такие задачи возникают при попытке оптимизировать планирование и управление сложными системами, в первую очередь экономическими системами. Оптимизационную задачу можно сформулировать в общем виде: найти переменные x1 , x2 ,..., xn , удовлетворяющие системе неравенств (уравнений) (1.1) и обращающие в максимум (или минимум) целевую функцию, т.е. Z = f( (1.2) (Условия неотрицательности переменных, если они есть, входят в ограничения (1.1)). В тех случаях, когда функции f и в задаче (1.1)-(1.2) хотя бы дважды дифференцируемы, можно применять классические методы оптимизации . Однако применение этих методов в исследовании операций весьма ограничено, так как задача определения условного экстремума функции n переменных технически весьма трудна: метод дает возможность определить локальный экстремум, а из-за многомерности функции определение ее максимального (или минимального) значения (глобального экстремума) может оказаться весьма трудоемким - тем более, что этот экстремум возможен на границе области решений. Классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция Z задана таблично. В этих случаях для решения задачи (1.1)-(1.2) применяются методы математического программирования. Математическое программирование - область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи - это отражение оригинала в виде функций, уравнений, неравенств, цифр и т.д. Если критерий эффективности Z = f(x1 ,x2 ,...,xn ) представляет линейную функцию, а функции в системе ограничений (1) также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования. Если в задаче математического программирования имеется переменная времени и критерий эффективности (1.2) выражается не в явном виде как функция переменных, а косвенно - через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования. Из перечисленных методов математического программирования наиболее распространенном и разработанным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций. В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В. Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин и многие другие. Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др. Методы исследования операций, как и любые мат. методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, динамические процессы - статическими моделями и т.д. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т.Саати, как «искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами». 2. Линейное программирование Термин «линейное программирование» впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному программированию (основные задачи и приложения, критерий оптимальности, экономическая интерпретация, методы решения, геометрическая интерпретация результатов решения) были проведены в конце 30-х годов в СССР в Ленинградском университете Л. В. Канторовичем. Под линейным программированием понимается линейное планирование, т.е. получение оптимального плана - решения в задачах с линейной структурой. Линейное программирование широко применяется в сфере военной деятельности, сельском хозяйстве, промышленности, управлении производственными процессами и запасами, в экономике и на транспорте. 2.1. Общая задача линейного программирования. Общей задачей линейного программирования (ОЗЛП) называют задачу: Максимизировать (минимизировать) функцию (2.1) при ограничениях: (2.2) где cj , aij , bi -заданные действительные числа, (2.1) - целевая функция, (2.2) - ограничения, - план задачи. Экономическая интерпретация модели ЛП состоит в следующем. Моделируемая система характеризуется наличием нескольких видов «производственной деятельности» , для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы Расход i-го ресурса на единицу продукта j-го вида производственной деятельности равен aij . В свою очередь при таком потреблении результат j-го вида производственной деятельности для единицы соответствующего продукта (удельная стоимость или прибыль) характеризуется величиной cj . Цель построения модели состоит в определении уровней (объемов производства) каждого вида производственной деятельности xj , при которых оптимизируется (максимизируется или минимизируется) общий результат производственной деятельности системы в целом без нарушения ограничений, накладываемых на использование ресурсов. Оптимальным решением (или оптимальным планом ) задачи ЛП называется решение системы ограничений (2.2), при котором линейная функция (2.1) принимает оптимальное значение. Термины «решение» и «план» - синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй - о содержательной стороне (экономической интерпретации). Симметричной формой записи ЗЛП называют задачу или задачу (2.3) 2.2. Линейное программирование в экономике 1. Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, фирма и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров) Пj , Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Все эти виды ограничивающих факторов называют ингредиентами Ri , Они ограничены, и их количества равны соответственно b1 ,b2 ,...,bm условных единиц. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.д. Примем в качестве такой меры, например, цену реализации cj , j= . Известны также технологические коэффициенты aij , , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Обозначим через план производства, показывающий, какие виды товаров П1 , П2 , ..., Пn нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах. Математическая модель задачи имеет следующий вид: (2.4) Так как переменные xj входят в целевую функцию Z( ) и систему ограничений только в первой степени, а показатели aij , bi , cj являются постоянными в планируемый период, то (2.4) - задача линейного программирования. 2. Задача о смесях. В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи формировании минимальной потребительской продовольственной корзины, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т.д. Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы. Модель задачи о наилучшем составе смеси рассмотрим на примере задачи формирования минимальной потребительской продовольственной корзины. Задан ассортимент продуктов , имеющихся в продаже. Каждый продукт содержит определенное количество питательных веществ, обозначаемые номерами 1,2,..., m (углеводы, белки, жиры, витамины, микроэлементы и др.). Единица j-го продукта содержит aij единиц i-го питательного вещества. Для нормальной жизнедеятельности в заданный промежуток времени нужно потреблять не менее bi единиц i-го питательного вещества. Обозначим через cj стоимость единицы продукта j-го вида. Необходимо определить требуемую потребительскую продовольственную корзину, имеющую минимальную стоимость. Решение задачи - это количества xj продуктов каждого вида, обеспечивающие необходимое количество питательных веществ при минимальных затратах на исходные продукты. Математическая модель задачи имеет следующий вид: (2.5) 3. Задача о раскрое материалов. Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы ( по длине, площади, объему, массе или стоимости) сводятся к минимуму. На раскрой (распил, обработку) поступает материал нескольких видов в определенном количестве. Из этого материала необходимо изготовить различные изделия. Материал может быть раскроен разными способами. Каждый способ имеет свою себестоимость и позволяет получить разное количество изделий каждого вида. Определить способ раскроя, при котором суммарная себестоимость минимальна. Пусть n - число различных видов материала, поступающего на раскрой; dj - количество материала j-го вида, m - число различных видов изделий, которые надо изготовить; bi - число изделий i-го вида, ; l -число различных способов раскроя; aijk - число изделий i-го вида, которое можно получить из единицы материала j-го вида при k-м способе раскроя, ; cjk - себестоимость раскроя единицы материала j-го вида k-м способом, . Обозначим через xjk - количество единиц материала j-го вида, раскраиваемых k-м способом, . Математическая модель задачи имеет следующий вид: . Вместо критерия минимизации себестоимости в задаче может быть взят, например, критерий минимизации отходов. В этом случае в условии должно быть задано количество отходов, получаемых при каждом способе раскроя для единицы материала каждого вида. 2.3. Геометрическая интерпретация и графическое решение ЗЛП . Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Случай двух переменных не имеет особого практического значения, но его рассмотрение проясняет свойства ОЗЛП, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации. Пусть дана задача: Z=c1 x1 +c2 x2 max (2.6) (2.7) (2.8) Дадим геометрическую интерпретацию элементов этой задачи. Введем на плоскости декартову прямоугольную систему координат x1 Ox2 и сопоставим каждой паре чисел (x1 ,x2 ) точку плоскости с координатами x1 и х2. Выясним сначала, что представляет собой множество точек, соответствующих допустимым решениям данной задачи. Рассмотрим одно линейное неравенство . Оно определяет на плоскости одну из двух полуплоскостей, на которые прямая разбивает плоскость (сторона в которой располагается полуплоскость от прямой, указывается штриховкой). Убедиться в том, с какой стороны от прямой лежит полуплоскость, точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству соответствует другая плоскость. Каждое из ограничений (2.7), (2.8) задает на плоскости х1 Oх2 некоторую полуплоскость. Нас интересуют те точки плоскости, координаты которых принадлежат всем полуплоскостям. Следовательно, допустимое множество ЗЛП геометрически изображается пересечением (общей частью) полуплоскостей, определяемых отдельными ограничениями. Полуплоскость - выпуклое множество. Множество называется выпуклым, если ему вместе с двумя произвольными точками принадлежит и прямолинейный отрезок, их соединяющий. Пересечение любого числа выпуклых множеств является выпуклым множеством. Таким образом, область допустимых решений задачи (2.6) - (2.8) есть выпуклое множество. На рис.2.1 представлены возможные ситуации, когда область допустимых решений ЗЛП - выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), прямая линия (г), луч (д), отрезок (е), пустое множество (ж). X2 X2 X2 б) 0 а) X1 0 X1 Х2 Х2 Х2 в) 1 д) г) 0 Х1 0 Х1 0 Х 1 Х2 Х2 е) ж) Х1 х 0 0 Х1 Рис.2.1 Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП - непустое множество, например, многоугольник ABCDE рис.2.2. X2 B C M A D E 0 X1 Рис.2.2 N Выберем произвольное значение целевой функции Z=Z0 . Получим c1 x1 +c2 x2 =Z0 Это уравнение прямой линии (рис.2.2 - прямая MN). В точках прямой MN целевая функция сохраняет одно и то же постоянное значение Z0 . Считая Z0 параметром, получим семейство параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). Нас интересуют те точки области допустимых решений, которые принадлежат линии уровня с наибольшим значением Z0 по сравнению с его значениями для всех других линий уровня, пересекающихся с областью допустимых решений. Возникает вопрос: как установить направление возрастания (убывания) целевой функции по x1 и х2 : (2.9) (2.10) Частная производная (2.9) и (2.10) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, с1 и с2 - скорости возрастания вдоль осей Oх1 и Oх2. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор - указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Вектор перпендикулярен к прямым Z = const семейства Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения. 1, С учетом системы ограничений строим область допустимых решений. 2. Строим вектор наискорейшего возрастания целевой функции. 3. Проводим произвольную линию уровня Z=Z0, перпендикулярную к вектору так, чтобы она пересеклась с областью допустимых решений. 4. При решении задач на max перемещаем линю уровня Z=Z0 в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точки) (на рис.2.2 точка С). В случае решения задачи на min линию уровня Z=Z0 перемещают в направлении вектора - (на рис .2.2 - точка Е). Определяем оптимальный план и экстремальное значение целевой функции . Пример 2. 1. Предприятию необходимо изготовить два вида продукции А и В, с использованием трех видов ресурсов R1, R2 , R3 количество которых ограничено. Исходные данные задачи представлены в таблице: Вид ресурсов Количество ресурсов, идущих на изготовление единицы продукции Запасы ресурсов А В R1 6 6 36 R2 4 2 20 R3 4 8 40 Доходы от реализации продукции 12 15 Требуется составить такой план выпуска продукции, чтобы при ее реализации получить максимальный доход. Решение. Обозначим через х1 и х2 количество единиц продукции видов А и В, планируемых к выпуску. Известно, что доход от реализации единицы продукции А составляет 12 усл. ед. и количество этой продукции - х1 . Следовательно, доход от реализации всей продукции А составит 12х1 усл. ед. Аналогично, доход от реализации всей продукции В составит 15х2 усл. ед. Учитывая, что доход от реализации продукции должен быть максимальным, целевая функция задачи будет иметь вид: Известно также, что имеющиеся на предприятии ресурсы ограничены. Это обстоятельство в свою очередь необходимо отразить в модели. Предприятие производит продукцию, используя три вида ресурсов. Естественно, что фактический расход никакого вида ресурса не должен превышать запасов соответствующего вида ресурсов на предприятии. Поскольку расход каждого вида ресурсов на единицу каждого вида продукции и запасы ресурсов известны, это обстоятельство отражается в следующих ограничениях: Смысл первого ограничения состоит в том, что фактический расход ресурса R1 на производство продукции А и В, равный 6х1 +6х2 (здесь 6х1 - количество единиц ресурса R1 , идущего на изготовление х1 единиц продукции A; 6х2 - количество единиц ресурса R1, идущее на изготовление х2 единиц продукции В) не должен превышать запаса этого ресурса на предприятии, равного 36 ед. Аналогичный смысл имеют 2-е и 3-е ограничения только для ресурсов R2 и R3 соответственно. Количество продукции, выпускаемое предприятием, должно быть величиной положительной или равной нулю (если предприятие определенный вид продукции не производит). Следовательно, в модели должны присутствовать ограничения неотрицательности переменных: Таким образом, построена математическая модель нашей задачи как задачи линейного программирования: Начнем решение задачи с построения области допустимых решений (рис.2.3) В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных. В двумерном пространстве уравнению соответствует прямая линия, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Прямые х1 =0 и х2 =0 совпадают с осями координат. Полуплоскости x1 >0,x2 >0 лежат соответственно справа от оси Oх2 и выше оси Oх1 . Множество точек, удовлетворяющих одновременно неравенствам представляют собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти. Теперь рассмотрим ограничения задачи. Построим по порядку прямые: ` 6x1 +6x2 =36 или х1 +х2 =6 (а) 4х1 +2х2 =20 или 2х2 +х2 =10 (б) 4х1 +8х2 =40 или х1 +2х2 =10 (в) и определяем, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют строгим неравенствам: 6x1 +6x2 <36 4x1 +2x2 <20 4x1 +8x2 <40 Для определения полуплоскости решений первого неравенства возьмем произвольную точку плоскости, не лежащую на прямой 6х1 +6х2 =36, например (0;0), и подставим ее координаты в неравенство . В результате подстановки получили верное числовое неравенство 0< 36, и это означает, что начало координат лежит в полуплоскости решений первого неравенства. Сторона, в которой располагается полуплоскость от прямой, указывается штриховой. Аналогично строим полуплоскость решений остальных неравенств. [x X2 б) a) N2 в) M *6 в 0 N C x1 6 D Рис.2.3 Заштрихованная часть плоскости и представляет собой искомый многоугольник допустимых решений задачи (рис.2.3) Теперь нужно среди точек построенного многоугольника найти такую, в которой целевая функция Z=12x1 +15x2 достигает максимального значения. Для этого построим прямую, заданную уравнением 12х1 +15х2 =0, которая является линией нулевого уровня функции Z. Направление возрастания линейной функции Z=12x1 +15x2 указывает вектор с началом в точке (0;0) и концом в точке М1 (12,15), координаты которой равны коэффициентам при соответствующих переменных функции Z. Для нахождения оптимального плана нужно «передвигать» линию нулевого уровня Z параллельно самой себе в направлении вектора до точки ее «последней встречи» с многоугольником, которая и является оптимальным планом задачи. В нашем случае это вершина В многоугольника OABCD - точка пересечения прямых (а) и (в). Координаты ( ) точки найдем, решив систему уравнений. откуда х1 * =2, х2 * =4. Найдем соответствующее значение целевой функции: усл. ед. Ответ . Для обеспечения максимального дохода от реализации готовой продукции предприятию необходимо выпустить 2 ед. продукции вида А и 4 ед. продукции вида В. При таком плане доход от реализации составит 84 усл. ед. Геометрический метод решения ЗЛП обладает рядом достоинств: он прост, нагляден, позволяет быстро и легко получить ответ. Однако только геометрический метод решения никак не может удовлетворить ни математиков, ни экономистов. Возможны «технические» погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов производства, избыток питательных веществ и т.п.), не выявляются при геометрическом решении задач. Но самое главное - геометрический метод неприемлем для решения практических задач. Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных и выявить экономический смысл входящих в них величин. 3. Транспортная задача Методы линейного программирования, являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ позволяет значительно упростить решение задачи. Поэтому лицо, принимающее решение, получает возможность уделить большее внимание интерпретации и оценке решения задачи. Однако применение ППП предполагает предварительную формализацию модели линейного программирования. В процессе решения большинства проблем эта задача является основной. При построении модели необходимо идентифицировать ее переменные и сформулировать систему ограничений. При решении некоторых видов проблем распределения ресурсов использование специально созданных для этих целей алгоритмов упрощает процесс построения исходной модели. В дальнейшем рассмотрим два примера таких алгоритмов, созданных для решения транспортной задачи и задачи о назначениях. Эти задачи используются для моделирования и оптимизации экономических проблем, связанных с формированием оптимального плана перевозок, оптимального распределения индивидуальных контрактов на транспортировки, составление оптимального штатного расписания, определения оптимальной специализации предприятий, рабочих участков, оптимального назначения кандидатов на работы, оптимального использования торговых агентов. 3.1. Постановка задачи Пусть имеется m поставщиков А1 , А2 , ...,Аm однородного груза в количествах соответственно а1, а2 ,...,аm единиц и n потребителей В1, В2 ,...,Вn этого груза, потребность которых составляет соответственно b1 , b2, ...,bn единиц. Известна стоимость (тариф) cij перевозки единицы груза от i-го (i= поставщика к j-му ( потребителю. Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов Ai в пункты Bj в соответствии с потребностью и общая величина транспортных издержек будет минимальной. Обычно исходные данные транспортной задачи представляют в виде табл. 1: табл.1 Bj Ai b1 b2 ... bn a1 c11 c12 ... c1n a2 c21 c22 ... c2n ... ... ... ... ... am cm1 cm2 ... cmn При постановке конкретных задач перевозки грузов может возникнуть одна из трех ситуаций: (3.1) (3.2) (3.3) Каждой ситуации соответствует определенная модель ТЗ: ситуации (3.1) (суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей) отвечает закрытая модель ТЗ (сбалансированная транспортная модель), а ситуациям (3.2) и (3.3) - отвечает открытая модель ТЗ (несбалансированная транспортная модель). 3.2. Экономико-математическая модель ТЗ Рассмотрим ситуацию (3.1). Обозначим через количество единиц груза, которое необходимо доставить от i-го поставщика к j-му потребителю. Экономико-математическая модель ТЗ должна отражать все условия и цель задачи в математической форме. Переменные должны удовлетворять ограничениям по запасам, потребностям и условиям неотрицательности. В математической форме эти условия можно записать так: (3.4) (3.5) (3.6) Цель ТЗ - минимизировать общие затраты на реализацию плана перевозок, которые можно представить функцией: (4.7) Итак, математически ТЗ ставится так. Даны система ограничений (3.4) и (3.5) (ограничения (3.5) отражают тот факт, что весь груз от всех поставщиков должен быть вывезен, а ограничения (3.4) отражают тот факт, что каждый потребитель должен получить ровно столько груза, сколько ему необходимо) при условии (3.6) и линейная функция (3.7). Найти такое неотрицательное решение, при котором линейная функция (4.7) принимает минимальное значение. Для того, чтобы ТЗ (3.4)-(3.7) имела допустимые планы, необходимо и достаточно выполнение равенства (3.1) Решение транспортной задачи состоит из двух этапов: 1 этап. Нахождение начального плана перевозок (xij ), удовлетворяющего ограничениям (3.4)-(3.6); 2 этап. Улучшение начального плана перевозок и получение оптимального плана перевозок (xij ), доставляющего минимум функции (3.7). 3.3. Построение исходного опорного плана. Построение опорных планов, а также их преобразование будем производить непосредственно в распределительной таблице (табл.1). Если в плане перевозок переменная то это число а записываем в соответствующую клетку (i, j) и считаем ее занятой или базисной, если xij = 0 то клетку (i,j) оставляем свободной. Метод «северо-западного угла». Определение значений xij начинается с левой верхней, условно называемой северо-западной, клетки (1,1) табл.1. Находим x11 =min(a1 , b1 ). 1) если а1 <b1 , то x11 =a1 , строка 1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b1 уменьшается на а1 ; 2) если а1 >b1 , то х11 =b1 , столбец 1 исключается из дальнейшего рассмотрения (первый потребитель В1 будет полностью удовлетворен), а наличие груза у первого поставщика a1 уменьшается на b1 ; 3) если a1 =b1 , то x11 = a1 =b1 , первая строка и первый столбец исключаются из дальнейшего рассмотрения. Эта ситуация приводит к вырождению исходного решения. Затем аналогичные операции проделывают с оставшейся частью таблицы, начиная с ее северо-западного угла. На последнем шаге процесса остается одна строка (последняя) и один столбец (последний). После заполнения клетки, стоящей на их пересечении, т.е. клетки (m, n), процесс завершается. После завершения описанного процесса необходимо провести проверку полученного плана (решения) на вырожденность. Если количество заполненных (занятых) клеток равно m+n-1, то план является невырожденным, в противном случае - вырожденным. Если план вырожденный, то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями, чтобы общее число заполненных клеток стало равным m+n-1. Однако, при расстановке нулей необходимо помнить, что в таблице не должно быть ни одного прямоугольника, все вершины которого являются заполненными клетками. Например, переменные x11 ,x12 ,x21 ,x22 не могут быть одновременно базисными. Метод минимального элемента. В отличии от метода северо-западного угла данный метод учитывает при построении исходного плана стоимости перевозок. В ряде случаев он позволяет получить лучшее с точки зрения критерия оптимальности решение, сокращая количество итераций для получения оптимального плана. Определение значений xij начиная с клетки, имеющей минимальную стоимость перевозки. Если в таблице имеется несколько клеток с одинаковыми минимальными стоимостями, то заполняется прежде та клетка, в которую можно вписать большую поставку. Переменной, отвечающей выбранной клетке, присваивается минимальное из двух возможных значений: xij =min(ai ,bj ). Соответствующая строка или столбец исключаются из дальнейшего рассмотрения, а потребность потребителя или наличие груза у поставщика уменьшается на выбранную величину. Если для выбранной клетки с минимальной стоимостью перевозки наличие груза у поставщика равно потребности потребителя, то из дальнейшего рассмотрения исключаются и строка и столбец (это приводит к вырождению исходного плана). Затем в оставшейся части таблицы проделывают аналогичные операции, опять начиная с клетки, имеющей минимальную стоимость перевозки. Проверка плана на вырожденность и расстановка ( в случае вырожденности плана) нулей осуществляется так же, как это описано для метода северо-западного угла. Для нахождения оптимального плана перевозок необходимо уметь оценивать полученный план на оптимальность. Как это сделать, не имея в распоряжении всех возможных планов перевозок, которые можно было бы сравнить между собой? Для оценки плана на оптимальность вводится понятие косвенных затрат. Косвенные затраты - это затраты, получаемые для маршрутов, по которым не осуществляются перевозки при данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные затраты не меньше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты меньше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута. Ввод нового маршрута в план перевозок соответствует вводу в список базисных переменных переменной транспортной задачи, соответствующей этому маршруту. Эти рассуждения лежат в основе ряда методов, применяемых для нахождения оптимального плана перевозок. Рассмотрим один из них - метод потенциалов. 3.4 . Алгоритм решения ТЗ методом потенциалов 1. Построить опорный план по одному из правил. 2. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m+n-1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток. 3. Проверка плана на оптимальность. 3.1. Определение потенциалов поставщиков и потребителей. Для всех занятых клеток рассчитываются потенциалы по формуле (3.8) где ui - потенциалы поставщиков (строк), vj - потенциалы потребителей (столбцов). Так как всех занятых клеток должно быть m+n-1, т.е. на единицу меньше числа потенциалов (их m+n), то для определения чисел ui , vj необходимо решить систему из m+n-1 уравнений ui +vj =cij c m+n неизвестными. Система неопределенная, и, чтобы найти частные решения, одному из потенциалов придают произвольное числовое значение (обычно полагают u1 =0), тогда остальные потенциалы определяются однозначно. 3.2. Для всех свободных клеток рассчитываются оценки по формуле ) (3.9) Здесь - реальные тарифы, а - косвенные тарифы. Если все s то полученный план является оптимальным. При этом, если все sij >0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка sij =0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции. Если хотя бы для одной свободной клетки , то план может быть улучшен. Переход к шагу 4. 4. Среди отрицательных оценок выбирается минимальная. Например, для клеток (i, j) и (k,l) имеем оценки: sij =-2, skl =-4. В этом случае наиболее потенциальной (перспективной) является клетка (k,l). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загрузки данной клетки единицей груза. Так, от загрузки клетки (i,j) единицей груза транспортные расходы уменьшаются на денежных единиц, а от загрузки единицей груза клетки (k, l) - на денежных единиц. Эффективность плана от загрузки потенциальной клетки грузом в единиц составит денежных единиц. Для наиболее перспективной свободной клетки (клетки с min отрицательной оценкой) строится замкнутый цикл. Для этого из выбранной свободной клетки проводится по строке или столбцу прямая линия до любой занятой клетки, затем под углом 90 линия проводится до следующей занятой клетки и так до тех пор пока цепь не замкнется в исходной клетке (цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Каждое звено цепи соединяет две клетки строки (столбца). Для свободной клетки всегда можно построить единственный цикл. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободной клетки). 5. В вершинах цепи, чередуя проставляются знаки «+» и «-», начиная с выбранной свободной клетки (в нее помещают знак «+»). В клетках со знаком «-» выбирается минимальная поставка ( , которая перераспределяется по цепи: там, где стоит знак «+» она прибавляется, а где «-» - отнимается. В результате чего баланс цикла не нарушается. Исходная свободная клетка становится занятой, а клетка в которой выбрана минимальная поставка - свободной (рис.3.1 а, б) а) б) + - 20 20 40 - + 80 20 60 Рис.3.1 Может случится, что найденное наименьшее число ( одинаково для нескольких клеток цепи, помеченных знаком «-» (рис.3.2а). В этом случае во всех таких клетках (с минимальными стоимостями), кроме одной, нужно оставить нулевые (фиктивные) поставки (рис.3.2б). а) б) + 4 - 3 33 20 20 - + 10 30 30 10 - 2 + 0 60 20 40 Рис.3.2 Составляется новый план, рассчитывается значение целевой функции. Переходим к шагу 2. 3.5. Пример решения транспортной задачи На четырех строительных площадках В1 , В2 , В3 , В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит налажено на трех заводах А1, А2 , А3 в размере соответственно 100,70 и 50 м3 . Известны стоимости перевозки (табл.2) 1м3 сборных плит из каждого пункта производства в каждый пункт потребления (ден. ед./ м3 ). Требуется так закрепить строительные площадки за заводами, чтобы при полном обеспечении сборными плитами перекрытий затраты на перевозку были минимальными. РЕШЕНИЕ. Исходное опорное решение получим по методу «северо-западного угла» (табл.3) и по методу min элемента (табл.4). Здесь ,т.е имеем закрытую модель ТЗ (табл.2 ). табл.2 Bj Ai 20 120 20 60 100 6 4 2 4 70 1 2 7 2 50 2 4 1 4 табл.3 Bj Ai 20 120 20 60 100 6 20 4 80 2 4 70 1 2 40 7 20 2 10 50 2 4 1 4 50 Транспортные расходы f= табл.4 Bj Ai 20 120 20 60 100 6 4 100 2 4 70 1 20 2 7 2 50 50 2 4 20 1 20 4 10 f= Транспортные расходы для опорного плана, построенного по методу min элемента, меньше. Поэтому за исходное решение возьмем то, которое получено по методу min элемента (табл.4). Количество заполненных клеток в табл.4 равно 6: m+n-1=3+4-1=6. Следовательно, полученный план невырожденный. Для определения потенциалов (см. формула 3.8) составляем уравнения: u1 +v2 =4, u2 +v1 =1, u2 +v4 =2, u3 +v2 =4, u3 +v3 =1, u3 +v4 =4. Положим u1 =0, тогда v2 =4, u3 =0, v3 =1, v4 =4, u2 =-2, v1 =3. Потенциалы проставлены в табл.5 (последняя строка и последний столбец). Их можно вычислять и непосредственно в таблице не выписывая систему уравнений. Т.к. если известны потенциал и тариф (стоимость перевозки) занятой клетки, то из соотношения ui +vj =cij легко определить неизвестный потенциал (из суммы вычесть известное слагаемое, получим неизвестное слагаемое. Роль суммы в данном равенстве играет тариф cij ) Определим по формуле (3.9) оценки свободных клеток: s11 =6-(0+3)=3>0, s13 =2-(0+1)=1>0, s14 =4-(0+4)=0 s22 =2-(-2+4)=0, s23 =7-(-2+1)=8>0, s31 =2-(0+3)= -1<0 табл.5 табл.6 Bj Ai 20 120 20 60 ui Bj Ai 20 120 20 60 ui 100 6 4 100 2 4 0 100 6 4 100 2 4 0 70 - 1 20 2 7 + 2 50 -2 70 - 1 10 + 2 7 2 60 -1 50 2 + 4 20 1 20 -- 4 10 0 50 + 2 10 - 4 20 1 20 4 0 vi 3 4 1 4 vj 2 4 1 3 План неоптимальный, т.к. s31 <0. Строим для клетки (3;1) цикл непосредственно в табл.5. В цикл войдут клетки (3;1), (3;4), (2;4), (2;1). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, В результате смещения по циклу получим новый план (табл.6). Транспортные расходы ( а были равны 660). Будет ли полученный план оптимальным? План невырожденный. Определим для него новые потенциалы: u1 +v2 =4, u2 +v1 =1, u2 +v4 = 2, u3 +v1 =2, u3 +v2 =4, u3 +v3 =1. Положим u1 =0, тогда v2 =4, u3 =0, v1 =2, v3 =1, u2 = -1, v4 =3. Проставим значения найденных потенциалов в табл.6. Определим оценки свободных клеток: s11 =6-(0+2)=4>0, s13 =2-(0+1)=1>0, s14 =4-(0+3)=1>0 s22 =2-(-1+4)=-1<0, s23 =7-(-1+1)=7>0, s44 =4-(0+3)=1>0. План (табл.6) неоптимальный, т.к. s22 <0. Строим для клетки (2;2) цикл непосредственно в табл.6. В цикл войдут клетки (2;2), (2;1), (3;1), (3;2). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, В результате смещения по циклу получим новый план (табл.7). План невырожденный. Транспортные расходы f = (а были равны 650). Табл.7 Bj Ai 20 120 20 60 ui 100 6 4 100 2 4 0 70 1 2 10 7 2 60 -2 50 2 20 4 10 2444 1 1111 20 4 0 vj 2 4 1 4 Будет ли полученный план оптимальным? Определим для него новые потенциалы: u1 +v2 =4, u2 +v2 =2, u2 +v4 =2, u3 +v1 =2, u3 +v2 =4, u3 +v3 =1. Положим u1 =0, тогда v2 =4, u2 =-2, v4 =4, u3 =0, v1 = 2, v3 =1. Проставим значения найденных потенциалов в табл.7. Определим оценки свободных клеток: s11 =6-(0+2)=4>0, s13 =2-(0+1)=1>0, s14 =4-(0+4)=0 s21 =1-(-2+2)=1>0, s23 =7-(-2+1)=8>0, s34 =4-(0+4)=0 Оценки свободных клеток неотрицательны, следовательно, полученный план является оптимальным: x12 =100, x22 =10, x24 =60, x31 =20, x32 =10, x33 =20 Минимальные транспортные расходы для этого плана f=640. Все оценки свободных клеток равны нулю. Это свидетельствует о неединственности оптимального плана. ОТВЕТ. Согласно оптимальному плану, с первого завода A1 нужно поставить 100м3 перекрытый на вторую строительную площадку B2 , с завода А2 - 10м3 на строительную площадку В2 и 60м3 на строительную площадку В4 , с завода А3 - на 20 м3 на строительную площадку В1 , 10 м3 на строительную площадку В2 и 20 м3 на строительную площадку В3. 3.7. Транспортные задачи, имеющие некоторые усложнения в постановке 1. Транспортная задача с избытком запасов : Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn +1 с потребностью bn +1 и полагают стоимости перевозок грузов в Bn +1 равными нулю. Полученная новая транспортная задача является закрытой. Найдя оптимальный план xij этой транспортной задачи и отбрасывая в полученной таблице последний столбец, получим оптимальный план исходной транспортной задачи. 2. Транспортная задача с избытком заявок : Эта задача несколько сложнее предыдущей: дело в том, что как ни развози грузы, все потребности удовлетворить все равно не удается. Поэтому постановка задачи нуждается в уточнении. 2.1. Все пункты назначения требуется удовлетворить пропорционально поданным заявкам. В этом случае, подсчитав коэффициент пропорциональности и «подправив» заявки: получим закрытую модель транспортной задачи. 2.2. Если не заботиться о «справедливости» удовлетворения заявок, а по-прежнему интересоваться лишь минимизацией транспортных расходов, то для отыскания оптимального плана вводят фиктивный пункт (m+1)-й отправления Am +1 с запасом груза am +1 и полагают стоимости перевозок грузов из Am +1 равными нулю. Полученная транспортная задача является закрытой. Найдя оптимальный план xij этой транспортной задачи и отбрасывая в полученной таблице последнюю строку, получим оптимальный план исходной транспортной задачи. И в случае 1 и в случае 2.2 при преобразовании открытой задачи в закрытую, целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю. 3. Транспортная задача с поиском максимума целевой функции . Перейдем к целевой функции Z=-F и найдем план ( , доставляющий ей минимум. Тогда ( будет оптимальным и для исходной задачи, причем (. 4. Транспортная задача с запретными маршрутами. Речь идет о задачах, в которых нельзя перевозить груз из некоторых пунктов отправления Ai в некоторые пункты назначения Bj . В этом случае стоимости соответствующих перевозок полагаем равными достаточно большому числу. Тогда при отыскании оптимального плана соответствующие перевозки будут блокированы. 5. Транспортная задача с обязательными поставками. Иногда приходится решать транспортную задачу, в которой дополнительным условием в ограничениях является обязательное обеспечение конкретных перевозок по определенным маршрутам. В этом случае каждую обязательную перевозку xij =dij реализуем условно, уменьшая на dij запасы в Ai и потребности в Bj . Если это не удается сделать, то исходная задача не имеет решения. В противном случае стоимости обязательных поставок полагаем равными достаточно большому числу, решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной задачи. 6. Транспортная задача с ограничениями снизу. Пусть требуется решить транспортную задачу, в которой некоторые из перевозок ограничены снизу xij pij . Организуем условные перевозки, уменьшив на pij запасы в Ai и потребности в Bj . Если это сделать не удается, то исходная задача решения не имеет, в противном случае решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной транспортной задачи. 3.8. Экономические задачи, сводящиеся к транспортным моделям Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие: - оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком; - оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij . Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности; - задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции; - увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность. ПРИМЕР. Выбор оптимального варианта использования производственного оборудования. На предприятии имеются три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 часов. Каждая операция должна выполняться соответственно 100, 120, 70, 130 часов. Определить, сколько времени и на какую операцию нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей. Производительность каждой группы станков на каждую операцию задана матрицей 3 5 11 10 5 5 10 15 3 2 4 8 6 12 10 1. Оптимальное распределение оборудования Оборудование m различных видов нужно распределить между n рабочими участками. Производительность одной единицы оборудования i-го вида на j-м рабочем участке равна pij ; Потребность j-го участка в оборудовании составляет bj , Запас оборудования i-го вида равен ai , Найти распределение оборудования на рабочие участки, при котором суммарная производительность максимальная. Данная задача относится к классу транспортных задач при условии, что производительность линейно зависит от количества используемого оборудования. Поставщиками в задаче являются различные виды оборудования, потребителями - рабочие участки. Предложение определяется запасом оборудования каждого вида, спрос - потребностью в нем на рабочем участке. Обозначим через xij число единиц оборудования i-го вида, выделенное на j-й рабочий участок, Математическая модель задачи имеет следующий вид: Построенная модель является сбалансированной. Если запас оборудования и потребность в нем не равны, то переход к сбалансированной модели осуществляется с помощью преобразований, изложенных в пункте 4.7. В данной задаче требуется максимизировать целевую функцию P, представляющую суммарную производительность. Для перехода к стандартной транспортной модели надо заменить функцию P на противоположную функцию Z=-P, которую нужно будет минимизировать. При решении в транспортной таблице вместо тарифов на перевозки запишутся производительности pij , взятые с противоположным знаком. Далее задача решается как обычно. 2. Формирование оптимального штата фирмы. Фирма набирает штат сотрудников. Она располагает n группами различных должностей по bj вакантных единиц в каждой группе, Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по ai кандидатов в каждой группе, Для каждого кандидата из i-й группы требуются определенные затраты cij на обучение для занятия j-й должности, (В частности, некоторые cij =0, т.е. кандидат полностью соответствует должности, или cij = , т.е. кандидат вообще не может занять данную должность.) Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение. Предположим, что общее число кандидатов соответствует числу вакантных должностей. (если это не так, то следует просто проделать преобразования пункта 4.7.) Тогда данная задача соответствует транспортной модели. В роли поставщиков выступают группы кандидатов, а в роли потребителей - группы должностей. Предложением является число кандидатов в каждой группе, спросом - число вакансий в каждой группе должностей. В качестве тарифов на перевозки рассматриваются затраты на переобучение. Обозначим через xij число кандидатов из i-й группы, назначенных на j-ю должность, Математическая модель задачи имеет следующий вид: Методы решения этой задачи такие же, как и транспортной задачи. ПРИМЕР 2. Имеется m видов сельскохозяйственных культур и n хозяйств, где их можно выращивать. Из-за различных условий доход, получаемый с 1 га посева одной и той же культуры, в различных хозяйствах неодинаков. Обозначим через cij доход для i-й культуры и j-го хозяйства. Общие площади посева культур ai (i=1,m) и площади пашни в хозяйствах bj (j=1,n) известны. Требуется составить такой план размещения сельскохозяйственных культур по хозяйствам, чтобы общий доход был максимальным. Обозначим площадь посева i-й культуры в j-м хозяйстве через xij . Тогда получаем задачу: Найти план X=(xij ) такой, что При условиях: а) план посева по каждой культуре должен быть выполнен б) пашня в хозяйствах должна быть использована полностью в) 4. Нелинейное программирование Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать линейными, более детальное рассмотрение позволяет обнаружить их нелинейность. Как правило, такие показатели, как прибыль, себестоимость, капитальные затраты на производство и др., в действительности зависят от объема производства, расхода ресурсов и т.п. нелинейно. В этом случае возникает задача нелинейного программирования (ЗНП). 4.1 Общая задача нелинейного программирования В общем виде ЗНП формулируется следующим образом: , (4.1) , (4.2) , (4.3) где - управляющие переменные или решения ЗНП; - фиксированные параметры; - заданные функции от n переменных, причем целевая функция или (и) хотя бы одна из функций являются нелинейными. Решить задачу нелинейного программирования - это значит найти такие значения управляющих переменных , которые удовлетворяют системе ограничений (4.2),(4.3) и доставляют максимум или минимум целевой функции . Для задачи нелинейного программирования, в отличие от линейных задач, нет единого метода решения. В зависимости от вида целевой функции (4.1) и ограничений (4.2) разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод. Процесс составления математической модели ЗНП принципиально не отличается от составления модели ЗЛП. Рассмотрим несколько примеров. Задача 4.1. На m предприятиях выпускается некоторый продукт. Себестоимость единицы этого продукта на каждом из указанных предприятий есть , где - доля себестоимости, не зависящая от объема выпуска продукции, - план выпуска продукта на i-м предприятии. Предприятия должны обеспечить n потребителей с потребностями , стоимость перевозки из i-го предприятия к j-му потребителю равна . Требуется определить такой план распределения выпуска продукта предприятиями и план перевозок его потребителям, чтобы суммарная себестоимость выпуска и стоимость перевозки была минимальной. Математическую модель задачи . Пусть - план перевозок от i-го предприятия к j-му потребителю. Для удобства запишем данные и искомые величины задач в виде таблицы: Табл.4.1 Потребители Предприятия 1 2 ... n План выпуска изделий 1 x11 x12 ... x1n x1 2 x21 x22 ... x2n x2 ... m xm1 xm2 xmn xm Потребности заказчиков b1 b2 ... bn Система ограничений задачи: (4.4) Целевая функция f запишется так: Вместо подставим значения, данные в условии задачи: (4.5) Надо найти минимальное значение функции (6.5) на множестве допустимых решений (4.4). Задача 4.2. На производство некоторого продукта расходуется два вида ресурсов. Определите оптимальное распределение величин затрачиваемых ресурсов, если цена ресурса первого вида 30 рублей, второго - 40 рублей, а всего выделено на производство 120 рублей. Известно, что из количества x1 первого ресурса и x2 второго ресурса можно получить единиц продукта. Вообще, функция выражающая зависимость между количеством вырабатываемого продукта и величиной расходуемых на него ресурсов, называется производственной функцией. Простейшая производственная функция для продукта, получаемого из двух различных ресурсов имеет вид: где - постоянные величины, причем Функция y выведена в предположении, что существует только два ресурса: x1 - труд, x2 - капитал, где указывает на соответствующую долю использования каждого из этих ресурсов; c - некоторый постоянный коэффициент; y - это количество совокупного продукта, которое при определенных технологических условиях может быть получено из данных продуктов. Функция y простейшая производственная функция, так как рассматривает зависимость между двумя ресурсами и одним продуктом. Математическая модель задачи . Пусть x1 - количество ресурсов вида 1, x2 - количество ресурсов вида 2. Система ограничений: (4.6) Целевая функция: (4.7) Требуется найти наибольшее значение функции (4.7) на множестве решений системы (4.6). 4.2. Некоторые особенности решения задач нелинейного программирования Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой или она не относится ни к тому, ни к другому классу. Говорят, что множество выпукло , если оно вместе с любыми своими точками А и В содержит и все точки отрезка АВ. Примерами выпуклых множеств в пространстве могут служить сфера, пирамида, призма и т.д. В невыпуклом множестве можно указать хотя бы две точки, такие, что не все точки отрезка АВ принадлежат рассматриваемому множеству. Примером невыпуклого множества в пространстве является тор. Функцию y = f(x) одной переменной будем называть выпуклой , если отрезок, соединяющий две любые точки ее графика, принадлежит графику или расположен выше его. Функция вогнута , если отрезок, соединяющий две любые точки графика, принадлежит ему или расположен ниже его. Аналогично можно сформулировать определения понятий вогнутой и выпуклой функций нескольких переменных. Говорят, что гиперповерхность z=f(x1 ,x2 ,...,xn ) выпуклая, если отрезок, соединяющий две ее любые точки, лежит на поверхности или выше ее. Гиперповерхность z=f(x1 ,x2 ,...,xn ) вогнута, если отрезок, соединяющий две ее любые точки, лежит на поверхности или ниже ее. Пусть дана функция , определенная на замкнутом множестве Ф. Элементами множества Ф являются точки . Поэтому функцию можно записать так: . Говорят, что функция , определенная на некотором множестве X, достигает в точке локального максимума (локального минимума) , если найдется такое число , что для всех , удовлетворяющих неравенству , выполняется неравенство Точка , в которой функция достигает локального максимума (минимума), называется точкой локального максимума (минимума). Пусть функция определена на замкнутом множестве X. Если и для любой точки , то говорят, что в точке функция достигает глобального максимума (глобального минимума). Точка , в которой все частные производные функции равны 0, называется стационарной точкой. Необходимое условие экстремума. Если в точке функция имеет экстремум, то частные производные функции в этой точке равны нулю: Как и в случае одной переменной, необходимое условие не является достаточным для того, чтобы стационарная точка была точкой экстремума. Для получения достаточных условий следует определить в стационарной точке знак дифференциала второго порядка. Дифференциал второго порядка обозначается