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

Заказать работу

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


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


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


по предмету


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

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

на тему :

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


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

студент группы П-407 Преподаватели

Чубаков А.С. Капустина Р.Н.

Токарев С.Б.


1998 г.


КР. 2203 81 - 21

ВВЕДЕНИЕ

Развитие современного общества характеризуется повышением технического

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

Решение экстремальных экономических задач можно разбить на три этапа :

Построение экономико - математической задачи.

Нахождение оптимального решения одним из математических методов.

Промышленное внедрение в народное хозяйство.

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

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

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

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

в трудах зарубежных ученых Робертса , Ланга и др.

В настоящие время оно в основном развивается в планировании приложений к различным родам многоэтапным процессам.


КР. 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» потребителю


Ограничения:


Балансовое ограничение.

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

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

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

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

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

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

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

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

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

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

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

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


КП. 2203 81 - 21

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

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

F = ее Cij· cij min.


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



КР. 2203 81 - 21

5.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.


Слово « компьютер »означает « вычислитель » , т.е устройство для вычислений.

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

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

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

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

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

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

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


КР. 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.АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ

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

ij –Cij

Другие материалы

  • Решение задач о планировании перевозок
  • ... значение в отрицательных клетках. Во всех отрицательных клетках это значение отнимается, в положительных прибавляется. Получили новый план перевозок. Решение задачи 1. Определим модель задачи b1+b2+b3+b4+b5+b6=230+220+130+170+190+110=1050 a1+a2+a3+a4+a5=240+360+180+120+150=1050 Так как ...

  • Рационализация перевозок грузов различными видами транспорта
  • ... , участвующих в перевозках; — техническая норма загрузки четырех-, шести-, восьмиосных вагонов данным грузом. 1.4 Рационализация перевозок грузов различными видами транспорта Факторы, определяющие развитие и размещение транспортной системы Капитальные вложения, направляемые на развитие ...

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

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

  • Маркетинг в сфере авиапассажирских перевозок (на примере ОАО "Аэрофлот – российские авиалинии")
  • ... подвигу народа нашей страны в Великой Отечественной войне. 3.4 Аэрофлот – Бонус и Sky Team Авиакомпания "Аэрофлот - российские авиалинии" предлагает программы поощрения пассажиров "Аэрофлот Бонус". Став участником программы, клиенты получают уникальную возможность: · ...

  • Состояние и проблемы развития контейнерных перевозок
  • ... контейнеров, из которых 56,7 тысяч крупнотоннажных, что на 19,5% больше аналогичного периода 2003 года. 3. Проблемы в развитии контейнерных перевозок Современный рынок контейнерных перевозок в России характеризуется двумя основными грузопотоками: внешнеэкономические (экспорт, импорт и транзит ...

  • Организация перевозок и управление движением
  • ... 175. Основными задачами маршрутизации являются А) организация движения; минимизация сроков доставки грузов; Б) безопасность движения; эффективное использование транспортных средств; В) выполнение планов и графиков перевозок; Г) оперативность в реагировании на изменение дорожных условий Д) ...

  • Анализ себестоимости перевозок филиала "Троллейбусный парк № 2"
  • ... с современной быстродействующей вычислительной и организационной техникой [16 , с.268]. 2. Анализ себестоимости перевозок филиала «Троллейбусный парк № 2»   2.1 Характеристика предприятия Филиал «Троллейбусный парк № 2» входит в состав КУП «Минсктранс» в качестве обособленного ...

  • Совершенствование организации грузовых автомобильных перевозок в Республике Беларусь
  • ... актуальной. Целью работы является исследование организации грузовых автомобильных перевозок и разработка путей совершенствования в этом направлении. Исходя из поставленной цели, предметом работы является система грузовых автомобильных перевозок Российской Федерации. Данная работа исследует ...

  • Информационные технологии мультимодальных и интермодальных перевозок
  • ... находится контейнер в кон-кретном отсеке. Это указывают последующие две цифры. в.  В нашем случае - это (04). мультимодальная интермодальная система информационная г.  Ряд, в котором помещен контейнер. Последние две цифры указывают ряд - (12). д.  Фактически положение контейнера ...

  • Риски в логистике и их минимизация с помощью страхования
  • ... , продажи, кредита и т.п. Страхование - передача или распределение рисков, возникающих у одного лица, между рядом лиц. Устранение риска - отказ от некоторых видов деятельности, связанных с риском. Основные пути минимизации рисков в логистике Минимизация рисков, возникающих в ЛС, основывается на ...

  • Проблемы правового регулирования налога на добавленную стоимость
  • ... процентов Кодексом не определен. Научное исследование А.А. Бастрикова посвящено изучению общих принципов обложения налогом на добавленную стоимость и выявлению степени соотношения их с правовым регулированием рассматриваемого налога. В работе содержится обоснованное утверждение о том, что ряд ...

  • Расчеты налога на добавленную стоимость
  • ... -фактуры и Правила ведения журналов учета полученных и выставленных счетов-фактур, книг покупок и книг продаж при расчетах по налогу на добавленную стоимость. Согласно пункту 2 статьи 169 Кодекса счета-фактуры, составленные и выставленные с нарушением порядка, установленного пунктами 5 и 6 этой ...

Каталог учебных материалов

Свежие работы в разделе

Наша кнопка

Разместить ссылку на наш сайт можно воспользовавшись следующим кодом:

Контакты

Если у вас возникли какие либо вопросы, обращайтесь на email администратора: admin@kazreferat.info