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

--PAGE_BREAK--КП. 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. Вводим фиктивный сотолбец, т.е Ciф=0 (i =1,m). Все стоимости будут равны нулю, это значит, что грузы ciф останутся невостребованными, т.е введением фиктивного потребителя, мы свели транспортную задачу с неправильным балансом к задаче с правильным балансом.

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

е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

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

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

<img width=«80» height=«12» src=«ref-1_655877356-241.coolpic» v:shapes="_x0000_s1033">F =ее  Cij·cij                        min.
Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти его минимум.


    продолжение
--PAGE_BREAK--КР. 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



     a­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







<img width=«108» height=«50» src=«ref-1_655877597-253.coolpic» v:shapes="_x0000_s1026">                                    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







<img width=«108» height=«50» src=«ref-1_655877850-254.coolpic» v:shapes="_x0000_s1028">                                      1,1                        1,4            

                                                    10 

                                      3,1                        3,4            

    продолжение
--PAGE_BREAK--