Закрытая транспортная модель

Содержание

                                                                                                                                 С.

Введение ………………………………..…………………………….………3

Глава 1. Общая  характеристика экономико-математических методов и моделей ……………………………………………………………………………4

1.1 Экономико-математическое моделирование …………………………...4

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

Глава 2. Закрытая транспортная модель …………………………..…..9

2.1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей …………………………………………………………….…..9

2.2 Закрытая модель транспортной задачи ……………………………......14

2.3 Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения …………………………………...…14

Глава 3. Решение закрытой транспортной задачи ………………....…17

3.1 Постановка задачи ………………………………………………………17

3.2 Алгоритм решения ……………………………………………………...18

Заключение …………………………….……………………………..……22

Список используемой литературы ………………………………..……24

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Моделирование в научных  исследованиях стало применяться  еще в глубокой древности и  постепенно захватывало все новые  области научных знаний: техническое  конструирование, строительство и  архитектуру, астрономию, физику, химию, биологию и, наконец, общественные науки. Большие успехи и признание практически  во всех отраслях современной науки  принес методу моделирования ХХ в. Однако, методология моделирования долгое время развивалась независимо отдельными науками. Отсутствовала единая система понятий, единая терминология. Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания.

Термин "модель" широко используется в различных сферах человеческой деятельности и имеет  множество смысловых значений. Рассмотрим только такие "модели", которые  являются инструментами получения  знаний.

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

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

Экономико-математическое моделирование  является неотъемлемой частью любого исследования в области экономики. Бурное развитие математического анализа, исследования операций, теории вероятностей и математической статистики способствовало формированию различного рода моделей  экономики.

Целью математического моделирования  экономических систем является использование  методов математики для наиболее эффективного решения задач, возникающих  в сфере экономики, с использование, как правило, современной вычислительной техники.

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

Кроме того, к задачам  транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

Цель заданной работы - освоить  математическую постановку закрытой транспортной задачи.

 

Глава 1. Общая характеристика экономико-математических методов и моделей

 

1. Экономико-математическое моделирование

 

В процессе исследования объекта  часто бывает нецелесообразно или  даже невозможно иметь дело непосредственно  с этим объектом. Удобнее бывает заменить его другим объектом, подобным данному в тех аспектах, которые важны в данном исследовании. В общем виде модель можно определить как условный образ реального объекта (процессов), который создается для более глубокого изучения действительности. Метод исследования, базирующийся на разработке и использовании моделей, называется моделированием. Необходимость моделирования обусловлена сложностью, а порой и невозможностью прямого изучения реального объекта (процессов). Значительно доступнее создавать и изучать прообразы реальных объектов (процессов), т.е. модели. Можно сказать, что теоретическое знание о чем-либо, как правило, представляет собой совокупность различных моделей. Эти модели отражают существенные свойства реального объекта (процессов), хотя на самом деле действительность значительно содержательнее и богаче.

Модель - это мысленно представляемая или материально реализованная  система, которая, отображая или  воспроизводя объект исследования, способна замещать его так, что ее изучение дает новую информацию об этом объекте.

На сегодняшний день общепризнанной единой классификации моделей не существует. Однако из множества моделей  можно выделить словесные, графические, физические, экономико-математические и некоторые другие типы моделей.

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

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

По целевому назначению модели делятся на:

• Теоретико-аналитические (используются в исследовании общих свойств и закономерностей экономических процессов);

• Прикладные (применяются в решении конкретных экономических задач, таких как задачи экономического анализа, прогнозирования, управления).

По учету фактора времени  модели подразделяются на:

• Динамические (описывают экономическую систему в развитии);

• Статистические (экономическая система описана в статистике, применительно к одному определенному моменту времени; это как бы снимок, срез, фрагмент динамической системы в какой-то момент времени).

По длительности рассматриваемого периода времени различают модели:

• Краткосрочного прогнозирования или планирования (до года);

• Среднесрочного прогнозирования или планирования (до 5 лет);

• Долгосрочного прогнозирования или планирования (более 5 лет).

По цели создания и применения различают модели:

• Балансовые;

• Эконометрические;

• Оптимизационные;

• Сетевые;

• Систем массового обслуживания;

• Имитационные (экспертные).

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

Параметры эконометрических моделей оцениваются с помощью  методов математической статистики. Наиболее распространены модели, представляющие собой системы регрессионных  уравнений. В данных уравнениях отражается зависимость эндогенных (зависимых) переменных от экзогенных (независимых) переменных. Данная зависимость в  основном выражается через тренд (длительную тенденцию) основных показателей моделируемой экономической системы. Эконометрические модели используются для анализа  и прогнозирования конкретных экономических процессов с использованием реальной статистической информации.

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

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

Модели систем массового  обслуживания создаются для минимизации  затрат времени на ожидание в очереди  и времени простоев каналов обслуживания.

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

По учету фактора неопределенности модели подразделяются на:

• Детерминированные (с однозначно определенными результатами);

• Стохастические (вероятностные; с различными, вероятностными результатами).

По типу математического  аппарата различают модели:

• Линейного программирования (оптимальный план достигается в крайней точке области изменения переменных величин системы ограничений);

• Нелинейного программирования (оптимальных значений целевой функции может быть несколько);

• Корреляционно-регрессионные;

• Матричные;

• Сетевые;

• Теории игр;

• Теории массового обслуживания и т.д.

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

 

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

 

Как и всякое моделирование, экономико-математическое моделирование  основывается на принципе аналогии, т.е. возможности изучения объекта посредством  построения и рассмотрения другого, подобного ему, но более простого и доступного объекта, его модели.

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

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

Рассмотрим вопросы классификации  экономико-математических методов. Эти  методы представляют собой комплекс экономико-математических дисциплин, являющихся сплавом экономики, математики и кибернетики. Поэтому классификация  экономико-математических методов  сводится к классификации научных  дисциплин, входящих в их состав.

С известной долей условности классификацию этих методов можно  представить следующим образом.

• Экономическая кибернетика: системный анализ экономики, теория экономической информации и теория управляющих систем.

• Математическая статистика: экономические приложения данной дисциплины - выборочный метод, дисперсионный анализ, корреляционный анализ, регрессионный анализ, многомерный статистический анализ, теория индексов и др.

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

• Методы принятия оптимальных решений, в том числе исследование операций в экономике. Это наиболее объемный раздел, включающий в себя следующие дисциплины и методы: оптимальное (математическое) программирование, сетевые методы планирования и управления, теорию и методы управления запасами, теорию массового обслуживания, теорию игр, теорию и методы принятия решений.

В оптимальное программирование в свою очередь входят линейное и  нелинейное программирование, динамическое программирование, дискретное (целочисленное) программирование, стохастическое программирование и др.

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. Закрытая транспортная модель

 

2.1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей

 

Под названием “транспортная  задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам  линейного программирования и могут  быть решены симплексным методом. Однако матрица системы ограничений  транспортной задачи настолько своеобразна, что для ее решения разработаны  специальные методы. Эти методы, как и симплексный метод, позволяют  найти начальное опорное решение, а затем, улучшая его, получить оптимальное  решение.

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

Различают два типа транспортных задач: но критерию стоимости (план перевозок  оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имеющегося в наличии груза– :

;

заказы каждого из потребителей (потребности) обозначим соответственно , а общее количество потребностей – :

,

Тогда при условии

мы имеем закрытую модель, а при условии

– открытую модель транспортной задачи.

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

Так же существуют одноэтапные  модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный  пункт”, например – склад.

План перевозок с указанием  запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

 

Пункты Отправления	Пункты назначения				Запасы
			…
			…
			…
…	…	…	…	…	…
			…
Потребности			…		или

 

Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).

Очевидно, переменные должны удовлетворять условиям:

Система (2.1) содержит уравнений с неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (2.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

Такая структура системы (2.1) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней  мере, один из двух их индексов равен  единице, а, следовательно, свободные неизвестные определяются условием , .Перепишем систему (2.1) в виде

где символы  и означают суммирование по соответствующему индексу. Так, например,

При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь  , ).

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

или короче

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

Так как для закрытой модели транспортной задачи , то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное , мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

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

 

В системе (2.3) выделен указанный  выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а  базисные неизвестные остальных  уравнений образуют первую строку матрицы  перевозок без первого неизвестного [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется уравнений, выделенный базис содержит неизвестных, а, следовательно, и ранг системы (2.1) .

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

Совокупность тарифов  также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

 

Пункты Отправления	Пункты назначения									Запасы
						…
						…
						…
…	…			…		…	…			…
						…
Потребности						…				или

          Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных :

 

Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).

Таким образом, мы видим, что  транспортная задача является задачей  линейного программирования. Для  ее решения применяют также симплекс-метод, но в силу специфики задачи здесь  можно обойтись без симплекс-таблиц. Решение можно получить путем  некоторых преобразований таблицы  перевозок. Эти преобразования соответствуют  переходу от одного плана перевозок  к другому. Но, как и в общем  случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как  в данном случае ранг системы ограничений-уравнений  равен то среди всех неизвестных выделяется базисных неизвестных, а остальные ·

неизвестных являются свободными. В базисном решении свободные  неизвестные равны нулю. Обычно эти  нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким  образом, в таблице перевозок, представляющей опорный план, мы имеем  заполненных и · пустых клеток.

Для контроля надо проверять, равна ли сумма чисел в заполненных  клетках каждой строки таблицы перевозок  запасу груза на соответствующей  базе, а в каждом столбце —  потребности заказчика [этим подтверждается, что данный план является решением системы (2.1)].

Замечание 1. Не исключаются  здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей  свободных неизвестных вписываются  в соответствующую клетку, и эта  клетка считается заполненной.

Замечание 2. Под величинами , очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, выражены в тоннах, а в километрах, то величина , определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.

 

 

 

 

 

2.2 Закрытая модель транспортной задачи

 

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