Моделирование транспортной задачи

Введение

 

 

Темой КП является - решение транспортной задачи открытого типа.

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

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

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

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

"Аналогией" называют суждение о каком-либо частном сходстве двух объектов. При этом сходство может быть существенным и несущественным. Понятие существенности и не существенности сходства или различия зависит от уровня абстрагирования и в общем случае определяется конечной целью проводимого исследования. Гипотезы и аналогии, отражающие реальный, объективно существующий мир, должны обладать наглядностью или сводится к удобным для исследования логическим схемам. Такие логические схемы, упрощающие рассуждения и логические построения или позволяющие производить эксперименты, называются "моделями". Другими словами модель (лат.modulus-тера) - это объект-заместитель объекта оригинала, обеспечивающий изучение некоторых свойств оригинала.

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Предметная область моделирования

1.1 Понятие модели и их разновидности

 

 

Модель (фр. modиle, от лат. modulus -- «мера, аналог, образец») -- некоторый материальный или мысленно представляемый объект или явление, являющийся упрощённой версией моделируемого объекта или явления (прототипа) и в достаточной степени повторяющий свойства, существенные для целей конкретного моделирования (опуская несущественные свойства, в которых он может отличаться от прототипа).

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

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

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

Смоделировать можно любой процесс производственный, экономический (от процесса сборки до процесса прогнозирования цены акций на финансовом рынке)

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

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

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

• Постановка задачи, ее теоретическая и логическая формулировка.
• Анализ структуры исследуемой экономической системы.
• Построение модели отвечающей экономическим условиям задачи и математическим принципам.
• Заполнение системы уравнений необходимыми статистическими данными.
• Разработка математического алгоритма, решение задачи и получение численных результатов.
• Экономическая интерпретация, и анализ полученных результатов.

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

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

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

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

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

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

 

 

1.2  Построение модели

 

 

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

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

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

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

Процесс оптимизации в таких моделях сводится к нахождению таких положительных значений неизвестных х₁*…*х_n , которые удовлетворяются условию ограничений и доставляют экстремум с целевой функции.

Задача, в которой целевая функция и условия ограничений заданы линейными функциями, называется задачей линейного программирования (ЗЛП).

Общая задача линейного программирования имеет несколько форм записи:

- Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А₁х₁ + А₂x₂ + ... + А_Nx_N = А_о, X 0, где С = (с₁, с₂, ..., с_N); Х = (х₁, х₂, ..., х_N); СХ - скалярное произведение; векторы  A₁, A₂,..., A_N, A₀ состоят соответственно из коэффициентов при неизвестных и свободных членах.

- Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀, Х  0, где С = (с₁, с₂, ..., с_N) - матрица-cтрока; А = (а_ij) - матрица системы; Х - матрица-столбец, А₀ - матрица-столбец.

- Запись с помощью знаков суммирования. Минимизировать линейную функцию Z =   С_jх_j при ограничениях:

Определение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂, ..., х_N).

Определение 2. План Х = (х₁, х₂, ..., х_N) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами  х , являются  линейно независимыми. Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

Определение 3. Опорный план называется невырожденным,  если он содержит М положительных  компонент, в противном случае опорный план называется вырожденным.

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

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

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

- Правая часть системы ограничений состоит из неотрицательных чисел, т. е. P₀ ³ 0

- Канонический вид системы содержит полный набор базисных векторов.

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

Найти минимальное значение линейной функции:

    Z = С₁х₁+С₂х₂+... +С_Nx_N     (1.2.1)

при ограничениях:

a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N   b₁

  a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N   b₂

. . . . . . . . . . . . . . .   (1.2.2)

a_M1x₁ + a_M2x₂ + ... + a_MNХ_N   b_M

x_j   0 (j = 1, 2, ... ,n) (1.2.3)

Совокупность чисел х₁, х₂, ..., х_N, удовлетворяющих ограничениям (1.2.2) и (1.2.3), называется решением. Если система неравенств (1.2.2) при условии (1.2.3) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместной.

Рассмотрим на плоскости х₁Ох₂ совместную систему линейных неравенств

a₁₁x₁ + a₂₂x₂   b₁

a₂₁x₁ + a₂₂x₂   b₂

. . . . . . . .

a_M1x₁ + a_M2x₂   b_M

 

x₁  0, x₂  0

Это все равно, что в системе (1.2.2) - (1.2.3) положить N=2. Каждое неравенство  этой  системы геометрически определяет полуплоскость с граничной прямой