Реферат

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

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 9.11.2024




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

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

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

по предмету

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

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


на тему :

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

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

   студент группы П-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 останутся неудовлетворенными. Среди них могут оказаться те потребности , которые необходимо обязательно удовлетворить. Для этого вводим коэффициент:

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

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

Каждому поставщику Ai поставим в соответствии некоторые числа ai , называемые потенциалом , а каждому потребителю Bj – число bj.

Для каждой независимой клетки , т.е для каждой независимой переменной рассчитываются так называемые косвенные тарифы ( Cўij) по формуле

 Cўij= ai + bj. А для заполненных  клеток , т.е базисных переменных Cўij =Cij.

Проверяем полученный план на оптимальность. Если для каждой независимой клетки выполняется условие Cўij - Cij <=0 , то такой план является оптимальным. Если хотя бы в одной свободной клетке Cўij > Cij , то следует приступить к улучшению плана.

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

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

В каждой клетки цикла , начиная со свободной , проставляются поочередно знаки

І + І и  І -  І .  В клетках со знаком  І - І выбирается минимальная величина. Новый базисный план начинается путем сложений выбранной величины с величинами , стоящих в клетках цикла со знаком І + І и вычитанием этой величины из величины , стоящей в клетке со знаком І -  І . Выбранная минимальная величина будет соответствовать перемененной выводимой из базиса.
КП. 2203 81 - 21

 Значения переменных включенных в цикл , после описанной корректировки , переносятся в новую таблицу.

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

F = ее  Cij· cij                        min.
Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти его минимум.


КР. 2203 81 - 21


5.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.
Слово « компьютер »означает « вычислитель » , т.е устройство для вычислений.

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

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

Программы . работающие на компьютеры можно разделить на три категории :

n Прикладные программы , непосредственно обеспечивающие выполнение необходимых пользователям работ : редактирование текстов , рисование

картинок , обработку информационных массивов и т.д.

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

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

КР. 2203 81 - 21

6.ОБОСНОВАНИЕ ВЫБОРА ЯЗЫКА




В 1992 году фирма Borland International выпустила два пакета программирования , основанные на использовании языка Паскаль - Borland Pascal 7.0 и Turbo Pascal 7.0. Система программирования Turbo Pascal , разработанная американской корпорацией Borland

остается одной из самых популярных систем программирования в мире. Этому способствует , с одной стороны , простота лежащего в ее основе языка программирования Паскаль , а с другой - труд и талант сотрудников Borland во главе с идеологом и создателем Turbo Pascal Андерсом Хейлсбергом , приложившим немало усилий к ее совершенствованию. Придуманный швейцарским ученым Никласом Виртом как средство для обучения студентов программированию , язык Паскаль стараниями А. Хейлсберга превратилась в мощною современною профессиональную систему программирования , которой по плечу любые задачи - от создания простых программ , предназначенных для решения несложных вычислительных задач , до разработки сложнейших реляционных систем управления базами данных. Появление Windows  и инструментальных средств Borland Pascal with Object и Delphi для разработки программ в среде Windows лишний раз показало , какие поистине не исчерпывающие возможности таит он в себе : и Borland Pascal , и используемый в Delphi язык Object Pascal основываются на Турбо Паскале и развивают его идеи.

Пакет Turbo Pascal включает в себя как язык программирования  - одно из расширений языка Паскаль для ЭВМ типа IBM , так и среду , предназначенную для написания , отладки и запуска программ.

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

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


КР. 2203 81 - 21


7.РЕШЕНИЕ ЗАДАЧИ ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРРАММЫ.






    B1



    B2



     B3



     B4



     i



ai



A1

1         1

   

    30

2         2

 

    20

0         4

     

4         1

     



    50



    0

A2

2         2



3         3

   

   10

1         1

 

   10

5         5

 

    10



    30



    1

A3

1         3



2         2

0         4

4         4

    

    10



    10



    0

заявки

    bj

 

   30



    30



   10



      20



    90



   Bj 



    1



     2



    0



      4







                                    1,2                          1,4         

                                                     10              

                                     2,2                         2,4

         


B1

B2

B3

B4 

ai

ai



A1

1         1

 

   30

2         2

   

    10

0         4

     

1         1

   

    10



     50



      0



A2

2         2

     

3         3

     

    20

1         1

    

    10

2         5

      



     30



      1



A3

4         3

5         2

3         4

4         4

    

     10



      10



       3

bj



     30



      30



      10



      20

 

      90





Bj



     1



       2



       0



      1







                                      1,1                        1,4            

                                                    10 

                                      3,1                        3,4            

КР. 2203 81 - 21






     B1



   B2



   B3



   B4



    ai



ai



A1

1         1

  

    20

2         2

   

    10

0         4

1         1

  

     20



     50



     0



A2

2         2

3         3

 

   20

1         1

 

   10

2         5



     30



     1



A3

3         3

   

   10

4         2

2         4

3         4



     10



     2



  bj



     30



      30



      10



      20

 

     90





  B­j



      1



       2



       0

 

       1







                                1,1                              1,2

                                                     10

                                3,1                              3,2            





   B1



    B2



    B3



    B4



    ai



ai



A1

1        1

    30

-1         2

-3         4

1        1

    20



    50



   0



A2

5        2

3          3

     20

1          1

     10

5        5



    30



   4



A3

4        3

2          2

      10

0          4

4        4

     E



   10+E



   3



bj



    30



    30



    10



 20+E



  90+E





Bj



    1



     -1



    -3



    1







                               1,1                               1,2

                                               

10

                               2,1                               2,2

КР. 2203 81 - 21






   B1



    B2



   B3



   B4



    ai



ai



A1

1        1

    10

2          2

     20

0          4

1        1

     20



     50



   0



A2

2        2

    20

3          3

1          1

      10

2        5



     30



    1



A3

1        3

2          2

      10

0          4

1        4



      10



    0



bj



   30



      30



      10



     20



       90





Bj



    1



      2



       0



      1







F­min=1·10 +2·20 +2·10 +1·10 +2·20 +20*1 = 140
Найден оптимальный план перевозок , равный 140.

КР. 2203 81 – 21


8.АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ


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

Cўij –Cij <=0

Так же суммарная стоимость перевозок груза с каждой последующей итерацией уменьшалась и оказалась равной 140 рублям.

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

Результат подсчитанный ручным счетом сходится с ответом , полученным на ЭВМ с помощью составленной программы. Расхождений нет.

Вектор полученных результатов:
          10  20  0  20

c=      20  0   10  0

           0   10  0   0
                                                          КП. 2203 81 - 21
                                                    ЗАКЛЮЧЕНИЕ
Основной задачей данного курсового проекта являеся нахождение оптимального плана перевозок груза от поставщиков к потребителям . нахождение минимальной функции.

Эта задача сводится к транспортной задаче.

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


1. Сочинение на тему Литературный герой МАРУИ
2. Реферат на тему Обеспечение русской армии конец XV - первая половина XVII вв
3. Реферат Аддамс, Доун
4. Реферат Возникновение и формирование профсоюзного движения
5. Реферат Материальные ресурсы предприятия
6. Доклад Зимние виды спорта. Сноубординг
7. Биография Список известных художников и скульпторов, связанных с Ташкентом
8. Реферат на тему Карьерные железнодорожные пути Устройство рельсовой колеи и стрелочных переводов
9. Отчет по практике Анализ хозяйственной деятельности фирмы МВЕН
10. Реферат на тему The Rise Of The UFW Essay Research