Минимизация стоимостей перевозок (183315)

Посмотреть архив целиком



Московский Государственный Колледж


Информационных Технологий





Курсовой проект


по предмету



« Языки программирования и разработка

программного обеспечения »

на тему :

« Минимизация стоимостей перевозок »











Работу выполнил Работу проверили

студент группы П-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.ВЫБОР МЕТОДА РЕАЛИЗАЦИИ ПРОДУКЦИИ.

ОБОСНОВАНИЕ ВЫБОРА МЕТОДА.

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

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

которые в силу некоторых особенностей своей структуры допускают решение более

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

Распределительный метод решения транспортной задачи обладает одним

недостатком :

нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой

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

задачи , который называется методом потенциалов. Он позволяет автоматически

выделять циклы с отрицательной ценой и определять их цены.

В отличии от общего случая ОЗЛП с произвольными ограничениями и

минимизированной функцией , решение транспортной задачи всегда существует.

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

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

Определение значений x­­­­i,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 (i=1,m)


КП. 2203 81 – 21

åxij=bj (j=1,n)

Здесь вводим фиктивного потребителя Bф и приписываем ему заявку bфai - åbj . Вводим фиктивный сотолбец , т.е C=0 (i =1,m). Все стоимости будут равны нулю , это значит , что грузы c останутся невостребованными , т.е введением фиктивного потребителя , мы свели транспортную задачу с неправильным балансом к задаче с правильным балансом.

Если сумма подданных заявок превышает наличные запасы

åbj >åa­i , то такая задача называется – транспортная задача с избытком запаса. Эту задачу можно свести к обычной задаче с правильным балансом , если ввести фиктивный пункт отправления Aф , приписав ему фиктивный запас aф bj - åai . Добавляем фиктивную строку , где Cфi= 0 ( j=1,n).

Стоимости будут равны нулю . это значит , что часть заявок cфj останутся неудовлетворенными. Среди них могут оказаться те потребности , которые необходимо обязательно удовлетворить. Для этого вводим коэффициент:

Rai : åbj и каждый запас bj умножаем на этот коэффициент. Таким образом задача сведена к транспортной задаче с правильным балансом.

Построенный выше исходный план можно довести до оптимального с помощью метода потенциалов.


Случайные файлы

Файл
20869-1.rtf
12455.rtf
81316.rtf
8633.rtf
147218.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.