Автор работы: Пользователь скрыл имя, 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.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 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.
Построим задачу, двойственную к
транспортной. С этой целью вспомним,
что каждому пункту
В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная в двойственной задаче. Тем самым устанавливается соответствие между всеми пунктами и и всеми неизвестными двойственной задачи.
Обозначим неизвестную в двойственной задаче, отвечающую пункту отправления , через , а пункту назначения – через .
Каждому неизвестному в транспортной задаче соответствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное входит ровно в два ограничения системы (6.1): одно из них отвечает пункту , а другое – пункту . В обоих этих уравнениях коэффициент при равен 1. Поэтому соответствующее ограничение в двойственной задаче имеет вид
.
Правая часть неравенства (6.2) равна , потому что именно с этим коэффициентом неизвестная входит в минимизируемую формулу (2.4).
Оптимизируемая форма двойственной задачи имеет вид
Таким образом, задача
Предположим, что нам известно некоторое допустимое базисное решение транспортной задачи, в котором все базисные неизвестные строго положительны. Это решение оптимально лишь в том случае, когда соответствующая ей система оказывается совместной. Эта система возникает из системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным заменить точными равенствами.
В итоге приходим к соотношению:
(для всех свободных
Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточным условием оптимальности.
Моделирование в научных исследованиях стало применяться в глубокой древности, постепенно захватывая всё новые области научных знаний: техническое конструирование, строительство и архитектуру, астрономию, физику, химию, биологию и, наконец, общественные науки. Большие успехи и признание практически во всех отраслях современной науки принёс методу моделирования - ХХ век. Однако методология моделирования долгое время развивалась независимо отдельными науками. Отсутствовала единая система понятий, единая терминология. Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания.
Термин
модель широко используется в различных
сферах человеческой деятельности и
имеет множество смысловых
Модель - это материальный или мысленно представляемый объект, который в процессе исследования замещает объект - оригинал, так, что его непосредственное изучение даёт новые знания об объекте - оригинале.
Под
моделированием понимается процесс
построения, изучения и применения
моделей. Оно тесно связано с
такими категориями, как абстракция,
аналогия, гипотеза и др. Процесс
моделирования обязательно
Главная особенность моделирования в том, что это метод опосредованного познания с помощью объектов - заместителей. Модель выступает как своеобразный инструмент познания, который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект. Именно эта особенность метода моделирования определяет специфические формы использования абстракций, аналогий, гипотез, других категорий и методов познания.
Необходимость использования метода моделирования определяется тем, что многие объекты (или проблемы, относящиеся к этим объектам) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.
Метод моделирования включает три элемента:
1. субъект (исследователь);
2. объект исследования;
3.
модель, опосредствующую отношения
познающего субъекта и
Пусть имеется или необходимо создать некоторый объект А Мы конструируем (материально или мысленно) или находим в реальном мире другой объект В- модель объекта А. Рассмотрим основные этапы моделирования (рисунок 1.1.).
Этап построения модели предполагает наличие некоторых знаний об объекте- оригинале. Познавательные возможности модели обусловливаются тем, что модель отражает какие- либо существенные черты объекта – оригинала. Вопрос о необходимой и достаточной мере сходства оригинала и модели требует конкретного анализа. Очевидно, модель утрачивает свой смысл как в случае тождества с оригиналом (тогда он перестаёт быть оригиналом), так и в случае чрезмерного во всех существенных отношениях отличия от оригинала.
Таким образом, изучение одних сторон моделируемого объекта осуществляется ценой отказа от отражения других сторон. Поэтому любая модель замещает оригинал лишь в строго ограниченном смысле. Из этого следует, что для одного объекта может быть построено несколько “специализированных” моделей концентрирующих внимание на определённых сторонах исследуемого объекта или же характеризующих объект с разной степенью детализации.
На втором этапе процесса моделирования модель выступает как самостоятельный объект исследования. Одной из форм такого исследования является проведение “модельных” экспериментов, при которых сознательно изменяются условия функционирования модели и систематизируются данные об ее «поведении». Конечным результатом этого этапа является множество знаний о модели R
Этапы моделирования | ||||
1 | Построение модели |
|||
2 | Исследование свойств модели | |||
3 | Перенос знаний с модели на объект-оригинал | |||
4 | Практическая проверка полученных с помощью модели знаний |
Рисунок 1.1. Этапы моделирования
На третьем этапе осуществляется перенос знаний с модели на оригинал формирование множества знаний S об объекте. Этот процесс переноса знаний проводится по определённым правилам. Знания о модели должны быть скорректированы с учётом тех свойств объекта - оригинала, которые не нашли отражения или были изменены при построении модели. Мы можем с достаточным основанием переносить какой-либо результат с модели на оригинал, если этот результат необходимо связан с признаками сходства оригинала и модели. Если же определённый результат модельного - исследования связан с отличием модели от оригинала, то этот результат переносить неправомерно.
Четвёртый этап - практическая проверка полученных с помощью моделей знаний и их использование для построения обобщающей теории объекта, его преобразования или управления им.
Для
понимания сущности моделирования
важно не упускать из виду, что моделирование
- не единственный источник званий об объекте.
Процесс моделирования “
Моделирование
- циклический процесс. Это означает,
что за первым четырёхэтапным циклом
может последовать второй, третий
и т. д. При этом знания об исследуемом
объекте расширяются и
Информация о работе Линейные и нелинейные модели. транспортная задача