Линейные и нелинейные модели. транспортная задача

Автор работы: Пользователь скрыл имя, 16 Января 2012 в 18:38, курсовая работа

Краткое описание

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

Содержание работы

1. Теоретическая часть 4
1.1. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей 4
1.2. Методы составления начального опорного плана 10
1.3. Понятие потенциала и цикла. 14
1.4. Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения 21
1.5. Задача, двойственная к транспортной. 23
1.6. Экономико-математическое моделирование 24
1.7. Классификация экономико-математических моделей 34
1.8. Экономико-математическая модель оптимизационной задачи 38
1.9. Этапы экономико-математического моделирования 42
2. Практическая часть 49
Заключение 64
Список используемых источников: 65

Содержимое работы - 1 файл

ЭМММ-линейные и нелинейные модели. транспортная задача.docx

— 1.32 Мб (Скачать файл)

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

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

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

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

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

    Выше  рассматривалась закрытая модель  транспортной  задачи, с правильным балансом, когда выполняется условие (1.3). В случае выполнения (1.4) (открытая модель)  баланс  транспортной  задачи  может  нарушаться  в  2-ух  направлениях:

      1. Сумма  запасов  в  пунктах   отправления  превышает  сумму   поданных  заявок (транспортная  задача  с  избытком  запасов):

                å аi > å bj  ( где i=1,...,m ; j=1,...,n );

          2. Сумма  поданных  заявок  превышает  наличные  запасы (транспортная  задача  с   избытком  заявок):

                  å аi < å bj  ( где i=1,...,m ; j=1,...,n );

    Рассмотрим  последовательно  эти  два  случая:

    Транспортная  задача   с  избытком  запасов.

    Сведем  её  к  ранее  рассмотренной  транспортной  задаче  с  правильным  балансом.  Для  этого, сверх  имеющихся  n  пунктов назначения  В1, B2, ... , Bn,  введём  ещё   один, фиктивный, пункт назначения   Bn+1, которому   припишем  фиктивную заявку, равную  избытку запасов над заявками 

                bn+1 = å аi - å bj   ( где i=1,...,m ; j=1,...,n ) ,

    а  стоимость  перевозок  из  всех  пунктов  отправления  в  фиктивный  пункт  назначения  bn+1  будем считать равной  нулю. Введением фиктивного  пункта  назначения  B n+1  с его заявкой b n+1  мы  сравняли  баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную  задачу  с правильным  балансом.

    Транспортная  задача  с  избытком  заявок.

    Эту задачу можно свести к обычной  транспортной задаче с правильным  балансом,  если  ввести  фиктивный  пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из  фиктивного  пункта  отправления во  все пункты  назначения  принять равной  нулю.  

    1. Задача, двойственная к транспортной.

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

      

В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная  в двойственной задаче. Тем самым устанавливается соответствие между всеми пунктами и и всеми неизвестными двойственной задачи.

      Обозначим неизвестную в двойственной задаче, отвечающую пункту отправления , через , а пункту назначения – через .

      Каждому неизвестному в транспортной задаче соответствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное входит ровно в два ограничения системы (6.1): одно из них отвечает пункту , а другое – пункту . В обоих этих уравнениях коэффициент при равен 1. Поэтому соответствующее ограничение в двойственной задаче имеет вид

         .

Правая  часть неравенства (6.2) равна  , потому что именно с этим коэффициентом неизвестная входит в минимизируемую формулу (2.4).

Оптимизируемая  форма двойственной задачи имеет  вид

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

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

В итоге  приходим к соотношению:

(для всех свободных неизвестных  )

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

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

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

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

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

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

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

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

      Метод моделирования включает три элемента:

      1. субъект (исследователь);

      2. объект исследования;

      3. модель, опосредствующую отношения  познающего субъекта и познаваемого  объекта,

      Пусть имеется или необходимо создать  некоторый объект А Мы конструируем (материально или мысленно) или  находим в реальном мире другой объект В- модель объекта А. Рассмотрим основные этапы моделирования (рисунок 1.1.).

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

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

      На  втором этапе процесса моделирования  модель выступает как самостоятельный  объект исследования. Одной из форм такого исследования является проведение “модельных” экспериментов, при  которых сознательно изменяются условия функционирования модели и  систематизируются данные об ее «поведении». Конечным результатом этого этапа является множество знаний о модели R

  Этапы моделирования  
       
  1
Построение  модели
 
       
  2 Исследование  свойств модели  
       
  3 Перенос знаний с модели на объект-оригинал  
       
  4 Практическая  проверка полученных с помощью модели знаний  

Рисунок 1.1. Этапы моделирования

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

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

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

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

Информация о работе Линейные и нелинейные модели. транспортная задача