Реферат Оптимальные решения с помощью линейных транспортных задач
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
МИНИСТЕРСТВО ПУТЕЙ СООБЩЕНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский государственный университет путей сообщения (МГУ ПС)
(МИИТ)
Кафедра: «________________________________________________________________»
КУРСОВАЯ работа
«____________________________________________________________________________»
Выполнила: ст-ка гр-пы № ВЭТ-311
Приняла:
г. Москва
2003 г.
ВВЕДЕНИЕ
Важной проблемой управления предприятиями в сложных условиях рынка являются своевременное принятие правильных решений в связи с изменениями в экономической ситуации. Одним из путей решения этой проблемы является применение методов экономико-математического моделирования в управлении предприятиями, в том числе и железнодорожным транспортом.
Математические модели и методы, являющиеся необходимым элементом современной экономической науки, как на микро-, так и макроуровне, изучаются а таких её разделах, как математическая экономика и эконометрика.
Эконометрика - это раздел экономической науки, который изучает количественные закономерности в экономике при помощи корреляционно-регрессионного анализа и широко применяется при планировании и прогнозировании экономических процессов в условиях рынка.
Математическая экономика занимается разработкой, анализом и поиском решений математических моделей экономических процессов, среди которых выделяют макро- и микроэкономические классы моделей.
Макроэкономические модели изучают экономику в целом, опираясь на такие укрупнённые показатели, как валовый национальный продукт, потребление, инвестиции, занятость и т.д. При моделировании рыночной экономики особое место в этом классе занимают модели равновесия и экономического роста.
Равновесные модели описывают такие состояния экономики, когда результирующая всех сил, стремящихся вывести её из некоторого состояния, равна нулю (модель «затраты – выпуск» В. Леонтьева, модель Эрроу-Добре).
Модели экономического роста описывают экономическую динамику и приводят к поиску и анализу траекторий стационарного роста: (модель Харрода-Домара, модель Солоу, модели магистрального типа).
Микроэкономические модели описывают экономические процессы на уровне предприятий и фирм, помогая решать стратегические и оперативные вопросы планирования и оптимального управления в рыночных условиях. Важное место среди микроэкономических моделей занимают оптимизационные модели (задачи распределения ресурсов и финансирования, транспортная задача, максимизация прибыли фирмы, оптимальное проектирование).
Первая часть посвящена рассмотрению основных принципов математического моделирования в экономике на микроэкономическом уровне и реализации этих принципов на примере классической оптимизационной модели, используемой в экономике железнодорожного транспорта - транспортной задаче. В последующих выпусках учебного пособия по экономико-математическому моделированию предполагается продолжить рассмотрение оптимизационных и равновесных моделей микроэкономических процессов, отразить основные проблемы эконометрики, а также дать рекомендации по выбору современных программных продуктов, необходимых для решения задач планирования, проектирования и прогнозирования экономических процессов на железнодорожном транспорте.
Глава 1.
ПРИНЦИПЫ ЭКОНОМИКО-МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ
1.1. Экономико-математическое моделирование как метод научного познания
Моделирование в научных исследованиях стало применяться в глубокой древности, постепенно захватывая всё новые области научных знаний: техническое конструирование, строительство и архитектуру, астрономию, физику, химию, биологию и, наконец, общественные науки. Большие успехи и признание практически во всех отраслях современной науки принёс методу моделирования - ХХ век. Однако методология моделирования долгое время развивалась независимо отдельными науками. Отсутствовала единая система понятий, единая терминология. Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания.
Термин модель широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений. Рассмотрим только такие модели, которые являются инструментами получения знаний.
Модель - это материальный или мысленно представляемый объект, который в процессе исследования замещает объект - оригинал, так, что его непосредственное изучение даёт новые знания об объекте - оригинале.
Под моделированием понимается процесс построения, изучения и применения моделей. Оно тесно связано с такими категориями, как абстракция, аналогия, гипотеза и др. Процесс моделирования обязательно включает и построение абстракций, и умозаключения по аналогии, и конструирование научных гипотез.
Главная особенность моделирования в том, что это метод опосредованного познания с помощью объектов - заместителей. Модель выступает как своеобразный инструмент познания, который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект. Именно эта особенность метода моделирования определяет специфические формы использования абстракций, аналогий, гипотез, других категорий и методов познания.
Необходимость использования метода моделирования определяется тем, что многие объекты (или проблемы, относящиеся к этим объектам) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.
Метод моделирования включает три элемента:
1. субъект (исследователь);
2. объект исследования;
3 модель, опосредствующую отношения познающего субъекта и познаваемого объекта,
Пусть имеется или необходимо создать некоторый объект А Мы конструируем (материально или мысленно) или находим в реальном мире другой объект В- модель объекта А. Рассмотрим основные этапы моделирования (рисунок 1.1.).
Этап построения модели предполагает наличие некоторых знаний об объекте- оригинале. Познавательные возможности модели обусловливаются тем, что модель отражает какие- либо существенные черты объекта – оригинала. Вопрос о необходимой и достаточной мере сходства оригинала и модели требует конкретного анализа. Очевидно, модель утрачивает свой смысл как в случае тождества с оригиналом (тогда он перестаёт быть оригиналом), так и в случае чрезмерного во всех существенных отношениях отличия от оригинала.
Таким образом, изучение одних сторон моделируемого объекта осуществляется ценой отказа от отражения других сторон. Поэтому любая модель замещает оригинал лишь в строго ограниченном смысле. Из этого следует, что для одного объекта может быть построено несколько “специализированных” моделей концентрирующих внимание на определённых сторонах исследуемого объекта или же характеризующих объект с разной степенью детализации.
На втором этапе процесса моделирования модель выступает как самостоятельный объект исследования. Одной из форм такого исследования является проведение “модельных” экспериментов, при которых сознательно изменяются условия функционирования модели и систематизируются данные об ее «поведении». Конечным результатом этого этапа является множество знаний о модели R
| | Этапы моделирования | | ||
| | | | | |
| | 1 | Построение модели | | |
| | | | | |
| | 2 | Исследование свойств модели | | |
| | | | | |
| | 3 | Перенос знаний с модели на объект-оригинал | | |
| | | | | |
| | 4 | Практическая проверка полученных с помощью модели знаний | | |
Рисунок 1.1. Этапы моделирования
На третьем этапе осуществляется перенос знаний с модели на оригинал формирование множества знаний S об объекте. Этот процесс переноса знаний проводится по определённым правилам. Знания о модели должны быть скорректированы с учётом тех свойств объекта - оригинала, которые не нашли отражения или были изменены при построении модели. Мы можем с достаточным основанием переносить какой-либо результат с модели на оригинал, если этот результат необходимо связан с признаками сходства оригинала и модели. Если же определённый результат модельного - исследования связан с отличием модели от оригинала, то этот результат переносить неправомерно.
Четвёртый этап - практическая проверка полученных с помощью моделей знаний и их использование для построения обобщающей теории объекта, его преобразования или управления им.
Для понимания сущности моделирования важно не упускать из виду, что моделирование - не единственный источник званий об объекте. Процесс моделирования “погружён” в более общий процесс познания. Это обстоятельство учитывается не только на этапе построения модели, но и на завершающей стадии, когда происходит объединение и обобщение результатов исследования, получаемых на основе многообразных средств познания.
Моделирование - циклический процесс. Это означает, что за первым четырёхэтапным циклом может последовать второй, третий и т. д. При этом знания об исследуемом объекте расширяются и уточняются, а исходная модель постепенно совершенствуется. Недостатки, обнаруженные после первого цикла моделирования, обусловленною малым знанием объекта и ошибками в построении модели, можно исправить в последующих циклах В методологии моделирования, таким образом. заложены большие возможности саморазвития.
Проникновение математики в Экономическую науку связано с преодолением значительных трудностей, лежащих в природе экономических процессов и специфике экономической науки.
Большинство объектов, изучаемых экономической наукой, может быть охарактеризовано кибернетическим понятием - “сложная система”.
Наиболее распространено понимание системы как совокупности элементов, находящихся во взаимодействии и образующих некоторую целостность, единство. Важным качеством любой системы является эмерджентность - наличие таких свойств, которые не присущи ни одному из элементов, входящих в систему. Поэтому при изучении систем недостаточно пользоваться методом их расчленения на элементы с последующим изучением этих элементов в отдельности. Одна из трудностей экономических исследований - в том, что почти не существует экономических объектов, которые можно было бы рассматривать как отдельные (внесистемные) элементы.
Сложность системы определяется количеством входящих в неё элементов, связями между этими элементами, а также взаимоотношениями между системой и средой. Экономика страны обладает всеми признаками очень сложной системы. Она объединяет огромное число элементов, отличается многообразием внутренних связей и связей с другими системами (природная среда, экономика других стран и т. д.). В управлении экономикой взаимодействуют природные, технологические, социальные процессы, объективные и субъективные факторы.
Сложность экономики иногда рассматривалась как обоснование невозможности её моделирования, изучения средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно объект любой природы и. любой сложности, И как раз сложные объекты представляют наибольший интерес для моделирования; именно здесь моделирование может дать результаты, которые нельзя получить другими способами исследования.
Потенциальная возможность математического моделирования любых экономических объектов и процессов не означает, разумеется, её успешной осуществимости при данном уровне экономических и математических знаний, имеющейся конкретной информации и вычислительной технике. И, хотя нельзя указать абсолютные границы математической формализуемости экономических проблем, всегда будут существовать неформализованные ещё проблемы, для которых математическое моделирование недостаточно эффективно.
С экономической точки зрения оптимальные решения, полученные с помощью экономическо-математического моделирования, обладают следующими основными свойствами (рисунок 1.2.)
| | Свойства оптимального решения | | |||
| | | | | | |
| | | | | | |
| | 1. Зависимость от поставленной цели | | | ||
| | | | |||
| | | | | | |
| | 2. Зависимость от текущей хозяйственной обстановки | | | ||
| | | | |||
| | | | | | |
| | 3. Устойчивость базиса оптимального плана относительно малых изменений условий | | | ||
| | | | |||
| | | | | ||
| | 4. Взаимозависимость решений по всем объектам экономики | | | ||
| | | | |||
| | | | | | |
| | 5. Зависимость от уровня управления | | | ||
| | | | |||
Рисунок 1.2. Свойства оптимального решения
1. Оптимальность решения зависит от целей, поставленных при планировании процесса. Например, выбор типа транспорта по критерию стоимости перевозки будет отличаться от выбора по критерию скорости.
2. Оптимальность решения зависит от текущей хозяйственной обстановки (иными словами, оптимум всегда конкретен, его нельзя вычислять абстрактно).
3. Существенные изменения оптимального варианта происходят только при значительных изменениях обстановки - это свойство называется устойчивостью базиса оптимального плана относительно малых изменений условий (т.е. оптимальные решения можно находить достаточно надёжно, несмотря на приблизительный характер почти всей экономической информации).
4. При определении взаимозависимости решений по всем объектам экономики особое значение имеют обратная связь объектов и издержки обратной связи. Например, если предприятия А и Б потребляют один и тот же ограниченный ресурс, то увеличение доли предприятия А уменьшает долю предприятия Б (обратная связь).
Возможно, потребление данного ресурса (сырья, топлива высшего сорта) снижает производственные издержки. Тогда, увеличение доли предприятия А приведёт к экономии на этом предприятии и к дополнительным издержкам на предприятии Б в результате замены ресурса менее эффективным (издержки обратной связи).
5. Оценка рациональности конкретного мероприятия зависит от уровня управления: решение, оптимальное для отдельного предприятия, может быть неоптимальным для отрасли или экономики а целом.
Возможности использования математических моделей для выбора оптимальных решений зависят от типа оптимизируемых процессов и характера решаемых вопросов. Выделяют три типа многовариантных проблем планирования и управления (рисунок 1.3.).
| | Типы проблем планирования и управления | | |||
| | | | | | |
| | | | | | |
| | 1. | Полностью структурированные проблемы: Ø все цели оптимизации и факторы оптимирующего процесса поддаются количественному измерению Ø проблема может быть целиком представлена в виде экономико-математической модели или системы моделей Ø оптимальное решение находится на основе построенной модели некоторым математическим методом | | | |
| | | | |||
| | | | | | |
| | 2. | Частично или слабо структурированные проблемы: Ø менее четко проеделены цели Ø неизвестны количественные зависимости между некоторыми факторами Ø количественному анализу и оптимизации подвергаются отдельные части проблемы | | | |
| | | | |||
| | | | | | |
| | | | | | |
| | 3. | Неструктурированные проблемы: Ø невозможность количественного анализа Ø непредсказуемость факторов | | | |
| | | | |||
Рисунок 1 3. Типы проблем планирования и управления
Объектом для экономико-математического моделирования является полностью структурированные проблемы, характеристики которых приведены в блоке 1 рисунка 1.3. Частично или слабо структурированные проблемы, определяются во втором блоке, является объектами для методов системного анализа, сочетающих неформализованные решения специалистов с модельными расчётами по отдельным предметам.
Неструктурированные проблемы (блок 3) является объектами для экспертных решений, принимаемых на основе опыта и интуиции специалистов
Уже длительное время главным тормозом практического применения математического моделирования в экономике является сложность наполнения разработанных моделей конкретной и качественной информацией. Точность и полнота первичной информации, реальные возможности её сбора и обработки во многом определяют выбор типов прикладных моделей. С другой стороны, исследования по моделированию экономики выдвигают новые требования к системе информации.
В зависимости от моделируемых объектов и назначения моделей используемая в них исходная информация имеет существенно различный характер и происхождение. Она может быть разделена на две категории: о прошлом развитии и современном состоянии объектов (экономические наблюдения и их обработка) и о будущем развитии объектов, включающую данные об ожидаемых изменениях их внутренних параметров и внешних условий (прогнозы). Вторая категория информации является результатом самостоятельных исследований, которые так же могут выполняться посредством моделирования.
Методы экономических наблюдений и использование результатов этих наблюдений разрабатываются эконометрикой. Поэтому стоит отметить только специфические проблемы экономических наблюдений, связанные с моделированием экономических процессов.
В экономике многие процессы являются массовыми, они характеризуются закономерностями, которые не обнаруживаются на основании лишь одного или нескольких наблюдений. Поэтому моделирование в экономике должно опираться на массовые наблюдения.
Другая проблема порождается динамичностью экономических процессов, изменчивостью их параметров и структурных отношений. Вследствие этого экономические процессы приходится постоянно держать под наблюдением, необходимо иметь устойчивый поток новых данных. Поскольку наблюдения за процессами и обработка эмпирических данных обычно занимают довольно много времени, то при построении математических моделей экономики требуется корректировать исходную информацию с учётом её запаздывания.
Познание количественных отношений экономических процессов и явлений опирается на экономические измерения. Точность измерений в значительной степени предопределяет и точность конечных результатов количественного анализа посредством моделирования. Поэтому необходимым условием эффективного использования математического моделирования является совершенствование экономических измерителей. Применение математического моделирования заострило проблему измерений и количественных различных аспектов и явлений социально-экономического развития, достоверности и полноты получаемых данных, их защиты от намеренных и технических искажений.
В процессе моделирования возникает взаимодействие “первичных’ и “вторичных экономических измерителей. Любая модель в экономике опирается на определённую систему экономических измерителей (продукции, ресурсов элементов и т.д.). В то же время одним из важных результатов экономико-математического моделирования является получение новых (вторичных) экономических измерителей - экономически обоснованных цен на продукцию различных отраслей, оценок эффективности разнокачественных природой ресурсов, измерителей общественной полезности продукции. Однако, эти вторичные измерители могут испытывать влияние недостаточно обоснованных первичных измерителей, что вынуждает разрабатывать особую методику корректировки первичных измерителей для экономических моделей.
С точки зрения “интересов” моделирования экономики в настоящее время наиболее актуальными проблемами совершенствования экономических измерителей являются: оценка результатов интеллектуальной деятельности (особенно в сферё научно- технических разработок, индустрии информатики), построение обобщающих показателей экономического развития, измерение эффектов обратных связей (влияние экономических и социальных механизмов на эффективность производства).
Для методологии планирования экономики важное значение имеет понятие неопределённости экономического развития. В исследованиях по экономическому прогнозированию и планированию различают два типа неопределённости:
“истинную”, обусловленную свойствами экономических процессов,
“информационную”, связанную с неполнотой и неточностью имеющейся информации об этих процессах. Истинную неопределённость нельзя смешивать с объективным существованием различных вариантов экономического развития и возможностью сознательного выбора среди них эффективных вариантов. Речь идёт о принципиальной невозможности точного выбора единственного (оптимального) варианта.
В развитии экономики неопределённость вызывается тем, что ход планируемых и управляемых процессов, а также внешние воздействия на эти процессы не могут быть точно предсказаны из-за действия случайных факторов и ограниченности человеческого познания в каждый момент. Особенно характерно это для прогнозирования научно- технического прогресса, потребностей общества, экономического поведения. Неполнота и неточность информации об объективных процессах и экономическом поведении усиливают истинную неопределённость.
На первых этапах исследований по моделированию экономики применились в основном модели детерминистского типа. В этих моделях все параметры предполагаются точно известными. Однако, детерминистские модели неправильно понимать в механическом духе и отождествлять их с моделями, которые лишены всех “степеней выбора” (возможностей выбора) и имеют единственное допустимое решение. Классическим представителем жёстко детерминистских моделей являлась оптимизационная модель народного хозяйства, которая применялась для определения наилучшего варианта экономического развития среди множества допустимых вариантов.
В результате накопления опыта использования жестко детерминистских моделей были созданы реальные возможности успешного применения более совершенной методологии моделирования экономических процессов, учитывающих стохастику и неопределённость. Здесь можно выделить такие основные направления исследований как: усовершенствование методики моделей жестко детерминистского типа, проведение многовариантных расчётов и модельных экспериментов с вариацией конструкции модели и её исходных данных, изучение устойчивости и надежности получаемых решений, выделение зоны неопределённости, включение в модель резервов, применение приёмов, повышающих приспособляемость экономических решений вероятным и непредвиденным ситуациям, а также распространение моделей, непосредственно отражающих сложность и неопределённость экономических процессов и соответствующий математический аппарат: теорию вероятностей и математическую статистику, теорию игр и статистических решений, теорию массового обслуживания, стохастическое программирование, теорию случайных процессов.
1.2. Классификация экономико-математических моделей
Для классификации математических моделей экономических процессов и явлений используются разные признаки (рисунок 1.4.).
По целевому назначению экономико-математические модели делятся на теоретико-аналитические, используемые в исследованиях общих свойств и закономерностей экономических процессов, и прикладные, применяемые в решении конкретных экономических задач (модели экономического анализа, прогнозирования, управления).
При классификации моделей по исследуемым экономическим процессам и содержательной проблематике можно выделить модели макро- и микроэкономики, а также комплексы моделей производства, потребления, формирования и распределения доходов, трудовых ресурсов, ценообразования, финансовых связей и т.д. Остановимся более подробно на характеристике таких классов экономико-математических моделей, с которыми связаны наибольшие особенности методологии и техники моделирования.
| | | | | Признаки классификации экономико-математических моделей | | | | ||||||||||||
| | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | |
| 1. Целевое назначение | | | 2. Иссле-дуемые экономичес-кие процессы и содержа-тельная проб-лематика | | | 3. Функ-циональные и структурный | | | 4. Дескриптив-ные и нормальные | | | 5. Характер отражения причинно-следственных связей | | | |||||
| | | | | | | | | | | | | | | | | | | | |
| 6. Способ отражения фактора времени | | 7. Форма математи-ческих зави-симостей | | 8. Соотно-шение экзо-генных и эндогенных переменных | | 9. Этапность принимаемых решений | | 10. Характер системы ограниченной | |||||||||||
Рисунок 1.4. Признаки классификации экономико-математических моделей
В соответствии с общей классификацией математических моделей они подразделяются на функциональные и структурные, а также включают промежуточные формы (структурно - функциональные). В исследованиях он макроэкономическом уровне чаще применяются структурные модели, поскольку в планировании и управлении большое значение имеют взаимосвязи подсистем. Типичными структурными моделями являются модели межотраслевых связей. Функциональные модели широко применяются в экономическом регулировании, когда на поведение объекта (“выход”) воздействуют путём изменения «входа». Примером может служить модель поведения потребителей в условиях рыночных отношений. Один м тот же объект может описываться одновременно и структурной, и функциональной моделью. Так, например, для планирования отдельной отраслевой системы используется структурная модель, а на макроэкономическом уровне каждая отрасль может быть представлена функциональной моделью.
Следующим признаком является характер модели-дескриптивная или нормативная. Дескриптивные модели отвечают на вопрос: как это происходит? или как это вероятнее всего может дальше развиваться?, т.е. они только объясняют наблюдаемые факты или дают вероятный прогноз. Нормативные модели отвечают на вопрос: как это должно быть?, т.е. предполагают целенаправленную деятельность. Типичным примером нормативных моделей являются модели планирования, формализующие тем или иным способом цели экономического развития, возможности и средства их достижения.
Применение дескриптивного подхода с моделировании экономики объясняется необходимостью эмпирического выявления различных зависимостей в экономике. Установления статистических закономерностей экономического поведения социальных групп, изучения вероятных путей развития каких-либо процессов при не изменяющихся условиях или протекающих без внешних воздействий. Примерами дескриптивных моделей являются производственные функции покупательского спроса, построенные на основе обработки статистических данных.
Является ли экономико-математическая модель дескриптивной или нормативной, зависит не только от её математической структуры, но от характера использования этой модели. Например, модель межотраслевого баланса дескриптивная, если она используется для анализа пропорций прошлого периода. Но эта же математическая модель становится нормативной, когда она применяется для расчётов сбалансированных вариантов развития макроэкономических процессов.
Многие экономико-математические модели сочетают признаки дескриптивных и нормативных моделей. Типична ситуация, когда нормативная модель сложной структуры объединяет отдельные блоки, которые являются частными дескриптивными моделями. Например, межотраслевая модель может включать функции покупательского спроса, описывающие поведение потребителей при изменении доходов. Подобные примеры характеризуют тенденцию эффективного сочетания дескриптивного и нормативного подходов к моделированию экономических процессов, дескриптивный подход широко применяется в имитационном моделировании.
По характеру отражения причинно-следственных связей различают модели жёстко- детерминистские и модели, учитывающие случайность и неопределённость, при этом необходимо различать неопределённость, для описания которой законы теории вероятностей неприменимы. данный тип неопределенности гораздо более сложен для моделирования.
По способам отражения фактора времени экономико-математические модели делятся на статистические и динамические. В статистических моделях все зависимости относятся к одному моменту или периоду времени, динамические модели характеризуют изменения экономических процессов во времени. По длительности рассматриваемого периода времени различаются модели краткосрочного (до года), среднесрочного (до 5 лет), долгосрочного (10-15 и более лет) прогнозирования и планирования. Само время в экономико-математических моделях может изменяться либо непрерывно, либо дискретно.
Модели экономических процессов чрезвычайно разнообразны по форме математических зависимостей. Особенно важно выделить класс линейных моделей, наиболее удобных для анализа и вычислений и получивших вследствие этого большое распространение. Различия между линейными и нелинейными моделями существенны не только с математической точки зрения, но и в теоретико-экономическом отношении, поскольку многие зависимости в экономике носят принципиально нелинейный характер: эффективность использования ресурсов при увеличении производства, изменение спроса и потребления населения при увеличении производства, изменение спроса и потребления населения при росте доходов и т.п.
По соотношению экзогенных и эндогенных переменных, включаемых в модель, они могут разделяться на открытые и закрытые. Полностью открытых моделей не существует; модель должна содержать хотя бы одну эндогенную переменную. Полностью закрытые экономико-математические модели, т.е. не включающие экзогенных переменных, исключительно редки; их построение требует полного абстрагирования от “среды”, т.е. серьёзного упрощения реальных экономических систем, всегда имеющих внешние связи. Подавляющее большинство экономико-математических моделей занимает промежуточное положение, и различаются по степени открытости (закрытости).
В зависимости от этапности принимаемых решений модели бывают одноэтапные и многоэтапные. В одноэтапных задачах требуется принять решение относительно однократно выполняемого действия, а в многоэтапных оптимальное решение находится за несколько этапов взаимосвязанных действий.
В зависимости от характера системы ограничений выделяются модели обычного вида и специальные виды (транспортные, распределительные задачи), отличающиеся более простой системой ограничений и возможностью благодаря этому использовать более простые методы решения.
Таким образом, общая классификация экономико-математических моделей включает более десяти основных признаков. С развитием экономико-математических исследований проблема классификации применяемых моделей усложняется. Наряду с появлением новых типов моделей (особенно смешанных типов) и новых признаков их классификации осуществляется процесс интеграции моделей разных типов в более сложные модельные конструкции.
1.3. Экономико-математическая модель оптимизационной задачи
Обязательными элементами экономико-математической модели оптимизационной задачи являются переменные параметры процесса, ограничения задачи и критерии оптимальности (рисунок 1.5).
| | Элементы математической модели оптимизационной задачи | | ||||||
| | | | | | | | | |
| | | | | | | | | |
| 1. Переменные параметры процесса | | 2. Органические задачи | | 3. Критерий оптимальности | ||||
Рисунок 1.5. Элементы математической модели оптимизационной задачи.
При этом, переменные параметры процесса это - набор неизвестных величин, численные значения которых определяются в ходе решения и используются для рациональной организации процесса, ограничения задачи символическая запись обязательных условий организации данного процесса (как правило, линейные неравенства или уравнения), критерий оптимальности экономический показатель, сведение которого к максимуму или минимуму говорит о наиболее полном достижении целей оптимизации. Запись критерия в виде функции от переменных задачи называется целевой функцией.
| | Типы ограничений | | |
| | | ||
| | | | |
| | 1. | Задания по объему производства | |
| | | ||
| | | | |
| | 2. | Ограничения на объем используемых ресурсов | |
| | | ||
| | | | |
| | 3. | Балансовые соотношения между переменными | |
| | | ||
| | | | |
| | 4. | Специальные условия для защиты интересов отдельных предприятий | |
| | | ||
| | | | |
| | 5 | Требование типизации и стандартизации технического оснащения технических процессов (условия связности) | |
| | | ||
Рисунок 1.6. Типы ограничений
Правильное установление Ограничений является важным этапом разработки оптимизационной экономико-математической модели. При этом следует избегать двух крайностей: переусложение модели, которое затрудняет подготовку данных и процесс решения и переупрощение модели, которое может привести к получению модели, неадекватной реальному процессу. Типы ограничений показаны на рисунке 1.6.
В большинстве оптимизационных задач соблюдается принцип единственности критерия. При выборе критерия оптимальности учитывается ряд общих требований (рисунок 1.7.).
В качестве критерия оптимальности могут быть приняты только те показатели, которые поддаются вычислению для каждого возможного варианта с ошибкой не более 2-3%, иначе сравнение вариантов становятся ненадежным.
Сложность экономических процессов и явлений и другие отмеченные выше особенности экономических систем затрудняют не только построение математических моделей, но и проверку их адекватности, истинности получаемых результатов.
Можно привести следующие примеры локальных критериев оптимальности: предположим, предприятие выпускает дефицитную продукцию, в этом случае цепь оптимизации - максимальное увеличение выпуска, а локальным критерием может служить максимальный выпуск продукции с единицы производственной мощности.
Если производственные мощности предприятия достаточны для полного удовлетворения потребностей в выпускаемой продукции, то при оптимизации выбирается наилучший вариант организации производства и возможный локальный критерий оптимальности в этом случае - получаемая прибыль.
| Требования к локальному критерию оптимальности | |||||||
| | | | | | | ||
| | | | | | | ||
| 1. Соответствие глобальному критерию | | | 2. Учет экономического последствия принимаемых решений | ||||
| | | | | | | ||
| | | | | | | ||
| 3. Исключение одинаковых по величине издержек | | | 4. Учет реальной хозяйственной обстановки данного периода | ||||
Рисунок 1.7. Требования к локальному критерию оптимальности
Если объём производства задан и не подлежит вариации, то при оптимизации критерием могут служить издержки (в стоимостном выражении) или минимум расхода какого- либо дефицитного ресурса.
В естественных науках достаточным условием истинности результатов моделирования и любых других форм познания является совпадение результатов моделирования с наблюдаемыми фактами. Категория “практика” совпадает здесь с категорией «действительность». В экономике и других общественных науках понимаемые таким образом принцип “практика - критерий истины” в большей степени применим к простым дескриптивным моделям, используемым для пассивного описания и объяснения действительности (анализа прошлого развития краткосрочного прогнозирования неуправляемых экономических процессов и т.п.)
Однако, основная задача экономической науки конструктивно разработка научных методов планирования и управления экономикой. Поэтому распространённый тип математических моделей экономики – это модели управляемых и регулируемых экономических процессов используемые для преобразования экономической действительности. Такие модели называются нормативными. Если ориентировать нормативные модели только на подтверждение действительности то они не смогут служить инструментом решения качественно новых экономических задач.
Специфика верификации нормативных моделей экономики состоит в том, что они, как правило, “конкурируют” с другими уже нашедшим практическое применение методами планирования и управления. При этом далеко не всегда можно поставить чистый эксперимент по верификации модели, устранив влияние других управляющих воздействий на моделируемый объект.
Ситуация ещё более усложняется когда ставится вопрос о верификации моделей долгосрочного прогнозирования и планирования (как дескриптивных, так и нормативных) Ведь нельзя же 10-15 лет и более пассивно ожидать наступления событий, чтобы проверить правильность предпосылок модели.
Несмотря на отмеченные усложняющие обстоятельства, соответствие модели фактам и тенденциям реальной экономической жизни остаётся важнейшим критерием определяющим направления совершенствования моделей. Всесторонний анализ выявляемых расхождений между действительно и моделью. сопоставление результатов по модели с результата полученными иными методами, помогают выработать пути коррекции моделей.
Значительная роль в проверке моделей принадлежит логическому анализу, в том числе средствами самого математического моделирования. Такие формализованные приёмы верификации моделей, как доказательство существование решения модели, проверка истинности статистических гипотез о связях между параметрами и переменными модели, сопоставления размерности величин и т.д., позволяют сузить класс потенциально “правильных” моделей
Внутренняя непротиворечивость предпосылок модели проверяется также путём сравнения друг с другом получаемых с её помощью следствий, а также со следствиями “конкурирующих” моделей.
Оценивая современное состояние проблемы адекватности математических моделей экономики, следует признать, что создание конструктивной комплексной методики верификации моделей, учитывающей как объективные особенности моделируемых объектов, так и особенности их познания. по- прежнему является одной из наиболее актуальных задач экономико-математических исследований.
1.4. Этапы экономико-математического моделирования
Рассмотрим последовательность и содержание этапов одного цикла экономико-математического моделирования (рисунок 1.8.)
1. Постановка экономической проблемы п её качественный анализ.
Главное задача этого этапа – чётко сформулировать сущность проблемы, принимаемые допущения и те вопросы, на которые требуется получить ответы. Этап включает выделение важнейших черт и свойств моделируемого объекта и абстрагирование от второстепенных; изучение структуры объекта, основных зависимостей, связывающих его элементы; формирование гипотез (хотя бы предварительных), объясняющих поведение и развитие объекта.
2. Построение математической модели.
Это этап формализации экономической проблемы, выражения её в виде конкретных математических зависимостей и отношений (функций, уравнений, неравенств и т.д.). Обычно, сначала определяется основная конструкция (тип) математической модели, а затем уточняются детали этой конструкции (конкретный перечень переменных и параметров, форма связей). Таким образом, построение модели подразделяется в свою очередь на несколько стадий.
Неправильно полагать, что, чем больше фактов учитывает модель, тем она лучше “работает” и даёт лучшие результаты. То же можно сказать о таких характеристиках сложности модели, как используемые формы математических зависимостей (линейные и нелинейные), учёт факторов случайности и неопределённости и т.д. Излишняя сложность и громоздкость модели затрудняют процесс исследования. Нужно учитывать не только реальные возможности информационного и математического обеспечения но и сопоставлять затраты на моделирование с получаемым эффектом (при возрастании сложности модели прирост затрат может превысить прирост аффекта).
| | Этапы экономико-математического моделирования | | ||
| | | |||
| | | | | |
| | 1. Постановка экономической проблемы | | ||
| | | |||
| | | | | |
| | 2. Построение математического моделирования | | ||
| | | | | |
| | 3. Математический анализ модели | | ||
| | | | | |
| | 4. Подготовка исходной информации | | ||
| | | | | |
| | 5. Решение задачи | | ||
| | | | | |
| | 6. Анализ численных результатов и их применение | | ||
Рисунок 1.8. Этапы экономико-математического моделирования
Одна из важных особенностей математических моделей – потенциальная возможность их использования для решения разнокачественных проблем. Поэтому, даже сталкиваясь с новой экономической задачей, не нужно стремиться “изобретать” модель вначале необходимо попытаться применить для решения этой задачи уже известные модели.
В процессе построения модели осуществляется взаимосопоставление двух систем научных знаний – экономических и математических. Естественно стремиться к тому, чтобы получить модель, принадлежащую хорошо изученному классу математических задач. Часто это удаётся сделать путём некоторого упрощения исходных предпосылок модели, не искажающих существенных черт моделируемого объекта. Однако возможна и такая ситуация, когда формализация экономической проблемы приводит к неизвестной ранее математической структуре. Потребности экономической науки и практики в середине ХХ в. способствовали развитию математического программирования, теории игр, функционального анализа, вычислительной математики. Вполне вероятнее’ что в будущем развитие экономической науки станет важным стимулом для создания новых разделов математики.
3. Математический анализ модели.
Целью этого этапа является выяснение общих свойств модели, для чего применяются математические приёмы исследования. Наиболее важный момент- доказательство существования решений в сформулированной модели (теорема существования).. Если удастся доказать, что математическая задача не имеет решения, то необходимость в последующей работе по первоначальному варианту модели отпадает; следует скорректировать либо постановку экономической задачи, либо способы её математической формализации. При аналитическом исследовании модели выясняются такие вопросы, как, например, единственно ли решение, какие переменные (неизвестные) могут входить в решение, каковы будут соотношения между ними, в каких пределах и в зависимости от каких исходных условий они изменяются, каковы тенденции их изменения и т.д. Аналитическое исследование модели по сравнению с эмпирическим (численным) имеет то преимущество, что получаемые выводы сохраняют свою силу при различных конкретных значениях внешних и внутренних параметров модели.
Знание общих свойств модели имеет важное значение, но модели сложных экономических объектов с большим трудом поддаются аналитическому исследованию. В тех случаях, когда аналитическими методами не удаётся выяснить общих свойств модели, а упрощение модели приводит к Недопустимым результатам, переходят к численным методам исследования.
4. Подготовка исходной информации
Моделирование предъявляет жёсткое требования к системе информации. В то же время реальные возможности получения информации ограничивают выбор моделей, предназначаемых для практического использования. При этом принимается во внимание не только принципиальная возможность подготовки информации (за определенные сроки), но и затраты на подготовку соответствующих информационных массивов. Эти затраты не должны превышать эффект от использования дополнительной информации.
В процессе подготовки информации широко используется методы теории вероятностей, теоретической и математической статистики. При системном экономико-математическом одел исходная информация, используемая в одних моделях, является результатом функционирования других моделей.
5. Численное решение.
Этот этап включает разработку алгоритмов для численного решения задачи, подбор необходимого программного обеспечения и непосредственное проведение расчётов. Трудности этого этапа обусловлены прежде всего большой размерностью экономических задач и необходимостью обработки значительных массивов информации.
Обычно расчёты по экономико-математической модели носят многовариантный характер. Благодаря высокому быстродействию современных компьютеров удаётся проводить Многочисленные “модельные” эксперименты, изучая “поведение” модели при различных изменениях некоторых условий. Исследование, проводимое численными методами, может существенно дополнить результаты аналитического исследования, а для многих моделей оно является единственно осуществимым. Класс экономических задач, которые можно решать численными методами, значительно шире, чем класс задач, доступных аналитическому исследованию.
6. Анализ численных результатов п их применение.
На этом заключительном этапе цикла встаёт вопрос о правильности и полноте результатов моделирования, о степени практической применимости последних.
Математические методы проверки могут выявлять некорректные построения модели и тем самым сужать класс потенциально правильных моделей. Неформальный анализ теоретических выводов и численных результатов, получаемых посредством модели, сопоставление их с имеющимися знаниями и фактами действительности также позволяют обнаруживать недостатки постановки экономической задачи, сконструированной математической модели, её информационного и математического обеспечения.
Обратим внимание на обратные связи этапов моделирования (на рис. 1.8.), возникающие вследствие того, что в процессе исследования обнаруживаются недостатки предшествующих этапов процесса.
Уже на этапе построения модели может выясниться, что постановка задачи противоречива или приводит к слишком сложной математической модели. В соответствии с этим исходная постановка задачи корректируется. далее, математический анализ модели (этап 3) может показать, что небольшая модификация постановки задачи или её формализации даёт интересный аналитический результат.
Наиболее часто необходимость возврата к предшествующим этапам моделирования возникает при подготовке исходной информации (этап 4). Может обнаружиться, что необходимая информация отсутствует или же затраты на её подготовку слишком велики. Тогда приходится возвращаться к постановке задачи и её формализации, изменяя их так, чтобы приспособиться к имеющейся информации.
Недостатки, которые не удаётся исправить на промежуточных этапах моделирования, устраняются в последующих циклах. Но результаты нашего цикла имеют и вполне самостоятельное значение. Начав исследование с построения простой модели, можно быстро получить полезные результаты, а затем перейти к созданию более совершенной модели, дополняемой новыми условиями, включающей уточнённые математические зависимости.
По мере развития и усложнения экономико-математического моделирования его отдельные этапы обособляются в специализированные области исследований, усиливаются различия между теоретико-аналитическими и прикладными моделями, происходит дифференциация моделей по уровням абстракции и идеализации.
Теория математического анализа моделей экономики развивалась в особую ветвь современной экономической науки- математическую экономику, ценность моделей которой для экономической теории и практики состоит в том, что они служат теоретической базой для моделей прикладного типа.
Довольно самостоятельными областями исследований является подготовка и обработка экономической информации и разработка математического обеспечения для решения экономических задач (создание баз данных и банков информации, программ автоматизированного построения моделей и программного сервиса для экономистов- пользователей). На этапе практического использования моделей ведущую роль должны играть специалисты в соответствующей области экономического анализа, планирования, управления. Главным участком работы экономистов- математиков остаётся постановка и формализация экономических задач и синтез процесса экономико-математического Моделирования.
Следует выделить четыре основных ,аспекта применения математических методов в решении практических проблем.
1. Совершенствование системы экономической информации. Математические методы позволяют упорядочить систему экономической информации, выявлять недостатки в имеющейся информации и вырабатывать требования для подготовки новой информации или её корректировки. Разработка и применение экономико-математических моделей указывают пути совершенствования экономической информации, ориентированной на решение определённой системы задач планирования и управления. Прогресс в информационном обеспечении планирования и управления опирается на бурно развивающиеся технические и программные средства информатики.
2. Интенсификация и повышение точности экономических расчётов. Формализация экономических задач и применение компьютеров многократно ускоряют типовые, массовые расчёты, повышают точность и сокращают трудоёмкость, позволяют проводить многовариантные экономические обоснования сложных мероприятий.
3. Углубление количественного анализа экономических проблем, Благодаря применению метода моделирования значительно усиливаются возможности конкретного количественного анализа: влияния многих факторов на экономические процессы, количественная оценка последствий изменения условий развития экономических объектов и т.п.
4. Решение принципиально новых экономических задач. Посредством математического моделирования удаётся решать такие экономические задачи, которые иными средствами решать практически невозможно.
В области планирования и управления работой железнодорожного транспорта можно выделить следующие проблемы, при решении которых методы моделирования дают наиболее очевидный эффект:
o планирование грузовых перевозок, оптимальное прикрепление потребителей к поставщикам, оптимальное распределение перевозочной работы между видами транспорта;
o рациональное распределение грузопотоков и вагонопотоков по параллельным линиям, особенно при ограниченной пропускной способности; оперативное маневрирование поездопотоками;
o оптимальное регулирование вагонных парков, включая комплексное управление парками с учётом взаимозаменяемости вагонов;
o текущее планирование использования специализированных видов вагонов и контейнеров;
o организация вагонопотоков, выбор оптимальных вариантов плана формирования поездов, распределение сортировочной работы между станциями;
o оптимизация работы перевалочных узлов разных видов транспорта (максимизация перерабатывающей способности, сведение к минимуму простоев подвижного состава);
o определение оптимальных резервов локомотивов и вагонов и их оптимальное размещение на сети;
o размещение, специализация и кооперирование обслуживающих устройств транспорта (локомотивных и вагонных депо, ремонтных заводов, пунктов промывки вагонов, материальных складов и т.д.);
o оптимальное распределение заданий между разными типами взаимозаменяемого оборудования – станочного парка заводов и дело, грузовых механизмов, путевых и строительных машин;
o оптимизация размеров, размещения и использования материальных запасов вместимости складов, размеров оборотных средств;
o оптимальное календарное планирование строительных, ремонтных проектных и других работ сетевыми методами;
o оптимизация развития транспортной сети на перспективу с целью освоения предстоящих перевозок при минимальных затратах.
Сфера практического применения метода моделирования ограничивается возможностями и эффективностью формализации экономических проблем и ситуаций, а также состоянием информационного, математического, технического обеспечения используемых моделей. Стремление во что бы то ни стало применить математическую модель может не дать хороших результатов из-за отсутствия хотя бы некоторых необходимых условий.
В соответствии с современными научными представлениями системы разработки и принятия экономических решений должны сочетать формальные и неформальные методы, взаимоусиливающие и взаимодополняющие друг друга.
Глава 2.
ПОИСК ОПТИМАЛЬНЫХ РЕШЕНИЙ С ПОМОЩЬЮ ЛИНЕЙНЫХ
ТРАНСПОРТНЫХ ЗАДАЧ
Одной из главных задач макроэкономической науке является разработка различных методов наилучшего распределения ограниченных трудовых, материальных, финансовых, временных и других ресурсов для оптимального управления предприятиями. Наиболее подходящем инструментом решения проблем оптимизации является линейное программирование – один из разделов математического программирования.
Линейное программирование – это метод поиска неотрицательных значений переменных, максимизирующих или минимизирующих значение линейной целевой функции при наличии ограничений, заданных в виде линейных неравенства.
Метод нахождения решения основной задачи линейного программирования, получивший название “симплексный метод” или “метод решения с помощью мультипликатора”, независимо друг от друга открыли в 1940г. советский учёный Л.В. Канторович и американский математик Дж. Данциг.
Разновидностью общей задачи линейного программирования является так называемая транспортная задача, применяемая как для оптимизации перевозки грузов, таки в ряде друг их приложений.
2.1. Постановка линейной транспортной Задачи
Формальным признаком транспортной задачи является то, что каждая переменная входит лишь в два ограничения, причем с коэффициентами, равными единице. Если при этом критерий оптимальности (сумма расходов, общий пробег) прямо пропорционален значениям переменных (транспортных потоков), возникает линейная транспортная задача. В других случаях рассматривается нелинейная транспортная задача, решаемая другими методами.
Транспортные задачи известны в двух постановках: матричной и сетевой.
Матричная:
Пусть имеется ряд пунктов потребления и предприятий-поставщиков некоторой продукции.
Дано:
Аi – ресурс i-го поставщика (запас продукции или план отгрузки из текущего производства).
Вi – потребности в той же продукции в пунктах j.
Сi – расстояние или стоимости перевозки из i в j.
Требуется найти такие размеры поставок от каждого поставщика каждому потребителю Хi (переменные задачи), при которых общая сумма расходов или общий пробег будут минимальными.
Различают следующие разновидности транспортных задач (рисунок 2.1.)
Система ограничений закрытой задачи: предусматривает поставку каждому потребителю количество продукции, равного потребности в ней (2.1.) и вывоз продукции от каждого поставщика в количестве, равном ее ресурсу (2.2.)
Σ Хij = Bi (j=1,2, … n); (2.1)
Σ Xij = Ai (i= 1,2, … m); (2.2)
| | | Типы транспортных задач | | | |||
| | | | | | | | |
| | | | | | | | |
| ΣАi = ΣBj | | ΣАi > ΣBj | | ΣАi < ΣBj | |||
| | | | | | | | |
| Закрытая задача | | Открытая задача с превышением ресурсов | | Открытая задача с превышением потребностей | |||
| | | | | | | | |
| Применение: В текущем планировании | | Применение: Для оптимизации перспективного планирования | | Применение: Может быть составной частью сложных оптимизированных задач | |||
Рис. 2.1. Разновидности транспортных задач
В открытой задаче с превышением ресурсов возможен вывоз меньше наличия:
Σ Xij < Ai (i=1,2, …m ), где
m – отправители;
n – получатели.
Каждая конкретная переменная входит в два условия: типа (2.1) для данного потребителя и типа (2.2) для данного поставщика.
Критерием оптимальности решения является минимум общих расходов по перевозке или с пробега в тонно-километрах (вагоно-километрах) по всем планируемым корреспонденциям. Если стоимость перевозки (расстояние) от i до j - обозначить как Сij то целевая функция определится следующим образом:
F = Σ Σ Cij Xij → min
Транспортная задача в этой постановке решается на матрице, в строках которой показываются поставщики, в столбцах – получатели, а в клетках (пересечениях)- корреспонденции между ними.
Сетевая задача:
Оптимальное планирование перевозок может быть произведено непосредственно на схеме сети путей сообщения (рисунок 2.2). Схема состоит из (или дуг) и узлов (или вершин). Вершинами являются пункты или (центры агрегации) погрузки и выгрузки а также все реальные узловые пункты сети.
Вершины без погрузки и выгрузки данного груза являются транзитными.
Каждый участок (звено) сети между двумя соседними вершинами обычно рассматривают как две дуги противоположного направления с движением в одну сторону по каждой дуге.
| Г |
Рисунок 2.2. Схеме транспортной сети
-8 Д - Пункты и размеры прибытия
- линии соединения – «дуги» или «звенья»
- стрелка – поток груза
ХАВ = 8 - размер груза
Каждая дуга характеризуется показателем расстояния (или стоимости) перевозки единицы груза- или длиной дуги. При решении задач по критерию стоимости длины прямой и обратной дуг обычно различны (т.к. издержки перевозки по участку “туда” и “обратно” не совпадают).
Переменными сетевой транспортной задачи являются потоки груза по каждой дуге. Поток может включать много отправок, например, поток по дуге Б-Д включает поставки из Б в Д – 8 единиц груза, а из Б в Г – 7 единиц груза.
до решения, как правило, неизвестно, в какую сторону будет перевозиться груз по участку в оптимальном варианте. поэтому в число переменных включаются потоки в обоих направлениях, а общее число переменных принимается равным удвоенному числу участков сёти. (При значительном числе поставщиков и получателей число переменных при сетевой постановке значительно меньше чем при матричной, что облегчает решение задачи, Например, при наличии на сети 600 участков, 50 пунктов отправления и 200 пунктов назначения, число переменных при сетевой постановке составит 1200 (6002), а при матричной постановке оно будет гораздо больше (200*50=10000 переменных).
Обязательным условием сетевой задачи является требование балансировки прибытия и отправления груза в каждой вершине сети: прием груза со всех направлений плюс собственная погрузка равны сдаче на все направления собственная выгрузка:
Σ Xks – Σ Xkr = Rk (2.3)
где К – произвольная вершина;
Rk – погрузка (+) или выгрузка (-) (Rk -О для транзита);
Хks – потоки от К по всем соседним вершинам S;
Хkr – потоки к К от соединительных вершин r;
Целевая функция закрытой сетевой задачи имеет вид:
F = Σ Crs Xrs → min (2.4)
Суммирование выполняется по всем дугам сети.
Итак, сетевая транспортная модель включает в себя:
а) расчетную транспортную сеть
б) переменные Хrs для каждой дуги
в) уравнение (2.3) для каждой вершины
г) целевую функцию (2.4) с коэффициентами Сrs, равными расстояниям или показателям стоимости перевозок по дугам сети.
Описанная модель сетевой задачи не учитывает пропускной способности участков сети - для этого вводится дополнительное ограничение:
Хrs < drs (2.5)
где drs – пропускная способность участка сети r-s в направлении от r к s.
С учетом (2.5) получаем сетевую транспортную задачу с ограничением пропускной способности в простейшем виде (для перевозки одного груза).
Сетевая и матричная модели в большинстве случаев взаимозаменяемы.
Но есть и особые ситуации, так, например, при большом числе потребителей и поставщиков преимущество имеет сетевая постановка задачи; эта же форма применяется при оптимизации перевозок с учетом ограничений пропускной способности участков транспортной сети.
Оптимизацию планирования перевозок взаимозаменяемых грузов удобнее производить в матричной форме и т.д.
Критерии оптимальности:
Выбор критерия зависит от: характера проблемы, наличной информации и требуемой точности нахождения оптимума.
Примерами локального критерия оптимальности транспортной задачи могут служить:
а) критерий минимума суммарного пробега (пригоден только для решения закрытых транспортных задач в пределах одного вида транспорта).
б) при оптимизации перевозок в пределах года обычным стоимостным критерием является сумма зависящих приведенных расходов:
С = Эзав + Эпер + Еn (Кпс + Cгр)
где Эзав – зависящие от движения эксплуатационные расходы;
Кпс – капитальные вложения в подвижной состав;
Сгр – стоимость грузов, находящихся в процессе перевозки;
Эпер – издержки по перевалкам.
в) При составлении оптимальных схем перевозок на перспективу возможно усиление пропускной способности линий в зависимости от размещения на них оптимальных грузопотоков. Поэтому в критерии оптимальности учитывается:
Кпост. – затраты на необходимое развитие пропускной способности по постоянным устройствам;
Энез – независящие эксплуатационные расходы.
С = Эзав + Энез + Еп + (Кпс + Кпост. + Сгр)
г) в некоторых случаях при решение открытых транспортных задач допускается использование в качестве критерия - суммы издержек производства и тарифных плат за перевозки.
д) в отдельных задачах по оптимизации срочных перевозок в качестве критерия выступает время: тонно-часы (вагоны-часы) пребывания груза в процессе перевозки или общее время завершения определенной перевозочной операции.
2.2. Решение матричных транспортных задач методом условно-оптимальных планов
Из многих методов решения матричных задач наиболее распространенными является
o метод потенциалов (Канторович П.А. и Говорин М.В.)
o метод условно- оптимальных планов (Лурье А.Л.)
Метод условно- оптимальны планов относится к методам сокращения невязок:
o в начальном варианте допускается нарушение основных ограничений транспортной задачи;
o Σ Хij = Bi (j=1,2, … n);
o Σ Xij = Ai (i= 1,2, … m);
o допущенные невязки и разбалансировки устраняются путем внесения ряда поправок.
Основные этапы метода условно- оптимальных планов рассмотрим на примере некоторой транспортной задачи (таблицы 2.1.), требующей увязать ресурсы трёх поставщиков А1, А2, АЗ,А4 (строки таблицы 2.1.) с потребностями четырёх потребителей В1÷В6 (столбцы таблицы 2.1). В правых верхних углах клеток матрицы 2.1 показаны, стоимости перевозки Сij единицы груза от поставщика Аi и потребителя Вj — оптимальное решение будет получено за четыре этапа решения, которые называются приближениями задачи и также показаны в таблице 2.1
Каждый этап решения состоит из следующих девяти шагов (пунктов):
Порядок вычислений
1. Построение начального варианта.
В каждом столбце матрицы (2.1) находится клетка с минимальной стоимостью:
Сkj = min Сij
В эту клетку заносится поставка, равная полной потребности столбца:
Xki = Bij
При наличии нескольких клеток с минимальной стоимостью поставка Bi распределяется между ними произвольно.
В таблице 2.1 для первого, второго и третьего столбца минимальные стоимости обнаружены в первой строке (390, 220, 130), для четвертого, пятого и шестого столбца – во второй строке (160, 430, 420).
2. Определение сумм поставок в невязках
Находятся суммы поставок по каждой строке ΣХij и разности между ресурсами поставщиков и предусмотренными поставками
Ri = Ai – Σ Xij
Разности R называются невязками или разбалансами Так, в таблице, в приближение № 1 разбалансы показаны в последнем столбце и равны для четырёх поставщиков соответственно -183, -67, +100, +150.
Приближение № 2 (-83, -67, -0, +150)
Приближение № 3 (-56, -67, -0, +123)
Приближение № 4 ( -56, -25, -0, +81)
Приближение № 5 ( 0, -25, -0, +25)
Приближение № 6 ( 0, 0, 0, 0)
3. Проверка наличия отрицательных разбалансов.
Отсутствие. отрицательных разбапансов говорит об оптимальности найденного варианта решения (прибл. № 6). в приближение № 1 таблицы 2.1. первая строка. имеет отрицательный раэбаланс -183, поэтому поиск оптимального решения будет продолжен.
4. Классификация строк.
Строка i считается абсолютно недостаточной, если её разбаланс отрицательный и абсолютно избыточной если разбаланс положительный. При R=0 строки классифицируются на относительно избыточные и относительно недостаточные. В приближение № 1 (таблицу 2.1.) 1-я, 2-я строки абсолютно недостаточные, 3-я, 4-я строки абсолютно избыточные.
Приближение № 2 - 1-я, 2-я строки абсолютно недостаточные, 3-я, 4-я строки абсолютно избыточные.
Приближение № 3 - 1-я, 2-я и 3-я строки абсолютно недостаточные, 4-я строка абсолютно избыточна.
Приближение № 4 - 1-я, 2-я и 3-я строки абсолютно недостаточные, 4-я строка абсолютно избыточна.
Приближение № 5 - 1-я строка абсолютно достаточна; 2-я и 3-я строки абсолютно недостаточные, 4-я строка абсолютно избыточна.
Приложение № 6 – все строки достаточны.
5. Преобразование матрицы стоимостей.
- включает в себя следующие действия:
а) В каждом столбце, имеющем поставку в недостаточной строке, находится минимальная из стоимостей на пересечении с избыточными строками:
Сrj = min Сij
I є U , где U – множество абсолютно и относительно избыточных строк.
Например: в приближение № 1 в первом столбце наименьшая стоимость по избыточным строкам:
Сr1 = min (970, 1090)=970.
Во втором столбце наименьшая стоимость по избыточным строкам С r2 (1120,1260) = 1120, в третьем Сr3, (1090, 1190)=1090. В четвертом, пятом, шестом столбцах Сrj min по избыточным строкам не определяется, т.к. эти столбцы не имеют поставки в единственной недостаточной первой строке.
Приближение № 2 в 1-ом столбце наименьшая стоимость по избыточным строкам:
Сr1 = min (1090)=1090.
Во втором столбце наименьшая стоимость по избыточным строкам С r2 (1260) = 1260, в третьем Сr3, (1190)=1190.
Приближение № 3 в 3-ем столбце наименьшая стоимость по избыточным строкам:
Сr3 = min (940)=940.
В четвертом столбце наименьшая стоимость по избыточным строкам С r4 (1210) = 1210, в пятом Сr5, (1160)=1160.
Приближение № 4 во 2-ом столбце наименьшая стоимость по избыточным строкам:
Сr2 = min (1260)=1260.
В третьем столбце наименьшая стоимость по избыточным строкам С r3 (1190) = 1190.
Приближение № 5 во 4-ом столбце наименьшая стоимость по избыточным строкам:
Сr4 = min (1760, 940)=940.
В пятом столбце наименьшая стоимость по избыточным строкам С r5 (1480, 1210) = 1210.
б) в каждом столбце, имеющем поставку в недостаточной строке, определяется разность между минимальной стоимостью по избыточным строкам и минимальной стоимостью по столбцу в целом.
Δj = Crj – Ckj
Значение Δj фиксируется во вспомогательной строке (строка в таблице 2.1.)
Например, в приближение № 1 в первом столбце Δj = 970-390 = 580, во втором стелбце Δj = 1120-220 = 900, в третьем столбце Δj = 1090-130 =960. В четвертом, пятом, шестом столбцах значение Δ не определяется т.к. поставка находится в избыточной строке.
Приложение № 2 в первом столбце Δj = 1090-970 = 120, во втором столбце Δj = 1260-800 = 460, в третьем столбце Δj = 1190-710 = 480. В четвертом, пятом, шестом столбцах значение Δ не определяется.
Приложение № 3 в четвертом столбце Δj = 940-860 = 80, в пятом столбце Δj = 1210-1130 = 80, в шестом столбце Δj = 1160-1120 = 40. В первом, втором, третьем столбцах значение Δ не определяется.
Приложение № 4 во втором столбце Δj = 1260-960 = 300, в третьем столбце Δj = 1190-870 = 320. В первом, четвертом, пятом, шестом столбцах значение Δ не определяется.
Приложение № 5 в четвертом столбце Δj = 1760-1200 = 560, в пятом столбце Δj = 1480-1470 = 10. В первом, втором, третьем, шестом столбцах значение Δ не определяется.
Приложение № 6 – значение Δ не определяется.
в) находится наименьшее значение из всех Δj
Δ = min Δj, которое прибавляется по всем стоимостям во всех недостаточных строках.
Так, для приближения № 1 получаем:
Δ = min (580, 900, 960) = 580
Все стоимости в недостаточной первой строке увеличиваю на Δ=580, в остальных не меняются. Значения стоимостей на этом этапе решения показываются дробью в правом верхнем углу клеток в недостаточных строках, причём в числителе дроби – первоначальное значение стоимости, в знаменателе – обновлённое в соответствии с шагом 5 алгоритма решения задачи.
Для приближения № 2 - Δ = min (120, 460, 480) = 120
Для приближения № 3 - Δ = min (80, 80, 40) = 40
Для приближения № 4 - Δ = min (300, 320) = 300
Для приближения № 5 - Δ = min (560, 10) = 10
Для приближения № 6 – не определяется
6. Нахождение связей строк, возникших в результате преобразования стоимостей в пункте 5.
Строка S считается связанной со строкой t при соблюдении 2-ух условий:
а) в каком-либо столбце d имеется совпадение стоимостей
Сsd = Ctd
б) в клетке sd имеется поставка
Xsd > 0
При этих условиях существует направленная связь клеток
sd → td
При ручном выполнение расчетов связи удобно показывать стрелками на матрице.
Смысл понятия связи строк следующий. В рассматриваемом методе допустимыми для поставок являются клетки матриц с минимальными по столбцу стоимостями. После изменения стоимостей в матрице появляется новая допустимая клетка (иногда несколько), в которую может быть перенесена часть поставки из недостаточной строки.
Связь строк указывает возможное направление переноса поставки. Так, в приближение № 1 после изменения стоимостей в первой строки клетка 3.1 стала допустимой. Это означает возможность переноса поставки из клетки 1.1 в клетку 3.1 , те. наличие связи между этими строками.
Приложение № 2 – из клетки 1.1 в клетку 4.1
Приложение № 3 – из клетки 2.6 в клетку 4.6
Приложение № 4 – из клетки 1.2 в клетку 4.2
Приложение № 5 – из клетки 2.5 в клетку 1.5 и из клетки 1.2 в клетку 4.2
Приложение № 6 – не определяется.
7. Нахождение после последовательности (цепи) связей между абсолютно недостаточной и любой избыточной строками.
Цепь может состоять из одной или несколько связей и возникает после исполнения пункта 6. В нее всегда входит вновь образованная в этом пункте связь, начиная от которой удобно вести поиск цепи.
Например, в приближение № 5 новая связь появилась между клетками 2.5 и 4.2.; от прежнего цикла (приближения) осталась связь клетки 1.2 и 4.2, Цепь от абсолютно недостаточной первой строки до избыточной второй строки проходит по клеткам 2.5-1.5. и 1.2-4.2. В приближение № 1 цепь состоит лишь из одной связи 1.1-3.1, т.к. эта связь начинается в абсолютно недостаточной и кончается в избыточной строке.
Приложение № 2 – цепь между клетками 1.1 – 4.1
Приложение № 3 – цепь между клетками 2.6 – 4.6
Приложение № 4 – цепь между клетками 1.2 – 4.2
Приложение № 6 – не определяется.
8. Определение величины переноса поставок ΔХ, выполняемого одновременно по всем связям найденной цепи.
Эта величина равняется наименьшему, из следующих чисел:
o абсолютному значению разбаланса в недостаточной строке, где цепь начинается;
o разбалансу в избыточной строке, где цепь кончается;
o значению поставок во всех клетках, где начинаются связи, входящие в цепь.
ΔХ = min [ │Rнач │; │Rкон │; Xij ]
Хij – поставки в нечетных клетках цепи, если переписать их в порядке от недостающей строки к избыточной
Rнач, Rкон – невязки в строках, где начинает и кончается цепь переноса поставок.
Например, величина переноса по цепи, найденной в приближение № 1
ΔХ = min (183, 100, 127) = 100,
а по цепи, найденной в приближение № 5:
ΔХ = min (25, 25, 35) = 25.
Приближение № 2 – ΔХ = min (83, 150, 27) = 27.
Приближение № 3 – ΔХ = min (67, 123, 42) = 42.
Приближение № 4 – ΔХ = min (56, 81, 99) = 56.
Приближение № 6 – не определяется.
9. Перенос поставок.
Найденное значение ΔХ вычитается из поставок во всех нечетных по порядку клетках цепи и добавляется к поставкам во всех четных, В результате получается новый вариант плана, либо оптимальный, либо с меньшей по модулю суммой отрицательных разбалансов, чем предыдущий вариант. Далее метод условно оптимальных планов предполагает переход к шагу 2 и циклическое продолжение шагов алгоритма до тех пор, пока в цикле не обнаружится, что отрицательных разбапансов больше нет и найденное решение оптимально.
Так, в приближение № 1 переносится 100 единиц поставок из клетки 1,1 в клетку 3.1. и происходит переход к приближению № 2.
При выполнении пункта 9 во втором приближение 27 единиц поставок переносятся из клетки 1.1 в клетку 4.1 и происходит переход к приближению 3. В третьем приближение 42 единицы поставок переносится из клетки 2.6 в клетку 4.6; в четвертом приближении 56 единиц поставок переносятся из клетки 1.2 в 4.2; в пятом приближении 25 единиц поставок переносятся из клетки 5.2 в 2.4 (цепь 2.5-1.5 – 1.2-4.2). Полученное в результате шестого приближение после проверки на шаге 3 алгоритма решения оказывается оптимальным.
Решение матричной транспортной задачи с применением компьютеров позволяет использовать иной вариант метода условно-оптимальных планов алгоритм дифференциальных рент, при котором переносы поставок по связям не делаются, а вместо этого на каждом цикле расчета все поставки распределяются заново по допустимым клеткам (с наименьшими по столбцу стоимостями, учитывая ранее выполненные изменения стоимости).
2.3. Решение сетевых транспортных задач методом потенциалов
Для решения сетевых транспортных задач широко применяется метод потенциалов, который основан на свойстве потенциальности оптимального плана.
Пусть имеется некоторая схема потоков однородного ресурса (груза, порожних вагонов) по транспортной сети с ограниченной пропускной способностью звеньев. Пропускную способность звена r-6 в направлении к s обозначим drs Все звенья в зависимости от наличия потока Xrs данного груза
делятся на три категории:
o базисные с потоками 0<Xrs<drs
o пустые без потока данного груза Xrs = 0
o насыщенные Xrs = drs
Рассматривается однопродуктовая задача.
В многопродуктовой задаче насыщенными являются звенья с суммой потоков всех грузов, равной пропускной способности.
Если схема потоков оптимальна, всем вершинам сети могут быть присвоены потенциалы U, удовлетворяющие следующим условиям:
o для базисных звеньев Us – Ur = Сгs, (2.6)
где Сrs или издержки (в зависимости от используемого критерия) перевозки единицы груза от г до s
o для пустых звеньев Us - Ur ≤ Crs (2.7)
o для насыщенных звеньев Us - Ur ≥ Crs (2.8)
Равенство во всех случаях допустимо и не противоречит оптимальности схемы. Нарушение условий (2.7) и (2.8), т.е. Us - Ur ≤ Crs – для пустого звена и Us - Ur ≥ Crs – для насыщенного говорит о неоптимальности плана и указывает путь к его улучшению.
При решении сетевой задачи в начале разрабатывается исходная схема потоков. Затем ведется циклический расчет по улучшению ялана. Каждый цикл включает в себя присвоение потенциалов вершинам, проверки условий (2.7) и (2.8) и замещение схемы потоков.
План вычислений
1. Построение начального плана.
Начальная схема потоков должна удовлетворять следующим требования
а) соблюдение условия баланса для всех вершин сети
б) непревышение пропускной способности звеньев; поток Хrs , на всех дугах сети,
в) отсутствие замкнутых контуров, Образованных базисными звеньями с потоками 0<Х
Желательно построить начальную схему без явных нерациональных (встречностей окружностей), что позволит сократить число вводимых в последствии поправок
2. Присвоение потенциалов всем вершинам сети.
Какой либо вершине, к которой примыкает хотя бы одно базисное звено, присваивается произвольный потенциал (число одного порядка с наибольшей дальностью перевозок)
Затем присваиваем потенциалы остальным вершинам сети, следуя по всем базисным законам.
При потоке от вершины присваивается потенциал (где длина звена). Если поток следует от, что потенциал определяется по следующей формуле
В процессе присвоения потенциалов может обнаружится так называемый случай выро совокупность (граф) базисных звеньев распадается на не связанных между собой систем, на рисунке 2.3. показаны две такие системы, В-А-Г и Д-Б-Е.
В этом случае имеющихся базисных звеньев недостаточно для присвоения потенциалов всем вершинам. Тогда вводятся нулевые потоки, связывающих между собой отдельные системы базисных звеньев. Звенья с нулевыми потоками считаются базисными и используются для присвоения потенциалов.
В задаче с ограничениями пропускной способности компоненты базисного графа могут быть отделены друг от друга не только пустыми, но и насыщенными звеньями.
Тогда вводятся условные нулевые резервы пропускной способности на некоторых насыщенных звеньях, которые далее считаются базисными.
3. Проверка соблюдения условий (2.7 и 2.8) на всех пустых насыщенных звеньях сети.
Если эти условия соблюдаются везде, то задача решена и план оптимален.
При наличии нарушений - невязок выбираем участок с наибольшей невязкой и переходим к пункту 4.
На рисунке 2.4. показан начальный вариант плана сетевой транспортной задачи с ограничениями пропускной способности звеньев. Вершинам сети присвоены потенциалы. Проверка нужна для пустых звеньев А-Е, Е-Д и насыщенного звена Г-Д. Остальные звенья - базисные. Длины звеньев в направлении туда и обратно совпадают.
Условие 2.7 нарушено на звене А-Е:
= 440- 220 = 220 > С = 200;
= 220- 200=20.
Условие (2 8.) нарушено на звене Г-Д:
= 330- 230 < С = 100;
= 100-50 = 50.
На звене Е-Д условие оптимальности соблюдено. Выбираем звено с наибольшей невязкой Г-Д и переходим к пункту 4.
| |
| |
Рисунок 2.3. Вырожденная схема потоков
4. Поиск пути по базисным звеньям между вершинами-концами звена с навязкой.
Совокупность этого пути и звена с невязкой называется контуром.
Для начального варианта на рисунке 2.4. контур составляют звенья ГД, ДЖ, ЖБ и БГ. Для второго варианта (рисунок 2.5.) в контур входят звенья АЕ, ЕВ, ВЖ, ЖД, ДГ, ГА. для третьего варианта (рисунок 2.6.) контур состоит из звеньев БЖ, ЖБ, ВЕ, ЕА, АГ и ГБ.
Дальнейшее действие зависит от того, является ли звено с невязкой пустым или насыщенным.
5. Классификация потоков контура.
а) Устанавливается направление потока на звене с невязкой от меньшего потенциала к большему.
б) Все другие потоки в контуре делятся на попутные и встречные этому потоку.
Так, для начального варианта (рисунок 2.4.) звенья ГД и БГ- попутные, а ДЖ и ЖБ- встречные, во втором варианте (рисунок 2.5.) звенья АЕ, ВЖ, ЖД попутные, а ЕБ, ДГ и ГА- встречные, в третьем варианте (рисунок 2.7.)- БЖ. ВЕ. АГ- попутные, а )КБ, БА, ГБ- встречные.
6. Определение изменение потоков ΔХ.
Изменение потоков:
а) для пустого звена с невязкой ΔХ = min [minX; min(d-x)] (2.9.)
где d-пропускная способность звена.
Следовательно, поправка равно меньшей из двух величин: наименьшего встречного потока и наименьшего свободного остатка пропускной способности для попутных потоков.
б) для насыщенного звена с невязкой (в точности обратное правило).
ΔХ = min [minХ; min(d-x)] (2.10.)
т.е. берется наименьший попутный поток и наименьший из резервов пропускной способности для встречных потоков.
При использовании правил (2.9) и (2.10) звено с невязкой учитывается в числе попутных.
для начального варианта величина изменения потоков ΔХ1 определится как минимальное из следующих величин:
ΔХ1 =min [(20,8;(16-11), (10-6)]=4
так как звено с невязкой- пустое.
Для второго варианта величина изменения потоков ΔХ2 определится следующим образом:
ΔХ2 =min [(15,16,22,30;(16-14),(16-15)]=1,
так как звено с невязко насыщенное.
Для третьего варианта величина изменения потоков ΔХ3 определится так:
ΔХ3 = min [(10,14,21;(16-15),(30-1),(30-4)]=1 ,
так как звено с невязки- насыщенное.
7. Исправление плана.
а) При исправлении невязки на пустом звене потоки по всем попутным звеньям контура (включая звенья с невязкой) увеличиваются на ΔХ, а по встречным уменьшается на ΔХ.
б) При исправлении невязки на насыщенном звене, наоборот, потоки на всех попутных звеньях контура уменьшаются, а на встречных увеличиваются на ΔХ.
В расчете получается новый вариант плана, для которого заново определяются потенциалы, проверяется наличиё невязок и т.д. (те, от пункта 7 переходим к пункту 2).
Расчет заканчивается, когда в п. З не будет обнаружено ни одной невязки, что и происходит в четвёртом варианте решения, которое является оптимальным и показано на рисунке 2.7.
Решение сетевой транспортной задачи непосредственно не содержит значений поставок по корреспонденциям, а дает лишь схему потоков по участкам
Поставки по корреспонденциям должны быть получены исходя из этой схемы, причем одной и той же оптимальной схеме потоков часто соответствует много вариантов поставок, равноценных по значению критерия оптимальности.
Такие равноценные оптимальные варианты называются альтернативными оптимумами.
Например, в варианте на рисунке 2.6. груз, прибывший от Б к Г может быть выгружен в Г или направлен далее к Д в составе потока 15 единиц по участку Г-Д. При наличии альтернативных оптимумов из них можно выбрать более удобный или выгодный по соображениям, не учтенным в критерии оптимальности. Простота и наглядность нахождения большого числа альтернативных оптимумов является одним из преимуществ сетевой постановки транспортной задачи.
