Экономико-математические методы

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ЭКОНОМИКО - МАТЕМАТИЧЕСКИЕ МЕТОДЫ

Методические указания

по изучению дисциплины и выполнению

контрольной работы

Методические указания по изучению дисциплины подготовил

к.т.н., проф. кафедры математических методов обработки

информации, зав. каф. ММОИ Клетин В.А.

Москва, 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) выражается не в явном виде как функция переменных, а косвенно - через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.

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

В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В. Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин и многие другие.

Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др.

Методы исследования операций, как и любые мат. методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, динамические процессы - статическими моделями и т.д. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т.Саати, как «искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами».

Линейное программирование

Термин «линейное программирование» впервые появился в 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 Линейное программирование в экономике

Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, фирма и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров) Пj, Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Все эти виды ограничивающих факторов называют ингредиентами Ri, Они ограничены, и их количества равны соответственно b1,b2,...,bm условных единиц. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.д. Примем в качестве такой меры, например, цену реализации cj, j=. Известны также технологические коэффициенты aij, , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Обозначим через план производства, показывающий, какие виды товаров П1, П2, ..., Пn нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Математическая модель задачи имеет следующий вид:

(2.4)

Так как переменные xj входят в целевую функцию Z() и систему ограничений только в первой степени, а показатели aij, bi, cj являются постоянными в планируемый период, то (2.4) - задача линейного программирования.

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

Модель задачи о наилучшем составе смеси рассмотрим на примере задачи формирования минимальной потребительской продовольственной корзины. Задан ассортимент продуктов , имеющихся в продаже. Каждый продукт содержит определенное количество питательных веществ, обозначаемые номерами 1,2,..., m (углеводы, белки, жиры, витамины, микроэлементы и др.). Единица j-го продукта содержит aij единиц i-го питательного вещества. Для нормальной жизнедеятельности в заданный промежуток времени нужно потреблять не менее bi единиц i-го питательного вещества. Обозначим через cj стоимость единицы продукта j-го вида. Необходимо определить требуемую потребительскую продовольственную корзину, имеющую минимальную стоимость.

Решение задачи - это количества xj продуктов каждого вида, обеспечивающие необходимое количество питательных веществ при минимальных затратах на исходные продукты.

Математическая модель задачи имеет следующий вид:

(2.5)

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

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

Пусть n - число различных видов материала, поступающего на раскрой; dj - количество материала j-го вида, m - число различных видов изделий, которые надо изготовить; bi - число изделий i-го вида, ; l -число различных способов раскроя; aijk - число изделий i-го вида, которое можно получить из единицы материала j-го вида при k-м способе раскроя, ; cjk - себестоимость раскроя единицы материала j-го вида k-м способом, .

Обозначим через xjk - количество единиц материала j-го вида, раскраиваемых k-м способом, .

Математическая модель задачи имеет следующий вид:

.

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

2.3 Геометрическая интерпретация и графическое решение ЗЛП

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

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

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

Z=c1x1+c2x2 max (2.6)

(2.7)

(2.8)

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

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

Рассмотрим одно линейное неравенство .

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

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

Каждое из ограничений (2.7), (2.8) задает на плоскости х1Oх2 некоторую полуплоскость. Нас интересуют те точки плоскости, координаты которых принадлежат всем полуплоскостям. Следовательно, допустимое множество ЗЛП геометрически изображается пересечением (общей частью) полуплоскостей, определяемых отдельными ограничениями. Полуплоскость - выпуклое множество. Множество называется выпуклым, если ему вместе с двумя произвольными точками принадлежит и прямолинейный отрезок, их соединяющий. Пересечение любого числа выпуклых множеств является выпуклым множеством. Таким образом, область допустимых решений задачи (2.6) - (2.8) есть выпуклое множество. На рис.2.1 представлены возможные ситуации, когда область допустимых решений ЗЛП - выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), прямая линия (г), луч (д), отрезок (е), пустое множество (ж).

X₂ X₂

б)

0 а) X₁ 0 X₁

Х₂ Х₂ Х₂

в) 1 д)

г)

0 Х₁ 0 Х₁ 0 Х ₁

Х₂ Х₂

е) ж)

Х₁

0 0 Х₁

Рис.2.1

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

X₂

B C

M

A

D

E

0 X₁

Рис.2.2 N

Рис.2.2 N

Выберем произвольное значение целевой функции Z=Z0. Получим

c1x1+c2x2=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, С учетом системы ограничений строим область допустимых решений.

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

Проводим произвольную линию уровня Z=Z0, перпендикулярную к вектору так, чтобы она пересеклась с областью допустимых решений.

При решении задач на 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₂

б)

a) N₂

в) M

*6

в

0 N

C x₁

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.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<b1, то x11=a1, строка 1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b1 уменьшается на а1;

если а1>b1, то х11=b1, столбец 1 исключается из дальнейшего рассмотрения (первый потребитель В1 будет полностью удовлетворен), а наличие груза у первого поставщика a1 уменьшается на b1;

если a1=b1, то x11= a1=b1, первая строка и первый столбец исключаются из дальнейшего рассмотрения. Эта ситуация приводит к вырождению исходного решения.

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

После завершения описанного процесса необходимо провести проверку полученного плана (решения) на вырожденность. Если количество заполненных (занятых) клеток равно m+n-1, то план является невырожденным, в противном случае - вырожденным.

Если план вырожденный, то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями, чтобы общее число заполненных клеток стало равным m+n-1. Однако, при расстановке нулей необходимо помнить, что в таблице не должно быть ни одного прямоугольника, все вершины которого являются заполненными клетками. Например, переменные x11,x12,x21,x22 не могут быть одновременно базисными.

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

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

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

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

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

Для нахождения оптимального плана перевозок необходимо уметь оценивать полученный план на оптимальность. Как это сделать, не имея в распоряжении всех возможных планов перевозок, которые можно было бы сравнить между собой? Для оценки плана на оптимальность вводится понятие косвенных затрат. Косвенные затраты - это затраты, получаемые для маршрутов, по которым не осуществляются перевозки при данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные затраты не меньше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты меньше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута. Ввод нового маршрута в план перевозок соответствует вводу в список базисных переменных переменной транспортной задачи, соответствующей этому маршруту. Эти рассуждения лежат в основе ряда методов, применяемых для нахождения оптимального плана перевозок. Рассмотрим один из них - метод потенциалов.

3.4 Алгоритм решения ТЗ методом потенциалов

Построить опорный план по одному из правил.

Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m+n-1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.

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

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линия проводится до следующей занятой клетки и так до тех пор пока цепь не замкнется в исходной клетке (цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Каждое звено цепи соединяет две клетки строки (столбца). Для свободной клетки всегда можно построить единственный цикл. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободной клетки).