Главная / Рефераты / Рефераты по экономико-математическому моделированию
Реферат: Минимизация стоимостей перевозок
Notice: Undefined variable: ref_img in /home/area7ru/area7.ru/docs/referat.php on line 323
Московский Государственный Колледж Информационных Технологий Курсовой проект по предмету « Языки программирования и разработка программного обеспечения » на тему : « Минимизация стоимостей перевозок » Работу выполнил Работу проверили студент группы П-407 Преподаватели Чубаков А.С. Капустина Р.Н. Токарев С.Б. 1998 г. КР. 2203 81 - 21 ВВЕДЕНИЕ Развитие современного общества характеризуется повышением технического уровня , усложнением организационной структуры производства , углублением общественного разделения труда , предъявлением высоких требований к методам планирования и хозяйственного руководства. В этих условиях только научный подход к руководству к экономической жизни общества позволит обеспечить высокие темпы развития народного хозяйства. В настоящие время новейшие достижения математики и современной вычислительной техники находят все более широкие применение в экономических исследованиях и планированияx. Этому способствует развитие таких разделов математики . как математическое программирование , теория игр , теория массового обслуживания , а так же бурное развитие быстродействующей электронно - вычислительной техники. Одной из основных ставится задача создания единой системы оптимального планирования и управление народным хозяйством на базе широкого применения математических методов в электронно - вычислительной техники в экономике. Решение экстремальных экономических задач можно разбить на три этапа : 1. Построение экономико - математической задачи. 2. Нахождение оптимального решения одним из математических методов. 3. Промышленное внедрение в народное хозяйство. Построение экономическо - математической модели состоит в создании упрощенной математической модели , в которой в схематичной форме отражена структура изучаемого процесса. При этом особое внимание должно быть уделено отражении в модели всех существенных особенностей задачи и учет всех ограничивающих условий , которые могут повлиять на результат. Затем определяется цель решения , выбирается критерий оптимальности и дают математическую формулировку задачи. Составными частями математического программирования являются линейное , нелинейное и динамическое программирование. При исследовании в большинстве случаев имеют место задачи нелинейного программирования , аппроксимация их линейными задачами вызвана только тем , что последние хорошо изучены. Динамическое программирование как самостоятельная дисциплина сформулировалась в пятидесятых годах нашего века. Большой вклад в ее развитие внес американский математик Р. Бельман. Дальнейшие развитие динамическое программирование получило в трудах зарубежных ученых Робертса , Ланга и др. В настоящие время оно в основном развивается в планировании приложений к различным родам многоэтапным процессам. КР. 2203 81 – 21 2. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ Производственное предприятие имеет в своем составе три филиала которые производят однородную продукцию соответственно в количествах , равных 50 , 30 и 10 единиц. Эту продукцию получают четыре потребителя , расположенных в разных местах. Их потребности соответственны равны 30 , 30 , 10 и 20 единиц. Тарифы перевозов единицы продукции от каждого филиалов соответствующим потребителям задаются матрицей : 1 2 4 1 Сij = 2 3 1 5 3 2 4 4 Составить такой план прикрепления получателе продукции к ее поставщикам , при котором общая стоимость перевозок будет минимальной. КП. 2203 81 - 21 2.МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ 2. Математическая модель задачи Имеется: m (i=1,2,…,m) – филиалы. Ai – количество единиц продукции «i» филиала. n (j=1,2,…,n) – потребители Bj – потребности «j» потребителя Cij – стоимость перевозки 1 условной единицы продукции от «i» филиала к «j» потребителю Ограничения: 1. Балансовое ограничение. Предполагается, что сумма всех запасов (ai) равна сумме всех заявок (bj):
2. Ресурсное ограничение.
Суммарное количество груза, направленного из каждого пункта отправления во все пункты назначения должно быть равно запасу груза в данном пункте. Это даст m – условий равенств: или
3. Плановое ограничение.
Суммарное количество груза, доставляемого в каждый пункт назначения изо всех пунктов отправления должно быть равно заявке (bj) поданной данным пунктом. Это даст нам n – условий равенств:
КП. 2203 81 - 21 или
4. Реальность плана перевозок. Перевозки не могут быть отрицательными числами:
5. Требуется составить такой план перевозок, при котором все заявки были бы выполнены и при этом общая стоимость всех перевозок была бы минимальна, поэтому целевая функция или критерий эффективности:
КП. 2203 81 – 21 3.ВЫБОР МЕТОДА РЕАЛИЗАЦИИ ПРОДУКЦИИ. ОБОСНОВАНИЕ ВЫБОРА МЕТОДА. Симплекс - метод является универсальным и применяется для решения любых задач. Однако существуют некоторые частные типы задач линейного программирования , которые в силу некоторых особенностей своей структуры допускают решение более простыми методами. К ним относится транспортная задача. Распределительный метод решения транспортной задачи обладает одним недостатком : нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой трудоемкой работы нас избавляет специальный метод решения транспортной задачи , который называется методом потенциалов. Он позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. В отличии от общего случая ОЗЛП с произвольными ограничениями и минимизированной функцией , решение транспортной задачи всегда существует. Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплекс - метода ,. а именно : сначала находят опорный план транспортной задачи , а затем его улучшают до получения оптимального плана. Далее будет рассматриваться сам метод потенциалов. Решение транспортной задачи , как и любой другой задачи линейного программирования начинается с нахождения опорного решения , или , как мы говорим опорного плана. Для его нахождения созданы специальные методы , самым распространенным из них считается метод северо - западного угла. Определение значений xi,j начинается с левой верхней клетки таблицы. Находим значения x1,1 из соотношения x11 = min(a1,b1(. Если ai < b1 то x11=a1 , строка i=1 исключается из дальнейшего рассмотрения , а потребность первого потребителя b1 уменьшается на величину a1. Если a1>b1 , то x11=b1 , столбец j=1 исключается из дальнейшего рассмотрения , а наличие груза у первого поставщика a1 уменьшается на величину b1. Если a1=b1 , то x11=a1=b1 , строка i=1 и столбец j=1 исключаются из дальнейшего рассмотрения. Данный вариант приводит к вырождению исходного плана. Затем аналогичные операции проделывают с оставшийся частью таблицы , начиная с его северо - западного угла. После завершения оптимального процесса необходимо провести проверку полученного плана на вырожденность. Если количество заполненных клеток равно m + n -1 , то план является невырожденным. Если план вырожденный , т.е количество заполненных клеток стало меньше m + n -1 , то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями , чтобы общие количество заполненных клеток стало равным m + n -1. Транспортная задача с неправильным балансом называется открытой моделью . Чтобы ее решить , необходимое сбалансировать. Достигается это следующим образом: Когда еai >еbj это транспортная задача с избытком запасов. еxijеai , то такая задача называется – транспортная задача с избытком запаса. Эту задачу можно свести к обычной задаче с правильным балансом , если ввести фиктивный пункт отправления Aф , приписав ему фиктивный запас aф =еbj - еai . Добавляем фиктивную строку , где Cфi= 0 ( j=1,n). Стоимости будут равны нулю . это значит , что часть заявок cфj останутся неудовлетворенными. Среди них могут оказаться те потребности , которые необходимо обязательно удовлетворить. Для этого вводим коэффициент: R=еai : еbj и каждый запас bj умножаем на этот коэффициент. Таким образом задача сведена к транспортной задаче с правильным балансом. Построенный выше исходный план можно довести до оптимального с помощью метода потенциалов. Каждому поставщику Ai поставим в соответствии некоторые числа ai , называемые потенциалом , а каждому потребителю Bj – число bj. Для каждой независимой клетки , т.е для каждой независимой переменной рассчитываются так называемые косвенные тарифы ( Cўij) по формуле Cўij= ai + bj. А для заполненных клеток , т.е базисных переменных Cўij =Cij. Проверяем полученный план на оптимальность. Если для каждой независимой клетки выполняется условие Cўij - Cij Cij , то следует приступить к улучшению плана. Для правильного перемещения перевозок , чтобы не нарушить ограничений , строится цикл , т.е замкнутый путь , соединяющий выбранную свободную клетку с той же самой , и проходящий через заполненные клетки. Цикл строится следующим образом. Вычеркиваются все строки и столбцы , содержащие ровно одну заполненную клетку (выбранная при этом клетка считается заполненной). Все остальные заполненные клетки составляют и лежат в его углах. Направление построения цикла ( по часовой стрелке или против ) несущественно. В каждой клетки цикла , начиная со свободной , проставляются поочередно знаки І + І и І - І . В клетках со знаком І - І выбирается минимальная величина. Новый базисный план начинается путем сложений выбранной величины с величинами , стоящих в клетках цикла со знаком І + І и вычитанием этой величины из величины , стоящей в клетке со знаком І - І . Выбранная минимальная величина будет соответствовать перемененной выводимой из базиса. КП. 2203 81 - 21 Значения переменных включенных в цикл , после описанной корректировки , переносятся в новую таблицу. Все остальные переменные записываются в новую таблицу без изменения. Осуществляется переход к шагу один. Дальше подсчитывается значение целевой функции F = ее Cij· cij min. Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти его минимум. КР. 2203 81 - 21 5.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ. Слово « компьютер »означает « вычислитель » , т.е устройство для вычислений. Это связано с тем , что первые компьютеры создавались как устройства для вычислений , грубо говоря , усовершенствованные , арифметические арифмометры. Принципиальное отличие компьютеров от арифмометров и других счетных устройств состояло в том , что арифмометры могли выполнять лишь отдельные вычислительные операции(сложение , вычитание , умножение , деление и др.) , а компьютеры позволяли проводить без участия человека сложные последовательные вычислительные операции по заранее заданной инструкции - программе. Кроме того , для хранения данных , промежуточных и итоговых результатов вычислений компьютеры содержат память. Компьютер - это универсальный прибор для переработки информации. Но сам по себе компьютер...
ВНИМАНИЕ!
Текст просматриваемого вами реферата (доклада, курсовой) урезан на треть (33%)!
Чтобы просматривать этот и другие рефераты полностью, авторизуйтесь на сайте:
|
|
|
Добавлено: 2012.06.26
Просмотров: 1917
|
Notice: Undefined offset: 1 in /home/area7ru/area7.ru/docs/linkmanager/links.php on line 21
При использовании материалов сайта, активная ссылка на AREA7.RU обязательная! |