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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 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 Закрытая модель транспортной задачи

 

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